stl list - 复杂度

Question

列表的所有插入（任何位置）是否为常量？

访问呢？

正面，背面 - 恒定时间？

并在列表中间 - 线性时间？

Answer 1

http://www.sgi.com/tech/stl/List.html

列表是一个双向链表。也就是说，它是一个序列，支持向前和向后遍历，以及（分期付款）恒定时间插入和删除在开始或结束，或在中间的元素。列出有插入和拼接，不坏迭代器列表元素的重要属性，即使去除无效只指向被删除

至于访问的元素，如果你要迭代器搜索中间的某个元素，这需要线性时间。但是一旦你有了一个迭代器，它就会（当然）是恒定的访问时间，并且不会因其他插入或删除而失效。

Answer 2

插入任何地方在std::list是恒定时间操作。这就是说，在你插入之前，你需要获得一个迭代器到你想插入的位置，除非你正在讨论前面或后面，否则这是一个线性时间操作。

Answer 3

插入单个元素到std::list<>需要一定的时间，无论您在哪里插入它。请注意，std::list<>不是一个固有排序的容器，这意味着您指定了插入新元素的确切位置。难怪，时间是线性的。

插入（“拼接”）一个[子]的序列元件的从另一个列表中移动到该一个（即std::list<>::splice方法）采用任一恒定时间或线性时间（线性在元件的插入的数目）。这是因为如果std::list<>执行具有一个选择任一：

（1）实现在恒定时间std::list<>::size方法，并且通过在执行线性时间std::list<>::splice，或

（2）实施std::list<>::splice方法支付它时间不变，并通过线性时间实施std::list<>::size来支付。

你可以有这个或那个，但你不能同时拥有这两个。遵循特定方法的决定取决于实施。

Answer 4

它是由C++标准23.2.2/1保证：

list一个是一种序列的支持双向迭代器和允许恒定时间插入物和序列内的任何地方擦除 操作，自动处理存储管理。与矢量 （23.2.4）和deques（23.2.1）不同，不支持对列表元素的快速随机访问，但许多算法只有 需要顺序访问。

Answer 5

需要注意的是，这主要是由于更好局部性数据的，在实践中std::vector往往快于std::list，即使在理论上它应该是周围的其他方法。所以默认顺序容器应该是std::vector。

如果你怀疑，第一项措施是容器是否在所有关键（增加一段代码的速度甚至十几倍，如果这一块只使用总时间的2％没有使用），然后将测量结果与std::list和std::deque进行比较并做出选择。