Pho*_*reo 3 c++ algorithm time-complexity deque c++11
背景
std::deque使用子数组来存储其元素.它有一个额外的簿记数据结构,以跟踪其子阵列.这样,与之相比std::vector,std::deque可以从后面更快地增长(O(1)与摊销的O(1)相比),并且在前面更快(O(1)与O(n)相比).这是因为std::deque可以在任一端添加子数组,只需要修改其簿记数据结构.
题
我不明白的是,为什么子阵列有自己的尺寸固定为解释在这里:
典型的实现使用一系列单独分配的固定大小的数组
没有固定大小的子阵列有很多优点.例如,由于子阵列的大小是固定的,因此中间的任何插入都必须是O(n)复杂度,其中n是到最近端的元素的数量.然而,如果子阵列可以自由生长,则在中间插入将是O(k),其中k是子阵列中元素的数量,其快得多,特别是如果std::deque具有许多子阵列.从中间删除也是一样的.
是因为std::deque想要保持其子阵列平衡吗？如果子阵列太大/太小,则可以通过启用子阵列进行拆分或合并来轻松减轻这种情况.复杂性将只是O(k),其中k是最大子阵列的大小.(或者最小的子阵列和它的较小邻居的组合大小)
是因为固定大小的子阵列使得随机迭代更快吗？例如,如果你想要第n个元素,你必须通过簿记数据结构并添加所有先前子阵列的大小,使得复杂度为O(k),其中k是簿记数据结构的大小.但这不是一个大问题,因为std::deque广告宣传是一个双向链表,无论如何都有更好的缓存.
编辑: std::deque只是链表实现和数组实现之间的中间人.我想我的问题已经失去了它的原始含义,只是暗示它应该表现得更像链接列表而不是矢量
我不明白的是为什么子阵列的大小固定
因为这允许标准所要求的恒定复杂性随机访问,如评论中所指出的那样.
但这不是一个大问题
我不同意,大概是标准委员会也是如此.
因为
std::deque被宣传为双重链接列表......
这不是广告.