c++ - 链表只是用途有限吗？

Question

今天我仔细查看了我的 STL 选项。然后我想到了一件事。

似乎链表(std::list)的用途有限。也就是说，它只是看起来有用的话

• 容器中元素的顺序很重要，并且

• 我需要在中间删除或插入元素。

也就是说，如果我只想要大量数据而不关心它的顺序，如果我想要 O(log n) 查找或std::unordered_map( HashMap )如果我想要 O(1) 预期查找或 std::vector(连续数组)以获得更好的引用位置，或者 std::deque(双端队列)如果我需要在前面和后面插入。

OTOH，如果顺序确实很重要，我最好使用 std::vector 以获得更好的引用位置和更少的开销，或者如果需要进行大量调整大小则使用 std::deque。

那么，我是不是漏掉了什么？还是链表不是那么好？除了中间插入/删除之外，到底为什么有人要使用一个？

Answer 1

任何类型的插入/删除都是 O(1)。即使 std::vector 不是 O(1) 用于追加，它接近 O(1) 因为大多数时候是这样，但有时您将不得不增加该数组。

它也非常擅长处理批量插入、删除。如果您有 100 万条记录，并且想要从另一个列表 (concat) 追加 100 万条记录，那就是 O(1)。每个其他结构(假设标准/天真的实现)至少为 O(n)(其中 n 是添加的元素数)。