code_junkie

How do I sort a std::vector by the values of a different std::vector?

Nov 11th, 2011
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.01 KB | None | 0 0
  1. std::vector<int> Index = { 3, 1, 2 };
  2. std::vector<std::string> Values = { "Third", "First", "Second" };
  3.  
  4. Transformation = sort(Index);
  5. Index is now { 1, 2, 3};
  6.  
  7. ... magic happens as Tranformation is applied to Values ...
  8. Values is now { "First", "Second", "Third" };
  9.  
  10. typedef vector<int>::const_iterator myiter;
  11.  
  12. vector<pair<size_t, myiter> > order(Index.size());
  13.  
  14. size_t n = 0;
  15. for (myiter it = Index.begin(); it != Index.end(); ++it, ++n)
  16. order[n] = make_pair(n, it);
  17.  
  18. struct ordering {
  19. bool operator ()(pair<size_t, myiter> const& a, pair<size_t, myiter> const& b) {
  20. return a.second < b.second;
  21. }
  22. };
  23.  
  24. sort(order.begin(), order.end(), ordering());
  25.  
  26. template <typename T>
  27. vector<T> sort_from_ref(
  28. vector<T> const& in,
  29. vector<pair<size_t, myiter> > const& reference
  30. ) {
  31. vector<T> ret(in.size());
  32.  
  33. size_t const size = in.size();
  34. for (size_t i = 0; i < size; ++i)
  35. ret[i] = in[reference[i].first];
  36.  
  37. return ret;
  38. }
  39.  
  40. using namespace std;
  41.  
  42. template< typename Iterator, typename Comparator >
  43. struct Index {
  44. vector<Iterator> v;
  45.  
  46. Index( Iterator from, Iterator end, Comparator& c ){
  47. v.reserve( std::distance(from,end) );
  48. for( ; from != end; ++from ){
  49. v.push_back(from); // no deref!
  50. }
  51. sort( v.begin(), v.end(), c );
  52. }
  53.  
  54. };
  55.  
  56. template< typename Iterator, typename Comparator >
  57. Index<Iterator,Comparator> index ( Iterator from, Iterator end, Comparator& c ){
  58. return Index<Iterator,Comparator>(from,end,c);
  59. }
  60.  
  61. struct mytype {
  62. string name;
  63. double number;
  64. };
  65.  
  66. template< typename Iter >
  67. struct NameLess : public binary_function<Iter, Iter, bool> {
  68. bool operator()( const Iter& t1, const Iter& t2 ) const { return t1->name < t2->name; }
  69. };
  70.  
  71. template< typename Iter >
  72. struct NumLess : public binary_function<Iter, Iter, bool> {
  73. bool operator()( const Iter& t1, const Iter& t2 ) const { return t1->number < t2->number; }
  74. };
  75.  
  76. void indices() {
  77.  
  78. mytype v[] = { { "me" , 0.0 }
  79. , { "you" , 1.0 }
  80. , { "them" , -1.0 }
  81. };
  82. mytype* vend = v + _countof(v);
  83.  
  84. Index<mytype*, NameLess<mytype*> > byname( v, vend, NameLess<mytype*>() );
  85. Index<mytype*, NumLess <mytype*> > bynum ( v, vend, NumLess <mytype*>() );
  86.  
  87. assert( byname.v[0] == v+0 );
  88. assert( byname.v[1] == v+2 );
  89. assert( byname.v[2] == v+1 );
  90.  
  91. assert( bynum.v[0] == v+2 );
  92. assert( bynum.v[1] == v+0 );
  93. assert( bynum.v[2] == v+1 );
  94.  
  95. }
  96.  
  97. typedef std::vector<int> int_vec_t;
  98. typedef std::vector<std::string> str_vec_t;
  99. typedef std::vector<size_t> index_vec_t;
  100.  
  101. class SequenceGen {
  102. public:
  103. SequenceGen (int start = 0) : current(start) { }
  104. int operator() () { return current++; }
  105. private:
  106. int current;
  107. };
  108.  
  109. class Comp{
  110. int_vec_t& _v;
  111. public:
  112. Comp(int_vec_t& v) : _v(v) {}
  113. bool operator()(size_t i, size_t j){
  114. return _v[i] < _v[j];
  115. }
  116. }
  117.  
  118. index_vec_t indices(3);
  119. std::generate(indices.begin(), indices.end(), SequenceGen(0));
  120. //indices are {0, 1, 2}
  121.  
  122. int_vec_t Index = { 3, 1, 2 };
  123. str_vec_t Values = { "Third", "First", "Second" };
  124.  
  125. std::sort(indices.begin(), indices.end(), Comp(Index));
  126. //now indices are {1,2,0}
Add Comment
Please, Sign In to add comment