c++ - 双端队列中元素的随机访问如何提供恒定的时间复杂度？

标签 c++

<分区>

双端队列为访问任何元素提供了恒定的复杂性(cpp reference)。在 Vector 中，它始终是恒定的复杂性(vector 中第一个元素的地址 + 元素数 * 每个元素的大小)但是它如何用于 Deque？双端队列元素在内存中是不连续的，那么它是如何实现 O(1) 时间复杂度来访问任何元素的呢？当我运行以下程序时，对于 Vector，它给出了正确的输出，但对于 Deque，它给出了一些任意数字(同意不给出正确的结果，因为元素不连续)。

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 90000

最佳答案

双端队列通常实现为两层结构，顶层是指向固定大小块的指针数组。使用该大小的知识，确定哪个 block 包含感兴趣的项目是恒定的复杂性，并且确定正在请求 block 中的哪个项目是恒定的复杂性。

仅仅因为它是常量并不表示它始终是简单的直接内存访问，只是该特定操作的所有访问都需要相同的步骤。

关于c++ - 双端队列中元素的随机访问如何提供恒定的时间复杂度？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/52241192/

上一篇：c++ - while循环c++中的非法指令

下一篇：c++ - 模板打印函数 C++

相关文章：

c++ - 在调试期间显示 cpu 缓存和寄存器内容

c++ - 为什么下面的代码编译

c++ - SQLite 找出违反了哪个约束

c++ - 对记录数组进行快速排序(结构)

c++ - 为什么像 cin、cout、string 等被认为是对象？

c++ - 设置位置后，Qt 使用 contains() 删除对象

c++ - WORD* 类型的参数与 LPCWSTR 类型的参数不兼容

c++ - 使用 C++ 实现线程

c++ - 更好的做法 : Ever looping thread or successive threads?

c++ - 各种操作系统的语言环境格式