5

我有一个包含成员 x、y、z 和 w 的结构。如何在 C++ 中先按 x，然后按 y，按 z，最后按 w 有效排序？

4

4 回答 4

9

如果要实现字典顺序，那么最简单的方法是使用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++11tuple支持，你可以使用std::tr1::tie（使用 header <tr1/tuple>）或使用boost.tuple libraryboost::tie来实现它。

于 2013-06-13T06:42:07.633 回答
6

您可以将 struct 转换为std::tupleusing 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::setstd::map

关于效率，来自在线参考：

所有比较运算符都是短路的；它们不会访问超出确定比较结果所需的元组元素。

如果您有 C++11 环境，则更喜欢std::tie这里给出的手写解决方案。它们更容易出错且可读性更差。

于 2013-06-13T06:43:34.940 回答
2

如果您滚动自己的比较运算符，那么您可以自由地将对象放入std::maps 或调用std::sort中。此实现设计简单，因此您可以在需要时轻松验证和修改它。通过仅operator<用于比较 x、y、z 和 w，如果这些变量不具有可比性（例如，如果它们是您自己的结构而不是 ints、double、std::strings，则它可以最大限度地减少您可能需要实现的运算符的数量ETC。）。

bool operator<(const Q& lhs, const Q& rhs)
{
    if (lhs.x < rhs.x) return true;
    if (rhs.x < lhs.x) return false;
    if (lhs.y < rhs.y) return true;
    if (rhs.y < lhs.y) return false;
    if (lhs.z < rhs.z) return true;
    if (rhs.z < lhs.z) return false;
    if (lhs.w < rhs.w) return true;
    return false;
}

有时类型会定义一个比较函数，该函数返回 -1、0 或 1 来表示小于、等于或大于，这既是为了支持 , , , , 的实现<，<=也是==因为!=有时>=会>执行 a <then a !=or>会重复很多工作（考虑比较只有最后一个字符不同的长文本字符串）。如果 x、y、z 和 w 恰好属于此类类型并且具有更高性能的比较功能，则您可以通过以下方式提高整体性能：

bool operator<(const Q& lhs, const Q& rhs)
{
    int c;
    return (c = lhs.x.compare(rhs.x) ? c :
           (c = lhs.y.compare(rhs.y) ? c :
           (c = lhs.z.compare(rhs.z) ? c :
           lhs.w < rhs.w;
}
于 2013-06-13T06:43:35.237 回答
2

此解决方案每个元素比较最多有 4 次比较，并且不需要构造其他对象：

// using function as comp
std::sort (quadrupleVec.begin(), quadrupleVec.end(), [](const Quadruple& a, const Quadruple& b)
{
    if (a.x != b.x) 
        return a.x < b.x;

    if (a.y != b.y)
        return a.y < b.y;

    if (a.z != b.z)
        return a.z < b.z;

    return a.w < b.w;
});
于 2013-06-13T06:48:26.413 回答