1365人阅读
C-C++（18）
STL源码剖析（7）
在介绍STL的deque的容器之前，我们先来总结一下vector和list的优缺点。vector在内存中是分配一段连续的内存空间进行存储，其迭代器采用原生指针即可，因此其支持随机访问和存储，支持下标操作符，节省空间。但是其在分配的内存不够的情况下，需要对容器整体进行重新分配、拷贝和释放等操作，而且在vector中间插入或删除元素效率很低。
而list是以节点形式来存放数据，使用的是非连续的内存空间来存放数据，因此，在其内部插入和删除元素的时间复杂度都是O(1),但是其不支持随机访问和存取，不支持下标，而且比vector占用的内存要多。
综合上述的优缺点，我们貌似需要一个支持随机访问和存取，支持下标访问，而且插入和删除的效率高的容器。于是，STL的deque诞生了，下面就跟着我一起去看看deque的设计和源码实现吧！
vector是一个单向开口的容器，deque则是一个双向开口的容器，所谓双向开口就是再头尾两端均可以做元素的插入和删除操作。deque容器给我们的直观感觉大概是下面这样的(配图来自STL源码剖析)：
deque相比于vector最大的差异就在于支持常熟时间内对首尾两端进行插入和删除操作，而且deque没有容量的概念，其内部采用分段连续内存空间来存储元素，在插入元素的时候随时都可以重新增加一段新的空间并链接起来。
deque提供了Ramdon Access Iterator，同时也支持随机访问和存取，但是它也为此付出了昂贵的代价，其复杂度不能跟vector的原生指针迭代器相提并论。在下面的讲解中会一一为大家介绍STL是怎样”辛苦地”维持一个随机访问迭代器的。
deque的中控器
deque为了维持整体连续的假象，设计一个中控器，其用来记录deque内部每一段连续空间的地址。大体上可以理解为deque中的每一段连续空间分布在内存的不连续空间上，然后用一个所谓的map作为主控，记录每一段内存空间的入口，从而做到整体连续的假象。其布局大概如下(配图来自STL源码剖析)
看完图解，再来看看源码会很好理解的。
template &class T, class Alloc = alloc, size_t BufSiz = 0&
class deque {
typedef T value_
typedef value_type*
typedef const value_type* const_
typedef value_type&
typedef const value_type& const_
typedef size_t size_
typedef ptrdiff_t difference_
protected:
typedef pointer* map_
map_pointer map;
size_type map_
抛弃型别定义，我们可以看到map实际上就是一个指向指针的指针(T**)，map所指向的是一个指针，该指针指向型别为T的一块内存空间。理解到这里，大概就清楚了deque的实现原理，不过，这些都不是重点！重点是deque的各种运算符的实现。做好心理准备，咱们继续往下看！！！
deque的迭代器
deque提供的是一个随机访问迭代器，由于是分段连续空间，其必须记录当前元素所在段的信息，从而在该段连续空间的边缘进行前进或者后退的时候能知道跳跃到的上一个或下一个缓冲区。deque必须完完全全地掌握和控制这些信息，以达到正确地跳跃！
template &class T, class Ref, class Ptr, size_t BufSiz&
struct __deque_iterator {
typedef __deque_iterator&T, T&, T*, BufSiz&
typedef __deque_iterator&T, const T&, const T*, BufSiz& const_
typedef random_access_iterator_tag iterator_
typedef T value_
typedef size_t size_
typedef ptrdiff_t difference_
typedef T** map_
typedef __deque_
template &class T, class Ref, class Ptr, size_t BufSiz&
inline random_access_iterator_tag
iterator_category(const __deque_iterator&T, Ref, Ptr, BufSiz&&) {
return random_access_iterator_tag();
template &class T, class Ref, class Ptr, size_t BufSiz&
inline T* value_type(const __deque_iterator&T, Ref, Ptr, BufSiz&&) {
template &class T, class Ref, class Ptr, size_t BufSiz&
inline ptrdiff_t* distance_type(const __deque_iterator&T, Ref, Ptr, BufSiz&&) {
从源码中可以看出，deque的迭代器中有cur,first,last和node四个指针，前三个记录了迭代器与缓冲区的联系，最后一个记录了迭代器于中控器的关系。从下面这张图可以很好的看出其关系：
仅仅定义了迭代器结构还只是开始，迭代器是一个随机访问迭代器，所以其必须提供++，–，下标操作符等运算符。下面就来一一剖析吧！
buffer_size函数
static size_t buffer_size() {
return __deque_buf_size(BufSiz, sizeof(T));
inline size_t __deque_buf_size(size_t n, size_t sz)
return n != 0 ? n : (sz & 512 ? size_t(512 / sz) : size_t(1));
set_node函数
当迭代器处在当前缓冲区的边缘时，一旦前进或者后退，就要考虑超过当前缓冲区的情况，此时需要跳转到下一个缓冲区，这时候set_node就派上用场了。
void set_node(map_pointer new_node)
node = new_
first = *new_
last = first + difference_type(buffer_size());
各种运算子
以下源码都是deque迭代器重载的运算子，以满足随机访问迭代器的要求。
reference operator*() const { return * }
pointer operator-&() const { return &(operator*()); }
difference_type operator-(const self& x) const
return difference_type(buffer_size()) * (node - x.node - 1) +
(cur - first) + (x.last - x.cur);
self& operator++()
if (cur == last) {
set_node(node + 1);
return *this;
self operator++(int)
self tmp = *this;
self& operator--()
if (cur == first) {
set_node(node - 1);
return *this;
self operator--(int)
self tmp = *this;
self& operator+=(difference_type n)
difference_type offset = n + (cur - first);
if (offset &= 0 && offset & difference_type(buffer_size()))
difference_type node_offset =
offset & 0 ? offset / difference_type(buffer_size())
: -difference_type((-offset - 1) / buffer_size()) - 1;
set_node(node + node_offset);
cur = first + (offset - node_offset * difference_type(buffer_size()));
return *this;
self operator+(difference_type n) const
self tmp = *this;
return tmp +=
self& operator-=(difference_type n) { return *this += -n; }
self operator-(difference_type n) const {
self tmp = *this;
return tmp -=
reference operator[](difference_type n) const { return *(*this + n); }
bool operator==(const self& x) const { return cur == x. }
bool operator!=(const self& x) const { return !(*this == x); }
bool operator&(const self& x) const {
return (node == x.node) ? (cur & x.cur) : (node & x.node);
deque的数据结构
先前在deque的中控器中讲到，deque维护着一个map，用来记录每个缓冲区的位置。除了map外，deque的数据结构中还维护着start和finish两个迭代器，分别指向deque的首尾。此外，它还必须知道map的大小，一旦map所提供的节点不足，就需要配置一块更大的map。
接下来，我们来看看deque的数据结构源代码：
template &class T, class Alloc = alloc, size_t BufSiz = 0&
class deque {
typedef T value_
typedef value_type*
typedef size_t size_
typedef __deque_iterator&T, T&, T*, BufSiz&
protected:
typedef pointer* map_
protected:
map_pointer map;
size_type map_
typedef simple_alloc&value_type, Alloc& data_
typedef simple_alloc&pointer, Alloc& map_
pointer allocate_node() { return data_allocator::allocate(buffer_size()); }
void deallocate_node(pointer n)
data_allocator::deallocate(n, buffer_size());
在上述结构体下，可以很轻松地实现“连续”容器的各种机能函数，如下：
iterator begin() { return }
iterator end() { return }
const_iterator begin() const { return }
const_iterator end() const { return }
reference operator[](size_type n) { return start[difference_type(n)]; }
const_reference operator[](size_type n) const {
return start[difference_type(n)];
reference front() { return * }
reference back() {
iterator tmp =
const_reference front() const { return * }
const_reference back() const {
const_iterator tmp =
size_type size() const { return finish -; }
size_type max_size() const { return size_type(-1); }
bool empty() const { return finish == }
deque的构造函数
deque和vector、list一样，提供了多种构造函数。我们先来看看默认构造函数：
deque() : start(), finish(), map(0), map_size(0)
create_map_and_nodes(0);
static size_type initial_map_size() { return 8; }
template &class T, class Alloc, size_t BufSize&
void deque&T, Alloc, BufSize&::create_map_and_nodes(size_type num_elements)
size_type num_nodes = num_elements / buffer_size() + 1;
map_size = max(initial_map_size(), num_nodes + 2);
map = map_allocator::allocate(map_size);
map_pointer nstart = map + (map_size - num_nodes) / 2;
map_pointer nfinish = nstart + num_nodes - 1;
__STL_TRY {
for (cur = cur &= ++cur)
*cur = allocate_node();
start.set_node(nstart);
finish.set_node(nfinish);
start.cur = start.
finish.cur = finish.first + num_elements % buffer_size();
除了默认构造函数，deque还提供了一系列的构造函数：
deque(const deque& x)
: start(), finish(), map(0), map_size(0)
create_map_and_nodes(x.size());
uninitialized_copy(x.begin(), x.end(), start);
deque(size_type n, const value_type& value)
: start(), finish(), map(0), map_size(0)
fill_initialize(n, value);
template &class T, class Alloc, size_t BufSize&
void deque&T, Alloc, BufSize&::fill_initialize(size_type n,
const value_type& value)
create_map_and_nodes(n);
__STL_TRY {
for (cur = start. cur & finish. ++cur)
uninitialized_fill(*cur, *cur + buffer_size(), value);
uninitialized_fill(finish.first, finish.cur, value);
catch (...) {
for (map_pointer n = start. n & ++n)
destroy(*n, *n + buffer_size());
destroy_map_and_nodes();
template &class InputIterator&
deque(InputIterator first, InputIterator last)
: start(), finish(), map(0), map_size(0)
range_initialize(first, last, iterator_category(first));
template &class T, class Alloc, size_t BufSize&
template &class ForwardIterator&
void deque&T, Alloc, BufSize&::range_initialize(ForwardIterator first,
ForwardIterator last,
forward_iterator_tag) {
size_type n = 0;
distance(first, last, n);
create_map_and_nodes(n);
uninitialized_copy(first, last, start);
当然，deque还提供了很多种构造函数，基本上都调用上述函数来构造map和缓冲区，这里就不在赘述！
deque的析构函数
destroy(start, finish);
destroy_map_and_nodes();
template &class T, class Alloc, size_t BufSize&
void deque&T, Alloc, BufSize&::destroy_map_and_nodes()
for (map_pointer cur = start. cur &= finish. ++cur)
deallocate_node(*cur);
map_allocator::deallocate(map, map_size);
deque支持的操作函数
push_back完成在尾部插入一个元素，根绝上述的deque的结构特点，里面有很多情况需要考虑。
如果备用空间足够，就直接push进去
如果备用空间不足，就要考虑配置一个新的缓冲区
配置新缓冲区的时候，还需要考虑map空间是否足够
如果map空间足够，就直接配置一块新的缓冲区，链接到map中
如果map空间不足，就需要考虑重新配置一块map
可见，为了维持整体连续的假象，确确实实，deque的操作函数需要考虑各个方面。下面来看看源代码。
void push_back(const value_type& t)
if (finish.cur != finish.last - 1) {
construct(finish.cur, t);
push_back_aux(t);
template &class T, class Alloc, size_t BufSize&
void deque&T, Alloc, BufSize&::push_back_aux(const value_type& t)
value_type t_copy =
reserve_map_at_back();
*(finish.node + 1) = allocate_node();
__STL_TRY {
construct(finish.cur, t_copy);
finish.set_node(finish.node + 1);
finish.cur = finish.
__STL_UNWIND(deallocate_node(*(finish.node + 1)));
void reserve_map_at_back (size_type nodes_to_add = 1)
if (nodes_to_add + 1 & map_size - (finish.node - map))
reallocate_map(nodes_to_add, false);
template &class T, class Alloc, size_t BufSize&
void deque&T, Alloc, BufSize&::reallocate_map(size_type nodes_to_add,
bool add_at_front)
size_type old_num_nodes = finish.node - start.node + 1;
size_type new_num_nodes = old_num_nodes + nodes_to_
map_pointer new_
if (map_size & 2 * new_num_nodes) {
new_nstart = map + (map_size - new_num_nodes) / 2
+ (add_at_front ? nodes_to_add : 0);
if (new_nstart & start.node)
copy(start.node, finish.node + 1, new_nstart);
copy_backward(start.node, finish.node + 1, new_nstart + old_num_nodes);
size_type new_map_size = map_size + max(map_size, nodes_to_add) + 2;
map_pointer new_map = map_allocator::allocate(new_map_size);
new_nstart = new_map + (new_map_size - new_num_nodes) / 2
+ (add_at_front ? nodes_to_add : 0);
copy(start.node, finish.node + 1, new_nstart);
map_allocator::deallocate(map, map_size);
map = new_
map_size = new_map_
start.set_node(new_nstart);
finish.set_node(new_nstart + old_num_nodes - 1);
pop_back是将deque的尾部元素弹出，即拿掉该元素并释放空间。
void pop_back()
if (finish.cur != finish.first) {
destroy(finish.cur);
pop_back_aux();
template &class T, class Alloc, size_t BufSize&
void deque&T, Alloc, BufSize&:: pop_back_aux()
deallocate_node(finish.first);
finish.set_node(finish.node - 1);
finish.cur = finish.last - 1;
destroy(finish.cur);
push_front
此函数用来在deque的头部压入一个元素。
void push_front(const value_type& t)
if (start.cur != start.first) {
construct(start.cur - 1, t);
push_front_aux(t);
template &class T, class Alloc, size_t BufSize&
void deque&T, Alloc, BufSize&::push_front_aux(const value_type& t)
value_type t_copy =
reserve_map_at_front();
*(start.node - 1) = allocate_node();
__STL_TRY {
start.set_node(start.node - 1);
start.cur = start.last - 1;
construct(start.cur, t_copy);
catch (...) {
start.set_node(start.node + 1);
start.cur = start.
deallocate_node(*(start.node - 1));
此函数实现从头部弹出一个元素，同pop_back()。
void pop_front() {
if (start.cur != start.last - 1)
destroy(start.cur);
pop_front_aux();
template &class T, class Alloc, size_t BufSize&
void deque&T, Alloc, BufSize&::pop_front_aux()
destroy(start.cur);
deallocate_node(start.first);
start.set_node(start.node + 1);
start.cur = start.
擦除deque中的每一个元素
template &class T, class Alloc, size_t BufSize&
void deque&T, Alloc, BufSize&::clear()
for (map_pointer node = start.node + 1; node & finish. ++node) {
destroy(*node, *node + buffer_size());
data_allocator::deallocate(*node, buffer_size());
if (start.node != finish.node) {
destroy(start.cur, start.last);
destroy(finish.first, finish.cur);
data_allocator::deallocate(finish.first, buffer_size());
destroy(start.cur, finish.cur);
erase实现了擦除单个指定元素和擦出区间两个版本，源代码分析如下：
iterator erase(iterator pos)
iterator next =
difference_type index = pos -
if (index & (size() && 1))
copy_backward(start, pos, next);
pop_front();
copy(next, finish, pos);
pop_back();
return start +
擦除[first,last)区间的元素。此函数按下列步骤来擦除区间。
需要擦除整个空间，直接调用clear()
需要擦出中间指定区间
擦除中间指定区间，需要考虑一下两种情况
区间前面的元素少，就移动前面的元素
区间后面的元素少，就移动后面的元素
template &class T, class Alloc, size_t BufSize&
deque&T, Alloc, BufSize&::iterator
deque&T, Alloc, BufSize&::erase(iterator first, iterator last)
if (first == start && last == finish) {
difference_type n = last -
difference_type elems_before = first -
if (elems_before & (size() - n) / 2) {
copy_backward(start, first, last);
iterator new_start = start +
destroy(start, new_start);
for (map_pointer cur = start. cur & new_start. ++cur)
data_allocator::deallocate(*cur, buffer_size());
start = new_
copy(last, finish, first);
iterator new_finish = finish -
destroy(new_finish, finish);
for (map_pointer cur = new_finish.node + 1; cur &= finish. ++cur)
data_allocator::deallocate(*cur, buffer_size());
finish = new_
return start + elems_
在指定位置前插入元素，deque的源码中，为insert提供了多个版本，这里列举插入一个元素和n和元素的版本。
在指定位置插入一个元素
iterator insert(iterator position, const value_type& x)
if (position.cur == start.cur) {
push_front(x);
else if (position.cur == finish.cur) {
push_back(x);
iterator tmp =
return insert_aux(position, x);
template &class T, class Alloc, size_t BufSize&
typename deque&T, Alloc, BufSize&::iterator
deque&T, Alloc, BufSize&::insert_aux(iterator pos, const value_type& x)
difference_type index = pos -
value_type x_copy =
if (index & size() / 2) {
push_front(front());
iterator front1 =
iterator front2 = front1;
pos = start +
iterator pos1 =
copy(front2, pos1, front1);
push_back(back());
iterator back1 =
iterator back2 = back1;
pos = start +
copy_backward(pos, back2, back1);
在指定位置插入n个元素的情况
template &class T, class Alloc, size_t BufSize&
void deque&T, Alloc, BufSize&::insert(iterator pos,
size_type n, const value_type& x)
if (pos.cur == start.cur) {
iterator new_start = reserve_elements_at_front(n);
uninitialized_fill(new_start, start, x);
start = new_
else if (pos.cur == finish.cur) {
iterator new_finish = reserve_elements_at_back(n);
uninitialized_fill(finish, new_finish, x);
finish = new_
insert_aux(pos, n, x);
iterator reserve_elements_at_front(size_type n)
size_type vacancies = start.cur - start.
if (n & vacancies)
new_elements_at_front(n - vacancies);
return start - difference_type(n);
template &class T, class Alloc, size_t BufSize&
void deque&T, Alloc, BufSize&::new_elements_at_front(size_type new_elements)
size_type new_nodes = (new_elements + buffer_size() - 1) / buffer_size();
reserve_map_at_front(new_nodes);
__STL_TRY {
for (i = 1; i &= new_ ++i)
*(start.node - i) = allocate_node();
catch (...) {
for (size_type j = 1; j & ++j)
deallocate_node(*(start.node - j));
void reserve_map_at_front (size_type nodes_to_add = 1)
if (nodes_to_add & start.node - map)
reallocate_map(nodes_to_add, true);
template &class T, class Alloc, size_t BufSize&
void deque&T, Alloc, BufSize&::insert_aux(iterator pos,
size_type n, const value_type& x)
const difference_type elems_before = pos -
size_type length = size();
value_type x_copy =
if (elems_before & length / 2) {
iterator new_start = reserve_elements_at_front(n);
iterator old_start =
pos = start + elems_
__STL_TRY {
if (elems_before &= difference_type(n)) {
iterator start_n = start + difference_type(n);
uninitialized_copy(start, start_n, new_start);
start = new_
copy(start_n, pos, old_start);
fill(pos - difference_type(n), pos, x_copy);
__uninitialized_copy_fill(start, pos, new_start, start, x_copy);
start = new_
fill(old_start, pos, x_copy);
__STL_UNWIND(destroy_nodes_at_front(new_start));
iterator new_finish = reserve_elements_at_back(n);
iterator old_finish =
const difference_type elems_after = difference_type(length) - elems_
pos = finish - elems_
__STL_TRY {
if (elems_after & difference_type(n)) {
iterator finish_n = finish - difference_type(n);
uninitialized_copy(finish_n, finish, finish);
finish = new_
copy_backward(pos, finish_n, old_finish);
fill(pos, pos + difference_type(n), x_copy);
__uninitialized_fill_copy(finish, pos + difference_type(n),
pos, finish);
finish = new_
fill(pos, old_finish, x_copy);
__STL_UNWIND(destroy_nodes_at_back(new_finish));
还是那句话，deque为了实现整体连续的假象，导致其实现起来比较繁琐，尽量少使用它。另外，如果需要对deque进行排序的话，最好是先复制到vector中，然后再进行排序，最后在把元素拷贝回来，这样效率会提高一点。
侯捷先生的《STL的源码剖析》
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
个人博客：
访问：280621次
积分：5125
积分：5125
排名：第4227名
原创：236篇
评论：82条
阅读：7934
阅读：1415
阅读：10317
文章：165篇
阅读：190706
(1)(12)(3)(19)(61)(41)(45)(33)(12)(6)(2)(9)原文链接：
STL中deque是我们常说的双端队列,既可以从头添加元素,也可以从尾部添加元素,deque的成员函数和vector的成员函数十分相似,但是它们的内部实现却又很多不同.
deque的模板声明:
template&&&class&T,&class&Allocator&=&allocator&&T&
&&class&deque;
1)deque的内存分配方式,deque的内存管理方式比vector复杂.
上面程序在执行完最后的push_back后内存分布如下图:
追踪push_back函数我们看到:
我们先看几个变量的含义, _Myoff成员变量始终表示队头距离存储空间开始位置的元素个数, _DEQUESIZ宏定义如下,可以看到为了避免太小内存块,_DEQUESIZ会根据我们定义类型大小来确定一个block大小.
_Mysize表示队列中实际元素个数,_Map是一个_Ty**类型二级指针,正是挂接block的chunk,&宏_DEQUEMAPSIZ正是_Map的最小分配粒度.
如果存储空间不足时_DEQUESIZ我们要进行内存分配, 可以看到程序根据_Myoff和_Mysize来计算block编号,因此我们可以把_Map看成是一个环,而所有的block也可以看成一个环.在前面计算好block后,
判断该block是否已经分配内存,如果没有则分配内存,如果有则直接对新添加的对象在分配的内存中进行构造.
下面我们看下_Growmap函数,这里我做了简化,把copy数据的过程去掉了,我们可以看到在我们重新分配内存大小是以原来chunk大小的一半进行增加,如果增加大小小于最小粒度_DEQUEMAPSIZ,则取最小粒度,
如果用户需求大于我们计算的值,则以用户需求值进行增加,然后释放原来_Map的空间.
其他push_front操作和push_back操作类似,只是在计算block位置是不一样, 如下:
2)deque其他操作,pop_front和pop_back时只是将队头和队尾元素移除,进行insert操作时有点复杂,我们看看插入在一个位置插入多个元素的情况.
上面列出了靠近队头位置时的处理情况,靠近队尾时情况差不多,这里不再贴出,insert的其他重载函数操作类似.
deque在进行erase进行移除元素时,要比insert操作简单多了,如下:
deque的clear操作和vector不一样,这里clear的话是直接将内存释放掉了.
总结:deque在进行内存管理上更复杂,但与vector比较内存管理更加有效,特别是对大量数据序列,不过我们可以看到内存在根据我们的需求不断申请,但是没有释放,如果在数据量波动比较大的地方,可能比较消耗内存,
不过我们可以使用clear函数将内存释放掉,我想clear这么做肯定是考虑到了这个需求.
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：2487次
排名：千里之外
转载：28篇
(5)(8)(10)(3)(3)(1)STL中deque是我们常说的双端队列,既可以从头添加元素,也可以从尾部添加元素,deque的成员函数和vector的成员函数十分相似,但是它们的内部实现却又很多不同.
deque的模板声明:
template&&&class&T,&class&Allocator&=&allocator&&T& &&class&deque;
1)deque的内存分配方式,deque的内存管理方式比vector复杂.
上面程序在执行完最后的push_back后内存分布如下图:
追踪push_back函数我们看到:
我们先看几个变量的含义, _Myoff成员变量始终表示队头距离存储空间开始位置的元素个数, _DEQUESIZ宏定义如下,可以看到为了避免太小内存块,_DEQUESIZ会根据我们定义类型大小来确定一个block大小.
_Mysize表示队列中实际元素个数,_Map是一个_Ty**类型二级指针,正是挂接block的chunk,&宏_DEQUEMAPSIZ正是_Map的最小分配粒度.
如果存储空间不足时_DEQUESIZ我们要进行内存分配, 可以看到程序根据_Myoff和_Mysize来计算block编号,因此我们可以把_Map看成是一个环,而所有的block也可以看成一个环.在前面计算好block后,
判断该block是否已经分配内存,如果没有则分配内存,如果有则直接对新添加的对象在分配的内存中进行构造.
下面我们看下_Growmap函数,这里我做了简化,把copy数据的过程去掉了,我们可以看到在我们重新分配内存大小是以原来chunk大小的一半进行增加,如果增加大小小于最小粒度_DEQUEMAPSIZ,则取最小粒度,
如果用户需求大于我们计算的值,则以用户需求值进行增加,然后释放原来_Map的空间.
其他push_front操作和push_back操作类似,只是在计算block位置是不一样, 如下:
2)deque其他操作,pop_front和pop_back时只是将队头和队尾元素移除,进行insert操作时有点复杂,我们看看插入在一个位置插入多个元素的情况.
上面列出了靠近队头位置时的处理情况,靠近队尾时情况差不多,这里不再贴出,insert的其他重载函数操作类似.
deque在进行erase进行移除元素时,要比insert操作简单多了,如下:
deque的clear操作和vector不一样,这里clear的话是直接将内存释放掉了.
总结:deque在进行内存管理上更复杂,但与vector比较内存管理更加有效,特别是对大量数据序列,不过我们可以看到内存在根据我们的需求不断申请,但是没有释放,如果在数据量波动比较大的地方,可能比较消耗内存,
不过我们可以使用clear函数将内存释放掉,我想clear这么做肯定是考虑到了这个需求.
阅读(...) 评论()