9.6 KiB
Executable File
二、STL容器II
2.1 queue 容器
2.1.1 queue概念
Queue 是一种先进先出(First In First Out,FIFO)的数据结构，它有两个出口，queue 容器允许从一端新增元素，从另一端移除元素。
2.1.2 queue 没有迭代器
Queue 所有元素的进出都必须符合”先进先出”的条件，只有 queue 的顶端元素，才 有机会被外界取用。Queue 不提供遍历功能，也不提供迭代器。
2.1.3 常用API
2.1.3.1 构造函数
queue<T> queT; //queue 采用模板类实现，queue 对象的默认构造形式：
queue(const queue &que);//拷贝构造函数
2.1.3.2 存取、插入和删除
void push(elem); //往队尾添加元素
void pop(); //从队头移除第一个元素
T back(); //返回最后一个元素
T front(); //返回第一个元素
2.1.3.3 赋值与大小
queue& operator=(const queue &que);//重载等号操作符
empty();//判断队列是否为空
size();//返回队列的大小
2.2 list 容器
2.2.1 list 概念
list(链表)是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。
每个结点包括两个部分：
1）存储数据元素的数据域，
2）存储下一个结点地址的指针域
list与vector的比较：
1） 相对于vector 的连续线性空间，list 就显得负责许多，每次插入或者删除一个元素，就是配置或者释放一个元素的空间。不浪费多余的空间，且插入与移除元素的操作是常数时间（稳定）。
2）list和vector 是两个最常被使用的容器, 但list是由双向链表实现的。
3）list插入操作和删除操作都不会造成原有 list 迭代器的失效。 【重要特性】
list特点：
1）采用动态存储分配，不会造成内存浪费和溢出
2）链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素
3）链表灵活，但是空间和时间额外耗费较大
2.2.2 list 的迭代器
List 不能像 vector 一样以普通指针作为迭代器，因为其节点不能保证在同一块连续的内存空间上。。List 迭代器必须有能力指向 list 的节点，并有能力进行正确的递增、递减、取值、成员存取操作。递增时指向下一个节点，递减时指向上一个节点，取值时取的是节点的数据值，成员取用时取的是节点的成员。
另外，list 是一个双向链表，迭代器必须能够具备前移、后移的能力，所以 list 容器提供的是 Bidirectional Iterators.（双向的迭代器）。
List 有一个重要的性质，插入操作和删除操作都不会造成原有 list 迭代器的失效。
【注意】list的迭代器，不支持+n操作。
2.2.3 list 数据结构
list 容器不仅是一个双向链表，而且还是一个循环的双向链表。
2.2.4 常用API
2.2.4.1 构造函数
list<T> lstT;//list 采用采用模板类实现,对象的默认构造形式：
list(beg,end);//构造函数将[beg, end)区间中的元素拷贝给本身。
list(n,elem);//构造函数将 n 个 elem 拷贝给本身。
list(const list &lst);//拷贝构造函数
2.2.4.2 插入和删除
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 值匹配的元素
2.2.4.3 大小
size();//返回容器中元素的个数
empty();//判断容器是否为空
resize(num);//重新指定容器的长度为 num, 若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除
resize(num, elem);
2.2.4.4 赋值
assign(beg, end); //将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem); //将 n 个 elem 拷贝赋值给本身。
list& operator=(const list &lst); //重载等号操作符
swap(lst); //将 lst 与本身的元素互换。
2.2.4.5 读取
front();//返回第一个元素。
back();//返回最后一个元素
2.2.4.6 反转和排序
reverse(); //反转链表
sort(); //list 排序
2.3 set/multiset 容器
2.3.1 set概念
set 的特性是所有元素都会根据元素的键值自动被排序。
set 的元素即是键值又是实值， 不允许两个元素有相同的键值。
set 的 iterator 是一种 const_iterator， 不允许修改set的键值。
set 拥有和 list 某些相同的性质，当对容器中的元素进行插入操作或者删除操作的 时候，操作之前的迭代器，在操作完成之后依然有效，被删除的那个元素的迭代器必然是一个例外。
2.3.2 set数据结构
multiset 特性及用法和 set 完全相同，唯一的差别在于它允许键值重复。set 和multiset 的底层实现是红黑树，红黑树为平衡二叉树的一种。
二叉树就是任何节点最多只允许有两个字节点。分别是左子结点和右子节点：
二叉搜索树，是指二叉树中的节点按照一定的规则进行排序，使得对二叉树中元素访问更加高效:
二叉搜索树的放置规则是：
任何节点的元素值一定大于其左子树中的每一个节点的元素值，并且小于其右子树的值。因此从根节点一直向左走，一直到无路可走，即得到最小值，一直向右走，直至无路可走，可得到最大值。那么在二叉搜索树中找到最大元素和最小元素是非常简单的事情。
如上图所示：那么当一个二叉搜索树的左子树和右子树不平衡的时候，那么搜索依据上图表示，搜索 9 所花费的时间要比搜索 17 所花费的时间要多，由于我们的输入或者经过我们插入或者删除操作，二叉树失去平衡，造成搜索效率降低。
2.3.3 常用API
2.3.3.1 构造函数
set<T> st;//set 默认构造函数：
mulitset<T> mst; //multiset 默认构造函数:
set(const set &st);//拷贝构造函数
2.3.3.2 赋值和大小
set& operator=(const set &st);//重载等号操作符
swap(st);//交换两个集合容器
size();//返回容器中元素的数目
empty();//判断容器是否为空
2.3.3.3 插入和删除
insert(elem); //在容器中插入元素。
clear(); //清除所有元素
erase(pos); //删除 pos 迭代器所指的元素，返回下一个元素的迭代器。
erase(beg, end); //删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。
erase(elem); //删除容器中值为 elem 的元素。
2.3.3.4 查找
find(key); //查找键 key 是否存在,若存在，返回该键的元素的迭代器；若不存在，返
回 set.end();
count(key);//查找键 key 的元素个数
lower_bound(keyElem);//返回第一个 key>=keyElem 元素的迭代器。
upper_bound(keyElem);//返回第一个 key>keyElem 元素的迭代器。
equal_range(keyElem);//返回容器中 key 与 keyElem 相等的上下限的两个迭代器。
2.3.3.5 set 排序规则
set自动排序， 但可以改变它的排序规则，默认从小到大。
自定义排序规则，可以使用struct或class, 声明 bool operator(v1, v2)仿函数重载。
2.3.4 对组(pair)
对组(pair)将一对值组合成一个值，这一对值可以具有不同的数据类型，两个值可 以分别用 pair 的两个公有属性 first 和 second 访问。
类模板：template <class T1, class T2> struct pair
用法一：
pair<string, int> pair1(string("name"), 20);
cout << pair1.first << endl;
cout << pair1.second << endl;
用法二：
pair<string, int> pair2 = make_pair("name", 30);
cout << pair2.first << endl;
cout << pair2.second << endl;
用法三：
pair<string, int> pair3 = pair2;
cout << pair3.first << endl;
cout << pair3.second << endl;
2.4 map/multimap 容器
Map 的特性是所有元素都会根据元素的键值自动排序。
Map 所有的元素都是pair,同时拥有实值和键值，pair 的第一元素被视为键值，第二元素被视为实值，map 不允许两个元素有相同的键值。
multimap 和 map 的操作类似，唯一区别 multimap 键值可重复。 map 和 multimap 都是以红黑树为底层实现机制。