c++ - 在列表 C++ 中搜索？

Question

感谢您提前查看我的问题。

我正在完成一个大学作业的问题，该问题询问以下内容：

对于每个 std::list< >、std::map< >、std::unordered_map< > 文档并解释元素插入和查找的保证性能。

在我开始解释列表中的元素查找之前，我大部分时间都没有遇到任何问题。

我一直在从 Josuttis 和http://www.cplusplus.com收集我的信息，但似乎找不到任何关于此的信息。

我猜是因为不可能？

Answer 1

You mention that you had no trouble except with the list portion, so I'm only going to answer for that portion.

In order to answer this question, you need to understand how std::list is implemented. Some quick searching brings up:

List containers are implemented as doubly-linked lists.

From how I interpret it, Guaranteed Performance means the same thing as Worse-case Runtime Complexity.

For element lookup in a doubly-linked list, the worst-case scenario is that your list does not contain the item you are trying to lookup. In that case, you would have to compare every item in the list to the item you are searching for. So the worst-case runtime complexity of this operation is O(n), where n is the size of the list.

Answer 2

如果您想要更正式地声明所支持的内容，请参考标准的内容。关于我们可以做的最佳搜索是使用二分搜索，例如std::lower_bound（§25.4.3.1/3）：

复杂性：最多 log ₂ ( last − first) + O(1) 次比较。

不过，这只告诉我们比较的次数。要在容器中移动，请lower_bound使用std::advance. 关于我们发现的 std::list (§23.3.5.1/1)：

列表是支持双向迭代器的序列容器 [...]

std::advance那么，对于提供双向迭代器的集合来说，它是如何工作的呢？（§24.4.4/1）：

[...] 对于输入、前向和双向迭代器，他们使用 ++ 来提供线性时间实现。

因此，要在列表中查找任何内容（通过值或位置），我们将总体上查看线性复杂度，并进行对数比较。老实说，我们可能会更好std::find（§25.2.5/2）：

复杂性：最多last - first应用相应谓词。

不过，两者之间的选择可能并不总是很明显——遍历列表显然是线性的。std::find最小化遍历，同时std::lower_bound最小化比较。如果比较比遍历更昂贵，std::lower_bound可能会做得更好。如果比较便宜，std::find可能会更好。

Answer 3

Answer 4

From http://www.cplusplus.com/reference/list/list/

The main drawback of lists and forward_lists compared to these other sequence containers is that they lack direct access to the elements by their position; For example, to access the sixth element in a list one has to iterate from a known position (like the beginning or the end) to that position, which takes linear time in the distance between these. They also consume some extra memory to keep the linking information associated to each element (which may be an important factor for large lists of small-sized elements).

So, iterating through a std::list< > (looking up an element) is linear complexity. Also, you cannot access elements by index.