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

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 lambdas.对于相对简单的排序,因为lambda将两个类型为MS的对象作为参数.

然而,对于lower_bound和其他二进制搜索查找算法呢？他们需要能够用(MS,双)参数调用比较器,反之亦然(双,MS),对吧？如何在调用lower_bound时最好地为lambda提供这些？我知道我可以创建一个MS虚拟对象,其中搜索了所需的键值,然后使用与std :: sort相同的lambda但是有没有办法在不使用虚拟对象的情况下执行它？

Answer 1

这是一个有点尴尬,但如果你检查的定义lower_bound,并upper_bound从标准,你会看到的定义lower_bound放iterator的反引用作为第一个比较的参数(和值秒),而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(或仿函数),而不是将double作为值传递,传递一个虚拟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不提供它.