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 int
s and some of them std::string
s.
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 Transformation is applied to Values ... Values are now { "First", "Second", "Third" };
If you cannot merge the data into a vector of pairs or struct with both, you could create a vector of iterators, or the indexes from 0 to size-1. Then sort this using a custom comparator. Finally, create a new vector, populating it using the iterators or indexes.
For example to sort two vectors i would use descending bubble sort method and vector pairs. For descending bubble sort, i would create a function that requires a vector pair. After that i would put your 2 vector values into one vector pair.
A vector in C++ can be easily sorted in ascending order using the sort() function defined in the algorithm header file. The sort() function sorts a given data structure and does not return anything. The sorting takes place between the two passed iterators or positions.
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; }
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With