标准模板类(STL)(一)，综述、容器及其操作

C++的 STL 是一个功能强大的库，它是建立在模板机制上，能够满足用户对存储管理不同类型数据的通用容器和施加在这些容器上的通用算法的巨大需求，并且具有完全的可移植性。因此在寻求程序的解决方案时，应该首先在 STL 中寻求恰当的容器和算法。

STL 是一个通用性极高的编程工具，这种通用性不仅表现在可以使用通用的容器存储和管理任意类型的数据，更重要的是可以对不同的容器施加统一通用的算法和操作。实现这种通用性的关键思想就是：通过引进一个间接层对象对不同结构的数据容器进行统一的访问操作，从而简化了对容器的操作，使得实现操作的算法和函数通用化。这种思想是 STL 的设计原则之一，也是软件设计中一个重要设计思想。 在 STL 中对容器访问的简化和独立就是通过循环子实现的，循环子可以无须依据某种特定容器的数据结构而完成对容器元素的访问，从而使得数据的存储结构与施加于数据的操作相互独立。标准模板库 STL 是由容器类模板，用于访问这些容器的循环子类模板和可以通过循环子在这些容器上实现的各种算法类模板以及函数类模板组成的。STL 为这种标准算法和函数（包括用户定义的函数）借助循环子在容器上实现的应用建立了统一的规则。

容器：可容纳各种数据类型的数据结构。

迭代器：可依次存取容器中元素的东西，连接容器和算法

算法：用来操作容器中的元素的函数模板。例如，STL用sort()来对一个vector中的数据进行排序，用find()来搜索一个list中的对象。

函数本身与他们操作的数据的结构和类型无关，因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用。

比如，数组int array[100]就是个容器，而 int * 类型的指针变量就可以作为迭代器，可以为这个容器编写一个排序的算法

一、容器

(一)容器综述

    标准库中定义了两种标准的容器：

1、序列容器（Sequence）：向量 vector、表 list 和双向队列 deque。

vector：后部插入/删除，直接访问
deque：前/后部插入/删除，直接访问
list：双向链表，任意位置插入/删除

2、关联容器 (Associative container)

映射 map、multimap 和集合 set、multiset。

set：快速查找，无重复元素
multiset ：快速查找，可有重复元素
map：一对一映射，无重复元素，基于关键字查找
multimap ：一对一映射，可有重复元素，基于关键字查找

前两种合称为第一类容器。

3、序列转接器容器(又名容器适配器)（Sequence Adapter）

    是一种可以改变函数对象或容器接口的组件。

   序列转接器：堆栈 stack、队列 queue 和优先级队列priority_queue。

stack：LIFO
queue：FIFO
priority_queue：优先级高的元素先出 

对象被插入容器中时，被插入的是对象的一个复制品。

4、预定义数组、字符串类 string、数值数组类 valarray 和位集合 bitset 均可以视为容器，但不是标准容器。标准容器的成员绝大部分都具有共同的成员名。，

（1）类型成员

value_type	元素类型
allocator_type	内存管理器类型
size_type	下标，元素计数类型
difference_type	循环子之间差的类型
iterator	循环子，相当于value_type*
const_iterator	常循环子，相当于const value_type*
reverse_iterator	逆序循环子，相当于value_type*
const_reverse_iterator	常逆序循环子，相当于const value_type*
reference	元素引用，相当于value_type&
const_reference	元素常引用，相当于const value_type&
key_type	关键字类型（只用于关联包容器）
mapped_type	映射值类型（只用于关联包容器）
key_compare	比较标准类型（只用于关联包容器）

（2）循环子操作

begin()	指向第一个元素
end()	指向最后一个元素的后一个位置
rbegin()	指向逆序的第一个元素
rend()	指向逆序的最后一个元素的后一个位置

（3）访问元素操作

front()	访问第一个元素
back()	访问最后一个元素
[]	无测试的下标访问（不用于list）
at()	有测试的下标访问（只用于vector和deque）

front():返回容器中第一个元素的引用，back():返回容器中最后一个元素的引用。比如，查 list::front 的help,得到的定义是：

reference front(); 

const_reference front() const;

list有两个front函数

reference 和 const_reference 是typedef的类型

对于 list<double> , 

list<double>::reference  实际上就是 double &

list<double>::const_reference  实际上就是 const double &

对于 list<int> , 

list<int>::refrence  实际上就是 int &

list<int>::const_refreence  实际上就是 const int &

（4）堆栈和队列操作

push_back()	将新元素加入到尾部
pop_back()	移出最后一个元素
push_front()	将新元素加入/插入头部（只用于list和deque）
pop_front()	移出/删除第一个元素（只用于list和deque）

push_back(): 在容器末尾增加新元素

pop_back(): 删除容器末尾的元素

（5）表操作

insert(p,x)	将元素x加入到p之前
insert(p,n,x)	在p之前加入n个x的拷贝
insert(p,first,last)	在p之前加入区间[first,last)中的序列
erase(p)	删除p处的元素
erase(first,last)	删除区间[first,last)中的序列
clear()	清除所有的元素

（6）其他操作

size()	获取元素个数
empty()	测试包容器是否为空
max_size()	最大可能的包容器的大小
capacity()	为向量包容器分配的空间（只用于vector）
reserve()	为扩充向量包容器保留空间（只用于vector）
resize()	改变包容器的大小（只用于vector,list和deque）
swap()	交换两个包容器中的元素
get_allocator()	获取包容器的内存管理器的副本
==	测试两个包容器的内容是否相等
!=	测试两个包容器的内容是否不同
<	测试一个包容器是否在另一个包容器字典序之前

（7）构造函数，析构函数

container()	构造一个空容器
container(n)	用缺省值构造n个元素的容器（不能用于关联包容器）
container(n,x)	构造具有n个x拷贝的容器（不能用于关联包容器）
container(first,last)	初始化容器区间[first,last)上的元素
container(x)	容器拷贝构造函数
~container()	析构容器和它的全部元素

（8）分配操作

operator=(x)	从容器中x元素拷贝分配
assign(n,x)	为容器分配n个x的拷贝（不用于关联容器）
assign(first,last)	在容器的[first,last)区间中分配

（9）关联操作

operator[](k)	访问带有关键字k的元素（用于具有唯一关键字的包容器）
find(k)	查找带有关键字k的元素
lower_bound(k)	查找带有关键字k的第一个元素
upper_bound(k)	查找带有大于k的关键字的第一个元素
equal_range(k)	查找带有关键字k的元素的lower_bound和upper_bound
key_comp()	获取关键字比较对象的拷贝
value_comp()	获取映射值比较对象的拷贝

（10）标准容器的操作比较（复杂度）

	[]操作	表操作	Front操作	Back操作	循环子
vector	const	O(n)+		const+	Ran
list		const	const	const	Bi
deque	const	O(n)	const	const	Ran
stack				const
queue			const	const
priority_queue			O(log(n))	O(log(n))
map	O(log(n))	O(log(n))+			Bi
Multimap		O(log(n))+			Bi
set		O(log(n))+			Bi
multiset		O(log(n))+			Bi
string	const	O(n)+	O(n)+	O(n)+	Ran
array	const				Ran
valarray	const				Ran
bitset	const				Ran

表中各种容器所对应的表项的含义如下：

① 空表项：表示容器无此项操作。

② const：表示容器此项操作的时间复杂度为常量。

③ O(n)：表示容器此项操作的时间复杂度与容器中元素个数n的线性相关。

④ O(n)+：表示容器此项操作的时间复杂度与容器中元素个数n线性相关并且还需要增加一些附加操作时间花费。

⑤ O(log(n))：表示容器此项操作的时间复杂度与容器中元素个数n对数相关。

⑥ O(log(n))+：表示容器此项操作的时间复杂度与容器中元素个数n对数相关并且还需要增加一些附加操作时间花费。

⑦ Ran：表示容器对应的循环子为随机访问循环子。

⑧ Bi：表示容器对应的循环子为双向访问循环子。