STL容器概述

具体讲容器之前,我先简单的使用一个容器,知道使用的感觉

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

**迭代器：**可依次存取容器中元素的东西

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

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

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

容器概述

**概念:**可以用于存放各种类型的数据（基本类型的变量，对象等）的数据结构。

容器分为三大类：

1. 顺序容器

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

2. 关联容器

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

前2者合称为第一类容器

3.容器适配器

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

容器特点

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

许多算法，比如排序，查找，要求对容器中的元素进行比较，所以，放入容器的对象所属的类，还应该实现 == 和 < 运算符。

STL 中的迭代器

STL 中的迭代器按功能由弱到强分为5种：

1. 输入迭代器：Input iterators 提供对数据的只读访问。
2. 输出迭代器：Output iterators 提供对数据的只写访问
3. 正向迭代器：Forward iterators 提供读写操作，并能一次一个地向前推进迭代器。
4. 双向迭代器：Bidirectional iterators提供读写操作，并能一次一个地向前和向后移动。
5. 随机访问迭代器：Random access iterators提供读写操作，并能在数据中随机移动。

编号大的迭代器拥有编号小的迭代器的所有功能，能当作编号小的迭代器使用。

不同迭代器所能进行的操作(功能）

• 所有迭代器： ++p, p ++
• 输入迭代器： * p, p = p1, p == p1 , p!= p1
• 输出迭代器：* p, p = p1
• 正向迭代器： 上面全部
• 双向迭代器： 上面全部，--p, p --,
• 随机访问迭代器： 上面全部，以及：
  • 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的迭代器是随机迭代器，所以遍历 vector 可以有以下几种做法：

vector<int> v(100);
vector<int>::value_type i; //等效于写 int i;(P687)
for(i = 0;i < v.size() ; i ++)
	cout << v[i];
vector<int>::const_iterator ii;
for( ii = v.begin(); ii != v.end ();ii ++ )
	cout << * ii;
//间隔一个输出：
ii = v.begin();
while( ii < v.end()) {
	cout << * ii;  
	ii = ii + 2; 
}

而 list 的迭代器是双向迭代器，所以以下代码可以：

	list<int> v;
	list<int>::const_iterator ii;
	for( ii = v.begin(); ii ！＝ v.end ();ii ++ )
		cout << * ii;	

以下代码则不行：

	for( ii = v.begin(); ii < v.end ();ii ++ )
		cout << * ii;	
	//双向迭代器不支持 <
	for(int i = 0;i < v.size() ; i ++)
		cout << v[i]; //双向迭代器不支持 []