企业官网建设流程全解析

大丰做网站哪家好,无锡企业推广网站,长春南京小学网站建设,wordpress 相册形式解析 std::deque 的‘地图-缓冲区’内存结构#xff1a;为什么它是实现高性能栈#xff08;Stack#xff09;的首选底座#xff1f;在现代C编程中#xff0c;选择正确的数据结构和底层容器对于构建高性能、高效率的应用程序至关重要。当我们谈论栈#xff08;Stack#…解析std::deque的‘地图-缓冲区’内存结构为什么它是实现高性能栈Stack的首选底座在现代C编程中选择正确的数据结构和底层容器对于构建高性能、高效率的应用程序至关重要。当我们谈论栈Stack这种抽象数据类型时其核心操作是LIFOLast In, First Out原则push入栈、pop出栈和top查看栈顶元素。这些操作的性能尤其是时间复杂度直接决定了栈在实际应用中的表现。虽然std::vector和std::list都可以作为std::stack的底层容器但通常情况下std::deque双端队列被认为是实现高性能栈的首选底座。这并非偶然而是源于其独特且精巧的“地图-缓冲区”Map-Buffer内存管理架构。本讲座将深入剖析std::deque的内存布局、其工作原理并详细阐述为什么这种设计使其成为高性能栈的理想选择。1. 栈Stack的本质与性能需求栈是一种简单而强大的数据结构广泛应用于函数调用、表达式求值、回溯算法等场景。其核心特性是LIFO (Last In, First Out)最后进入的元素最先离开。主要操作:push(element): 将元素添加到栈顶。pop(): 移除栈顶元素。top(): 获取栈顶元素的值不移除。empty(): 检查栈是否为空。size(): 获取栈中元素的数量。对于高性能栈而言我们期望这些核心操作都能在常数时间复杂度 O(1)内完成或者至少是均摊常数时间复杂度 O(1)。此外内存效率减少碎片、优化缓存命中率也是一个重要考量。2.std::deque的地图-缓冲区架构核心机制解析std::deque全称“double-ended queue”即双端队列顾名思义它支持在两端头部和尾部进行高效的插入和删除操作。与std::vector不同std::deque不保证所有元素在内存中是连续存储的与std::list也不同std::deque也不是由独立节点通过指针链接而成。它的独特之处在于其“地图-缓冲区”内存管理模型这种模型是介于两者之间的一种混合策略。2.1 整体概述逻辑连续物理分段std::deque的核心思想是将逻辑上连续的元素序列在物理内存上分割成若干个固定大小的缓冲区buffers这些缓冲区本身是连续的内存块。然后这些缓冲区的地址通过一个名为地图map的结构进行管理。地图本身是一个指针数组每个指针指向一个缓冲区。逻辑上的 std::deque 元素序列 ┌───────┬───────┬───────┬───────┬───────┬───────┬───────┐ │ Elem0 │ Elem1 │ Elem2 │ Elem3 │ Elem4 │ Elem5 │ Elem6 │ ... └───────┴───────┴───────┴───────┴───────┴───────┴───────┘ || / 物理内存布局 (通过地图和缓冲区实现) **Map (地图)**: 一个指针数组存储指向缓冲区的指针 ┌───────┬───────┬───────┬───────┬───────┐ │ Ptr0 │ Ptr1 │ Ptr2 │ Ptr3 │ Ptr4 │ ... └─┬─────┴─┬─────┴─┬─────┴─┬─────┴─┬─────┘ │ │ │ │ │ V V V V V **Buffers (缓冲区)**: 若干个固定大小的连续内存块 ┌───────┬───────┐ ┌───────┬───────┐ ┌───────┬───────┐ │ Elem0 │ Elem1 │ │ Elem2 │ Elem3 │ │ Elem4 │ Elem5 │ └───────┴───────┘ └───────┴───────┘ └───────┴───────┘ (Buffer 0) (Buffer 1) (Buffer 2)(注意以上为概念图示实际缓冲区大小通常远大于2个元素。)2.2 地图Map缓冲区的索引表std::deque的“地图”是一个动态增长的指针数组它的每一个元素都指向一个数据缓冲区。当地图需要扩展时它会像std::vector一样进行一次重新分配将所有缓冲区指针复制到新的、更大的地图中然后释放旧的地图内存。这个操作的开销是O(M)其中M是地图中缓冲区的数量。地图的特点:存储的是指针: 每个条目是一个T*或void*类型的指针指向一个已分配的缓冲区。动态调整容量: 随着deque中元素的增多可能需要更多的缓冲区从而导致地图本身也需要扩容。逻辑偏移:deque通常不会从地图的第一个索引开始存储缓冲区指针而是会预留一些空间以便在头部进行高效的插入。这个起始位置由一个内部的map_offset或类似变量维护。概念代码示例地图部分:// 假设这是 std::deque 内部的简化结构 template typename T class DequeInternal { private: T** map_; // 指向缓冲区指针数组的指针 (地图) size_t map_size_; // 地图当前可容纳的缓冲区指针数量 size_t map_offset_; // 当前第一个缓冲区在 map_ 中的索引 (用于高效 push_front) // ... 其他成员如元素计数当前首尾元素在缓冲区中的偏移等 };2.3 缓冲区Buffers数据的实际载体每个缓冲区都是一个固定大小的连续内存块用于存储std::deque的元素。这个固定大小通常是系统页面大小的整数倍例如4KB以优化内存分配和缓存性能。缓冲区的大小是一个编译时常量或者在运行时根据元素类型和系统特性确定。缓冲区的特点:固定大小: 所有缓冲区的大小都相同。这个大小是经过精心选择的通常足够大以减少缓冲区数量但又足够小以避免过度分配和提高缓存局部性。例如对于int类型一个4KB的缓冲区可以存储约1024个int。连续存储: 在单个缓冲区内部元素是连续存储的这使得对单个缓冲区内的元素访问具有良好的缓存局部性。按需分配/释放: 只有当现有缓冲区无法容纳新元素时才会分配新的缓冲区。当缓冲区完全变空时它们会被释放。概念代码示例缓冲区部分:// 假设缓冲区大小是一个常量 static const size_t BUFFER_SIZE 4096 / sizeof(T); // 例如4KB的缓冲区 // 缓冲区分配函数 T* allocate_buffer() { // 实际实现会使用 operator new T[BUFFER_SIZE] 或 std::allocator return new T[BUFFER_SIZE]; } // 缓冲区释放函数 void deallocate_buffer(T* buffer) { delete[] buffer; }2.4 元素寻址逻辑到物理的转换std::deque的复杂性在于它需要将逻辑上的索引例如第k个元素转换为物理内存上的地址。这个转换过程涉及到两次解引用根据元素的逻辑索引计算出它位于哪个缓冲区通过floor(k / BUFFER_SIZE)。获取该缓冲区的指针从地图中然后计算元素在该缓冲区内的偏移通过k % BUFFER_SIZE。寻址逻辑示意:// 假设 deque 内部维护了 // T** map_ // 地图指针 // size_t map_offset_ // 第一个有效缓冲区在 map_ 中的索引 // size_t front_idx_ // 第一个元素在 map_[map_offset_] 中的索引 // 获取第 k 个元素 (0-indexed) 的地址 T get_element_at(size_t k) { // 1. 计算元素所在的逻辑缓冲区索引 (相对于 deque 的第一个缓冲区) // 由于 deque 可能从一个缓冲区的中间开始我们需要考虑 front_idx_ // 这里简化处理假设 front_idx_ 是 0所有元素都从缓冲区头部开始填充 // 实际计算更复杂需要考虑 front_idx_ 和 back_idx_ size_t buffer_index k / BUFFER_SIZE; size_t element_offset_in_buffer k % BUFFER_SIZE; // 2. 获取实际的地图索引 size_t actual_map_index map_offset_ buffer_index; // 3. 访问元素 return map_[actual_map_index][element_offset_in_buffer]; }这种两级间接寻址虽然比std::vector直接的base_ptr[k]慢一点但仍然是O(1)操作。2.5 动态增长与收缩地图和缓冲区的协同工作std::deque的精髓在于其两端高效的插入和删除。2.5.1push_back(尾部插入)当向deque的尾部添加元素时当前缓冲区有空间: 如果当前最后一个缓冲区back_buffer仍有空间新元素会直接添加到该缓冲区的下一个可用位置。这是O(1)操作。当前缓冲区已满: 如果back_buffer已满deque会检查地图是否有空闲的指针位置来指向新的缓冲区。如果地图有空闲位置分配一个新的缓冲区将其指针存储在地图的下一个位置然后将新元素放入这个新缓冲区的起始位置。这是O(1)操作。如果地图已满则需要重新分配地图reallocate_map。这涉及到分配一个更大的新地图将旧地图中的所有缓冲区指针复制过去然后释放旧地图。这个操作是O(M)M为缓冲区数量但由于地图扩容是按指数级进行的因此均摊下来仍是O(1)。push_back概念逻辑:void push_back(const T value) { // 1. 检查当前尾部缓冲区是否已满 if (back_idx_ BUFFER_SIZE) { // back_idx_ 指向下一个可用位置 // 缓冲区已满需要新缓冲区 size_t current_map_idx (num_elements_ 0) ? map_offset_ : map_offset_ (num_elements_ - 1 front_idx_) / BUFFER_SIZE; if (current_map_idx 1 map_size_) { // 地图也满了需要重新分配地图 reallocate_map(map_size_ * 2); // 假设地图也双倍扩容 } // 分配新缓冲区并更新 back_buffer 指针 map_[current_map_idx 1] allocate_buffer(); back_idx_ 0; // 新缓冲区的起始位置 } // 2. 在当前尾部缓冲区中添加元素 map_[map_offset_ (num_elements_ front_idx_) / BUFFER_SIZE][back_idx_] value; back_idx_; num_elements_; }2.5.2pop_back(尾部删除)当从deque的尾部删除元素时当前缓冲区有多个元素: 如果back_buffer中仍有元素直接销毁最后一个元素并更新back_idx。这是O(1)操作。当前缓冲区只剩一个元素: 销毁最后一个元素后该缓冲区变空。deque会释放这个空缓冲区。更新内部指针使前一个缓冲区成为新的back_buffer。这是O(1)操作。pop_back不会导致地图的重新分配因为仅仅是释放了一个缓冲区地图中的指针仍可保留或者在极端情况下如果整个deque变空地图可能会收缩。pop_back概念逻辑:void pop_back() { if (empty()) { throw std::out_of_range(deque is empty); } // 1. 销毁最后一个元素 // 假设 back_idx_ 总是指向下一个可用位置所以实际最后一个元素在 back_idx_ - 1 size_t current_map_idx map_offset_ (num_elements_ - 1 front_idx_) / BUFFER_SIZE; --back_idx_; // 实际会调用元素的析构函数 // map_[current_map_idx][back_idx_].~T(); // 伪代码实际由容器管理 num_elements_--; // 2. 检查缓冲区是否变空 if (back_idx_ 0 num_elements_ 0) { // 如果当前缓冲区变空且deque不为空 // 释放当前缓冲区 (map_[current_map_idx]) deallocate_buffer(map_[current_map_idx]); map_[current_map_idx] nullptr; // 清空指针 // 更新 back_idx_ 到新的最后一个缓冲区的末尾 // 找到新的最后一个缓冲区并设置 back_idx_ 为 BUFFER_SIZE (如果其满) // 这个逻辑会有点复杂取决于 front_idx_ 和 num_elements_ // 简单来说就是将 back_idx_ 设置为 BUFFER_SIZE然后指向前一个缓冲区 back_idx_ BUFFER_SIZE; // 新的back_buffer将从其末尾开始 pop } else if (num_elements_ 0) { // 如果deque变空重置状态 front_idx_ 0; back_idx_ 0; // 也可以选择释放所有缓冲区和收缩地图但通常不是立即进行 } }2.5.3push_front和pop_front(头部插入/删除)std::deque支持在头部进行类似的高效操作。它通过在地图的map_offset之前预留空间或者在地图的map_offset指向的缓冲区的开头预留空间来实现。push_front: 如果当前第一个缓冲区有空间直接插入。如果无空间分配一个新缓冲区将其指针放在地图中map_offset-1的位置然后将map_offset递减。如果map_offset到达地图边界需要重新分配地图。这些操作同样是均摊O(1)。pop_front: 如果当前第一个缓冲区有多个元素直接删除。如果只剩一个元素删除后缓冲区变空释放该缓冲区然后map_offset递增。这些操作是O(1)。正是这种双向扩展的能力以及对地图和缓冲区的巧妙管理使得std::deque在两端操作上都能达到高效的性能。3.std::deque作为高性能栈底座的优势现在我们回到核心问题为什么std::deque是实现高性能栈的首选底座答案在于其地图-缓冲区架构如何优化了栈的核心操作 (push_back,pop_back,top)。3.1push_back(入栈) 的均摊 O(1) 性能栈的push操作对应于std::deque的push_back。现有缓冲区有空间: 最常见的情况。新元素直接放置在当前尾部缓冲区的下一个可用位置。这是一个简单的内存写入操作时间复杂度为O(1)。当前缓冲区已满但地图有空间: 分配一个新的缓冲区并将其指针添加到地图中。这个操作涉及到一次内存分配通常是系统调用但相对较快以及一次指针赋值。这也是O(1)操作。地图已满: 这种情况下需要重新分配整个地图。虽然地图的重新分配是一个O(M)操作M是缓冲区数量但由于地图的扩容策略通常是指数级增长例如翻倍这种开销会被分摊到多次push_back操作上从而使得均摊时间复杂度为O(1)。这与std::vector的均摊O(1)类似但deque重新分配的是一个小得多的指针数组地图而不是整个数据数组。表格比较push_back性能:容器类型push_back均摊时间复杂度最坏情况时间复杂度内存重新分配粒度std::vectorO(1)O(N)整个数据数组可能导致大量元素复制std::listO(1)O(1)单个节点std::dequeO(1)O(M) (M为缓冲区数)新的缓冲区或地图地图重新分配开销远小于vector可以看到std::deque在均摊意义上与std::vector和std::list持平但在最坏情况下其重新分配的开销远小于std::vector因为重新分配的是指针数组地图而不是元素本身。3.2pop_back(出栈) 的 O(1) 性能栈的pop操作对应于std::deque的pop_back。现有缓冲区有多个元素: 简单地将栈顶指针或索引向前移动一个位置销毁对应的元素。这是O(1)操作。当前缓冲区只剩一个元素: 销毁该元素后该缓冲区变为空。deque会释放这个缓冲区并更新其内部指针以指向前一个缓冲区。这个操作涉及到一次内存释放通常是系统调用也是O(1)操作。pop_back操作不会导致地图的重新分配。因此它的时间复杂度是严格的O(1)。3.3top(查看栈顶) 的 O(1) 性能栈的top操作对应于std::deque的back()方法。由于std::deque维护着指向最后一个有效缓冲区及其内部元素位置的指针/索引访问栈顶元素只需要通过两次指针解引用即可。这是一个直接的内存访问操作时间复杂度为O(1)。3.4 内存效率与缓存局部性避免大规模内存移动:std::deque在增长时不会像std::vector那样需要将所有元素复制到新的、更大的连续内存块中。它只需要分配新的小块缓冲区或者在地图满时重新分配一个相对较小的指针数组地图本身。这大大减少了内存移动的开销尤其是在存储大型对象时。减少内存碎片:std::deque分配的是固定大小的缓冲区。如果这些缓冲区大小是系统内存页的倍数可以提高内存分配器的效率并减少外部碎片。良好的缓存局部性局部: 尽管std::deque的元素在逻辑上连续但在物理上是分散在不同的缓冲区中。然而在单个缓冲区内部元素是连续存储的。这意味着当访问相邻元素时CPU缓存仍能发挥作用因为它们很可能位于同一个缓存行中。对于栈操作我们通常只关心栈顶附近的元素这些元素总是位于同一个缓冲区或相邻的缓冲区中因此缓存命中率仍然较高。相比std::list的优势:std::list的每个元素都是一个独立的节点通常包含数据和两个指针前向和后向。这导致了两个问题高内存开销: 每个元素额外的指针存储带来了显著的内存开销。差的缓存局部性: 独立节点可能分散在内存各处导致遍历时频繁的缓存缺失极大地降低性能。std::deque通过使用缓冲区显著降低了这种开销并改善了缓存局部性。3.5 迭代器和引用稳定性迭代器稳定性:std::deque的迭代器在push_front或push_back操作后通常不会失效除非地图本身需要重新分配。这比std::vector在容量改变时使所有迭代器失效要好。元素引用/指针稳定性:std::deque中元素的引用和指针在push_front或push_back操作后可能会失效。具体来说如果操作导致了新的缓冲区分配或者地图重新分配那么受影响的元素尤其是新分配缓冲区中的元素的地址可能会改变。然而对于栈操作push_back/pop_back通常只影响栈顶元素而不会影响栈中其他元素的地址。3.6std::deque作为std::stack默认底层容器C标准库中的std::stack是一个容器适配器它将底层容器的接口适配为栈的LIFO语义。std::stack的默认底层容器就是std::dequeT。这并非巧合而是经过深思熟虑的设计选择正是看中了std::deque在两端操作上的高性能和内存效率的平衡。#include iostream #include stack #include vector #include list #include deque #include chrono // For performance measurement // 简单封装用于测量不同底层容器的栈性能 templatetypename T, typename Container void benchmark_stack(const std::string name, size_t num_elements) { std::cout Benchmarking std::stack with name for num_elements elements. std::endl; // --- Push operations --- auto start_push std::chrono::high_resolution_clock::now(); std::stackT, Container s; for (size_t i 0; i num_elements; i) { s.push(i); } auto end_push std::chrono::high_resolution_clock::now(); std::chrono::durationdouble, std::milli push_time end_push - start_push; std::cout Push time: push_time.count() ms std::endl; // --- Top operations --- auto start_top std::chrono::high_resolution_clock::now(); for (size_t i 0; i num_elements; i) { // 实际应用中会使用 top() 的值这里只是为了模拟访问 volatile T val s.top(); } auto end_top std::chrono::high_resolution_clock::now(); std::chrono::durationdouble, std::milli top_time end_top - start_top; std::cout Top time: top_time.count() ms std::endl; // --- Pop operations --- auto start_pop std::chrono::high_resolution_clock::now(); while (!s.empty()) { s.pop(); } auto end_pop std::chrono::high_resolution_clock::now(); std::chrono::durationdouble, std::milli pop_time end_pop - start_pop; std::cout Pop time: pop_time.count() ms std::endl; std::cout -------------------------------------- std::endl; } // 实际运行可能需要更多元素才能看到明显差异 // int main() { // size_t num_elements 1000000; // 100万元素 // benchmark_stackint, std::dequeint(std::deque, num_elements); // benchmark_stackint, std::vectorint(std::vector, num_elements); // benchmark_stackint, std::listint(std::list, num_elements); // // 尝试使用自定义类型如果自定义类型构造/复制开销大差异会更明显 // struct LargeObject { // char data[1024]; // 1KB // // 构造函数、赋值运算符等 // LargeObject(int val 0) { data[0] (char)val; } // }; // num_elements 100000; // 10万大对象 // benchmark_stackLargeObject, std::dequeLargeObject(std::deque (LargeObject), num_elements); // benchmark_stackLargeObject, std::vectorLargeObject(std::vector (LargeObject), num_elements); // benchmark_stackLargeObject, std::listLargeObject(std::list (LargeObject), num_elements); // return 0; // }(上述代码仅为示例实际运行可能因编译器、操作系统、CPU缓存等因素而异。但通常情况下对于大量元素的push/pop操作std::deque和std::vector会表现出相似的O(1)均摊性能而std::list则可能因为缓存局部性差而表现稍逊尤其是在top操作时。当元素对象很大时std::vector的重新分配开销大量的对象复制会变得非常显著此时std::deque的优势会更加突出。)4.std::vector和std::list作为栈底座的对比与局限为了更全面地理解std::deque的优势我们有必要回顾一下其他常见容器作为栈底座的优缺点。4.1std::vectorT作为栈底座优点:极佳的缓存局部性: 元素在内存中是连续存储的顺序访问时CPU缓存命中率高。内存效率高: 除了存储元素本身没有额外的内存开销如指针。top()操作极快: 直接通过数组索引访问O(1)。缺点:push_back()的最坏情况性能: 当vector的容量不足时需要重新分配一块更大的内存并将所有现有元素复制到新内存区域。这是一个O(N)操作其中N是当前元素数量。虽然这是均摊O(1)但在某些实时性要求高的应用中这种突发的性能峰值是不可接受的。对于栈来说频繁的push操作可能导致多次这种昂贵的重新分配。push_front()/pop_front()效率极低: 需要移动所有元素O(N)操作不适合双端队列场景。但对于栈我们只使用push_back和pop_back。4.2std::listT作为栈底座优点:push_back()和pop_back()都是严格的O(1): 每次操作只涉及一个节点的分配/释放和几个指针的修改没有元素复制或大规模内存移动。内存使用灵活: 元素可以分散在内存的任何位置。缺点:极差的缓存局部性: 元素节点在内存中不连续导致CPU缓存命中率低性能下降。高内存开销: 每个元素需要额外的存储空间来保存前向和后向指针通常是2个sizeof(T*)。对于小类型如int这可能导致内存开销翻倍甚至更多。top()操作可能略慢: 虽然仍然是O(1)但由于需要解引用指针并且目标内存可能不在缓存中实际访问速度可能比vector或deque的缓冲区内访问慢。4.3 总结比较特性/容器std::vectorstd::liststd::deque内存连续性完全连续完全不连续节点缓冲区内连续缓冲区间不连续push_back()均摊O(1)最坏O(N)O(1)均摊O(1)最坏O(M) (M为缓冲区数)pop_back()O(1)O(1)O(1)top()O(1)O(1)O(1)缓存局部性极佳极差缓冲区内好缓冲区间可能差内存开销低高额外指针中地图和潜在部分填充缓冲区内存重新分配整个数组无单个节点地图或单个缓冲区作为栈底座常用但大对象时性能有隐患次优缓存差首选平衡性好std::deque通过其地图-缓冲区架构成功地在std::vector的内存局部性和std::list的灵活增长之间找到了一个最佳平衡点。它避免了std::vector可能出现的大规模内存移动和元素复制同时又比std::list提供了更好的缓存局部性和更低的内存开销。这使得它在大多数高性能栈应用场景中表现出色。5. 概念性代码示例构建一个简化的MyDeque和MyStack为了更好地理解std::deque的内部机制我们来构建一个高度简化的、教学性质的MyDeque。请注意这是一个概念性实现不包含所有边界检查、异常安全、内存分配器管理、迭代器实现等生产级std::deque所需的功能。#include iostream #include stdexcept #include vector // 仅用于 MyDeque 内部 Map 的简单实现实际 deque 不会依赖 vector // 假设缓冲区大小为 8 个元素方便演示 template typename T struct DequeBuffer { T data[8]; // 固定大小的缓冲区 // 实际的 std::deque 可能会使用动态分配的内存例如 new T[BUFFER_SIZE] // 并且会管理元素的构造和析构 }; template typename T class MyDeque { public: // 构造函数和析构函数 MyDeque() : map_(nullptr), map_capacity_(0), map_offset_(0), num_elements_(0), front_buffer_idx_in_map_(0), front_element_idx_in_buffer_(0), back_buffer_idx_in_map_(0), back_element_idx_in_buffer_(0) { // 初始分配一个小的地图例如能容纳 4 个缓冲区 reallocate_map(4); // 初始分配第一个缓冲区 map_[map_offset_] new DequeBufferT(); } ~MyDeque() { // 销毁所有元素 // 实际的 deque 会调用元素的析构函数 // 释放所有缓冲区 for (size_t i 0; i map_capacity_; i) { if (map_[i] ! nullptr) { delete map_[i]; map_[i] nullptr; } } // 释放地图 delete[] map_; } // 辅助函数获取缓冲区大小 static constexpr size_t get_buffer_size() { return sizeof(DequeBufferT) / sizeof(T); } // --- 核心操作 --- void push_back(const T value) { if (num_elements_ 0) { // 第一个元素特殊处理 map_[map_offset_]-data[front_element_idx_in_buffer_] value; back_element_idx_in_buffer_ front_element_idx_in_buffer_ 1; } else { // 检查当前尾部缓冲区是否已满 if (back_element_idx_in_buffer_ get_buffer_size()) { // 缓冲区已满需要新缓冲区 back_buffer_idx_in_map_; // 移动到下一个地图槽位 // 检查地图是否已满 if (back_buffer_idx_in_map_ map_capacity_) { reallocate_map(map_capacity_ * 2); // 地图扩容 } // 分配新缓冲区 map_[back_buffer_idx_in_map_] new DequeBufferT(); back_element_idx_in_buffer_ 0; // 新缓冲区的起始位置 } // 在当前尾部缓冲区中添加元素 map_[back_buffer_idx_in_map_]-data[back_element_idx_in_buffer_] value; back_element_idx_in_buffer_; } num_elements_; } void pop_back() { if (empty()) { throw std::out_of_range(MyDeque is empty); } // 销毁最后一个元素 (概念上) back_element_idx_in_buffer_--; // map_[back_buffer_idx_in_map_]-data[back_element_idx_in_buffer_].~T(); // 实际会调用析构函数 num_elements_--; // 检查缓冲区是否变空 (只考虑尾部缓冲区因为是栈) if (back_element_idx_in_buffer_ 0 num_elements_ 0) { // 当前缓冲区已空如果不是唯一的缓冲区则释放 if (back_buffer_idx_in_map_ ! front_buffer_idx_in_map_) { delete map_[back_buffer_idx_in_map_]; map_[back_buffer_idx_in_map_] nullptr; back_buffer_idx_in_map_--; back_element_idx_in_buffer_ get_buffer_size(); // 指向新尾部缓冲区的末尾 } else { // 最后一个缓冲区但仍有元素在其中这种情况不应该发生因为front_element_idx_in_buffer_不可能为0 // 除非 num_elements_ 也为0 // 实际的 deque 逻辑更复杂这里仅为简化 } } else if (num_elements_ 0) { // deque 变空重置状态 front_element_idx_in_buffer_ 0; back_element_idx_in_buffer_ 0; front_buffer_idx_in_map_ map_offset_; // 重置为初始地图偏移 back_buffer_idx_in_map_ map_offset_; // 也可以选择释放所有缓冲区和收缩地图但通常不是立即进行 } } T back() { if (empty()) { throw std::out_of_range(MyDeque is empty); } // 获取最后一个元素 return map_[back_buffer_idx_in_map_]-data[back_element_idx_in_buffer_ - 1]; } bool empty() const { return num_elements_ 0; } size_t size() const { return num_elements_; } private: DequeBufferT** map_; // 指针数组地图指向缓冲区 size_t map_capacity_; // 地图的容量能容纳多少个缓冲区指针 size_t map_offset_; // 第一个活跃缓冲区在地图中的索引 size_t num_elements_; // 当前元素总数 // 用于管理当前首尾缓冲区及其内部索引 size_t front_buffer_idx_in_map_; // 第一个元素所在的缓冲区在地图中的索引 size_t front_element_idx_in_buffer_; // 第一个元素在该缓冲区内的索引 size_t back_buffer_idx_in_map_; // 最后一个元素所在的缓冲区在地图中的索引 size_t back_element_idx_in_buffer_; // 最后一个元素在该缓冲区内下一个可用位置的索引 // 重新分配地图 void reallocate_map(size_t new_capacity) { if (new_capacity map_capacity_) return; DequeBufferT** new_map new DequeBufferT*[new_capacity]; for (size_t i 0; i new_capacity; i) { new_map[i] nullptr; // 初始化为nullptr } // 计算旧地图中有效缓冲区的位置 size_t old_num_buffers (num_elements_ 0) ? 0 : (back_buffer_idx_in_map_ - front_buffer_idx_in_map_ 1); // 新地图的起始偏移量 (通常放在中间以支持双向扩展) size_t new_map_offset (new_capacity - old_num_buffers) / 2; // 复制旧地图中的缓冲区指针到新地图 for (size_t i 0; i old_num_buffers; i) { new_map[new_map_offset i] map_[front_buffer_idx_in_map_ i]; map_[front_buffer_idx_in_map_ i] nullptr; // 清空旧地图指针防止 double free } // 释放旧地图 delete[] map_; map_ new_map; map_capacity_ new_capacity; // 更新地图索引 front_buffer_idx_in_map_ new_map_offset; back_buffer_idx_in_map_ new_map_offset old_num_buffers - ((num_elements_ 0) ? 1 : 0); map_offset_ new_map_offset; // 更新整体地图偏移 } }; // 使用 MyDeque 构建 MyStack 适配器 template typename T, typename Container MyDequeT class MyStack { private: Container c; public: void push(const T value) { c.push_back(value); } void pop() { c.pop_back(); } T top() { return c.back(); } bool empty() const { return c.empty(); } size_t size() const { return c.size(); } }; // int main() { // MyStackint s; // std::cout Is stack empty? s.empty() std::endl; // 1 (true) // s.push(10); // s.push(20); // s.push(30); // std::cout Stack size: s.size() std::endl; // 3 // std::cout Top element: s.top() std::endl; // 30 // s.pop(); // std::cout Stack size after pop: s.size() std::endl; // 2 // std::cout Top element after pop: s.top() std::endl; // 20 // // 触发缓冲区和地图扩容 // for (int i 0; i 20; i) { // 20 超过了 8*1 的缓冲区大小和 4 个缓冲区的地图容量 // s.push(i * 5); // } // std::cout Stack size after more pushes: s.size() std::endl; // std::cout Top element after more pushes: s.top() std::endl; // while (!s.empty()) { // std::cout Popping: s.top() std::endl; // s.pop(); // } // std::cout Is stack empty? s.empty() std::endl; // 1 (true) // return 0; // }上述MyDeque的简化实现展示了地图和缓冲区如何协同工作来管理数据。reallocate_map函数说明了当底层地图需要扩容时它会分配一个新的更大的地图并将旧地图中的缓冲区指针移动到新地图的中间位置以支持双向增长。push_back和pop_back则演示了元素如何在其各自的缓冲区内移动以及何时需要分配/释放新的缓冲区。6. 权衡与考量尽管std::deque是高性能栈的优秀选择但它并非没有权衡内存开销: 除了存储元素数据std::deque还需要额外的内存来存储地图指针数组以及管理每个缓冲区的开销。此外由于缓冲区是固定大小的如果deque的元素数量不能完美填充缓冲区可能会有部分缓冲区被浪费内部碎片。缓存性能: 尽管单个缓冲区内部具有良好的缓存局部性但当从一个缓冲区跳到另一个缓冲区时可能会发生缓存缺失这在某些极端访问模式下可能比std::vector稍慢。然而对于栈这种只在末端操作的场景这种影响通常不大。随机访问:std::deque支持O(1)的随机访问operator[]但由于需要两次解引用地图-缓冲区-元素其常数因子通常会略大于std::vector的直接索引访问。7.std::deque高性能栈的黄金标准综上所述std::deque凭借其独特的“地图-缓冲区”内存管理机制为实现高性能栈提供了一个近乎完美的基石。它巧妙地平衡了内存连续性和灵活性在以下几个关键方面表现出色高效的均摊O(1)push操作: 避免了std::vector在扩容时的大规模元素复制只重新分配较小的地图或单个缓冲区。严格的O(1)pop和top操作: 确保了栈核心操作的稳定高性能。良好的内存效率和缓存局部性: 优于std::list并且在处理大对象时比std::vector更具优势。迭代器稳定性: 提供了比std::vector更好的迭代器稳定性保证。这些特性共同使得std::deque成为C标准库中std::stack的默认底层容器也使其在各种需要高性能栈的场景中成为开发者首选的底层数据结构。选择std::deque作为栈的底座是在性能、内存效率和实现复杂性之间取得的一个优秀工程平衡。