C++结构排序

Question

• 我有一个定制结构向量，每次都需要根据不同的标准进行排序。
• 实现运算符<只允许一个条件
• 但我希望能够在每次调用C++标准排序时指定排序条件。

怎么做？

• 请注意，运行时间要有效率比较好。

谢谢

Answer 1

通过使用第三个参数，可以定义排序算法每次运行中要使用的比较函数：

template <class RandomAccessIterator, class StrictWeakOrdering>
void sort(RandomAccessIterator first, RandomAccessIterator last,
          StrictWeakOrdering comp);

一个简单的例子：

struct person {
   std::string name;
   int age;
};
bool sort_by_name( const person & lhs, const person & rhs )
{
   return lhs.name < rhs.name;
}
bool sort_by_age( const person & lhs, const person & rhs )
{
   return lhs.age < rhs.age;
}
int main() {
   std::vector<person> people;
   // fill in the vector
   std::sort( people.begin(), people.end(), sort_by_name );
   std::sort( people.begin(), people.end(), sort_by_age );
}

Answer 2

有两个版本的std::sort，第二个版本接受比较函子：

template <class RandomAccessIterator, class StrictWeakOrdering>
void sort(RandomAccessIterator first, RandomAccessIterator last,
          StrictWeakOrdering comp);
//--------^^^^^^^^^^^^^^^^^^^^^^^

例如：

bool isLessThan(const MyStruct& first, const MyStruct& second) {
   if (first.name < second.name) return true;
   else if (first.name == second.name) {
      if (first.date > second.date) return true;
      // etc.
   }
   return false;
}

...

sort(v.begin(), v.end(), isLessThan);

另见http://www.cplusplus.com/reference/algorithm/sort/。

这个变体仍然使用相同的快速排序算法，所以它平均是O(n log )。

Answer 3

为了完整起见，下面是一个使用c++0x lambda函数的示例：

std::vector<Person> v;
std::sort(v.begin(), v.end(), [](Person a, Person b) { return a.name_ < b.name_; });
...
std::sort(v.begin(), v.end(), [](Person a, Person b) { return a.address_ < b.address_; });