rlb*_*ond 3 c++ language-agnostic containers
今天我好好看看我的STL选项.然后我想到了什么.
似乎链表(std :: list)的用途有限.也就是说,它只是真的有用
容器中元素的顺序很重要,和
我需要在中间擦除或插入元素.
也就是说,如果我只是想要大量数据并且不关心它的顺序,那么如果我想要O(log n)查找或者std ::我最好使用std :: set(平衡树) unordered_map(哈希映射)如果我想要O(1)期望查找或std :: vector(连续数组)以获得更好的引用位置,或者如果我需要插入std :: deque(双端队列)在前面和后面.
OTOH,如果顺序很重要,我最好使用std :: vector来获得更好的引用局部性和更少的开销,或者如果需要进行大量的调整,则最好使用std :: deque.
那么,我错过了什么吗？或者链接列表不是很好吗？除了中间插入/擦除之外,为什么有人想要使用一个呢？
Tal*_*joe 11
任何类型的插入/删除都是O(1).即使std :: vector对于追加也不是O(1),它接近O(1)因为它大多数时候都是,但有时你将不得不增长那个数组.
它也非常擅长处理批量插入和删除.如果你有100万条记录并希望从另一个列表(concat)中追加100万条记录,那就是O(1).每个其他结构(假设stadard/naive实现)至少为O(n)(其中n是添加的元素数).