C++ sorting and keeping track of indexes

173

80

Using C++, and hopefully the standard library, I want to sort a sequence of samples in ascending order, but I also want to remember the original indexes of the newly samples.

For example, I have a set, or vector, or matrix of samples A : [5, 2, 1, 4, 3]. I want to sort these to be B : [1,2,3,4,5], but I also want to remember the original indexes of the values, so I can get another set which would be: C : [2, 1, 4, 3, 0 ] - which corresponds to the index of the each element in 'B', in the original 'A'.

For example, in Matlab you can do:

 [a,b]=sort([5, 8, 7])
 a = 5 7 8
 b = 1 3 2

Can anyone see a good way to do this?

Mingus

Posted 2009-10-16T11:18:24.393

Reputation: 938

Answers

221

Using C++11 lambdas

template <typename T>
vector<size_t> sort_indexes(const vector<T> &v) {

  // initialize original index locations
  vector<size_t> idx(v.size());
  iota(idx.begin(), idx.end(), 0);

  // sort indexes based on comparing values in v
  sort(idx.begin(), idx.end(),
       [&v](size_t i1, size_t i2) {return v[i1] < v[i2];});

  return idx;
}

Now you can use the returned index vector in iterations such as

for (auto i: sort_indexes(v)) {
  cout << v[i] << endl;
}

Obviously, you can also choose to supply your own original index vector, sort function, comparator, or automatically reorder v in the sort_indexes function using an extra vector.

Lukasz Wiklendt

Posted 2009-10-16T11:18:24.393

Reputation: 2 481

3Love this answer.If your compiler does not support lambdas, you can use a class:

template<typename T> class CompareIndicesByAnotherVectorValues { std::vector<T> _values; public: CompareIndicesByAnotherVectorValues(std::vector<T> values) : _values(values) {} public: bool operator() (const int& a, const int& b) const { return (_values)[a] > (_values)[b]; } }; – Ben-Uri – 2012-10-18T07:47:55.787

1I love this answer too, there is no need to copy the original vector to create the vector of pairs. – headmyshoulder – 2013-01-28T22:43:11.320

1This is much better than the accepted answer in my opinion! Awesome! – Ela782 – 2014-11-06T15:39:17.123

2Beautiful solution! – Anonymous – 2015-01-21T13:31:56.647

21Rather than the hand-crafted for (size_t i = 0; i != idx.size(); ++i) idx[i] = i; I prefer the standard std::iota( idx.begin(), idx.end(), 0 ); – Wyck – 2015-04-30T17:53:11.120

5use #include &lt;numeric&gt; for iota() – Kartik_Agarwal – 2017-01-08T10:16:50.110

81

You could sort std::pair instead of just ints - first int is original data, second int is original index. Then supply a comparator that only sorts on the first int. Example:

Your problem instance: v = [5 7 8]
New problem instance: v_prime = [<5,0>, <8,1>, <7,2>]

Sort the new problem instance using a comparator like:

typedef std::pair<int,int> mypair;
bool comparator ( const mypair& l, const mypair& r)
   { return l.first < r.first; }
// forgetting the syntax here but intent is clear enough

The result of std::sort on v_prime, using that comparator, should be:

v_prime = [<5,0>, <7,2>, <8,1>]

You can peel out the indices by walking the vector, grabbing .second from each std::pair.

RAC

Posted 2009-10-16T11:18:24.393

Reputation: 2 181

A lovely answer, making good use of the comparator option. – Bill Cheatham – 2011-11-30T16:28:31.917

1This is exactly how I would do it as well. The basic sort function doesn't track the old versus new positions as that would add extra unnecessary overhead. – the_mandrill – 2009-10-16T12:13:33.280

2stl only, minimal coding; too simple to think of it myself... – gimpf – 2009-10-16T12:32:16.913

4The drawback with this function is that it requires you to reallocate memory for all values. – Ben-Uri – 2012-10-18T07:50:23.897

This is obviously a workable approach, but it has a downside that you have to change your original container from "container of numbers" to "container of pairs". – Ruslan – 2018-03-05T10:23:30.070

10

I wrote generic version of index sort.

template <class RAIter, class Compare>
void argsort(RAIter iterBegin, RAIter iterEnd, Compare comp, 
    std::vector<size_t>& indexes) {

    std::vector< std::pair<size_t,RAIter> > pv ;
    pv.reserve(iterEnd - iterBegin) ;

    RAIter iter ;
    size_t k ;
    for (iter = iterBegin, k = 0 ; iter != iterEnd ; iter++, k++) {
        pv.push_back( std::pair<int,RAIter>(k,iter) ) ;
    }

    std::sort(pv.begin(), pv.end(), 
        [&comp](const std::pair<size_t,RAIter>& a, const std::pair<size_t,RAIter>& b) -> bool 
        { return comp(*a.second, *b.second) ; }) ;

    indexes.resize(pv.size()) ;
    std::transform(pv.begin(), pv.end(), indexes.begin(), 
        [](const std::pair<size_t,RAIter>& a) -> size_t { return a.first ; }) ;
}

Usage is the same as that of std::sort except for an index container to receive sorted indexes. testing:

int a[] = { 3, 1, 0, 4 } ;
std::vector<size_t> indexes ;
argsort(a, a + sizeof(a) / sizeof(a[0]), std::less<int>(), indexes) ;
for (size_t i : indexes) printf("%d\n", int(i)) ;

you should get 2 1 0 3. for the compilers without c++0x support, replace the lamba expression as a class template:

template <class RAIter, class Compare> 
class PairComp {
public:
  Compare comp ;
  PairComp(Compare comp_) : comp(comp_) {}
  bool operator() (const std::pair<size_t,RAIter>& a, 
    const std::pair<size_t,RAIter>& b) const { return comp(*a.second, *b.second) ; }        
} ;

and rewrite std::sort as

std::sort(pv.begin(), pv.end(), PairComp(comp)()) ;

hkyi

Posted 2009-10-16T11:18:24.393

Reputation: 1 194

7

vector<pair<int,int> >a;

for (i = 0 ;i < n ; i++) {
    // filling the original array
    cin >> k;
    a.push_back (make_pair (k,i)); // k = value, i = original index
}

sort (a.begin(),a.end());

for (i = 0 ; i < n ; i++){
    cout << a[i].first << " " << a[i].second << "\n";
}

Now a contains both both our values and their respective indices in the sorted.

a[i].first = value at i'th.

a[i].second = idx in initial array.

Aditya Aswal

Posted 2009-10-16T11:18:24.393

Reputation: 69

6

I came across this question, and figured out sorting the iterators directly would be a way to sort the values and keep track of indices; There is no need to define an extra container of pairs of ( value, index ) which is helpful when the values are large objects; The iterators provides the access to both the value and the index:

/*
 * a function object that allows to compare
 * the iterators by the value they point to
 */
template < class RAIter, class Compare >
class IterSortComp
{
    public:
        IterSortComp ( Compare comp ): m_comp ( comp ) { }
        inline bool operator( ) ( const RAIter & i, const RAIter & j ) const
        {
            return m_comp ( * i, * j );
        }
    private:
        const Compare m_comp;
};

template <class INIter, class RAIter, class Compare>
void itersort ( INIter first, INIter last, std::vector < RAIter > & idx, Compare comp )
{ 
    idx.resize ( std::distance ( first, last ) );
    for ( typename std::vector < RAIter >::iterator j = idx.begin( ); first != last; ++ j, ++ first )
        * j = first;

    std::sort ( idx.begin( ), idx.end( ), IterSortComp< RAIter, Compare > ( comp ) );
}

as for the usage example:

std::vector < int > A ( n );

// populate A with some random values
std::generate ( A.begin( ), A.end( ), rand );

std::vector < std::vector < int >::const_iterator > idx;
itersort ( A.begin( ), A.end( ), idx, std::less < int > ( ) );

now, for example, the 5th smallest element in the sorted vector would have value **idx[ 5 ] and its index in the original vector would be distance( A.begin( ), *idx[ 5 ] ) or simply *idx[ 5 ] - A.begin( ).

behzad.nouri

Posted 2009-10-16T11:18:24.393

Reputation: 37 806

3

Its easier than it seems to be.

Suppose Given vector is

A=[2,4,3]

Create A new vector

V=[0,1,2] // indicating positions

Sort V and while sorting instead of comparing elements of V , compare corresponding elements of A

 //Assume A is a given vector with N elements
 vector<int> V(N);
 int x=0;
 std::iota(V.begin(),V.end(),x++); //Initializing
 sort( V.begin(),V.end(), [&](int i,int j){return A[i]<A[j];} );

MysticForce

Posted 2009-10-16T11:18:24.393

Reputation: 411

2

Make a std::pair in function then sort pair :

generic version :

template< class RandomAccessIterator,class Compare >
auto sort2(RandomAccessIterator begin,RandomAccessIterator end,Compare cmp) ->
   std::vector<std::pair<std::uint32_t,RandomAccessIterator>>
{
    using valueType=typename std::iterator_traits<RandomAccessIterator>::value_type;
    using Pair=std::pair<std::uint32_t,RandomAccessIterator>;

    std::vector<Pair> index_pair;
    index_pair.reserve(std::distance(begin,end));

    for(uint32_t idx=0;begin!=end;++begin,++idx){
        index_pair.push_back(Pair(idx,begin));
    }

    std::sort( index_pair.begin(),index_pair.end(),[&](const Pair& lhs,const Pair& rhs){
          return cmp(*lhs.second,*rhs.second);
    });

    return index_pair;
}

ideone

Omid

Posted 2009-10-16T11:18:24.393

Reputation: 1 328

2

Beautiful solution by @Lukasz Wiklendt! Although in my case I needed something more generic so I modified it a bit:

template <class RAIter, class Compare>
vector<size_t> argSort(RAIter first, RAIter last, Compare comp) {

  vector<size_t> idx(last-first);
  iota(idx.begin(), idx.end(), 0);

  auto idxComp = [&first,comp](size_t i1, size_t i2) {
      return comp(first[i1], first[i2]);
  };

  sort(idx.begin(), idx.end(), idxComp);

  return idx;
}

Example: Find indices sorting a vector of strings by length, except for the first element which is a dummy.

vector<string> test = {"dummy", "a", "abc", "ab"};

auto comp = [](const string &a, const string& b) {
    return a.length() > b.length();
};

const auto& beginIt = test.begin() + 1;
vector<size_t> ind = argSort(beginIt, test.end(), comp);

for(auto i : ind)
    cout << beginIt[i] << endl;

prints:

abc
ab
a

sigvaldm

Posted 2009-10-16T11:18:24.393

Reputation: 239

1

If it's possible, you can build the position array using find function, and then sort the array.

Or maybe you can use a map where the key would be the element, and the values a list of its position in the upcoming arrays (A, B and C)

It depends on later uses of those arrays.

HyLian

Posted 2009-10-16T11:18:24.393

Reputation: 3 257

1

Are the items in the vector unique? If so, copy the vector, sort one of the copies with STL Sort then you can find which index each item had in the original vector.

If the vector is supposed to handle duplicate items, I think youre better of implementing your own sort routine.

Mizipzor

Posted 2009-10-16T11:18:24.393

Reputation: 22 588

no, not necessarily unique, it's the indexes I want – Mingus – 2009-10-16T11:50:00.740

1

There is another way to solve this, using a map:

vector<double> v = {...}; // input data
map<double, unsigned> m; // mapping from value to its index
for (auto it = v.begin(); it != v.end(); ++it)
    m[*it] = it - v.begin();

This will eradicate non-unique elements though. If that's not acceptable, use a multimap:

vector<double> v = {...}; // input data
multimap<double, unsigned> m; // mapping from value to its index
for (auto it = v.begin(); it != v.end(); ++it)
    m.insert(make_pair(*it, it - v.begin()));

In order to output the indices, iterate over the map or multimap:

for (auto it = m.begin(); it != m.end(); ++it)
    cout << it->second << endl;

Ulrich Eckhardt

Posted 2009-10-16T11:18:24.393

Reputation: 12 366

1

Well, my solution uses residue technique. We can place the values under sorting in the upper 2 bytes and the indices of the elements - in the lower 2 bytes:

int myints[] = {32,71,12,45,26,80,53,33};

for (int i = 0; i < 8; i++)
   myints[i] = myints[i]*(1 << 16) + i;

Then sort the array myints as usual:

std::vector<int> myvector(myints, myints+8);
sort(myvector.begin(), myvector.begin()+8, std::less<int>());

After that you can access the elements' indices via residuum. The following code prints the indices of the values sorted in the ascending order:

for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
   std::cout << ' ' << (*it)%(1 << 16);

Of course, this technique works only for the relatively small values in the original array myints (i.e. those which can fit into upper 2 bytes of int). But it has additional benefit of distinguishing identical values of myints: their indices will be printed in the right order.

Macmep

Posted 2009-10-16T11:18:24.393

Reputation: 11

1

For this type of question Store the orignal array data into a new data and then binary search the first element of the sorted array into the duplicated array and that indice should be stored into a vector or array.

input array=>a
duplicate array=>b
vector=>c(Stores the indices(position) of the orignal array
Syntax:
for(i=0;i<n;i++)
c.push_back(binarysearch(b,n,a[i]));`

Here binarysearch is a function which takes the array,size of array,searching item and would return the position of the searched item

Mohit Vachhani

Posted 2009-10-16T11:18:24.393

Reputation: 47

0

There are many ways. A rather simple solution is to use a 2D vector.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
 vector<vector<double>> val_and_id;
 val_and_id.resize(5);
 for (int i = 0; i < 5; i++) {
   val_and_id[i].resize(2); // one to store value, the other for index.
 }
 // Store value in dimension 1, and index in the other:
 // say values are 5,4,7,1,3.
 val_and_id[0][0] = 5.0;
 val_and_id[1][0] = 4.0;
 val_and_id[2][0] = 7.0;
 val_and_id[3][0] = 1.0;
 val_and_id[4][0] = 3.0;

 val_and_id[0][1] = 0.0;
 val_and_id[1][1] = 1.0;
 val_and_id[2][1] = 2.0;
 val_and_id[3][1] = 3.0;
 val_and_id[4][1] = 4.0;

 sort(val_and_id.begin(), val_and_id.end());
 // display them:
 cout << "Index \t" << "Value \n";
 for (int i = 0; i < 5; i++) {
  cout << val_and_id[i][1] << "\t" << val_and_id[i][0] << "\n";
 }
 return 0;
}

Here is the output:

   Index   Value
   3       1
   4       3
   1       4
   0       5
   2       7

Gokul

Posted 2009-10-16T11:18:24.393

Reputation: 4

0

Consider using std::multimap as suggested by @Ulrich Eckhardt. Just that the code could be made even simpler.

Given

std::vector<int> a = {5, 2, 1, 4, 3};  // a: 5 2 1 4 3

To sort in the mean time of insertion

std::multimap<int, std::size_t> mm;
for (std::size_t i = 0; i != a.size(); ++i)
    mm.insert({a[i], i});

To retrieve values and original indices

std::vector<int> b;
std::vector<std::size_t> c;
for (const auto & kv : mm) {
    b.push_back(kv.first);             // b: 1 2 3 4 5
    c.push_back(kv.second);            // c: 2 1 4 3 0
}

The reason to prefer a std::multimap to a std::map is to allow equal values in original vectors. Also please note that, unlike for std::map, operator[] is not defined for std::multimap.

fleix

Posted 2009-10-16T11:18:24.393

Reputation: 191