在 C++ 的标准库中，std::deque(双端队列)是一种动态数组的容器，它允许在两端进行高效的插入和删除操作。std::deque 的底层实现使用了一种被称为“分块连续内存”的数据结构。

　　std::deque 的底层内存结构通常由多个连续的固定大小的块(chunk)组成，每个块都是一个固定大小的数组。这些块通过一个指向块的指针进行连接，形成一个链表结构。当需要在 std::deque 的前端或后端插入或删除元素时，会根据情况选择在链表的前端或后端进行操作，而不需要移动其他元素。

　　具体来说，std::deque 的底层实现可以分为两个层次：

　　外层层次：外层层次是一个指向块的指针的数组，每个指针指向一个块。这个数组本身是动态增长的，可以根据需要分配更多的指针。这个数组的大小通常比实际元素数量大得多，因为每个块都有一个固定的大小，可以容纳多个元素。

　　内层层次：内层层次是每个块内部的固定大小的数组，用于存储元素。

　　当需要插入或删除元素时，std::deque 会根据位置的相对位置(前端或后端)选择在适当的块上进行操作，而不需要移动整个容器中的元素。这使得在 std::deque 的前端或后端执行插入和删除操作的时间复杂度为 O(1)，而在中间位置进行操作的时间复杂度则为 O(N)，其中 N 是容器中的元素数量。

　　总之，std::deque 使用了一种分块连续内存的数据结构，使得在两端进行插入和删除操作的性能非常高效。这使得 std::deque 成为一个适合频繁插入和删除元素的容器。

上一篇

c++setprecision用法

下一篇

c++stllist添加元素方法