std::binary_search 的神秘限制

Question

问题描述：
考虑一些具有 std::string name 成员的结构。为了清楚起见，我们假设它是一个struct Human，代表有关人的信息。除了名称之外，它还可以有许多其他数据成员。
假设有一个容器 std::vectorvec，其中对象已按名称排序。另外，为了清楚起见，假设所有名称都是唯一的。
问题是：使用一些字符串nameToFind来查找数组中是否存在具有该名称的元素。

解决方案和我的进展：
显而易见且自然的解决方案似乎是使用 std::binary_search 函数执行二分搜索。但有一个问题：被搜索的元素类型（std::string）与容器中元素的类型（Human）不同，而std ::binary_search 需要一个规则来比较这些元素。我尝试通过三种方式解决这个问题，如下所述。提供前两个只是为了说明我的解决方案的演变以及我遇到的问题。我的主要问题是针对第三个问题。

尝试 1：将 std::string 转换为 Human。

编写比较函数：

bool compareHumansByNames( const Human& lhs, const Human& rhs )
{
   return lhs.name < rhs.name;
}

然后添加一个构造函数来构造 Human来自 std::string 的 code> 对象：

struct Human
{
   Human( const std::string& s );
   //... other methods

   std::string name;
   //... other members
};

并按以下形式使用binary_search：

std::binary_search( vec.begin(), vec.end(), nameToFind, compareHumansByNames );

似乎有效，但出现了两个大问题：
首先，如何初始化除 Human::name 之外的其他数据成员，特别是在它们没有默认构造函数的情况下？设置魔法值可能会导致创建语义上非法的对象。
其次，我们必须将此构造函数声明为非显式的，以允许在算法期间进行隐式转换。这样做的不良后果是众所周知的。
此外，这样的临时 Human 对象将在每次迭代时构建，这可能会非常昂贵。

尝试2：将Human转换为std::string。

我们可以尝试添加一个operator string ()返回其名称的 Human 类，然后对两个 std::string 进行比较。然而，这种方法也很不方便，原因如下：

首先，由于讨论的问题，代码不会立即编译 此处。我们必须做更多的工作才能使编译器使用适当的运算符<。
其次，“将人类转换为字符串”是什么意思？这种转换的存在可能会导致类 Human 的语义错误使用，这是不希望的。

尝试3：不进行转换进行比较。

到目前为止，我得到的最好的解决方案是创建一个

struct Comparator
{
   bool operator() ( const Human& lhs, const std::string& rhs )
   {
      return lhs.name < rhs;
   }
   bool operator() ( const std::string& lhs, const Human& rhs )
   {
      return lhs < rhs.name;
   }
};

并使用二分搜索作为

binary_search( vec.begin(), vec.end(), nameToFind, Comparator() );

这可以正确编译和执行，一切似乎都很好，但这里是有趣的部分开始的地方:

看看 http://www.sgi.com/tech/stl/binary_search.html。这里说的是“ForwardIterator的值类型是与T相同的类型。”。相当令人困惑的限制，我的最后一个解决方案打破了它。让我们看看 C++ 标准对此有何规定：

---

25.3.3.4 binary_search

template<class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterator last,
const T& value);

template<class ForwardIterator, class T, class Compare>
bool binary_search(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);

要求： 类型 T 为 LessThanComparable (20.1.2)。

---

没有明确说明 < code>ForwardIterator 的类型。但是，在 20.1.2 中给出的 LessThanComparable 定义中，提到了相同类型的两个元素的比较。这是我不明白的。这是否确实意味着正在搜索的对象的类型和容器对象的类型必须相同，而我的解决方案打破了这一点限制 ？或者它不是指使用 comp 比较器时的情况，而仅涉及使用默认 operator operator < 进行比较时的情况？在第一种情况下，我对如何使用 std::binary_search 来解决这个问题而不遇到上述问题感到困惑。

预先感谢您的帮助并抽出时间阅读我的问题。

注意：我知道手动编写二分搜索不需要时间并且可以立即解决问题，但为了避免重新发明轮子，我想使用 std::binary_search。根据标准了解这种限制的存在对我来说也很有趣。

Answer 1

如果您的目标是查找是否存在具有给定名称的 Human，那么以下内容应该有效：

const std::string& get_name(const Human& h)
{
    return h.name;
}

...

bool result = std::binary_search(
    boost::make_transform_iterator(v.begin(), &get_name),
    boost::make_transform_iterator(v.end(), &get_name),
    name_to_check_against);

Answer 2

[完全重写；忽略注释]

措辞已从 C++03 更改为 C++0x。在后者中，不再要求 T 小于可比性，大概是为了减轻这种不必要的限制。

新标准仅要求 comp(e, value) 暗示 !comp(value, e)。因此，只要您的比较器实现了两个方向，您就应该能够合法地搜索 string 作为具有实现两个非对称比较的比较器函子的值（即您的“尝试 3”）。

Answer 3

我认为这里的标准所说的是表达式 fucntor(a, b) 需要是有效的严格弱排序，无论算法是否决定执行类似 functor(*开始，*（开始+ 1））。因此，我认为您的比较器需要提供 operator()(Human, Human) 的重载才能保持一致。

也就是说，我认为这是其中之一标准未明确允许的事情，但很少或根本不存在利用标准提供的自由度的实现。

Answer 4

我不认为标准中的任何地方都要求通过 binary_search 传递给比较函数（或 < 运算符）的值的类型必须相同。因此，从形式上来说，我认为使用适用于两种不同类型值的比较器是完全可以的。