原文地址：
http://blog.csdn.net/nishijibama/article/details/11852523
STL主要包含容器、算法、迭代器三大核心部分；
序列式容器中的元素顺序与元素值无关，只与元素插入的次序和存放位置有关;三种序列式容器，即Vectors（向量）、Deque（双向队列）和List（双向链表）。
vector：向量容器;
关联式容器中的元素位置是按元素值的大小自动排序的，缺省情况下为升序排列。其元素顺序与元素值有关，与元素插入的先后次序无关。关联式容器的底层实现是二叉搜索树的形式。关联式容器有Sets与Multisets(集合与多重集合)以及Map与Multimap(映射与多重映射) 。
迭代器
容器负责存储数据元素，算法负责加工处理数据元素，那么是谁负责将数据元素从容器里提取出来交给算法去处理呢？又是谁负责将算法处理过的数据元素写入容器呢？这项任务由迭代器负责完成。迭代器将容器与算法耦合起来，通过迭代器可以对容器内任意位置上的元素进行定位和存取(access)。
可以把迭代器看作一个类似于指向容器中元素的被泛化了的普通指针。可以像递增一个指针那样递增迭代器，使其依次指向容器中每一个后继元素；反之，也可以像递减一个指针那样递减迭代器，使其依次指向容器中每一个前驱元素。尽管迭代器类似于指针，但迭代器决不是普通的指针。它们的区别是：指针是指向它所要访问的数据元素的地址，而迭代器是指向它所要访问的数据元素的位置(即容器的某个位置的下标)。但它们也有相同之处，即要访问它们所指的数据元素时，都是在其前面缀“*”运算符。
容器负责存储数据元素，算法负责处理数据元素。而迭代器则负责从容器中存取一个个数据元素提交给算法去进行处理，或者将算法处理完的数据元素放入容器。因此，迭代器将算法和容器连在一起.STL把迭代器作为算法的参数而非把容器直接作为算法的参数。函数对象也可作为算法的参数。
各类容器的共性——各类容器一般来说都有下列成员函数，并且，由于它们都重载了比较运算符，所以它们都允许比较判断运算(设c1和c2是两个类型相容的容器对象) ：
·默认构造函数： 提供容器默认初始化构造函数
·复制构造函数： 将容器初始化为现有同类容器副本的构造函数
·析构函数： 不再需要容器时进行内存整理的析构函数
·c1.empty()： 若c1内没有数据元素存在返回true,否则返回false
· c1.max_size()： 返回c1中的最大元素个数
· c1.size()： 返回c1中当前实有元素个数
· c1.swap(c2)： 交换c1和c2的元素
下面的比较运算均返回true或者false：
·c1 = c2
·c1 < c2
·c1 <= c2
· c1 > c2
· c1 >= c2
· c1 == c2
· c1 != c2
容器类似于类，如容器vector(类) 内部包含一个动态数组，一个指向这个数组位置的迭代器(指针)（迭代器的定义为： vector<int>::iterator i），还有类vector 内部的一些函数方法vecList.clear()，vecList.erase(position)，vecList.insert(position, elem) ，vecList.push_back(elem)。容器list内部包含一个双向链表，一个指向这个数组的迭代器(指针)，还有类 内部的一些函数方法。算法则是独立于容器的全局函数。算法直接操作迭代器。(蓝色字体部分纯属个人理解，便于自己理解记忆，不一定对，请注意。)
vector类内嵌了一个iterator类，它是vector类的一个public成员。通过iterator类可以声明向量容器的一个或多个迭代器，例如语句：
vector<int>::iterator intVeciter; 将intVecIter声明为int类型的向量容器迭代器。
for (intVecIter = intList.begin(); intVecIter != intList.end();++intVecIter);
向量容器迭代器的运算表达式
++intVecIter 将迭代器intVecIter前移一个位置，使其指向容器中的下一个元素；
--intVecIter 将迭代器intVecIter后移一个位置，使其指向容器中的前一个元素；
*intVecIter 返回当前迭代器位置上的元素值。
容器的成员函数begin()和end()
不仅仅向量容器，所有容器都包含成员函数begin()和end()。函数begin()返回容器中第一个元素的位置；函数end()返回容器中最后一个元素的下一个位置。这两个函数都没有参数。
Deque双端队列
可以在其头尾两端插入或删除元素，而且十分迅速.push_front().也可以使用成员函数push_back()在deque尾部追加元素；vector并未提供在vector头部添加元素的push_front()成员函数。
Deque是双向队列，操作Deque的成员函数如下：
函 数
描 述
备注
assign(beg,end)
assign(n,elem)
给[beg; end) 区间赋值
将n个elem 的拷贝赋值
at(idx)
传回索引 idx 所指的数据，若idx 越界，抛出out_of_range
back()
传回最后一个数据，不检查这个数据是否存在
begin()
传回迭代器重的可一个数据
clear()
移除容器中所有数据
deque c1(c2)
deque c(n)
deque c(n, elem)
deque c(beg,end)
~deque()
复制一个deque
创建一个deque,含有n个数据,数据均已缺省构造产生
创建一个含有n个elem 拷贝的 deque
创建一个以[beg;end)区间的 deque
销毁所有数据，释放内存
构造函数
构造函数
构造函数
构造函数
析构函数
empty()
判断容器是否为空
end()
指向迭代器中的最后一个数据地址
erase(pos)
erase(beg,end)
删除pos位置的数据，传回下一个数据的位置
删除[beg,end)区间的数据,传回下一个数据的位置
front()
传回地一个数据
get_allocator
使用构造函数返回一个拷贝
insert(pos,elem)
insert(pos,n,elem)
insert(pos,beg,end)
在pos位置插入一个elem拷贝,传回新数据位置
在pos位置插入n 个elem数据,无返回值
在pos位置插入在[beg,end)区间的数据,无返回值
max_size()
返回容器中最大数据的数量
pop_back()
删除最后一个数据
pop_front()
删除头部数据
push_back(elem)
在尾部加入一个数据
push_front(elem)
在头部插入一个数据
rbegin()
传回一个逆向队列的第一个数据
rend()
传回一个逆向队列的最后一个数据的下一个位置
resize(num)
重新指定队列的长度
size()
返回容器中实际数据的个数
c1.swap(c2)
swap(c1,c2)
将 c1 和 c2 元素互换
同上操作
operator []
返回容器中指定位置的一个引用
Lists
List是(带头结点的)双向链表（doublelinked list），它是一种双线性列表。只能顺序访问它（从前向后或者从后向前逐个访问）。
List与向量和双端队列两种容器类有一个明显的区别就是：它不支持随机访问(所以没有成员函数 at(pos)和operator[])。要访问list中某个数据元素只能从表头或表尾处开始循环进行（可以通过迭代器来双向遍历读取）。list容器不提供对capacity()和内存维护相关的接口，因为list容器中的每个元素分配自己的内存空间，当元素删除时，其对应的内存空间自动销毁。List的优势是可以在其任何位置上插入或删除元素，而且比较迅速(不需要移动元素)。若程序中使用List容器，那么，必需先包含<list>头文件。
关联式容器
对于关联式容器，一是要注意这类容器具有自动排序能力，即它们内部的元素总是时刻自动有序的；二是要注意使用Set(集合) 和Multisets(多重集合)之前，必须先包含头文件<set>，而使用Map 和Multimap之前，必须先包含头文件<map>；三是要注意它们支持双向迭代器，但不支持随即迭代器，因此不能随即存取其元素。
一个集合（set）是一个容器，其所包含的元素的值是唯一的，而Multisets所包含的元素的值可以不唯一(即可以有重复元素)。注意，集合(set）与多重集合(Multisets)的内部数据组织是一颗红黑树(一种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能，因此，set和Mutilset内部的所有数据元素是自动有序的。
map（映射）是经过排序的二元组集合，map中的每个元素都是由两个值组成，其中key键值必须是唯一，而另一个值是该元素关联的数值。multimap（多重映射）和映射（map）相似，但其中的键值可以有重复值。map与multimap内部数据的组织也是一颗红黑树，所以它们内部所有的数据元素也都是自动有序的。
操作Set 和Multisets的成员函数及算法
(1)构造函数
定义一个元素为整数的集合intSet，可以用：
set<int> intSet;
(2) 数据元素基本操作方面的成员函数
Ø 插入元素i：intSet.insert(i);
Ø 删除元素i（如果存在）：intSet.erase(i);
Ø 判断元素i是否属于集合： if (intSet.find(i) != intSet.end()) ...
Ø 返回集合元素的个数：intSet.size()；
Ø 判断集合是否空：bool empty() const;
Ø 将集合清为空集：intSet.clear()。
问题：如何判断一个元素是否在Set中？
方法1：用成员函数count()来判定关键字是否出现，若出现返回值是1，否则返回0。比如查找关键字1是否出现：
int index ＝ intSet. count(1);
方法2：用成员函数find()来定位数据元素出现位置，它返回一个迭代器，当set中包含该数据元素时，返回数据元素所在位置的迭代器；如果不包含，返回的迭代器等于end函数返回的迭代器。比如查找关键字1是否出现：
if (intSet.find(1) == intSet.end())
cout<<”Not Find ”<<1<<endl;
else
cout<<” Find value ”<<1<<endl;
(3) 遍历方面的成员函数
·iterator begin(); //返回首元素的迭带器指针
·iterator end(); //返回尾元素后的迭带器指针，而不是尾元素的迭带器指针
·reverse_iterator rbegin(); //返回尾元素的逆向迭带器指针，用于逆向遍历容器
·reverse_iterator rend(); //返回首元素前的逆向迭带器指针，用于逆向遍历容器
(4) 其它操作方面的成员函数
·const_iterator lower_bound(const Key& key); //返回容器元素等于key迭代指针，//否则返回end()
·const_iterator upper_bound(const Key& key);
·int count(const Key& key) const; //返回容器中元素值等于key的元素个数
·pair<const_iterator , const_iterator> equal_range(const Key& key) const; // 返回//容器中元素值等于key的迭代指针[first, last)
·const_iterator find(const Key& key) const; //查找功能返回元素值等于key迭代器指针
·void swap(set& s); //交换单集合元素
·void swap(multiset& s); //交换多集合元素
(5) 集合的算法
STL中的算法包含在 <algorithm> 头文件中，集合的算法也包含在该头文件中。
Ø 集合的并：set_union
Ø 集合的交：set_intersection
Ø 集合的差：set_difference
操作Maps和Multimaps的成员函数
map是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可称为该关键字对应的值，即即一个数据元素为key/ value对的形式）的数据处理能力。map内部数据的组织也是一棵红黑树，所以map内部所有的数据元素都是自动有序的。
那么什么是一对一的数据映射？比如一个班级中，每个学生的学号跟他的姓名就存在着一一映射的关系，这个模型用map可以轻易描述，很明显学号用int描述，姓名用char *字符串描述，如下面的map描述代码：
map<int, char*> mapStudent;
一、STL中的通用工具pair与make_pair的用法
C++ STL预定义了几个通用工具类(或结构体)、函数等，结构体pair与函数make_pair()就是其中的两个。它们定义在通用工具头文件<utility>内，使用它们之前必需包含此头文件。
1、pair的应用
Pair的用途是将2个数据构造为一个数据元素(通过其构造函数)。当有这样的需求时就可以使用pair来构造，如STL中的容器map就是将key和value放在一起作为一个元素来保存的，因此，构造map的数据元素时就要用到pair。pair的另一个应用是，当一个函数需要返回2个值的时候，可以选择pair这种数据类型。 pair的实现是一个结构体，主要的两个成员变量是first 和second。 因定义pair是使用struct不是class，所以可以直接使用pair的成员变量(因为struct的成员都是public成员)。
std::pair模型：
template <class T1, class T2>
struct pair
{
T1 first; //key值部分
T2 second; //value部分
pair(const T1 a, const T2 b) : first(a), second(b) { } //构造函数
};
如：std::pair<int, float>(3, 1.1);将构造一个视为一个数据元素整体来对待的数对（3，1.1），其中3为int型，1.1为float型。
1、 便捷函数make_pair()
便捷函数make_pair()的作用也是将2个数据构造为一个数据元素(make_pair()的返回值)。make_pair()的函数模版声明如下：
template <class T1, class T2>
pair<T1,T2> make_pair (const T1 x, const T2 y)
{
return pair<T1,T2>(x, y); //调用pair类的构造函数
}
例如：std::make_pair(42,‵@′);与std::pair<int, char>(42,‵@′);都是返回一个由(42,‵@′)组成的数对(42,‵@′)，显然，std::make_pair(42,‵@′)更简便，而pair在有些编译器下不允许这么简便写。
二、操作Maps和Multimaps的成员函数
(1)构造函数
map共提供了6个构造函数，通常用图2-13所示的方法构造一个Map。
图2-13
构造map的常用方法
(2)数据的插入的三种方法
第一种方法：用insert函数插入pair数据
mapStudent.insert(pair<int, char*>(1, “student_one”));
第二种方法：用insert函数插入value_type数据
mapStudent.insert(map<int, char*>::value_type(1, “student_one”));
第三种方法：用数组方式插入数据
mapStudent[1] = “student_one”;
mapStudent[2] = “student_two”;
(3) 数据的删除
//如果要删除数据元素1,用迭代器删除
map<int, string>::iterator iter;
iter = mapStudent.find(1);
mapStudent.erase(iter);
(4) 数据的查找
第一种方法：用count函数来判定关键字是否出现，返回1，元素存在；否则返回1。比如查找关键字1是否存在？
int index ＝ mapStudent. count(1);
第二种方法：用find函数来定位数据出现位置，它返回的一个迭代器，当数据出现时，它返回数据所在位置的迭代器，如果map中没有要查找的数据，它返回的迭代器等于end函数返回的迭代器:
map<int, char*>::iterator iter;
iter = mapStudent.find(1);
if (iter != mapStudent.end())
cout<<”Find, the value is ”<<iter->second<<endl;
else
cout<<”Do not Find”<<endl;
(5) 数据的其它基本操作
Ø 返回map元素的个数： mapStudent.size();
Ø 将map清为空集：mapStudent.clear() ;
Ø 判断map是否为空：mapStudent.Empty() ;
Ø 数据的遍历：比如用数组方式
int nSize = mapStudent.size();
for(int nIndex = 0; nIndex < nSize; nIndex++)
{
cout<<mapStudent[nIndex]<<end;
}
(6)其它)操作函数
·void swap(map& s); //交换单映射元素
·void swap(multimap& s); //交换多映射元素
(7)特殊函数
·reference operator[](const Key& k); //仅用在单映射map类中，可以以数组的形式//给映射添加键---值对，并可返回值的引用
vector,list,deque,set,map of STL[转载]
List封装了链表,Vector封装了数组, list和vector得最主要的区别在于vector使用连续内存存储的，他支持[]运算符，而list是以链表形式实现的，不支持[]。 Vector对于随机访问的速度很快，但是对于插入尤其是在头部插入元素速度很慢，在尾部插入速度很快。List对于随机访问速度慢得多，因为可能要遍历整个链表才能做到，但是对于插入就快的多了，不需要拷贝和移动数据，只需要改变指针的指向就可以了。另外对于新添加的元素，Vector有一套算法，而List可以任意加入。 Map,Set属于标准关联容器，使用了非常高效的平衡检索二叉树：红黑树，他的插入删除效率比其他序列容器高是因为不需要做内存拷贝和内存移动，而直接替换指向节点的指针即可。 Set和Vector的区别在于Set不包含重复的数据。Set和Map的区别在于Set只含有Key，而Map有一个Key和Key所对应的Value两个元素。 Map和Hash_Map的区别是Hash_Map使用了Hash算法来加快查找过程，但是需要更多的内存来存放这些Hash桶元素，因此可以算得上是采用空间来换取时间策略。 vector - 会自动增长的数组 vector又称为向量数组，他是为了解决程序中定义的数组是不能动态改变大小这个缺点而出现的。一般程序实现是在类创建的时候同时创建一个定长数组，随着数据不断被写入，一旦数组被填满，则重新开辟一块更大的内存区，把原有的数据复制到新的内存区，抛弃原有的内存，如此反复。 由于程序自动管理数组的增长，对于我们程序员来说确实轻松了不少，只管把数据往里面插就行了，当然把物理内存和虚拟内存插爆掉了就是操作系统来找你麻烦了:-) vector由于数组的增长只能向前，所以也只提供了后端插入和后端删除，也就是push_back和pop_back。当然在前端和中间要操作数据也是可以的，用insert和erase，但是前端和中间对数据进行操作必然会引起数据块的移动，这对性能影响是非常大的。对于所有数组来说，最大的优势就是随机访问的能力。 在vector中，提供了at和[]运算符这两个方法来进行随机访问。由于每个数据大小相同，并且无间隔地排列在内存中，所以要对某一个数据操作，只需要用一个表达式就能直接计算出地址：address = base + index * datasize同样，对vector进行内存开辟，初始化，清除都是不需要花大力气的，从头到尾都只有一块内存。list - 擅长插入删除的链表有黑必有白，世界万物都是成对出现的。链表对于数组来说就是相反的存在。数组本身是没有动态增长能力的（程序中也必须重新开辟内存来实现），而链表强悍的就是动态增长和删除的能力。但对于数组强悍的随机访问能力来说的话，链表却很弱。list是一个双向链表的实现。为了提供双向遍历的能力，list要比一般的数据单元多出两个指向前后的指针。这也是没办法的，毕竟现在的PC内存结构就是一个大数组，链表要在不同的环境中实现自己的功能就需要花更多空间。 list提供了push_back，push_front，pop_back，pop_front四个方法来方便操作list的两端数据的增加和删除，不过少了vector的at和[]运算符的随机访问数据的方法。并不是不能实现，而是list的设计者并不想让list去做那些事情，因为他们会做得非常差劲。对于list来说，清除容器内所有的元素是一件苦力活，因为所有数据单元的内存都不连续，list只有一个一个遍历来删除。 deque - 拥有vector和list两者优点的双端队列黑与白，处于这两个极端之间的就是令人愉悦的彩色了。deque作为vector和list的结合体，确实有着不凡的实力。STL的deque的实现没有怎么去看过，不过根据我自己的猜测，应该是把数组分段化，在分段的数组上添加指针来把所有段连在一起，最终成为一个大的数组。 deque和list一样，提供了push_back，push_front，pop_back，pop_front四个方法。可以想象，如果要对deque的两端进行操作，也就是要对第一段和最后一段的定长数组进行重新分配内存区，由于分过段的数组很小，重新分配的开销也就不会很大。deque也和vector一样，提供了at和[]运算符的方法。要计算出某个数据的地址的话，虽然要比vector麻烦一点，但效率要比list高多了。首先和list一样进行遍历，每次遍历的时候累积每段数组的大小，当遍历到某个段，而且baseN <= index < baseN + baseN_length的时候，通过address = baseN + baseN_index就能计算出地址由于分过段的后链表的长度也不是很长，所以遍历对于整体性能的影响就微乎其微了。 看起来deque很无敌吧，不过deque和希腊神话的阿吉里斯一样，再怎么强大也是有自己的弱点的，之后的测试数据中就能看到了。