C++ STL: Custom sorting one vector based on contents of another [duplicate]

Question

This is probably best stated as an example. I have two vectors/lists:

People = {Anne, Bob, Charlie, Douglas} Ages   = {23, 28, 25, 21} 

I want to sort the People based on their ages using something like sort(People.begin(), People.end(), CustomComparator), but I don't know how to write the CustomComparator to look at Ages rather than People.

Answer 1

Obvious Approach

Instead of creating two separate vectors/lists, the usual way to handle this is to create a single vector/list of objects that include both names and ages:

struct person {      std::string name;     int age; }; 

To get a sort based on age, pass a comparator that looks at the ages:

std::sort(people.begin(), people.end(),            [](auto const &a, auto const &b) { return a.age < b.age; }); 

In older C++ (pre C++11, so no lambda expressions) you can define the comparison as a member overload of operator< or else as a function-object (an object that overloads operator()) to do the comparison:

struct by_age {      bool operator()(person const &a, person const &b) const noexcept {          return a.age < b.age;     } }; 

Then your sort would look something like:

std::vector<person> people; // code to put data into people goes here.  std::sort(people.begin(), people.end(), by_age()); 

As for choosing between defining operator< for the class, or using a separate comparator object as I show above, it's mostly a question of whether there's a single ordering that's "obvious" for this class.

In my opinion, it's not necessarily obvious that sorting people would always happen by age. If, however, in the context of your program it would be obvious that sorting people would be done by age unless you explicitly specified otherwise, then it would make sense to implement the comparison as person::operator< instead of in a separate comparison class the way I've done it above.

Other Approaches

All that having been said, there are a few cases where it really is impractical or undesirable to combine the data into a struct before sorting.

If this is the case, you have a few options to consider. If a normal sort is impractical because the key you're using is too expensive to swap (or can't be swapped at all, though that's pretty rare), you might be able to use a type where you store the data to be sorted along with just an index into the collection of keys associated with each:

using Person = std::pair<int, std::string>;  std::vector<Person> people = {     { "Anne", 0},     { "Bob", 1},     { "Charlie", 2},     { "Douglas", 3} };  std::vector<int> ages = {23, 28, 25, 21};  std::sort(people.begin(), people.end(),      [](Person const &a, person const &b) {          return Ages[a.second] < Ages[b.second];     }); 

You can also pretty easily create a separate index that you sort in the order of the keys, and just use that index to read through the associated values:

std::vector<std::string> people = { "Anne", "Bob", "Charlie", "Douglas" };    std::vector<int> ages = {23, 28, 25, 21};  std::vector<std::size_t> index (people.size()); std::iota(index.begin(), index.end(), 0);  std::sort(index.begin(), index.end(), [&](size_t a, size_t b) { return ages[a] < ages[b]; });  for (auto i : index) {      std::cout << people[i] << "\n"; } 

Note, however, that in this case, we haven't really sorted the items themselves at all. We've just sorted the index based on the ages, then used the index to index into the array of data we wanted sorted--but both the ages and names remain in their original order.

Of course, it's theoretically possible that you have such a bizarre situation that none of the above will work at all, and you'll need to re-implement sorting to do what you really want. While I suppose the possibility could exist, I've yet to see it in practice (nor do I even recall seeing a close call where I almost decided that was the right thing to do).

Answer 2

As others have noted, you should consider grouping People and Ages.

If you can't/don't want to, you could create an "index" to them, and sort that index instead. For example:

// Warning: Not tested struct CompareAge : std::binary_function<size_t, size_t, bool> {     CompareAge(const std::vector<unsigned int>& Ages)     : m_Ages(Ages)     {}      bool operator()(size_t Lhs, size_t Rhs)const     {         return m_Ages[Lhs] < m_Ages[Rhs];     }      const std::vector<unsigned int>& m_Ages; };  std::vector<std::string> people = ...; std::vector<unsigned int> ages = ...;  // Initialize a vector of indices assert(people.size() == ages.size()); std::vector<size_t> pos(people.size()); for (size_t i = 0; i != pos.size(); ++i){     pos[i] = i; }   // Sort the indices std::sort(pos.begin(), pos.end(), CompareAge(ages)); 

Now, the name of the nth person is people[pos[n]] and its age is ages[pos[n]]