C++结构排序向量中结构元素上的 std::sort 和 std::lower_bound/equal_range 的 lambda

Question

我有一个此结构的 std::vector：

struct MS
{        
  double aT;
  double bT;
  double cT;
};

我想在其上使用 std::sort 以及 std::lower_bound/equal_range > 等等...

我需要能够对它进行排序并在结构的前两个元素中的任何一个上查找它。所以目前我有这个：

class MSaTLess 
{
public:
  bool operator() (const MS &lhs, const MS &rhs) const
  {
    return TLess(lhs.aT, rhs.aT);
  }
  bool operator() (const MS &lhs, const double d) const
  {
    return TLess(lhs.aT, d);
  }
  bool operator() (const double d, const MS &rhs) const
  {
    return TLess(d, rhs.aT);
  }
private:
  bool TLess(const double& d1, const double& d2) const
  {
    return d1 < d2;
  }
};


class MSbTLess 
{
public:
  bool operator() (const MS &lhs, const MS &rhs) const
  {
    return TLess(lhs.bT, rhs.bT);
  }
  bool operator() (const MS &lhs, const double d) const
  {
    return TLess(lhs.bT, d);
  }
  bool operator() (const double d, const MS &rhs) const
  {
    return TLess(d, rhs.bT);
  }
private:
  bool TLess(const double& d1, const double& d2) const
  {
    return d1 < d2;
  }
};

这允许我使用 MSaTLess() 调用 std::sort 和 std::lower_bound 来基于 aT 元素进行排序/查找并使用 MSbTLess() 根据 bT 元素进行排序/查找。

我想摆脱函子并使用 C++0x lambda 代替。对于相对简单的排序，因为 lambda 将采用两个 MS 类型的对象作为参数。

那么 lower_bound 和其他二分搜索查找算法呢？他们需要能够使用 (MS, double) 参数调用比较器以及相反的 (double, MS)，对吧？如何在调用 lower_bound 时最好地为这些提供 lambda？我知道我可以创建一个 MS 虚拟对象，并搜索所需的键值，然后使用与 std::sort 相同的 lambda，但是有没有办法在不使用虚拟对象的情况下做到这一点？

Answer 1

这有点尴尬，但是如果您检查标准中 lower_bound 和 upper_bound 的定义，您会发现 lower_bound 的定义取消引用的迭代器作为比较的第一个参数（以及第二个值），而 upper_bound 将取消引用的迭代器第二个（以及第一个值） ）。

所以，我还没有测试过这个，但我想你会想要：

std::lower_bound(vec.begin(), vec.end(), 3.142, [](const MS &lhs, double rhs) {
    return lhs.aT < rhs;
});

这

std::upper_bound(vec.begin(), vec.end(), 3.142, [](double lhs, const MS &rhs) {
    return lhs < rhs.aT;
});

非常令人讨厌，并且没有查找更多的东西，我不确定你是否真的有权假设该实现仅在以下情况下使用比较器文本中描述的方式 - 这是结果的定义，而不是达到目标的方法。它对于 binary_search 或 equal_range 也没有帮助。

25.3.3.1 中没有明确指出迭代器的值类型必须可转换为 T，但算法的要求是 T（在本例中，double) 必须是 LessThanComparable，而不是 T 必须以任何特定顺序与迭代器的值类型进行比较。

因此，我认为最好始终使用比较两个 MS 结构的 lambda（或函子），而不是传递双精度值作为值，而是传递一个虚拟 MS，并将正确的字段设置为您要查找的值：

std::upper_bound(vec.begin(), vec.end(), MS(3.142,0,0), [](const MS &lhs, const MS &rhs) {
    return lhs.aT < rhs.aT;
});

如果你不想给 MS 一个构造函数（因为你希望它是 POD），那么你可以编写一个函数来创建你的 MS 对象：

MS findA(double d) {
    MS result = {d, 0, 0};
    return result;
}
MS findB(double d) {
    MS result = {0, d, 0};
    return result;
}

真的，既然有了 lambda，对于这项工作，我们需要一个二分搜索的版本它需要一个一元“比较器”：

double d = something();
unary_upper_bound(vec.begin(), vec.end(), [d](const MS &rhs) {
    return d < rhs.aT;
});

但 C++0x 不提供它。

Answer 2

算法 std::sort、std::lower_bound 和 std::binary_search 采用比较容器的两个元素的谓词。任何比较两个 MS 对象并在它们按顺序排列时返回 true 的 lambda 应该适用于所有三种算法。

Answer 3

与您所说的有关 lambda 的内容没有直接关系，但这可能是使用二分搜索函数的一个想法：

#include <iostream>
#include <algorithm>
#include <vector>

struct MS
{
    double aT;
    double bT;
    double cT;
    MS(double a, double b, double c) : aT(a), bT(b), cT(c) {}
};

// template parameter is a data member of MS, of type double
template <double MS::*F>
struct Find {
    double d;
    Find(double d) : d(d) {}
};

template <double MS::*F>
bool operator<(const Find<F> &lhs, const Find<F> &rhs) {
    return lhs.d < rhs.d;
}
template <double MS::*F>
bool operator<(const Find<F> &lhs, const MS &rhs) {
    return lhs.d < rhs.*F;
}
template <double MS::*F>
bool operator<(const MS &lhs, const Find<F> &rhs) {
    return lhs.*F < rhs.d;
}

int main() {
    std::cout << (Find<&MS::bT>(1) < Find<&MS::bT>(2)) << "\n";
    std::cout << (Find<&MS::bT>(1) < MS(1,0,0)) << "\n";
    std::cout << (MS(1,0,0) < Find<&MS::bT>(1)) << "\n";

    std::vector<MS> vec;
    vec.push_back(MS(1,0,0));
    vec.push_back(MS(0,1,0));
    std::lower_bound(vec.begin(), vec.end(), Find<&MS::bT>(0.5));
    std::upper_bound(vec.begin(), vec.end(), Find<&MS::bT>(0.5));
}

基本上，通过使用 Find 作为值，我们不必提供比较器，因为 Find 使用我们指定的字段与 MS 进行比较。这与您在这里看到的答案是同一类：如何排序STL 向量，但使用的是值而不是像这种情况下的比较器。不确定它是否很好用，但可能是，因为它指定了要搜索的值以及要在单个短表达式中搜索的字段。

Answer 4

我对 std::equal_range 遇到了同样的问题，并提出了替代解决方案。

我有一个指向在类型字段上排序的对象的指针的集合。我需要找到给定类型的对象范围。

const auto range = std::equal_range (next, blocks.end(), nullptr,
    [type] (Object* o1, Object* o2)
{
    return (o1 ? o1->Type() : type) < (o2 ? o2->Type() : type);
});

尽管它比专用谓词效率低，因为它为我的集合中的每个对象引入了不必要的 nullptr 测试，但它确实提供了一个有趣的替代方案。

顺便说一句，当我像您的示例中那样使用类时，我倾向于执行以下操作。除了更短之外，这还允许我添加其他类型，每个类型仅 1 个函数，而不是每个类型 4 个运算符。

class MSbTLess 
{
private:
    static inline const double& value (const MS& val)
    {
        return val.bT;
    }

    static inline const double& value (const double& val)
    {
        return val;
    }

public:
    template <typename T1, typename T2>
    bool operator() (const T1& lhs, const T2& rhs) const
    {
        return value (t1) < value (t2);
    }
};

Answer 5

在 lower_bound 的定义和其他 STL 算法中，Compare 函数使得第一个类型必须与前向迭代器的类型匹配，而第二个类型必须与 T 的类型（即值的类型）匹配。

template< class ForwardIt, class T, class Compare >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );

因此，人们确实可以比较来自不同对象的事物（执行另一种响应称为一元比较器的操作）。在 C++11 中：

vector<MS> v = SomeSortedVectorofMSByFieldaT();
double a_key;
auto it = std::lower_bound(v.begin(), 
                           v.end(), 
                           a_key, 
                           []{const MS& m, const double& a) {
                             m.aT < a; 
                           });

这也可以与其他 STL 算法函数一起使用。