C++ sorting and keeping track of indexes

C++ sorting and keeping track of indexes

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?

Answer by HyLian for C++ sorting and keeping track of indexes

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 that arrays.

Answer by Mizipzor for C++ sorting and keeping track of indexes

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.

Answer by RAC for C++ sorting and keeping track of indexes

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 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.

Answer by stefaanv for C++ sorting and keeping track of indexes

When dealing with multiple views on a container, always consider boost::multi_index_container. It might be a bit overkill, but it also might be just what you needed. You just insert and access and take a sorted view.

Answer by hkyi for C++ sorting and keeping track of indexes

I wrote generic version of index sort.

template   void argsort(RAIter iterBegin, RAIter iterEnd, Compare comp,       std::vector& indexes) {        std::vector< std::pair > pv ;      pv.reserve(iterEnd - iterBegin) ;        RAIter iter ;      size_t k ;      for (iter = iterBegin, k = 0 ; iter != iterEnd ; iter++, k++) {          pv.push_back( std::pair(k,iter) ) ;      }        std::sort(pv.begin(), pv.end(),           [&comp](const std::pair& a, const std::pair& b) -> bool           { return comp(*a.second, *b.second) ; }) ;        indexes.resize(pv.size()) ;      std::transform(pv.begin(), pv.end(), indexes.begin(),           [](const std::pair& 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 indexes ;  argsort(a, a + sizeof(a) / sizeof(a[0]), std::less(), 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 PairComp {  public:    Compare comp ;    PairComp(Compare comp_) : comp(comp_) {}    bool operator() (const std::pair& a,       const std::pair& b) const { return comp(*a.second, *b.second) ; }          } ;  

and rewrite std::sort as

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

Answer by Lukasz Wiklendt for C++ sorting and keeping track of indexes

Using C++11 lambdas

template   vector sort_indexes(const vector &v) {      // initialize original index locations    vector idx(v.size());    for (size_t i = 0; i != idx.size(); ++i) idx[i] = i;      // 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.

Answer by behzad.nouri for C++ sorting and keeping track of indexes

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   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( ).

Answer by Omid for C++ sorting and keeping track of indexes

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>  {      using valueType=typename std::iterator_traits::value_type;      using Pair=std::pair;        std::vector 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

Answer by Gui Borges for C++ sorting and keeping track of indexes

You can also do this using map or tuples!

    // Example program            #include             #include             #include             #include             #include             #include                 typedef std::tuple mytuple;            bool comparator(const mytuple& l, const mytuple& r)            {              return std::get<0>(l) < std::get<0>(r);            }    int main()  {         // declare vector of tuples double and int          std::vector > vtA;           //vector of doubles          std::vector vB;            //for exemple, fill "vB" with something          int j = 0;          for(int i = 10; i < 20 ; i++)          {              j = rand()% i;              vB.push_back(j);          }            for (int k = 0; k < vB.size(); k++)          {              //make a tuple with double and int (int is a indexis you want to save)              vtA.emplace_back(vB[k], k);              //print members before ordering              std::cout << std::get<0>(vtA[k]) << " - " << std::get<1>(vtA[k]) << std::endl;          }            std::cout << "\n";          std::cout << "\n";          std::sort(vtA.begin(), vtA.end(), comparator); //call function to increasing order          std::cout << "\n";          std::cout << "\n";            //prints vector with the old indices          for (int k = 0; k < vB.size(); k++)          {              std::cout << std::get<0>(vtA[k]) << " - " << std::get<1>(vtA[k]) << std::endl;          }  return(0);  }  

Answer by Ulrich Eckhardt for C++ sorting and keeping track of indexes

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

vector v = {...}; // input data  map 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 v = {...}; // input data  multimap 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;  

Answer by Macmep for C++ sorting and keeping track of indexes

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 myvector(myints, myints+8);  sort(myvector.begin(), myvector.begin()+8, std::less());  

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::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.

Fatal error: Call to a member function getElementsByTagName() on a non-object in D:\XAMPP INSTALLASTION\xampp\htdocs\endunpratama9i\www-stackoverflow-info-proses.php on line 72