对std :: binary_search的神秘限制

Question

问题描述:
考虑一些有std::string name成员的结构.为清楚起见,我们假设它是a 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秒.但是,由于以下原因,这种方法也很不方便:

首先,由于此处讨论的问题,代码不会立即编译.我们将需要更多工作来使编译器使用适当的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据说约的两个元素能比较同一类型.这是我不明白的.它确实意味着被搜索对象的类型和容器对象 的类型必须相同,我的解决方案是否打破了这一限制？或者它不是指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);

Answer 2

[完全重写; 无视评论]

措辞已从C++ 03更改为C++ 0x.在后者中,不再需要T低于可比性,可能是为了减轻这种不必要的限制.

新标准仅要求comp(e, value)暗示!comp(value, e).因此,只要您的比较器实现两个方向,您就应该能够合法地string使用比较器仿函数搜索a 作为值,该仿函数实现两个非对称比较(即您的"尝试3").