通俗地理解c 如何最简单 的deque容器? (通俗地理解CV的图像几何变换?)
本文目录导航：
如何最简单、通俗地理解c++的deque容器?
deque，即双端队列，是一种特殊的容器，采用多段地址连续的存储空间实现，便于高效地在两端插入和删除元素。
deque的迭代器为random access类型，其内部实现包含四部分：cur、ptr、base、node。
迭代器进行增减操作时，会自动跳转到下一个或上一个node，操作效率高。
内部数据结构封装在_Deque_impl_data中，它采用map形式存储数据，并且通过继承的方式避免引入内存消耗。
_Deque_base类中有一个_Deque_impl成员，用于管理node和map的内存分配与释放。
其中，_M_allocate_node和_M_deallocate_node用于分配和释放单个node的内存，_M_create_nodes和_M_destroy_nodes用于申请或释放多个node的内存，而_M_allocate_map和_M_deallocate_map用于管理map的内存分配。
std::deque类主要关注几个关键成员函数：push_back/front、pop_back/front、insert。
push_back和push_front分别用于在末尾或开头插入元素，操作时会考虑预留空间情况，如需扩展内存，则调用相应的函数实现。
pop_back和pop_front则相对简单，主要负责释放元素占用的node内存，而不涉及map的收缩。
insert函数支持在任意位置插入元素，处理逻辑较为复杂，包括插入单个元素、多个相同值、区间元素等不同情况。
对于插入单个元素或多个相同值，函数会移动元素腾出空间，然后插入新元素；对于插入迭代器指向的区间元素，需要区分迭代器类型，调用相应的处理函数。
总体而言，deque通过巧妙的数据结构设计和高效的内存管理策略，实现了对元素的高效操作。
C++ STL deque 容器底层实现原理（深度剖析）
了解C++ STL中的deque容器底层实现，关键在于其独特的存储结构和迭代器设计。
deque容器之所以能在序列的头部和尾部高效地插入或删除元素，得益于其分段连续存储方式。
与连续线性存储的vector不同，deque采用一组等长的连续空间，各段间不连续，散布在内存的不同区域。
为管理这些空间，deque使用一个数组(map)存储每个连续空间的首地址，实际上存储的是指针。
通过map数组，deque能实现整体连续的效果，当需要在头部或尾部添加存储空间时，只需申请新连续空间并在map中添加指针，空间即串接至容器两端。
若map空间满，简单地申请更大空间，复制原有数据，释放旧空间即可。
deque容器迭代器的复杂性则源于其底层的分段存储。
迭代器内部包含四个指针，分别用于定位当前元素、指向下一个元素、上一个元素以及当前连续空间的边界。
借助这四个指针，迭代器支持随机访问运算符，实现对分段连续空间中元素的遍历。
实现deque容器，除了map数组和迭代器结构，还需维护start和finish迭代器。
start迭代器指向map数组中第一个连续空间的首地址，finish迭代器指向最后一个连续空间的末尾后一位置。
基于这些迭代器和重载的运算符，deque容器能够提供包括成员函数在内的大部分操作。
综上所述，deque容器的底层实现通过分段连续存储结构和迭代器设计，实现了高效头部和尾部元素操作的特性。
理解其内部机制，对于优化代码性能和提升数据结构应用能力至关重要。
STL容器—deque使用技巧
std::deque是一种双端队列，提供快速在两端插入和删除元素的能力。
与std::vector不同，deque的元素非连续存储，通过一系列分配固定大小的数组实现，同时进行额外的管理。
这意味着访问deque的索引需要两次指针解引用，而vector则只需要一次。
deque的存储会自动根据需要调整大小，扩展比vector便宜，因为它无需复制现有元素到新位置。
然而，deque的内存成本相对较高，即使只存储一个元素，也需要分配整个内部数组（如64位libstdc++中8倍的对象大小；在64位libc++中，可能更大，至少为4096字节）。
在时间复杂度方面，deque在尾部和头部插入和删除的复杂度为O(1)，实际上比vector稍慢。
在手动内存清理方面，deque与vector类似，可以使用swap()接口释放内存。
在C++11之后，deque添加了shrink_to_fit()接口，因此也可以手动释放内存。
在选择deque还是vector时，vector通常应作为默认序列类型。
deque在序列大部分插入和删除发生在两端时是最佳选择。
因此，存储大量数据时，我认为使用deque的优先级高于vector，对于少量数据则应尽量使用vector。
有趣的是，标准库中的栈（std::stack）实现默认使用deque，尽管栈只涉及单端数据的插入和删除。
phper