C++ 之标准模板库（STL）的容器与迭代器

标准模板库

泛型程序设计(generic programming)的思想 : 模板机制，以及标准模板库STL 。

标准模板库 (STL,Standard Template Libaray)
一些常用数据结构和算法的模板的集合。将一些常用的数据结构（比如链表，数组，二叉树）和算法（比如排序，查找）写成模板，以后则不论数据结构里放的是什么对象，算法针对什么样的对象，则都不必重新实现数据结构，重新编写算法。

容器概述

可以用于存放各种类型的数据（基本类型的变量，对象等）的数据结构，都是类模版，分为三种：

顺序容器
vector,deque,list
关联容器(排序的，查找速度更快)
set,multiset,map,multimap
容器适配器
stack,queue,priority_queue

对象被插入容器中时，被插入的是对象的一个复制品。许多算法，比如排序，查找，要求对容器中的元素进行比较，有的容器本身就是排序的，所以，放入容器的对象所属的类，往往还应该重载 == 和 < 运算符。

顺序容器

容器并非排序的，元素的插入位置同元素的值无关。有 vector,deque,list三种。

vector 头文件 <vector>

动态数组。元素在内存连续存放。随机存取任何元素都能在常数时间完成。在尾端增删元素具有较佳的性能（大部分情况下是常数时间）。

---	A0	A1	A2	---	---	---	---	---	---	---	An	---
	begin											end

deque 头文件 <deque>

双向队列。元素在内存连续存放。随机存取任何元素都能在常数时间完成（但次于vector）。在两端增删元素具有较佳的性能（大部分情况下是常数时间）。

---	---	A0	A1	A2	A3	A4	A5	---	---	---	---	---	---	---
		begin						end

list 头文件 <list>
双向链表。元素在内存不连续存放。在任何位置增删元素都能在常数时间完成。不支持随机存取。
在这里插入图片描述

关联容器

元素是排序的
插入任何元素，都按相应的排序规则来确定其位置
在查找时具有非常好的性能
通常以平衡二叉树方式实现，插入和检索的时间都是O(log(N))

set/multiset 头文件 <set>

set 即集合。set中不允许相同元素，multiset中允许存在相同的元素。

map/multimap 头文件 <map>
map与set的不同在于map中存放的元素有且仅有两个成员变量，一个名为first，另一个名为second，map根据first值对元素进行从小到大排序，并可快速地根据first来检索元素。那first 则相当于关键字，second 则存储的是值；
map同multimap的不同在于是否允许相同first值的元素，即关键字可重复与否；

容器适配器

stack：头文件<stack>
栈。是项的有限序列，并满足序列中被删除、检索和修改的项只能是最近插入序列的项（栈顶的项）。后进先出。
在这里插入图片描述
queue头文件<queue>
队列。插入只可以在尾部进行，删除、检索和修改只允许从头部进行。先进先出。

priority_queue 头文件<queue>
优先级队列。最高优先级元素总是第一个出列

顺序/关联容器中均有的成员函数

begin 返回指向容器中第一个元素的迭代器
end 返回指向容器中最后一个元素后面的位置的迭代器
rbegin 返回指向容器中最后一个元素的迭代器
rend 返回指向容器中第一个元素前面的位置的迭代器
erase 从容器中删除一个或几个元素
clear 从容器中删除所有元素

顺序容器常用函数

front：返回容器中第一个元素的引用
back：返回容器中最后一个元素的引用
push_back：在容器末尾增加新元素
pop_back：删除容器末尾的元素。
erase：删除迭代器指向的元素（可能会使该迭代器失效），或删除一个区间，返回被删除元素后面的那个元素的迭代器

迭代器

定义一个容器类的迭代器的方法可以是：

容器类名::iterator 变量名;
容器类名::const_iterator 变量名;

容器类名::reverse_iterator 变量名;
容器类名::const_reverse_iterator 变量名;

访问一个迭代器指向的元素：*选代器变量名。

用于指向顺序容器和关联容器中的元素
迭代器用法和指针类似
有const和非const两种
通过迭代器可以读取它指向的元素
通过非const选代器还能修改其指向的元素

迭代器上可以执行++操作，以使其指向容器中的下一个元素。如果迭代器到达了容器中的最后一个元素的后面，此时再使用它,就会出错,类似于使用NULL或未初始化的指针一样。

双向迭代器

若p和p1都是双向迭代器,则可对p、p1可进行以下操作:
++p,p++使p指向容器中下一个元素
--p,p-使p指向容器中上一个元素
*p取p指向的元素
p=p1赋值
p==p1,p!=p1判断是否相等、不等

随机访问迭代器

双向迭代器的所有操作
p+=i 将p向后移动i个元素
p-=i 将p向向前移动i个元素
p+i 值为：指向p后面的第i个元素的迭代器
p-i 值为：指向p前面的第i个元素的迭代器
p[i] 值为：p后面的第i个元素的引用
p<p1，p<=p1，p>p1，p>=p1

容器容器上的迭代器类别

vector 随机访问
deque 随机访问
list 双向
set/multiset 双向
map/multimap 双向
stack 不支持选代器
queue 不支持迭代器
nriority aueue不支持迭代器

有的算法，例如sort，binary_search需要通过随机访问迭代器来访问容器中的元素，那么list以及关联容器就不支持该算法！

容器详解

顺序容器

Vector

可变长的动态数组
必须包含头文件 #include <vector>
支持随机访问迭代器
- 根据下标随机访问某个元素时间为常数
- 在尾部添加速度很快
- 在中间插入慢

成员函数：

成员函数	作用
vector();	无参构造函数,将容器初始化成空的
vector(int n);	将容器初始化成有n个元素
vector(int n,const T&val);	假定元素类型是T,将容器初始化成有n个元素,每个元素的值都是Val
vector(iterator first,iterator last);	将容器初始化为与别的容器上区间[first,last)一致的内容
void pop_back();	删除容器末尾的元素
void push_back(const T&val);	将val添加到容器末尾
int size();	返回容器中元素的个数
T&font();	返回容器中第一个元素的引用
T&back();	返回容器中最后一个元素的引用

List

在任何位置插入/删除都是常数时间
不支持根据下标随机存取元素
具有所有顺序容器都有的成员函数

成员函数：

成员函数	作用
push_front	在链表最前面插入
pop_front	删除链表最前面的元素
sort	排序(list不支持STL的算法sort)
remove	删除和指定值相等的所有元素
unique	删除所有和前一个元素相同的元素
merge	合并两个链表,并清空被合并的链表
reverse	颠倒链表
splice	在指定位置前面插入另一链表中的一个或多个元素,并在另一链表中删除被插入的元素

Deque

双向队列

必须包含头文件#include <deque>

成员函数：

所有适用于vector的操作都适用于deque
deque还有 push_front(将元素插入到容器的头部)和pop_front(删除头部的元素)操作

关联容器

set，multiset，map，multimap

内部元素有序排列，新元素插入的位置取决于它的值，查找速度快。
除了各容器都有的函数外，还支持以下成员函数：
- find：查找等于某个值的元素（x小于y和y小于x同时不成立即为相等）
- lower bound：查找某个下界
- upper_bound：查找某个上界
- equal_range：同时查找上界和下界
- count：计算等于某个值的元素个数（x小于y和y小于x同时不成立即为相等）
- insert：用以插入一个元素或一个区间

map/multimap容器里放着的都是pair模版类的对象，且按first从小到大排序

template<class _T1, class _T2>
struct pair{
typedef_T1 first type; 
typedef_T2 second_type; 
T1 first; 
T2 second; 
pair(): first(), second(){}
pair(const _T1&a, const_T2&b) : first(_a), second(b){}
template<class _U1, class _U2>
pair(const pair<_U1,_U2>&p) : first(p. first), second(p. second){}

Multiset

实现：

template<class Key,class Pred=less<Key>,class A=allocator<Key>>
class multiset{.....};

Pred类型的变量决定了multiset中的元素，“一个比另一个小”是怎么定义的。
multiset运行过程中，比较两个元素x，y的大小的做法，就是生成一个Pred类型的变量，假定为op，若表达式op（x，y）返回值为true，则x比y小。
Pred的缺省类型是less<Key>。
其中less模板定义：

template<class T>
struct less:public binary_function<T,T,bool>
{bool operator()(const T& x,const T& y){returnx<y;}const;};

成员函数 :

成员函数	作用
iterator find(const T&val);	在容器中查找值为val的元素,返回其迭代器.如果找不到,返回end().
iterator insert(const T&val);	将val插入到容器中并返回其迭代器.
void insert(iterator first,iterator last);	将区间[first,last)插入容器.
int count(const T&val);	统计有多少个元素的值和val相等.
iterator lower bound(const T&val);	查找一个最大的位置it,使得[begin(),it),中所有的元素都比val小.
iterator upper bound(const T&val);	查找一个最小的位置t,使得[t,end())中所有的元素都比val大.
pair<iterator,iterator>equal_range(const T&val);	同时求得lower_bound和upper_bound.
iterator erase(iterator it);	删除it指向的元素,返回其后面的元素的迭代器(Visual studio2010上如此,但是在cpp标准和Dev cpp中,返回值不是这样).

Set

实现：

template<class Key,class Pred=less<Key>,class A=allocator<Key>>
class set{...}

插入set中已有的元素时,忽略插入，重复的定义 : (a<b)||(b<a)=0 。

插入函数的不同

template<typename T>
pair<std::set<T>::iterator,bool> insert(const T&val); 将val插入到容器中并返回其迭代器。

Multimap

实现：

template<class Key,class T,class Pred=less<Key>,classA=allocator<T>>
class multimap{
..
typedef pair<const Key,T> value_type;
...…
};//Key代表关键字的类型

multimap中的元素由〈关键字,值〉组成,每个元素是一个pair对象,关键字就是first成员变量,其类型是Key
multimap中允许多个元素的关键字相同.元素按照first成员变量从小到大排列,缺省情况下用less<Key>定义关键字的"小于"关系.

示例：

# include <iostream>
# include<map>
using namespace std; 
int main(){
typedef multimap<int, double, less<int>>mmid; 
mmid pairs; 
pairs.insert(mmid: value_type(15,2.7);
cout<<"含有15元素个数："<<pairs.count(15)<< endl;

Map

实现：

template<class Key,class T,class Pred=less<Key>, class A=allocator<T>>
class map{
... ...
typedef pair<const Key,T> value_type;
... ...
};

map中的元素都是pair模板类对象.关键字(first成员变量)各不相同.元素按照关键字从小到大排列,缺省情况下用less<Key>, 即"<"定义"小于"。

若pairs为map模版类的对象

pairs[key]
返回对关键字等于key的元素的值（second成员变量）的引用。若没有关键字为key的元素，则会往pairs里插入一个关键字为key的元素，其值用无参构造函数初始化，并返回其值的引用。
如：
map<int，double>pairs；pairs[50]=5；会修改pairs中关键字为50的元素，使其值变成5。
若不存在关键字等于50的元素，则插入此元素，并使其值变为5。

实用类模板bitset

实现

bitset template<size_tN>
class bitset
{
......
};

特性

实际使用的时候,N是个整型常数如:
bitset<40>bst;
bst是一个由40位组成的对象
用bitset的函数可以方便地访问任何一位

成员函数

bitset&operator&=（const bitset&rhs）；
bitset&operatorl=（const bitset&rhs）；
bitset&operatorA=（const bitset&rhs）；
bitset&operator<<=（size_tnum）；
bitset&operator>>=（size_tnum）；
bitset&set（）；/全部设成1
bitset&set（size_t pos，bool val=true）；//设置某位
bitset&reset（）；//全部设成0
bitset&reset（size_t pos）；/某位设成0
bitset&flip（）；//全部翻转
bitset&flip（size_t pos）；//翻转某位
reference operator[]（size_t pos）；//返回对某位的引用。
bool operator[](size_t pos）const；//判断某位是否为1
reference at（size_t pos）；
bool at（size_t pos）const；
unsigned long to_ulong（）const；//转换成整数
string to_string（）const；//转换成字符串
size_t count（）const；//计算1的个数
size_t size（）const；
bool operator==（const bitset&rhs）const；
bool operator！=（const bitset&rhs）const；

容器适配器详解

可以用某种顺序容器来实现
（让已有的顺序容器以栈/队列的方式工作）

stack：头文件
栈--后进先出
queue：头文件
队列--先进先出
priority_queue：头文件
优先级队列--最高优先级元素总是第一个出列R

都有3个成员函数：

push：添加一个元素；
top：返回栈顶部或队头元素的引用
pop：删除一个元素容器适配器上没有迭代器
STL中各种排序，查找，变序等算法都不适合容器适配器

Stack

实现：

template<class T，class Cont=deque<T>>
class stack{
...
};

stack 是后进先出的数据结构
只能插入，删除，访问栈顶的元素
可用 vector，，list，deque来实现
- 缺省情况下，用deque实现
- 用vector和deque实现，比用list实现性能好
push，pop，top函数均在栈顶

Queue

实现：

template<class T，class Cont=deque<T>>
class queue{
}；

和stack 基本类似，可以用list和deque实现
缺省情况下用deque实现
push在队尾，pop，top函数均在队头

Priority_queue

和queue类似，可以用vector和deque实现
缺省情况下用vector实现
priority_queue 通常用堆排序技术实现，保证最大的元素总是在最前面
- 执行pop操作时，删除的是最大的元素
- 执行top操作时，返回的是最大元素的引用
默认的元素比较器是less<T>

任世事无常，勿忘初心

C++ 之 标准模板库（STL）的容器与迭代器

标准模板库

容器概述

顺序容器

关联容器

容器适配器

顺序/关联容器中均有的成员函数

顺序容器常用函数

迭代器

双向迭代器

随机访问迭代器

容器容器上的迭代器类别

容器详解

顺序容器

Vector

List

Deque

关联容器

Multiset

Set

Multimap

Map

实用类模板bitset

容器适配器详解

Stack

Queue

Priority_queue

C++ 之标准模板库（STL）的容器与迭代器