C++STL库的 deque、stack、queue、list、set/multiset、map/multimap

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 容器实现原理

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(beg, end); // 构造函数将 [beg, end) 区间中的元素拷贝给本身。

deque(n, elem); // 构造函数将 n 个 elem 拷贝给本身。

deque( const deque &deq); // 拷贝构造函数。

deque 赋值操作

assign(beg, end); // 将 [beg, end) 区间中的数据拷贝赋值给本身。

assign(n, elem); // 将 n 个 elem 拷贝赋值给本身。

deque& operator =( const deque &deq); // 重载等号操作符

swap(deq); // 将 deq 与本身的元素互换

deque 大小操作

deque.size(); // 返回容器中元素的个数

deque.empty(); // 判断容器是否为空

deque.resize(num); // 重新指定容器的长度为 num, 若容器变长，则以默认值填充新位 置。如果容器变短，则末尾超出容器长度的元素被删除。

deque.resize(num, elem); // 重新指定容器的长度为 num, 若容器变长，则以 elem 值 填充新位置 , 如果容器变短，则末尾超出容器长度的元素被删除。

deque 双端插入和删除操作

push_back(elem); // 在容器尾部添加一个数据

push_front(elem); // 在容器头部插入一个数据

pop_back(); // 删除容器最后一个数据

pop_front(); // 删除容器第一个数据

deque 数据存取

at(idx); // 返回索引 idx 所指的数据，如果 idx 越界，抛出 out_of_range 。

operator []; // 返回索引 idx 所指的数据，如果 idx 越界，不抛出异常，直接出错。

front(); // 返回第一个数据。

back(); // 返回最后一个数据

deque 插入操作

insert(pos,elem); // 在 pos 位置插入一个 elem 元素的拷贝，返回新数据的位置。

insert(pos,n,elem); // 在 pos 位置插入 n 个 elem 数据，无返回值。

insert(pos,beg,end); // 在 pos 位置插入 [beg,end) 区间的数据，无返回值。

deque 删除操作

clear(); // 移除容器的所有数据

erase(beg,end); // 删除 [beg,end) 区间的数据，返回下一个数据的位置。

erase(pos); // 删除 pos 位置的数据，返回下一个数据的位置。

stack 容器

容器基本概念

stack 是一种先进后出 (First In Last Out,FILO) 的数据结构，它只有一个出口，形式如图所示。stack 容器允许新增元素，移除元素，取得栈顶元素，但是除了最顶端外，没有任何其他方法可以存取 stack 的其他元素。换言之， stack 不允许有遍历行为。

有元素推入栈的操作称为 :push, 将元素推出 stack 的操作称为 pop

stack 没有迭代器

Stack 所有元素的进出都必须符合 ” 先进后出 ” 的条件，只有 stack 顶端的元素，才有机会被外界取用。Stack 不提供遍历功能，也不提供迭代器。

stack 构造函数

stack<T> stkT; //stack 采用模板类实现， stack 对象的默认构造形式：

stack( const stack &stk); // 拷贝构造函数

stack 赋值操作

stack& operator =( const stack &stk); // 重载等号操作符

stack 数据存取操作

push(elem); // 向栈顶添加元素

pop(); // 从栈顶移除第一个元素

top(); // 返回栈顶元素

stack 大小操作

empty(); // 判断堆栈是否为空

size(); // 返回堆栈的大小

queue 容器

容器基本概念

Queue 是一种先进先出 (First In First Out,FIFO) 的数据结构，它有两个出口， queue 容器允许从一端新增元素，从另一端移除元素。

queue 没有迭代器

Queue 所有元素的进出都必须符合 ” 先进先出 ” 的条件，只有 queue 的顶端元素，才有机会被外界取用。Queue 不提供遍历功能，也不提供迭代器。

queue 构造函数

queue<T> queT; //queue 采用模板类实现， queue 对象的默认构造形式：

queue( const queue &que); // 拷贝构造函数

queue 存取、插入和删除操作

push(elem); // 往队尾添加元素

pop(); // 从队头移除第一个元素

back(); // 返回最后一个元素

front(); // 返回第一个元素

queue 赋值操作

queue& operator =( const queue &que); // 重载等号操作符

queue 大小操作

empty(); // 判断队列是否为空

size(); // 返回队列的大小

list 容器

list 容器基本概念

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

相较于 vector 的连续线性空间， list 就显得负责许多，它的好处是每次插入或者删除一个元素，就是配置或者释放一个元素的空间。因此，list 对于空间的运用有绝对的精准，一点也不浪费。而且，对于任何位置的元素插入或元素的移除，list 永远是常数时间。

List 和 vector 是两个最常被使用的容器。

List 容器是一个双向链表。

采用动态存储分配，不会造成内存浪费和溢出

链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素

链表灵活，但是空间和时间额外耗费较大

list 容器的迭代器

List 容器不能像 vector 一样以普通指针作为迭代器，因为其节点不能保证在同一块连续的内存空间上。List 迭代器必须有能力指向 list 的节点，并有能力进行正确的递增、递减、取值、成员存取操作。所谓”list 正确的递增，递减、取值、成员取用” 是指，递增时指向下一个节点，递减时指向上一个节点，取值时取的是节点的数据值，成员取用时取的是节点的成员。

由于 list 是一个双向链表，迭代器必须能够具备前移、后移的能力，所以 list 容器提供的是 Bidirectional Iterators.

List 有一个重要的性质，插入操作和删除操作都不会造成原有 list 迭代器的失效。

这在 vector 是不成立的，因为 vector 的插入操作可能造成记忆体重新配置，导致原有的迭代器全部失效，甚至 List 元素的删除，也只有被删除的那个元素的迭代器失效，其他迭代器不受任何影响。

list 容器的数据结构

list 容器不仅是一个双向链表，而且还是一个循环的双向链表。

list 构造函数

list<T> lstT; //list 采用采用模板类实现 , 对象的默认构造形式：

list(beg,end); // 构造函数将 [beg, end) 区间中的元素拷贝给本身。

list(n,elem); // 构造函数将 n 个 elem 拷贝给本身。

list( const list &lst); // 拷贝构造函数。

list 数据元素插入和删除操作

push_back(elem); // 在容器尾部加入一个元素

pop_back(); // 删除容器中最后一个元素

push_front(elem); // 在容器开头插入一个元素

pop_front(); // 从容器开头移除第一个元素

insert(pos,elem); // 在 pos 位置插 elem 元素的拷贝，返回新数据的位置。

insert(pos,n,elem); // 在 pos 位置插入 n 个 elem 数据，无返回值。

insert(pos,beg,end); // 在 pos 位置插入 [beg,end) 区间的数据，无返回值。

clear(); // 移除容器的所有数据

erase(beg,end); // 删除 [beg,end) 区间的数据，返回下一个数据的位置。

erase(pos); // 删除 pos 位置的数据，返回下一个数据的位置。

remove(elem); // 删除容器中所有与 elem 值匹配的元素。

list 大小操作

size(); // 返回容器中元素的个数

empty(); // 判断容器是否为空

resize(num); // 重新指定容器的长度为 num ，

若容器变长，则以默认值填充新位置。

如果容器变短，则末尾超出容器长度的元素被删除。

resize(num, elem); // 重新指定容器的长度为 num ，

若容器变长，则以 elem 值填充新位置。

如果容器变短，则末尾超出容器长度的元素被删除。

list 赋值操作

assign(beg, end); // 将 [beg, end) 区间中的数据拷贝赋值给本身。

assign(n, elem); // 将 n 个 elem 拷贝赋值给本身。

list& operator =( const list &lst); // 重载等号操作符

swap(lst); // 将 lst 与本身的元素互换。

3.6.4.5 list 数据的存取

front(); // 返回第一个元素。

back(); // 返回最后一个元素。

3.6 .4 .6 list 反转排序

reverse(); // 反转链表，比如 lst 包含 1,3,5 元素，运行此方法后， lst 就包含 5,3,1 元素。

sort(); //list 排序

list 反转排序

reverse(); // 反转链表，比如 lst 包含 1,3,5 元素，运行此方法后， lst 就包含 5,3,1 元素。

sort(); //list 排序

set/multiset 容器

set/multiset 容器基本概念

Set 的特性是。所有元素都会根据元素的键值自动被排序。 Set 的元素不像 map 那样可以同时拥有实值和键值，set 的元素即是键值又是实值。 Set 不允许两个元素有相同的键值。

我们可以通过 set 的迭代器改变 set 元素的值吗？不行，因为 set 元素值就是其键值，关系到 set 元素的排序规则。如果任意改变 set 元素值，会严重破坏 set 组织。换句话说，set 的 iterator 是一种 const_iterator.

set 拥有和 list 某些相同的性质，当对容器中的元素进行插入操作或者删除操作的时候，操作之前所有的迭代器，在操作完成之后依然有效，被删除的那个元素的迭代器必然是一个例外。

multiset 特性及用法和 set 完全相同，唯一的差别在于它允许键值重复。 set 和 multiset 的底层实现是红黑树，红黑树为平衡二叉树的一种。

树的简单知识：

二叉树就是任何节点最多只允许有两个字节点。分别是左子结点和右子节点。

二叉树示意图

二叉搜索树，是指二叉树中的节点按照一定的规则进行排序，使得对二叉树中元素访问更加高效。二叉搜索树的放置规则是：任何节点的元素值一定大于其左子树中的每一个节点的元素值，并且小于其右子树的值。因此从根节点一直向左走，一直到无路可走，即得到最小值，一直向右走，直至无路可走，可得到最大值。那么在儿茶搜索树中找到最大元素和最小元素是非常简单的事情。下图为二叉搜索树：

上面我们介绍了二叉搜索树，那么当一个二叉搜索树的左子树和右子树不平衡的时候，那么搜索依据上图表示，搜索 9 所花费的时间要比搜索 17 所花费的时间要多，由于我们的输入或者经过我们插入或者删除操作，二叉树失去平衡，造成搜索效率降低。

所以我们有了一个平衡二叉树的概念，所谓的平衡不是指的完全平衡。

set 构造函数

set<T> st; //set 默认构造函数：

mulitset<T> mst; //multiset 默认构造函数 :

set( const set &st); // 拷贝构造函数

set 赋值操作

set& operator =( const set &st); // 重载等号操作符

swap(st); // 交换两个集合容器

set 大小操作

size(); // 返回容器中元素的数目

empty(); // 判断容器是否为空

set 插入和删除操作

insert(elem); // 在容器中插入元素。

clear(); // 清除所有元素

erase(pos); // 删除 pos 迭代器所指的元素，返回下一个元素的迭代器。

erase(beg, end); // 删除区间 [beg,end) 的所有元素，返回下一个元素的迭代器。

erase(elem); // 删除容器中值为 elem 的元素。

set 查找操作

find(key); // 查找键 key 是否存在 , 若存在，返回该键的元素的迭代器；若不存在，返 回 set.end();

count(key); // 查找键 key 的元素个数

lower_bound(keyElem); // 返回第一个 key>=keyElem 元素的迭代器。

upper_bound(keyElem); // 返回第一个 key>keyElem 元素的迭代器。

equal_range(keyElem); // 返回容器中 key 与 keyElem 相等的上下限的两个迭代器。

set 的返回值指定 set 排序规则:

// 插入操作返回值

// 插入操作返回值

void test01(){

set< int > s;

pair<set< int >::iterator, bool > ret = s.insert( 10 );

if (ret.second){

cout << " 插入成功 :" << *ret.first << endl;

}

else {

cout << " 插入失败 :" << *ret.first << endl;

}

ret = s.insert( 10 );

if (ret.second){

cout << " 插入成功 :" << *ret.first << endl;

}

else {

cout << " 插入失败 :" << *ret.first << endl;

}

struct MyCompare02{

bool operator ()( int v1, int v2){

return v1 > v2;

}

};

//set 从大到小

void test02(){

srand(( unsigned int )time(NULL));

//我们发现 set 容器的第二个模板参数可以设置排序规则，默认规则是 less<_Kt y>

set< int , MyCompare02> s;

for ( int i = 0 ; i < 10 ;i++){

s.insert(rand() % 100 );

}

for (set< int , MyCompare02>::iterator it = s.begin(); it != s.end (); it ++){

cout << *it << " " ;

}

cout << endl;

}

//set 容器中存放对象

class Person{

public :

Person(string name, int age){

this ->mName = name;

this ->mAge = age;

}

public :

string mName;

int mAge;

};

struct MyCompare03{

bool operator ()( const Person& p1, const Person& p2){

return p1.mAge > p2.mAge;

}

};

void test03(){

set<Person, MyCompare03> s;

Person p1( "aaa" , 20 );

Person p2( "bbb" , 30 );

Person p3( "ccc" , 40 );

Person p4( "ddd" , 50 );

s.insert(p1);

s.insert(p2);

s.insert(p3);

s.insert(p4);

for (set<Person, MyCompare03>::iterator it = s.begin(); it != s.end(); it++){

cout << "Name:" << it->mName << " Age:" << it->mAge << endl;

}

对组(pair)

对组(pair) 将一对值组合成一个值，这一对值可以具有不同的数据类型，两个值可以分别用 pair 的两个公有属性 first 和 second 访问。

类模板： template <class T1, class T2> struct pair.

如何创建对组 ?

// 第一种方法创建一个对组

pair<string, int > pair1(string( "name" ), 20 );

cout << pair1.first << endl; // 访问 pair 第一个值

cout << pair1.second << endl; // 访问 pair 第二个值

// 第二种

pair<string, int > pair2 = make_pair( "name" , 30 );

cout << pair2.first << endl;

cout << pair2.second << endl;

//pair= 赋值

pair<string, int > pair3 = pair2;

cout << pair3.first << endl;

cout << pair3.second << endl;

map/multimap 容器

map/multimap 基本概念

Map 的特性是，所有元素都会根据元素的键值自动排序。 Map 所有的元素都是 pair,同时拥有实值和键值， pair 的第一元素被视为键值，第二元素被视为实值， map 不允许两个元素有相同的键值。

我们可以通过 map 的迭代器改变 map 的键值吗？答案是不行，因为 map 的键值关系到 map 元素的排列规则，任意改变 map 键值将会严重破坏 map 组织。如果想要修改元素的实值，那么是可以的。

Map 和 list 拥有相同的某些性质，当对它的容器元素进行新增操作或者删除操作时，操作之前的所有迭代器，在操作完成之后依然有效，当然被删除的那个元素的迭代器必然是个例外。

Multimap 和 map 的操作类似，唯一区别 multimap 键值可重复。

Map 和 multimap 都是以红黑树为底层实现机制。

map 构造函数

map<T1, T2> mapTT; //map 默认构造函数 :

map( const map &mp); // 拷贝构造函数

map 赋值操作

map& operator =( const map &mp); // 重载等号操作符

swap(mp); // 交换两个集合容器

map 大小操作

size(); // 返回容器中元素的数目

empty(); // 判断容器是否为空

map 插入数据元素操作

map.insert(...); // 往容器插入元素，返回 pair<iterator,bool>

map< int , string> mapStu;

// 第一种通过 pair 的方式插入对象

mapStu.insert(pair< int , string>( 3 , " 小张 " ));

// 第二种通过 pair 的方式插入对象

mapStu.inset(make_pair(- 1 , " 校长 " ));

// 第三种通过 value_type 的方式插入对象

mapStu.insert(map< int , string>:: value_type ( 1 , " 小李 " ));

// 第四种通过数组的方式插入值

mapStu[ 3 ] = " 小刘 " ;

mapStu[ 5 ] = " 小王 " ;

map 删除操作

clear(); // 删除所有元素

erase(pos); // 删除 pos 迭代器所指的元素，返回下一个元素的迭代器。

erase(beg,end); // 删除区间 [beg,end) 的所有元素，返回下一个元素的迭代器。

erase(keyElem); // 删除容器中 key 为 keyElem 的对组。

map 查找操作

find(key); // 查找键 key 是否存在 , 若存在，返回该键的元素的迭代器； / 若不存在，返 回 map.end();

count(keyElem); // 返回容器中 key 为 keyElem 的对组个数。对 map 来说，要么是 0 ， 要么是 1 。对 multimap 来说，值可能大于 1 。

lower_bound(keyElem); // 返回第一个 key>=keyElem 元素的迭代器。

upper_bound(keyElem); // 返回第一个 key>keyElem 元素的迭代器。

equal_range(keyElem); // 返回容器中 key 与 keyElem 相等的上下限的两个迭代器。

multimap 案例

公司今天招聘了 5 个员工， 5 名员工进入公司之后，需要指派员工在那个部门工作人员信息有: 姓名年龄电话工资等组成通过 Multimap 进行信息的插入保存显示分部门显示员工信息显示全部员工信息

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;
// multimap 案例
// 公司今天招聘了 5 个员工，5 名员工进入公司之后，需要指派员工在那个部门工作
// 人员信息有: 姓名 年龄 电话 工资等组成
// 通过 Multimap 进行信息的插入 保存 显示
// 分部门显示员工信息 显示全部员工信息
#define SALE_DEPATMENT 1     // 销售部门
#define DEVELOP_DEPATMENT 2  // 研发部门
#define FINACIAL_DEPATMENT 3 // 财务部门
#define ALL_DEPATMENT 4      // 所有部门
// 员工类
class person
{
public:string name;   // 员工姓名int age;       // 员工年龄double salary; // 员工工资string tele;   // 员工电话
};
// 创建 5 个员工
void CreatePerson(vector<person> &vlist)
{string seed = "ABCDE";for (int i = 0; i < 5; i++){person p;p.name = "员工";p.name += seed[i];p.age = rand() % 30 + 20;p.salary = rand() % 20000 + 10000;p.tele = "010-8888888";vlist.push_back(p);}
}
// 5 名员工分配到不同的部门
void PersonByGroup(vector<person> &vlist, multimap<int, person> &plist)
{int operate = -1; // 用户的操作for (vector<person>::iterator it = vlist.begin(); it != vlist.end(); it++){cout << "当前员工信息:" << endl;
cout << "姓名：" << it->name << " 年龄:" << it->age << " 工
资:" << it->salary << " 电话：" << it->tele << endl;
cout << "请对该员工进行部门分配(1 销售部门, 2 研发部门, 3 财务
部门):" << endl;
scanf("%d", &operate);
while (true)
{if (operate == SALE_DEPATMENT){ // 将该员工加入到销售部门plist.insert(make_pair(SALE_DEPATMENT, *it));break;}else if (operate == DEVELOP_DEPATMENT){plist.insert(make_pair(DEVELOP_DEPATMENT, *it));break;}else if (operate == FINACIAL_DEPATMENT){plist.insert(make_pair(FINACIAL_DEPATMENT, *it));break;}else{
cout << "您的输入有误，请重新输入(1 销售部门, 2 研
发部门, 3 财务部门):" << endl;
scanf("%d", &operate);}
}}cout << "员工部门分配完毕!" << endl;cout << "********************************************************* **" << endl;
}
// 打印员工信息
void printList(multimap<int, person> &plist, int myoperate)
{if (myoperate == ALL_DEPATMENT){for (multimap<int, person>::iterator it = plist.begin(); it != plist.end(); it++){cout << "姓名：" << it->second.name << " 年龄:" << it->second.age << " 工资:" << it->second.salary << " 电话：" << it->second.t ele << endl;}return;}multimap<int, person>::iterator it = plist.find(myoperate);int depatCount = plist.count(myoperate);int num = 0;if (it != plist.end()){while (it != plist.end() && num < depatCount){cout << "姓名：" << it->second.name << " 年龄:" << it->second.age << " 工资:" << it->second.salary << " 电话：" << it->second.t ele << endl;it++;num++;}}
}
// 根据用户操作显示不同部门的人员列表
void ShowPersonList(multimap<int, person> &plist, int myoperate)
{switch (myoperate){case SALE_DEPATMENT:printList(plist, SALE_DEPATMENT);break;case DEVELOP_DEPATMENT:printList(plist, DEVELOP_DEPATMENT);break;case FINACIAL_DEPATMENT:printList(plist, FINACIAL_DEPATMENT);break;case ALL_DEPATMENT:printList(plist, ALL_DEPATMENT);break;}
}
// 用户操作菜单
void PersonMenue(multimap<int, person> &plist)
{int flag = -1;int isexit = 0;while (true){
cout << "请输入您的操作((1 销售部门, 2 研发部门, 3 财务部门, 4
所有部门, 0 退出)：" << endl;
scanf("%d", &flag);
switch (flag)
{
case SALE_DEPATMENT:ShowPersonList(plist, SALE_DEPATMENT);break;
case DEVELOP_DEPATMENT:ShowPersonList(plist, DEVELOP_DEPATMENT);break;
case FINACIAL_DEPATMENT:ShowPersonList(plist, FINACIAL_DEPATMENT);break;
case ALL_DEPATMENT:ShowPersonList(plist, ALL_DEPATMENT);break;
case 0:isexit = 1;break;
default:cout << "您的输入有误，请重新输入!" << endl;break;
}
if (isexit == 1)
{break;
}}
}
int main()
{vector<person> vlist;        // 创建的 5 个员工 未分组multimap<int, person> plist; // 保存分组后员工信息// 创建 5 个员工CreatePerson(vlist);// 5 名员工分配到不同的部门PersonByGroup(vlist, plist);// 根据用户输入显示不同部门员工信息列表 或者 显示全部员工的信息列表PersonMenue(plist);system("pause");return EXIT_SUCCESS;
}