C ++ Sorting one vector on another

Question

The best example that I have is that I want to sort names by their rating.

vector <string> Names {"Karl", "Martin", "Paul", "Jennie"}; vector <int> Score{45, 5, 14, 24}; 

So, if I sort the score to {5, 14, 24, 45}, the names should also be sorted based on their score.

Answer 1

As suggested in other answers: a combination of the name and rating of each person is probably the easiest solution.

In general, this can be achieved with what is sometimes called the "zip" operation: combining two vectors into a vector of pairs - along with the corresponding "unzip".

Implemented as a whole, it may look like this:

 #include <vector> #include <string> #include <algorithm> #include <iostream> #include <iterator> // Fill the zipped vector with pairs consisting of the // corresponding elements of a and b. (This assumes // that the vectors have equal length) template <typename A, typename B> void zip( const std::vector<A> &a, const std::vector<B> &b, std::vector<std::pair<A,B>> &zipped) { for(size_t i=0; i<a.size(); ++i) { zipped.push_back(std::make_pair(a[i], b[i])); } } // Write the first and second element of the pairs in // the given zipped vector into a and b. (This assumes // that the vectors have equal length) template <typename A, typename B> void unzip( const std::vector<std::pair<A, B>> &zipped, std::vector<A> &a, std::vector<B> &b) { for(size_t i=0; i<a.size(); i++) { a[i] = zipped[i].first; b[i] = zipped[i].second; } } int main(int argc, char* argv[]) { std::vector<std::string> names {"Karl", "Martin", "Paul", "Jennie"}; std::vector<int> score {45, 5, 14, 24}; // Zip the vectors together std::vector<std::pair<std::string,int>> zipped; zip(names, score, zipped); // Sort the vector of pairs std::sort(std::begin(zipped), std::end(zipped), [&](const auto& a, const auto& b) { return a.second > b.second; }); // Write the sorted pairs back to the original vectors unzip(zipped, names, score); for(size_t i=0; i<names.size(); i++) { std::cout << names[i] << " : " << score[i] << std::endl; } return 0; } 

Answer 2

The best way to do this is to create a structure that combines names with their ratings and has one vector.

 struct Person { std::string Name; int Score; }; 

Then you can declare your vector:

 std::vector<Person> people{ { "Karl", 45 }, { "Martin", 5 }, { "Paul", 14 } }; 

And sorting is easy with std::sort from <algorithm> :

 std::sort(people.begin(), people.end(), [](const auto& i, const auto& j) { return i.Score < j.Score; } ); 

Or you can change the lambda if you want to sort in descending order:

 std::sort(people.begin(), people.end(), [](const auto& i, const auto& j) { return i.Score > j.Score; } ); 

Answer 3

If you cannot combine data into a vector of pairs or a struct with both, you can create a vector of iterators or indices from 0 to size-1. Then sort using the specialized comparator. Finally, create a new vector by populating it with iterators or indexes.

 template<class T1, class A1, class T2, class A2> std::vector<T1, A1> sort_by( std::vector<T1,A1> const& vin, std::vector<T2,A2> const& keys ){ std::vector<std::size_t> is; is.reserve(vin.size()); for (auto&& unused:keys) is.push_back(is.size()); std::sort(begin(is),end(is),[&](std::size_t l, std::size_t r){ return keys[l]<keys[r]; }); std::vector<T1, A1> r; r.reserve(vin.size()); for(std::size_t i:is) r.push_back(vin[i]); return r; } 

Answer 4

One way to do this is to store names and ratings in a single data structure, such as std::vector<std::pair<std::string,int>> , and then sorting can be done as follows:

 #include <algorithm> #include <vector> #include <string> #include <utility> //... std::vector<std::pair<std::string, int>> names_scores_vec; // ... populate names_scores_vec... // lambda for sorting, change to > for descending order auto sort_by_scores = [](const std::pair<string,int>& _lhs, const std::pair<string,int>& _rhs) { return _lhs.second < _rhs.second; }; std::sort(names_scores_vec.begin(), names_scores_vec.end(), sort_by_scores); 

Alternatively, use storage like std::map or std::multimap if you need duplicate keys (i.e. duplicate names are allowed).

Answer 5

Could this not be done using a custom iterator type?

EDIT:

What I think in its simplest form, sorting a pair of vectors based on the first, is to have an iterator whose functions, such as dereferencing, signatures, membership access and equalities and ordering comparisons, will call the corresponding functions on the first iterator, all the rest functions (copy, arithmetic, swap, ...) acting on both iterators.

 template <typename Driver, typename Passenger> struct duo_iterator { . . . }; template <typename D, typename P> auto make_duo_iterator(D d, P p) -> duo_iterator<D, P> { . . . } sort(make_duo_iterator(begin(v1), begin(v2)), make_duo_iterator(end(v1), end(v2))); 

The iterator can be extended to multi_iterator to work with any reordering algorithm, indicating any number of additional merge sequences.
It can be a fun little project. Or perhaps something similar already exists, in Boost or elsewhere.

EDIT2:

Forget about it above. Eric Niebler The Range-v3 library has a view::zip wrapper that "Given the N ranges, returns a new range, where the Mth element is the result of calling make_tuple on the Mth elements of all N ranges."
Sorting a range with a predicate in the first tuple element can just do the trick.

Answer 6

So many asked this question, and no one came up with a satisfactory answer. Here is the std :: sort helper, which allows you to sort two vectors at a time, taking into account the values ​​of only one vector. This solution is based on a custom RadomIt (random iterator) and works directly with the original vector data without temporary copies, structural rearrangement or additional indexes:

 namespace std { namespace sort_helper { template <typename _Data, typename _Order> struct value_reference_t; template <typename _Data, typename _Order> struct value_t { _Data data; _Order val; inline value_t(_Data _data, _Order _val) : data(_data), val(_val) {} inline value_t(const value_reference_t<_Data,_Order>& rhs); }; template <typename _Data, typename _Order> struct value_reference_t { _Data* pdata; _Order* pval; value_reference_t(_Data* _itData, _Order* _itVal) : pdata(_itData), pval(_itVal) {} inline value_reference_t& operator = (const value_reference_t& rhs) { *pdata = *rhs.pdata; *pval = *rhs.pval; return *this; } inline value_reference_t& operator = (const value_t<_Data,_Order>& rhs) { *pdata = rhs.data; *pval = rhs.val; return *this; } inline bool operator < (const value_reference_t& rhs) { return *pval < *rhs.pval; } }; template <typename _Data, typename _Order> struct value_iterator_t : iterator< random_access_iterator_tag, value_t<_Data,_Order>, ptrdiff_t, value_t<_Data,_Order>*, value_reference_t<_Data,_Order> > { _Data* itData; _Order* itVal; value_iterator_t(_Data* _itData, _Order* _itVal) : itData(_itData), itVal(_itVal) {} inline ptrdiff_t operator - (const value_iterator_t& rhs) const { return itVal - rhs.itVal; } inline value_iterator_t operator + (ptrdiff_t off) const { return value_iterator_t(itData + off, itVal + off); } inline value_iterator_t operator - (ptrdiff_t off) const { return value_iterator_t(itData - off, itVal - off); } inline value_iterator_t& operator ++ () { ++itData; ++itVal; return *this; } inline value_iterator_t& operator -- () { --itData; --itVal; return *this; } inline value_iterator_t operator ++ (int) { return value_iterator_t(itData++, itVal++); } inline value_iterator_t operator -- (int) { return value_iterator_t(itData--, itVal--); } inline value_t<_Data,_Order> operator * () const { return value_t<_Data,_Order>(*itData, *itVal); } inline value_reference_t<_Data,_Order> operator * () { return value_reference_t<_Data,_Order>(itData, itVal); } inline bool operator < (const value_iterator_t& rhs) const { return itVal < rhs.itVal; } inline bool operator == (const value_iterator_t& rhs) const { return itVal == rhs.itVal; } inline bool operator != (const value_iterator_t& rhs) const { return itVal != rhs.itVal; } }; template <typename _Data, typename _Order> inline value_t<_Data,_Order>::value_t(const value_reference_t<_Data,_Order>& rhs) : data(*rhs.pdata), val(*rhs.pval) {} template <typename _Data, typename _Order> bool operator < (const value_t<_Data,_Order>& lhs, const value_reference_t<_Data,_Order>& rhs) { return lhs.val < *rhs.pval; } template <typename _Data, typename _Order> bool operator < (const value_reference_t<_Data,_Order>& lhs, const value_t<_Data,_Order>& rhs) { return *lhs.pval < rhs.val; } template <typename _Data, typename _Order> void swap(value_reference_t<_Data,_Order> lhs, value_reference_t<_Data,_Order> rhs) { std::swap(*lhs.pdata, *rhs.pdata); std::swap(*lhs.pval, *rhs.pval); } } // namespace sort_helper } // namespace std 

And this is a usage example that sorts both names and age based on age values ​​using standard std :: sort:

 char* Names[] = { "Karl", "Paul", "Martin", "Jennie" }; int Age[] = { 45, 14, 5, 24 }; typedef std::sort_helper::value_iterator_t<char*,int> IndexIt; std::sort(IndexIt(Names, Age), IndexIt(Names+4, Age+4)); 

sorted by:

 { "Martin", "Paul", "Jennie", "Karl" }; { 5, 14, 24, 45 }; 

Verified code for Visual Studio 2017 and GCC 5.4.0.