性病::神秘binary_search的限制 [英] Mystical restriction on std::binary_search

问题描述

问题desicription：
考虑有一个的std ::字符串名称一定的结构成员。为清楚起见我们假设它是一个结构人力，重约$人们p $ psenting信息。除了名称它也可以有很多其他的数据成员。
让我们有一个容器的std ::矢量＆lt;人与GT; VEC ，其中的对象已经按名称。同时为清楚起见假设所有的名字都是唯一的。
的问题是的：有一些字符串 nameToFind 找出是否有这样的名字存在一个元素数组中的

Problem desicription:
Consider some structure having an std::string name member. For clearness let's suppose that it's a struct Human, representing information about people. Besides the name it can also have many other data members.
Let there be a container std::vector<Human> vec, where the objects are already sorted by name. Also for clearness suppose that all the names are unique.
The problem is: having some string nameToFind find out if there exists an element in the array having such name.

解决方案和我的进步：
最明显的和自然的解决方案似乎执行使用的std :: binary_search的函数二进制搜索。但有一个问题：被搜索的元素的类型（的std ::字符串）是由元素的容器类型不同（人），和std ::需要binary_search的规则来比较这些元素。我试图解决这个方法有三种，如下所述。前两个是提供只是为了说明我的解决方案的演变，我遇到了问题。我的主要问题指的是第三个。

Solution and my progress:
The obvious and natural solution seems to perform a binary search using the std::binary_search function. But there is a problem: the type of the element being searched (std::string) is different from the type of the elements in the container (Human), and std::binary_search needs a rule to compare these elements. I tried to solve this in three ways, described below. First two are provided just to illustrate the evolution of my solution and the problems which I came across. My main question refers to the third one.

尝试1：转换的std ::字符串到人

Attempt 1: convert std::string to Human.

写比较函数：

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

然后添加一个构造函数，构造了一个人对象从的std ::字符串：

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

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

和使用在binary_search的格式如下：

and use the binary_search in following form:

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

似乎工作，但变成了两个大问题：
首先，如何初始化其他数据成员，但人::名称，尤其是在情况下，他们没有一个默认的构造函数？设置魔法值可能会导致创建一个对象，它在语义上是非法的。
其次，我们必须声明此构造非明确，允许在算法中隐式转换。这样做的不好的后果是公知的。
此外，这样的临时人对象将在每次迭代中，它可以变成是相当昂贵的构建。

Seems working, but turns up two big problems:
First, how to initialize other data members but Human::name, especially in the case when they don't have a default constructor ? setting magic values may lead to creation of an object which is semantically illegal.
Second, we have to declare this constructor as non explicit to allow implicit conversions during the algorithm. The bad consequences of this are well known.
Also, such a temporary Human object will be constructed at each iteration, which can turn out to be quite expensive.

尝试2：转换人到的std ::字符串

Attempt 2: convert Human to std::string.

我们可以尝试添加操作符字符串（）到人类，它返回它的名称，然后用之比较两的std ::字符串秒。但是，这种方法也不方便由以下原因：

We can try to add an operator string () to the Human class which returns it's name, and then use the comparsion for two std::strings. However, this approach is also inconvenient by the following reasons:

首先，code不能编译，因为讨论的问题<一的一次href="http://stackoverflow.com/questions/6788169/why-does-not-the-compiler-perform-a-type-conversion">here.我们必须努力多一点，以使编译器使用适当的运营商LT;
其次，是什么意思转换一个人来串？这种转换的存在会导致类人，这是不可取的语义错误的用法。

First, the code will not compile at once because of the problem discussed here. We will have to work a bit more to make the compiler use the appropriate operator <.
Second, what does mean "convert a Human to string" ? Existence of such conversion can lead to semantically wrong usage of class Human, which is undesirable.

尝试3：比较不转换

我迄今为止最好的解决方案是创建一个

The best solution I got so far is to create a

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() );

这编译和执行正确的，一切都似乎是确定的，但这里是有趣的部分开始的地方：

This compiles and executes correctly, everything seems to be ok, but here is where the interesting part begins:

看一看<一href="http://www.sgi.com/tech/stl/binary_search.html">http://www.sgi.com/tech/stl/binary_search.html.它在这里说， ForwardIterator 的值类型是同类型为T 的。相当混乱的限制，我的最后解决方案，打破它。让我们来看看什么是C ++标准说一下吧：

Have a look at http://www.sgi.com/tech/stl/binary_search.html. It's said here that "ForwardIterator's value type is the same type as T.". Quite confusing restriction, and my last solution breaks it. Let's see what does the C++ standard say about it:

25.3.3.4 binary_search的

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型是小于关系可比较（20.1.2）

Requires: Type T is LessThanComparable (20.1.2).

没有被明确地说，大约 ForwardIterator 的类型。但是，在定义的小于关系可比较的中的 20.1.2 的据说约相同类型的两个元素的comparsion给出。这里是什么，我不明白。这是否真的意味着的被搜索对象的类型的和的容器的对象的必须是一样的，我的解决方案打破了这种类型限制 ？或者，它不是指的情况下，当补偿比较时，只有约的情况下默认的运营商的LT; 用于comparsion？在第一种情况下，我很困惑如何使用的std :: binary_search的来解决这个问题，而不需要通过上面提到的问题来了。

Nothing is explicitly said about ForwardIterator's type. But, in definition of LessThanComparable given in 20.1.2 it is said about comparsion of two elements of the same type. And here is what I do not understand. Does it indeed mean that the type of the object being searched and the type of the container's objects must be the same, and my solution breaks this restriction ? Or it does not refer to the case when the comp comparator is used, and only is about the case when the default operator < is used for comparsion ? In first case, I'm confused about how to use std::binary_search to solve this without coming across the problems mentioned above.

先谢谢您的帮助，找到时间来阅读我的问题。

Thanks in advance for help and finding time to read my question.

注意：的我的理解是手写的二进制搜索不花时间，并会解决这个问题瞬间，但要避免重新发明轮子我想使用std :: binary_search的。此外，它是非常有趣的，我了解过，根据标准存在这样的限制。

Note: I understand that writing a binary search by hand takes no time and will solve the problem instantly, but to avoid re-inventing a wheel I want to use the std::binary_search. Also it's very interesting to me to find out about existence of such restriction according to standard.

推荐答案

如果你的目标是找出是否有一个人与给定的名称，然后下面应该为确保工作：

If your goal is to find if there is a Human with a given name, then the following should work for sure:

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);

这篇关于性病::神秘binary_search的限制的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！