C++ STL:根据另一个向量的内容自定义排序一个向量

2022-01-07 00:00:00 sorting c++ stl

这可能是最好的例子.我有两个向量/列表:

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

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

我想使用诸如 sort(People.begin(), People.end(), CustomComparator) 之类的东西根据人们的年龄对他们进行排序，但我不知道如何编写CustomComparator 用于查看 Ages 而不是 People.

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.

推荐答案

明显的方法

不是创建两个单独的向量/列表，处理此问题的常用方法是创建一个包含名称和年龄的对象的单个向量/列表:

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

在较旧的 C++(C++11 之前，因此没有 lambda 表达式)中，您可以将比较定义为 operator< 的成员重载，或者定义为函数对象(重载 operator()) 进行比较:

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());

至于在为类定义 operator< 还是使用单独的比较器对象(如我上面所示)之间进行选择，主要的问题是是否存在对此类显而易见"的单一排序.

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.

在我看来，按年龄对人进行分类并不一定很明显.但是，如果在您的程序的上下文中，除非您明确指定，否则很明显将按年龄对人员进行排序，那么实现比较是有意义的作为 person::operator< 而不是像我上面所做的那样在单独的比较类中.

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.

综上所述，在某些情况下，在排序之前将数据组合到结构中确实不切实际或不可取.

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

但是请注意，在这种情况下，我们根本没有真正对项目本身进行排序.我们刚刚根据年龄对索引进行了排序，然后使用该索引索引到我们想要排序的数据数组中――但年龄和姓名都保持其原始顺序.

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).

相关文章