我正在查看STL容器并试图弄清楚它们到底是什么(即使用的数据结构),并且deque阻止了我:我起初认为它是一个双链表,它允许从两端插入和删除恒定时间,但我对运营商[]在恒定时间内做出的承诺感到不安.在链表中,任意访问应该是O(n),对吗？
如果它是一个动态数组,它如何在恒定时间内添加元素？应该提到的是,可能会发生重新分配,并且O(1)是一个摊销成本,就像向量一样.
所以我想知道这个结构允许在恒定时间内任意访问,同时永远不需要移动到一个新的更大的地方.
c++ stl deque
以来
为什么有人对子级宁愿std::vector到std::deque？
std::vector
std::deque
c++ stl vector deque
c++ ×2
deque ×2
stl ×2
vector ×1