StudyingFather @ 2022-09-23 10:55:56
先简单叙述下问题背景：
STL 的 deque 的底层实现是用若干固定大小的块拼接而成，各块可以视为一个普通数组。在队列两端插入删除元素只需要移动头尾指针即可，如果头尾块已满则新创建一个块。
现在的问题是，如何在做到两端插入
为了实现 begin 指针和尾块的的 end 指针。利用首块的 begin 指针和每个块的大小，可以很快算出要访问第几个块，随后定位到该块内的元素。
但是，在这个实现下，deque 的前端插入就会出现问题。如果前端插入导致新块创建的话，原本存储各块位置的指针数组就要执行一个前端插入的操作，而这一操作显然是做不到
所以 STL 的 deque 究竟是怎么实现的呢？
by 灵华 @ 2022-09-23 10:57:11
不管如何，先刷qp
by 灵华 @ 2022-09-23 10:58:06
两个vector够不够用
by installb @ 2022-09-23 11:00:41
估计是均摊的 O(1)
by w23c3c3 @ 2022-09-23 11:05:09
两个vector够不够用。
by FZzzz @ 2022-09-23 11:06:49
直接拿两个 vector 是不是就可以做到了，但是这样不太支持弹出元素时即时释放空间？
用这题的 trick 大概可以做到空间随时与队内元素数量成线性，但是这样时间又变成均摊的了。
不是很懂，但是不能翻源码吗。
by w23c3c3 @ 2022-09-23 11:13:05
弹出确实不释放空间吧。
by NightStriker @ 2022-09-23 11:19:31
应该是2个 vector 罢。
by 宝硕 @ 2022-09-23 11:30:43
gcc/libstdc++-v3/include/bits/stl_deque.h#L1520-L1564
可以看看相关源码？
by Hisaishi_Kanade @ 2022-09-23 12:31:31
据说 deque 是一个大 map 套一堆 vector？
by _•́へ•́╬_ @ 2022-09-23 12:32:20
deque能吊打vector？