如何在C++中有效地排序四重结构？

Question

我有一个成员x,y,z和w的结构.我如何先用x排序,然后用y排序,用z排序,最后用C++排序？

Answer 1

如果要实现字典排序,那么最简单的方法是使用std::tie实现小于或大于比较的运算符或仿函数,然后std::sort在结构集合上使用.

struct Foo
{
  T x, y, z, w;
};

....    
#include <tuple> // for std::tie

bool operator<(const Foo& lhs, const Foo& rhs)
{
  // assumes there is a bool operator< for T
  return std::tie(lhs.x, lhs.y, lhs.z, lhs.w) < std::tie(rhs.x, rhs.y, rhs.z, rhs.w);
}

....

#include <algorithm> // for std::sort

std::vector<Foo> v = ....;
std::sort(v.begin(), v.end());

如果没有自然顺序Foo,则定义比较函子而不是实现比较运算符可能更好.然后,您可以将这些传递给排序:

bool cmp_1(const Foo& lhs, const Foo& rhs)
{
  return std::tie(lhs.x, lhs.y, lhs.z, lhs.w) < std::tie(rhs.x, rhs.y, rhs.z, rhs.w);
}

std::sort(v.begin(), v.end(), cmp_1);

如果你没有C++ 11 tuple的支持,可以实现这一点使用std::tr1::tie(用头<tr1/tuple>)或使用boost::tie从boost.tuple库.

Answer 2

您可以将结构转换为std::tuple使用std::tie,并使用词典比较std::tuple::operator<.这是一个使用lambda的例子std::sort

#include <algorithm>
#include <tuple> 
#include <vector>

struct S 
{
   // x, y, z, w can be 4 different types!
   int x, y, z, w;
};

std::vector<S> v;

std::sort(std::begin(v), std::end(v), [](S const& L, S const& R) {
    return std::tie(L.x, L.y, L.z, L.w) < std::tie(R.x, R.y, R.z, R.w);
});

此示例提供std:sort了一个即时比较运算符.如果你总是想使用字典比较,你可以写一个非成员bool operator<(S const&, S const&)会自动选择std::sort,或者通过有序的关联容器,如std::set和std::map.

关于效率,来自在线参考:

所有比较运算符都是短路的; 除了确定比较结果所必需的元素之外,它们不会访问元组元素.

如果您有C++ 11环境,请选择std::tie此处给出的手写解决方案.它们更容易出错且可读性更差.