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

Question

I have several std::vector, all of the same length. I want to sort one of these vectors, and apply the same transformation to all of the other vectors. Is there a neat way of doing this? (preferably using the STL or Boost)? Some of the vectors hold ints and some of them std::strings.

Pseudo code:

std::vector<int> Index = { 3, 1, 2 };
std::vector<std::string> Values = { "Third", "First", "Second" };

Transformation = sort(Index);
Index is now { 1, 2, 3};

... magic happens as Tranformation is applied to Values ...
Values is now { "First", "Second", "Third" };

Answer 1

Only one rough solution comes to my mind: create a vector that is the sum of all other vectors (a vector of structures, like {3,Third,...},{1,First,...}) then sort this vector by the first field, and then split the structures again.

Probably there is a better solution inside Boost or using the standard library.

Answer 2

friol's approach is good when coupled with yours. First, build a vector consisting of the numbers 1…n, along with the elements from the vector dictating the sorting order:

typedef vector<int>::const_iterator myiter;

vector<pair<size_t, myiter> > order(Index.size());

size_t n = 0;
for (myiter it = Index.begin(); it != Index.end(); ++it, ++n)
    order[n] = make_pair(n, it);

Now you can sort this array using a custom sorter:

struct ordering {
    bool operator ()(pair<size_t, myiter> const& a, pair<size_t, myiter> const& b) {
        return a.second < b.second;
    }
};

sort(order.begin(), order.end(), ordering());

Now you've captured the order of rearrangement inside order (more precisely, in the first component of the items). You can now use this ordering to sort your other vectors. There's probably a very clever in-place variant running in the same time, but until someone else comes up with it, here's one variant that isn't in-place. It uses order as a look-up table for the new index of each element.

template <typename T>
vector<T> sort_from_ref(
    vector<T> const& in,
    vector<pair<size_t, myiter> > const& reference
) {
    vector<T> ret(in.size());

    size_t const size = in.size();
    for (size_t i = 0; i < size; ++i)
        ret[i] = in[reference[i].first];

    return ret;
}

Answer 3

I think what you really need (but correct me if I'm wrong) is a way to access elements of a container in some order.

Rather than rearranging my original collection, I would borrow a concept from Database design: keep an index, ordered by a certain criterion. This index is an extra indirection that offers great flexibility.

This way it is possible to generate multiple indices according to different members of a class.

using namespace std;

template< typename Iterator, typename Comparator >
struct Index {
 vector<Iterator> v;

 Index( Iterator from, Iterator end, Comparator& c ){
  v.reserve( std::distance(from,end) );
  for( ; from != end; ++from ){
   v.push_back(from); // no deref!
  }
  sort( v.begin(), v.end(), c );
 }

};

template< typename Iterator, typename Comparator >
Index<Iterator,Comparator> index ( Iterator from, Iterator end, Comparator& c ){
 return Index<Iterator,Comparator>(from,end,c);
}

struct mytype {
 string name;
 double number;
};

template< typename Iter >
struct NameLess : public binary_function<Iter, Iter, bool> {
 bool operator()( const Iter& t1, const Iter& t2 ) const { return t1->name < t2->name; }
};

template< typename Iter >
struct NumLess : public binary_function<Iter, Iter, bool> {
 bool operator()( const Iter& t1, const Iter& t2 ) const { return t1->number < t2->number; }
};

void indices() {

 mytype v[] = { { "me" ,  0.0 }
     , { "you" ,  1.0 }
     , { "them" , -1.0 }
     };
 mytype* vend = v + _countof(v);

 Index<mytype*, NameLess<mytype*> > byname( v, vend, NameLess<mytype*>() );
 Index<mytype*, NumLess <mytype*> > bynum ( v, vend, NumLess <mytype*>() );

 assert( byname.v[0] == v+0 );
 assert( byname.v[1] == v+2 );
 assert( byname.v[2] == v+1 );

 assert( bynum.v[0] == v+2 );
 assert( bynum.v[1] == v+0 );
 assert( bynum.v[2] == v+1 );

}

Answer 4

Put your values in a Boost Multi-Index container then iterate over to read the values in the order you want. You can even copy them to another vector if you want to.

Answer 5

typedef std::vector<int> int_vec_t;
typedef std::vector<std::string> str_vec_t;
typedef std::vector<size_t> index_vec_t;

class SequenceGen {
public:
    SequenceGen (int start = 0) : current(start) { }
    int operator() () { return current++; }
private:
    int current;
};

class Comp{
   int_vec_t& _v;
 public:
   Comp(int_vec_t& v) : _v(v) {}
   bool operator()(size_t i, size_t j){
         return _v[i] < _v[j];
   }
}

index_vec_t indices(3);
std::generate(indices.begin(), indices.end(), SequenceGen(0));
//indices are {0, 1, 2}

int_vec_t Index = { 3, 1, 2 };
str_vec_t Values = { "Third", "First", "Second" };

std::sort(indices.begin(), indices.end(), Comp(Index));
//now indices are {1,2,0}

Now you can use the "indices" vector to index into "Values" vector