一、容器——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 | 不支持迭代器 |
网友评论