相关疑难解决方法(0)

我正在查看STL容器并试图弄清楚它们到底是什么(即使用的数据结构),并且deque阻止了我:我起初认为它是一个双链表,它允许从两端插入和删除恒定时间,但我对运营商[]在恒定时间内做出的承诺感到不安.在链表中,任意访问应该是O(n),对吗？

如果它是一个动态数组,它如何在恒定时间内添加元素？应该提到的是,可能会发生重新分配,并且O(1)是一个摊销成本,就像向量一样.

所以我想知道这个结构允许在恒定时间内任意访问,同时永远不需要移动到一个新的更大的地方.

我四处搜索,找不到bitset :: count()的性能时间规范.有人知道它是什么(O(n)或更好)以及在哪里找到它？

编辑按STL我只参考标准模板库.

Deque为访问任何元素(cpp引用)提供了持续的复杂性.在向量中,它总是不变的复杂性(向量中的第一个元素的地址+没有元素)但是它如何用于双端队列？Deque元素不是连续的,那么它如何为访问任何元素提供O(1)时间复杂度？当我运行以下程序时,在向量的情况下它给出了正确的输出但是对于双端队列,它给出了一些任意数字(同意不给出正确的结果,因为元素不是连续的).

vector<int> v1;
deque<int> d1;
for( int i =0; i < 1000000;++i)
    v1.push_back(i);
for( int j =0; j < 1000000;++j)
    d1.push_back(j);
cout << *(&v1[0] +90000) << endl; // output 90000
cout<<  *(&d1[0] +90000)<<endl;   // Output is not the same as expected