STL的组成
标准模板库STL关注的重点是泛型数据结构和算法，其关键组成部分是容器(containers)、算法(algorithms)、迭代器(iterators)、函数对象(Function Object)、适配(Adaptor)。
本文地址：http://www.cnblogs.com/archimedes/p/Cpp-STL-Vector.html，转载请注明源地址。
容器(containers)：容器是数据在内存中组织的方法，例如，数组、堆栈、队列、链表或二叉树(不过这些都不是STL标准容器)。
STL 中的容器是一种存储T (Template)类型值的有限集合的数据结构,
容器的内部实现一般是类。这些值可以是对象本身，如果数据类型T代表的是Class的话。
算法(algorithms)：算法是应用在容器上以各种方法处理其内容的行为或功能。例如，有对容器内容排序、复制、检索和合并的算法。在
STL中，算法是由模板函数表现的。这些函数不是容器类的成员函数。相反，它们是独立的函数。它们不仅可以将其用于STL容器，而且可以用于普通的C++
数组或任何其他应用程序指定的容器。
迭代器(iterators)
：一旦选定一种容器类型和数据行为(算法)，那么剩下唯一要他做的就是用迭代器使其相互作用。可以把迭代器看作一个指向容器中元素的普通指针。可以如递增
一个指针那样递增迭代器，使其依次指向容器中每一个后继的元素。迭代器是STL 的一个关键部分，因为它将算法和容器连在一起。
函数对象(Function Object)：定义了函数调用操作符(operator())的类
适配器(adaptor)：封装一个部件以提供另外的接口(例如用list实现stack)
容器的分类:
- 序列式容器（Sequence containers）
- 每个元素都有固定位置－－取决于插入时机和地点，和元素值无关。
- vector(向量)、deque(双端队列)、list(表)
- 关联式容器（Associated containers）
- 元素位置取决于特定的排序准则，和插入顺序无关
- set(集合)、multiset(多重集合)、
- pmap(映射)、multimap(多重映射)
向量（vector）
向量(vector 容器类):#include <vector> ，vector 是一个能够存放任意类型的动态数组，是基本数组的类模板。其内部定义了很多基本操作。
内部实现: 数组
vector <T, Alloc>
可以随机存取数据（用索引直接存取）。
向量尾部添加或删除数据,耗时O(1)。但是在中部或头部插入或删除数据需要移动后面数据,耗时O(N)。
vector 类中定义了4 中种构造函数：
- 默认构造函数，构造一个初始长度为0 的空向量，如： vector<int> v1 ;
- 带有单个整形参数的构造函数，此参数描述了向量的初始大小。这个构造函数还有一个可选的参数，这是一个类型为T的实例，描述了这个向量中各成员的初始值；如： vector<int> v2(n,0); 如果预先定义了 n, 他的成员值都被初始化为0；
- 复制构造函数，构造一个新的向量，作为已存在的向量的完全复制，如： vector<int> v3(v2) ;
- 带两个常量参数的构造函数，产生初始值为一个区间的向量。区间由一个半开区间 [ first,last ) 来指定。如： vector<int> v4(first,last)
举例：
#include <cstring>
#include <vector>
#include <iostream>
using namespace std;
int ar[10] = { 12, 45, 234, 64, 12, 35, 63, 23, 12, 55 };
char* str = "Hello World";
int main()
{
vector <int> vec1(ar, ar + 10); // first=ar,last=ar+10, 不包括ar+10
vector < char > vec2(str, str + strlen(str)); // first=str,last= str+strlen(str)
cout << "vec1:" << endl;
// 打印vec1 和vec2 ，const_iterator 是迭代器，后面会讲到
// 当然，也可以用for (int i=0; i<vec1.size(); i++)cout << vec[i]; 输出
//size() 是vector 的一个成员函数
for (vector<int>::const_iterator p = vec1.begin();p != vec1.end(); ++p)
cout << *p;
cout << '\n' << "vec2:" << endl;
for (vector< char >::const_iterator p1 = vec2.begin();p1 != vec2.end(); ++p1)
cout << *p1;
cout << '\n';
return 0;
}
vector操作：
头文件 #include<vector>
定义变量 vector<int> myvec;
主要成员函数
- myvec.clear() 移除容器中所有数据。
- myvec.push_back(elem) 在尾部加入一个数据elem。
- myvec.pop_back() 删除最后一个数据。
- myvec.size() 返回容器中实际数据的个数,类型为size_type。
- myvec.erase(pos) 删除pos位置的数据，返回下一个数据的位置。
- myvec.insert(pos,cnt,elem) 在pos位置插入cnt个数据elem。
- myvec.begin() 返回的指针指向数组中的第一个数据。
- myvec.end() 实际上是取末尾加一，以便让循环正确运行--它返回的指针指向最靠近数组界限的数据。
- myvec.empty() 判断容器是否为空。
- operator[] 返回容器中指定位置的一个引用
vector举例：
#include <iostream>
#include <vector>
using namespace std;
typedef vector<int> INTVECTOR;// 自定义类型INTVECTOR
int main() { // 测试vector 容器的功能
INTVECTOR vec1;//vec1 对象初始为空
INTVECTOR vec2(10, 6);//vec2 对象最初有10 个值为6 的元素
INTVECTOR vec3(vec2.begin(), vec2.begin() + 3);//vec3 对象最初有3 个值为6 的元素，拷贝构造
INTVECTOR::iterator i;// 声明一个名为i 的双向迭代器
cout << "vec1.begin()--vec1.end():" << endl;// 从前向后显示vec1 中的数据
for (i = vec1.begin(); i != vec1.end(); ++i) cout << *i << " "; cout << endl;
cout << "vec2.begin()--vec2.end():" << endl;// 从前向后显示vec2 中的数据
for (i = vec2.begin(); i != vec2.end(); ++i) cout << *i << " "; cout << endl;
cout << "vec3.begin()--vec3.end():" << endl;// 从前向后显示vec3 中的数据
for (i = vec3.begin(); i != vec3.end(); ++i) cout << *i << " "; cout << endl;
// 测试添加和插入成员函数，vector 不支持从前插入
vec1.push_back(2); // 从后面添加一个成员
vec1.push_back(4);
vec1.insert(vec1.begin() + 1, 5);// 在vec1 第一个的位置上插入成员5
vec1.insert(vec1.begin() + 1, vec3.begin(), vec3.end());// 从vec1 第一的位置开始插入vec3 的所有成员
cout << "after push() and insert() now the vec1 is:" << endl;
for (i = vec1.begin(); i != vec1.end(); ++i) cout << *i << " ";
cout << endl;
// 测试赋值成员函数
vec2.assign(8, 1); // 重新给vec2 赋值，8 个成员的初始值都为1
cout << "vec2.assign(8,1):" << endl;
for (i = vec2.begin(); i != vec2.end(); ++i)
cout << *i << " ";
cout << endl;
// 测试引用类函数
cout << "vec1.front()=" << vec1.front() << endl;// vec1 第零个成员
cout << "vec1.back()=" << vec1.back() << endl;// vec1 的最后一个成员
cout << "vec1.at(4)=" << vec1.at(4) << endl;// vec1 的第五个成员
cout << "vec1[4]=" << vec1[4] << endl;
// 测试移出和删除
vec1.pop_back();// 将最后一个成员移出vec1
vec1.erase(vec1.begin() + 1, vec1.end() - 2);// 删除成员
cout << "vec1.pop_back() and vec1.erase():" << endl;
for (i = vec1.begin(); i != vec1.end(); ++i)
cout << *i << " ";
cout << endl;
// 显示序列的状态信息
cout << "vec1.size(): " << vec1.size() << endl;// 打印成员个数
cout << "vec1.empty(): " << vec1.empty() << endl;// 清空
return 0;
}