C++, Sort One Vector Based On Another One

问题:

The best example I've got is that I want to sort Names based on their Score.

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.

回答1:

As already suggested in other answers: Combining the name and the score of each individual is likely the simplest solution.

Generically, this can be achieved with what is sometimes referred to as a "zip" operation: Combining two vectors into a vector of pairs - along with a corresponding "unzip".

Implemented generically, this may look as follows:

#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;
}

回答2:

Best way to do this would be to have a struct which combines the names with their scores and have 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 it 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; } );

回答3:

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.

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;
}

回答4:

One way you could do this would be to store the Names and Scores in a single data structure such as a 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 such as a std::map or std::multimap if you want repeated keys (i.e. repeated names allowed).

回答5:

Couldn't this be done through a custom iterator type?

EDIT:

What I'm thinking in its simplest form - sorting a pair of vectors based on the first one - is to have an iterator whose functions such as dereferencing, subscripting, member access and equality and ordering comparisons would call the corresponding functions on the first iterator, all other functions (copy, arithmetics, 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 could be extended into a multi_iterator to work with any reordering algorithm, pointing into any number of extra piggybacking sequences.
It could be a fun little project. Or maybe something similar already exists, in Boost or elsewhere.

EDIT2:

Forget the above.
Eric Niebler's Range-v3 library has a view::zip wrapper that "Given N ranges, return a new range where Mth element is the result of calling make_tuple on the Mth elements of all N ranges."
Sorting the range with a predicate on the first element of the tuples might just do the trick.

回答6:

So many asked this question and nobody came up with a satisfactory answer. Here is a std::sort helper that enables to sort two vectors simultaneously, taking into account the values of only one vector. This solution is based on a custom RadomIt (random iterator), and operates directly on the original vector data, without temporary copies, structure rearrangement or additional indices:

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 an usage example that sorts both Names and Age based on Age values, employing 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 to:

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

Code tested on Visual Studio 2017 and GCC 5.4.0.