C++ STL结构总结

1. 什么是STL

　　它的全名是stand template library, 标准模板库，主要是将一些结构和算法写成模板，以便能够实现对任意类型的对象都可以操作，而不需要再一次去写一些算法及结构。

　　它主要有以下三个概念：

　　　　容器－－容纳各种数据类型的结构，是类模板

　　　　迭代器－－类似于指针，指向容器内的对象的指针，主要用于指向元素

　　　　算法－－操作容器内的元素的运算函数，是函数模板，比如sort,find等排序算法，查找 算法，它与容器内元素类型无关

2.  容器

　　用于存放数据的容器可以分为三大类，顺序容器，关联容器，容器适配器：

　　顺序容器－－vector, list, deque

　　关联容器－－map, multimap, set, multiset

　　容器适配器－－stack, queue, priority_queue

2.1 顺序容器

　　顺序容器是无序的，插入的元素位置与值无关。

　　vector容器，头文件<vector>, 是一个动态数据，元素在内存中是连续存放的，可以随意取vector中的元素。　

　　deque, 头文件<deque>, 是一个双向队列，元素在内存中连续存放，可任意取容器中的元素，与vector中不一样的是，它存在一个头指针和一个尾指针，如

　　list, 头文件<list>， 是一个双向链表，元素内存中不连续存放，易添加删除元素，不可随意存取元素。

2.2 关联容器

　　关联容器是有序的，插入元素的同时对新加元素进行排序，如何排序取决于元素类中<符号的成员函数重载， 所有的容器都是以平衡二叉树来实现，查找时间为O(lgn).

　　set/multiset, 头文件<set>, 又称集合，两者唯一的区别是set不允许多个元素相等，而multiset则可以存放多个相等的元素，至于两个元素相等的定义为：

如元素A不小于元素B，也不大于B，则A与B相等。因此在此仍需要重载容器内元素类的<符号函数，才能让容器函数对元素进行大小比较。

　　map/multimap, 头文件<map>, 又称字典，元素内存在两个成员变量：first与second，它们一一对应，容器内以first的大小进行排序，first为key，second为first对应的值。multimap允许存在first相同的元素，而map则要求所有的元素first中值唯一。

2.3 容器适配器

　　stack,头文件<stack>, 栈，遵守先进后出的规则

　　queue,头文件<queue>, 队列， 元素先进先出，如图

　　priority_queue, 优先级队列，头文件<queue>, 内部以一定的顺序排列，优先级最高的元素第一个出列。

2.4  容器中的成员函数

　　顺序容器与关联容器的公有成员函数：

　　　　begin-- 返回指向第一个元素的迭代器

　　　　end--返回指向最后一个元素的后一个迭代器

　　　　rbegin--返回指向最后一个元素的迭代器

　　　　rend--返回指向第一个元素的前一个迭代器

　　　　erase -- 删除容器中的一个或几个元素

　　　　clear -- 删除容器内所有的元素

　　顺序容器的成员函数：

　　　　front -- 返回第一个元素的引用

　　　　back -- 返回最后一个元素的引用

　　　　push_back -- 在容器尾添加新元素

　　　　pop_back -- 删除容器尾的元素

　　　　erase -- 删除迭代器指向的元素或一个区间内的所有元素，返回删除元素的下一个元素的迭代器

3. 迭代器

　　类似于指针的用法，主要用于指向元素对象的位置，其定义如下：

　　　　容器类名::iterator  it;

　　　　容器类名::const_iterator  it;  //常量迭代器，不可修改对象的值

　　　　容器类名::reverse_iterator  it; //反向迭代器， it++指向前一个元素，如果是正向迭代器，则指向下一个元素

　　比较特殊的迭代器就是随机迭代器，可以进行操作 it + i， 直接跳进i个元素