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

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

I would suggest merging these two lists into a single list of structures. That way you can simply define operator < like dirkgently said.

Answer 2

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, define a comparator that looks at the ages:

struct by_age { 
    bool operator()(person const &a, person const &b) { 
        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());

Edit: As for choosing between defining operator< for the class, or using a separate comparator object as I have 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.

Answer 3

Generally you wouldn't put data that you want to keep together in different containers. Make a struct/class for Person and overload operator<.

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

bool operator< (const Person& a, const Person& b);

Or if this is some throw-away thing:

typedef std::pair<int, std::string> Person;
std::vector<Person> persons;
std::sort(persons.begin(), persons.end());

std::pair already implement comparison operators.

Answer 4

It doesn't make sense to keep them in two separate data structures: if you reorder People, you no longer have a sensible mapping to Ages.

template<class A, class B, class CA = std::less<A>, class CB = std::less<B> >
struct lessByPairSecond
    : std::binary_function<std::pair<A, B>, std::pair<A, B>, bool>
{
    bool operator()(const std::pair<A, B> &left, const std::pair<A, B> &right) {
        if (CB()(left.second, right.second)) return true;
        if (CB()(right.second, left.second)) return false;
        return CA()(left.first, right.first);
    }
};

std::vector<std::pair<std::string, int> > peopleAndAges;
peopleAndAges.push_back(std::pair<std::string, int>("Anne", 23));
peopleAndAges.push_back(std::pair<std::string, int>("Bob", 23));
peopleAndAges.push_back(std::pair<std::string, int>("Charlie", 23));
peopleAndAges.push_back(std::pair<std::string, int>("Douglas", 23));
std::sort(peopleAndAges.begin(), peopleAndAges.end(),
        lessByPairSecond<std::string, int>());

Answer 5

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]]