c++ - 对 std::binary_search 的神秘限制

Question

问题描述:
考虑一些具有 std::string name 的结构成员。为了清楚起见，我们假设它是 struct Human ，代表关于人的信息。除了 name它还可以有许多其他数据成员。
让有一个容器 std::vector<Human> vec ，其中对象已按 name 排序.同样为了清楚起见，假设所有名称都是唯一的。
问题是:有一些字符串 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 的对象:

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 ，尤其是在他们没有默认构造函数的情况下？设置魔法值可能会导致创建一个语义上非法的对象。
其次，我们必须将此构造函数声明为非 explicit允许在算法期间进行隐式转换。这样做的不良后果是众所周知的。
还有，这样的临时Human对象将在每次迭代时构造，这可能会非常昂贵。

尝试 2:转换 Human至 std::string .

我们可以尝试添加一个 operator string ()到 Human返回它的类是 name ，然后使用两个 std::string 的比较s。但是，由于以下原因，这种方法也很不方便:

首先，由于讨论的问题，代码不会立即编译here .我们将不得不做更多的工作以使编译器使用适当的 operator < .
其次，“将人类转换为字符串”是什么意思？这种转换的存在会导致类 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)。

没有明确说明 ForwardIterator的类型。但是，在 20.1.2 给出的 LessThanComparable 的定义中，提到了 的两个元素的比较。同类型 .这是我不明白的。是否确实表示被搜索对象的类型和容器对象的类型必须是一样的，我的解决方案打破了这个限制？或者它不指comp时的情况使用比较器，并且仅在默认 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);