c++容器及STL

一、容器——C++ primer 6th P713

储存其他对象的对象，且该对象有处理“其他对象”的方法。
1）容器优点

• 容器类为解决对特定代码重用。
• 可自行扩展。
• 容器类自动申请和释放内存.

基本容器特征 C++ primer P695 c++11 新增容器要求 P696

1.1 序列容器（sequence）

序列中的元素有确定的顺序

• 迭代器至少是正向迭代器：保证元素按特定顺序排序。
• 要求其元素线性顺序排列：存在首、尾元素，其余元素前后分别只有一个元素。

序列的要求

表中 t 表示类型为T（储存在容器中的值类型）的值， n 表示整数， p、q、i 和 j 表示迭代器。

序列可选要求

• 表中操作复杂度为固定。
• vector 未定义在头部操作（插入、删除）——操作复杂度为线性。
• list不支持数组表示法[ ]和随机访问.at( )。
• vector、list是可反转容器。

1）向量vector（线性表顺序储存）

• 可直接访问元素。
• 线性顺序结构，支持[ ]和vector.at()。
• 动态内存分配。
• 内部插入、删除效率低。通常在后端进行追加和删除。

2) 双向链表 list

中间每个元素都与前后元素链接。可以双向遍历链表。

• 链表不支持随机访问，不能用非成员函数的sort(),因此该类中定义了成员函数sort()。
• 单链表forward_list(C++11)。

list成员函数

3）双端队列 deque（double-ended queue）

• deque双端队列:允许在两端插入和删除元素。

双端队列的一些操作

4）适配器类（挖坑，目前仅了解）

• queue队列:是一种操作受限制的线性表——只允许在队首（front）删除元素、队尾（rear）添加元素。
  给底层类（默认queue）提供队列接口。

queue的操作

• priorty_queue:支持操作与queue相同。该模板类中最大的元素移到队首。？？？如何移

• stack 栈：给底层类（默认vector）提供栈接口。

stack的操作

1.2 关联式容器

关联容器将值和键关联在一起，并使用键来查找值。

• 优点：对元素快速访问。
• 关联容器允许插入新元素，但不能指定插入位置：通常有用于确定数据放置位置的算法。
• 通常使用树结构实现。

1）集合set、multiset

#include<set>
其值类型与键相同，键是唯一的。

• set :键就是值。
• multiset ：多个值的键相同。

2）map、multimap

#include<map>
其值类型与键不相同，键是唯一的。

• map ：每个键只对应一个值。
• multimap ：每个键与多个值相关联。

3）无序关联容器unordered_（C++11）

• 关联容器：基于树结构的。
• 无序关联容器：基于数据结构哈希表的，旨在提高添加、删除元素的速度及提高查找算法效率。
  unordered_set 和 unordered_multiset
unordered_map 和 unordered_multimap

二、STL函数——适用于容器的非成员函数

#include<algorithm>

books对象容器的源结构类型

• for_each():将被指向函数应用于容器区间中的各个元素。要求元素随机访问。

for(vector<Review>::iterator pr=books.begin();pr<books.end();pr++)
   ShowReview(*pr);

• 避免显示调用迭代器，可写为for_each(books.begin(),books.end(),ShowReview);
• 可替换为基于范围的for循环：
  for(auto x : books) ShowReview(x);
  x类型为Review,循环一次将books中每个Review对象传递给ShowReview()。
• 不同于for_each(),基于范围for循环可使用引用&修改容器内容:
  for(auto & x : books) InflateReview(x);

• random_shuffle():接受两个指定区间的迭代器参数，并随机排列该区间中的元素。

• sort():排序时使用内置操作符<进行比较;若对用户自定义对象使用sort()，则必须定义能够处理该类型对象的operator<()函数（操作符重载）;要求元素随机访问

c++ primer P681 全排序
c++ primer P681 完整弱排序

（1）sort(a.begin(),a.end()); //对a中的从a.begin()（包括它）到a.end()（不包括它，超尾元素）的元素进行从小到大排列
（2）reverse(a.begin(),a.end()); //元素倒置，但不排列.
（3）find(a.begin(),a.end(),10); //a中查找10，若存在返回其在向量中的位置

三、迭代器

模板使算法独立于存储的数据类型；迭代器使独立于使用的容器类型。

注意：迭代器不是常量，是广义指针：能够遍历容器的对象。

实现find函数，迭代器需具备的特征：

• 能对迭代器*解引用操作，访问其引用的值。
• 能将一个迭代器赋给另一个；迭代器之间能够比较。
• 能够使用迭代器遍历容器的所有元素——++运算符。C++将operator++前缀版本，operator++(int)后缀版本。

• s.end():返回一个指向超尾位置（末尾后一位）的迭代器。
• auto ：自动类型推断，简化

vector<double> s;
auto pd = s.begin(); //替代 vector<double>::iterater pd=s.begin(); 

1）迭代器功能分类

排序算法需要通过随机访问迭代器来访问容器中的元素，因此有的容器就不支持排序算法。

常用的迭代器按功能强弱分为输入、输出、正向、双向、随机访问五种，这里只介绍常用的三种。

• 正向迭代器。假设 p 是一个正向迭代器，则 p 支持以下操作：++p，p++，*p。此外，两个正向迭代器可以互相赋值，还可以用==和!=运算符进行比较。

• 双向迭代器。双向迭代器具有正向迭代器的全部功能。除此之外，若 p 是一个双向迭代器，则--p和p--都是有定义的。--p使得 p 朝和++p相反的方向移动。

• 随机访问迭代器。随机访问迭代器具有双向迭代器的全部功能。若 p 是一个随机访问迭代器，i 是一个整型变量或常量，则 p 还支持以下操作：

p+=i：使得 p 往后移动 i 个元素。
p-=i：使得 p 往前移动 i 个元素。
p+i：返回 p 后面第 i 个元素的迭代器。
p-i：返回 p 前面第 i 个元素的迭代器。
p[i]：返回 p 后面第 i 个元素的引用。

随机访问迭代器: p1、p2

• p1<p2 ：p1 经过若干次（至少一次）++操作后，就会等于 p2。 可用 <、>、<=、>= 运算符进行比较。
• p2-p1 ：返回值是 p2 所指向元素和 p1 所指向元素的序号之差（p2 和 p1 之间的元素个数减一）。
  注：++i比 i++执行速度更快。

表1：不同容器的迭代器的功能

容器	迭代器功能
vector	随机访问
deque	随机访问
list	双向
set / multiset	双向
map / multimap	双向
stack	不支持迭代器
queue	不支持迭代器
priority_queue	不支持迭代器