C++ STL：根据另一个向量的内容自定义排序一个向量
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1723066/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
C++ STL: Custom sorting one vector based on contents of another
提问by pwaldron
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 CustomComparatorto look at Ages rather than People.
我想使用类似的东西根据人们的年龄对他们进行排序sort(People.begin(), People.end(), CustomComparator)，但我不知道如何编写CustomComparator以查看年龄而不是人。
回答by Jerry Coffin
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:
在较旧的 C++（C++11 之前，因此没有 lambda 表达式）中，您可以将比较定义为成员重载，operator<否则定义为函数对象（重载 的对象operator()）来进行比较：
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.
至于在定义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.
在我看来，按年龄对人进行分类并不一定很明显。但是，如果在您的程序的上下文中很明显，除非您明确指定，否则将按年龄对人员进行排序，那么实现比较是有意义的，person::operator<而不是像我那样在单独的比较类中上面做了。
回答by éric Malenfant
As others have noted, you should consider grouping People and Ages.
正如其他人所指出的，您应该考虑对 People 和 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]]
现在，第n个人的名字是people[pos[n]]，年龄是ages[pos[n]]
回答by UncleBens
Generally you wouldn't put data that you want to keep together in different containers. Make a struct/class for Person and overload operator<.
通常，您不会将想要保存在一起的数据放在不同的容器中。为 Person 和重载创建一个结构/类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::pairalready implement comparison operators.
std::pair已经实现了比较运算符。
回答by ephemient
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.
将它们保存在两个单独的数据结构中是没有意义的：如果重新排序People，则不再有到 的合理映射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>());
回答by lyricat
I would suggest merging these two lists into a single list of structures. That way you can simply define operator <like dirkgently said.
我建议将这两个列表合并为一个结构列表。这样你就可以operator <像直接说的那样简单地定义。
回答by Jorge
Jerry Coffinanswer was fully clear and correct.
Jerry Coffin 的回答是完全清楚和正确的。
A just have a related issue that may grant a good discussion to the topic... :)
只是有一个相关的问题，可能会对该主题进行很好的讨论...... :)
I had to reorder the columns of a matrix object (lets say TMatrix< T >) based on the sorting of a vector (lets say sequence)... The TMatrix< T >class do not provide reference access to it's rows (thus I can not create a structure to reorder it...) but conveniently provides a method TMatrix< T >::swap(row1, row2)...
我不得不根据向量的排序（比如序列）重新排序矩阵对象的列（比如TMatrix< T >）...... TMatrix< T >类不提供对其行的引用访问（因此我不能创建一个结构来对其重新排序...) 但方便地提供了一个方法TMatrix< T >::swap(row1, row2)...
So that's the code:
所以这就是代码：
TMatrix<double> matrix;
vector<double> sequence;
//
// 1st step: gets indexes of the matrix rows changes in order to sort by time
//
// note: sorter vector will have 'sorted vector elements' on 'first' and
// 'original indexes of vector elements' on 'second'...
//
const int n = int(sequence.size());
std::vector<std::pair<T, int>> sorter(n);
for(int i = 0; i < n; i++) {
std::pair<T, int> ae;
ae.first = sequence[i];
ae.second = i;
sorter[i] = ae;
}
std::sort(sorter.begin(), sorter.end());
//
// 2nd step: swap matrix rows based on sorter information
//
for(int i = 0; i < n; i++) {
// updates the the time vector
sequence[i] = sorter[i].first;
// check if the any row should swap
const int pivot = sorter[i].second;
if (i != pivot) {
//
// store the required swaps on stack
//
stack<std::pair<int, int>> swaps;
int source = pivot;
int destination = i;
while(destination != pivot) {
// store required swaps until final destination
// is equals to first source (pivot)
std::pair<int, int> ae;
ae.first = source;
ae.second = destination;
swaps.push(ae);
// retrieves the next requiret swap
source = destination;
for(int j = 0; j < n; j++) {
if (sorter[j].second == source)
destination = j;
break;
}
}
}
//
// final step: execute required swaps
//
while(!swaps.empty()) {
// pop the swap entry from the stack
std::pair<int, int> swap = swaps.top();
destination = swap.second;
swaps.pop();
// swap matrix coluns
matrix.swap(swap.first, destination);
// updates the sorter
sorter[destination].second = destination;
}
// updates sorter on pivot
sorter[pivot].second = pivot;
}
}
I belive that's still O(n log n) since every row that is not in place will swap just one time...
我相信这仍然是 O(n log n) 因为没有到位的每一行只会交换一次......
Have fun! :)
玩得开心！:)
