ToB企服应用市场:ToB评测及商务社交产业平台

标题: C++ STL第三篇（搞清晰deque原理和有多少用法） [打印本页]

作者: 河曲智叟 时间: 2024-5-14 09:36
标题: C++ STL第三篇（搞清晰deque原理和有多少用法）
deque

Vector容器是单向开口的连续内存空间，deque则是一种双向开口的连续线性空间。所谓的双向开口，意思是可以在头尾两头分别做元素的插入和删除操纵，当然，vector容器也可以在头尾两头插入元素，但是在其头部操纵效率奇差，无法被接受。

Deque容器和vector容器最大的差异，一在于deque答应利用常数项时间对头端进行元素的插入和删除操纵。二在于deque没有容量的概念，因为它是动态的以分段连续空间组合而成，随时可以增长一段新的空间并链接起来，换句话说，像vector那样，”旧空间不足而重新配置一块更大空间，然后复制元素，再释放旧空间”这样的事情在deque身上是不会发生的。也因此，deque没有必须要提供所谓的空间保留(reserve)功能.
固然deque容器也提供了Random Access Iterator,但是它的迭代器并不是普通的指针，其复杂度和vector不是一个量级，这当然影响各个运算的层面。因此，除非有须要，我们应该尽可能的利用vector，而不是deque。对deque进行的排序操纵，为了最高效率，可将deque先完整的复制到一个vector中，对vector容器进行排序，再复制回deque.
实现原理

Deque容器是连续的空间，至少逻辑上看来云云，连续现行空间总是令我们联想到array和vector,array无法成长，vector虽可成长，却只能向尾端成长，而且其成长着实是一个假象，事实上(1) 申请更大空间 (2)原数据复制新空间 (3)释放原空间三步调，如果不是vector每次配置新的空间时都留有余裕，其成长假象所带来的代价黑白常昂贵的。
Deque是由一段一段的定量的连续空间构成。一旦有须要在deque前端大概尾端增长新的空间，便配置一段连续定量的空间，串接在deque的头端大概尾端。Deque最大的工作就是维护这些分段连续的内存空间的整体性的假象，并提供随机存取的接口，避开了重新配置空间，复制，释放的轮回，代价就是复杂的迭代器架构。
既然deque是分段连续内存空间，那么就必须有中央控制，维持整体连续的假象，数据布局的设计及迭代器的前进后退操纵颇为繁琐。Deque代码的实现远比vector或list都多得多。
Deque采取一块所谓的map(注意，不是STL的map容器)作为主控，这里所谓的map是一小块连续的内存空间，其中每一个元素(此处成为一个结点)都是一个指针，指向另一段连续性内存空间，称作缓冲区。缓冲区才是deque的存储空间的主体。

声明方法

默认构造形式：利用默认构造函数创建一个空的deque容器。

deque<T> deqT;
deque<int> r1;//默认构造形式：创建一个空的deque容器

复制代码

范围构造函数：利用指定范围内的元素创建deque容器，将[beg, end)区间中的元素拷贝给本身。

deque<T> deqT(beg, end);
int arr[] = { 1,2,3,4,5 };
deque<int> r2(arr, arr + 5);// 范围构造函数：将指定范围内的元素拷贝给本身

复制代码

其中，beg是指向范围起始位置的迭代器，end是指向范围结束位置的迭代器。

值构造函数：利用指定值创建deque容器，将n个elem拷贝给本身。

deque<T> deqT(n, elem);
deque<int> r3(3, 100);// 创建包含3个值为10的元素的deque

复制代码

其中，n是要创建的元素数目，elem是要拷贝的元素值。

拷贝构造函数：利用另一个deque容器进行拷贝构造，创建一个新的deque容器。

deque<T> deqT(deq);
deque<int> deq4(deq2);

复制代码

其中，deq是要进行拷贝的deque容器。
赋值操纵

assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem);//将n个elem拷贝赋值给本身。
deque&operator=(const deque &deq); //重载等号操纵符
swap(deq);// 将deq与本身的元素互换

[code]template void print(const T& r1, const T& r2){ std::cout

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)