stl中的一些容器没有查找功能

Question

一些STL容器例如std::list和std::vector没有find()方法作为成员函数.这是为什么？我知道有使用的替代std::find从<algorithm>,但仍然使用这也不是100%纯天然.

Answer 1

一般设计原则是尽可能使用std::find,并find在更有效时实现成员函数.

该容器做有一个find部件是具有更有效的元素的查找机制然后在执行线性搜索容器std::find.例如,二进制搜索树,例如std::set和std::map,或哈希表,例如它们的unordered对应物.

Answer 2

find,lower_bound和upper_bound成员函数仅当提供更有效的时比使用非成员的等同物,或非成员无法运行给定容器的公共API

特别要注意的是,它std::string具有为字符搜索find提供类似std::find()线性搜索功能的功能,以及std::search()用于子字符串搜索的类似设施:虽然非成员版本可能具有相同的大O效率,但它们可能效率低于专用机器代码指令通常可用于"字符串"搜索.还有历史,便利和易于移植的因素.

除了效率问题,值得注意的是一些容器:

• 本质上是排序的(multi- set,map)或未排序的(unordered_map,unordered_set),通常是未排序的(例如std::string),或者很容易(std::vector)

• 公开支持前向迭代和/或随机访问

• 可能私下支持二进制搜索

• 有一个专门用于元素访问的公共API,因此算法的潜在重用相对有限(例如unordered_map::bucket/ ::begin(n)等)

vector使用大量算法进行搜索也是有意义的:

• std::find 做一个强力线性O(n)搜索,它将首先"找到"低指数元素,

• std::binary_search 需要一个有序矢量但跳转以实现O(log2n)复杂度.

• 其他选项如外推搜索和散列可能适用

你会如何选择实施和添加成员？似乎有点武断.尽管如此,使用哪种选择在性能方面也是重要的:对于一百万个元素,find在匹配之前平均进行五十万个元素比较,并且每当元素不存在时平均为百万个元素,而binary_search通常需要进行~20个比较.

与容器find通常不提供这种灵活性,并且find和/或lower_bound/ upper_bound它们提供可被视为替代非成员的等同物,并且可能搜索容器的唯一合理的方法.

Answer 3

因为它的std::find功能algorithm适用于它们.

通常,容器喜欢std::vector并std::list具有线性搜索时间复杂度.因此,附加到它们的成员find函数是冗余的,因为已经存在std::find.对于其他容器(如,std::set或std::map等)有一个更好的方法(即,不是线性复杂度快)来实现搜索.因此,实现者将这些更快的搜索算法实现为成员函数.