列表 - 复杂性

Question

列表的所有插入(任何位置)是否都是常量？

访问怎么样？

前,后 - 恒定时间？

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

Answer 1

在a 中的任何位置插入std::list是恒定时间操作.

也就是说,在你可以插入之前,你需要获得一个迭代器到你要插入的位置,这是一个线性时间操作,除非你在谈论前面或后面.

@ user382499:`std :: list <t> :: begin()`和`std :: list <t> :: end()`都是常量时间操作.同样处理`push_front`,`push_back`,`pop_front`和`pop_back`. (6认同)

Answer 2

列表是双向链表。也就是说，它是一个既支持向前和向后遍历，又支持在开头或结尾或中间（摊销）恒定时间插入和删除元素的 Sequence。列表具有一个重要的属性，即插入和拼接不会使列表元素的迭代器无效，并且即使删除也只会使指向被删除元素的迭代器无效

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