是否有一个特定的数据结构,C++ STL中的deque应该实现,或者是一个deque只是这个模糊的概念,一个数组可以从前面和后面增长,然而实现选择实现？
我以前总是假设deque是一个循环缓冲区,但我最近在这里读了一个C++引用,听起来像deque是某种数组的数组.它似乎不是一个普通的旧循环缓冲区.那么它是一个间隙缓冲区,还是可扩展数组的其他变体,还是仅仅依赖于实现？
答案的更新和摘要:
似乎普遍的共识是,双端队列是一种数据结构,这样:
如果我们将第一个条件设为"非摊销的恒定时间",似乎没有人知道如何得到第一和第四条件的组合.链表实现1)但不是4),而典型的循环缓冲实现4)但不实现1).我想我的实现可以满足以下两个要求.评论？
我们从其他人建议的实现开始:我们分配一个数组并从中间开始放置元素,在前面和后面留下空间.在这个实现中,我们跟踪中心在前后方向上有多少元素,调用那些值F和B.然后,让我们用一个两倍于原始大小的辅助数组来扩充这个数据结构.数组(所以现在我们浪费了大量的空间,但渐近的复杂性没有变化).我们还将从中间填充这个辅助数组,并给它类似的值F'和B'.策略是这样的:每次我们在给定方向上向主数组添加一个元素时,如果F> F'或B> B'(取决于方向),最多两个值从主数组复制到辅助数据数组直到F'赶上F(或B'跟B).因此,插入操作涉及将1个元素放入主数组并从主数据库复制到辅助数据2,但它仍然是O(1).当主阵列变满时,我们释放主阵列,使辅助阵列成为主阵列,并制作另一个大2倍的辅助阵列.这个新的辅助数组以F'= B'= 0开始,并且没有复制到它(因此如果堆分配是O(1)复杂度,则调整大小op为O(1)).由于添加到主要和主要的每个元素的辅助副本2个元素最多开始半满,因此当主要用完空间时,辅助节点不可能赶上主要元素.删除同样只需要从主要删除1个元素,从辅助删除0或1.因此,假设堆分配为O(1),则此实现满足条件1).我们使数组为T*,并new在插入时使用以满足条件2)和3).最后,4)被实现,因为我们使用数组结构并且可以轻松实现O(1)访问.
由于几天前的这个问题,有一些事情一直困扰着我对于野外std::deque::push_back/push_front实际std::deque实施的复杂性要求.
上一个问题的结果是这些操作需要具有O(1)最差的案例复杂性.我确认这确实是这样的c++11:
从23.3.3.4 deque修饰符,参考insert,push/emplace前/后
复杂性:复杂性是插入元素数量的线性加上到双端队列开始和结束距离的较小者.在双端队列的开头或末尾插入单个元素总是需要恒定的时间并导致对T的构造函数的单个调用.
这与O(1)索引,通过operator[]等的复杂性要求相结合.
问题是实现并不严格满足这些要求.
在这两个方面msvc与gcc所述std::deque的实施是一个阻塞数据结构,由指针的动态阵列的至(固定大小)的块,其中每个块中存储有数量的数据元素.
在最坏的情况下,push_back/front etc可能需要一个额外的块将被分配(这是精-固定大小的分配是O(1)),但它也可以要求块指针的动态阵列被调整大小-这不是很好的,因为这是O(m)其中m是块数,在一天结束时O(n).
显然,这仍然是分摊的O(1)复杂性,因为通常m << n它在实践中会非常快.但似乎存在一致性问题？
作为进一步的点,我看不出你如何能设计一个数据结构,严格同时满足O(1)两个复杂性push_back/front etc和operator[].您可以拥有块指针的链接列表,但这并不能提供所需的operator[]行为.真的可以吗？
无论是在容器的前面,中间还是后面,都声称std :: list上的插入是恒定时间.
另一方面,为新插入项目获取内存由标准分配器处理,该分配器使用operator new.AFAIK operator new不保证有恒定的时间.
当operator new查找堆中的可用空间时,必须确保它不会覆盖先前分配的内存,因此它必须跟踪已在堆上分配的内容.我得出结论,插入必须至少与列表中已有的元素数量成线性关系.
这个推理出了什么问题？
我的问题是: