deque中元素的随机访问如何给出恒定的时间复杂度？

Question

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

Answer 1

deque通常实现为两层结构,顶层是指向固定大小块的指针数组.使用该大小的知识,确定哪个块保持感兴趣的项目和恒定的复杂性以确定正在请求块中的哪个项目是恒定的复杂性.

仅仅因为它是常量并不表示它总是一个简单的直接内存访问,只是对该特定操作的所有访问都需要相同的步骤.