1

我有一个列表，其中包含所有元素作为形式的结构

typedef struct person_node{
    string name;
    string country;
}person;

std::list<person> list;

该列表已按人名排序。

如何在此使用内置的binary_search()函数？

我已经知道如何在只有数字作为数据的列表上使用这个binary_search()，但我想知道如何将它用于这样的列表。

我将此二进制函数用作：

binary_search (list.begin(), list.end(), value, compare_function);

唯一我不知道的是，“如果我需要在列表中查找特定名称，我应该输入什么来代替value ？”

如果找到，我还希望迭代器指向该节点。

4

2 回答 2

6

您输入一个person包含name您要查找的内容。

另请注意，binary_search它很少有用（它只告诉您该项目是否存在，而不是它在集合中的位置。它在 a 上双重无用std::list，因为它需要随机访问迭代器才能正常工作（这std::list并不提供）。

因此，您可能想要的是std::vector<person>or std::deque<person>，您可能想要使用std::lower_boundor进行搜索std::upper_bound。std::lower_bound并将std::upper_bound每个返回一个迭代器到他们找到的项目，让您访问该对象。

于 2013-01-14T14:37:24.853 回答
2

第三项以您可以调用的方式描述了您正在搜索的内容

compare_function(*iter, value )

或者

compare_function( value, *iter )

whereiter是您的集合中的有效迭代器。如果必须出现在您的列表中以保持排序，这应该true在第一种情况下返回，在第二种情况下反之亦然。*itervalue

因此请注意，如果您支持这两个重载，您实际上可以将 astring作为第三个参数传入。compare_function原型是：

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

并且 T 不一定是迭代器的值类型。

顺便说一句，虽然您可以将它用于 a std::list，但对于不是随机访问的迭代器来说效率极低，因为每个std::advance语句都是O(N)因此整个操作是O(N log N). 即使是普通人std::find也会更快。

使用vectorormultiset如果你可以有重复，或者set如果你不允许重复。

binary_search它本身也会返回该项目是否存在并且true/false没有找到你的项目（所以你不会知道他们的国家）。如果您有重复项，您可以使用它std::equal_range来获取所有此类值的列表。如果不这样做，您可以使用std::lower_boundwhich 将为您提供一个迭代器，指向名称等于或大于您的名称的第一个项目，然后检查它是否相等，而不是更大。

于 2013-01-14T14:36:06.963 回答