首页 > 代码库 > ＳＴＬ 容器详解
ＳＴＬ 容器详解
STL的容器可以分为以下几个大类:
一：序列容器， 有vector, list, deque, string.
二 : 关联容器, 有set, multiset, map, mulmap, hash_set, hash_map, hash_multiset, hash_multimap
三: 其他的杂项： stack, queue, valarray, bitset
| 标准容器类 | 说明 |
| 顺序性容器 | |
| vector | 从后面快速的插入与删除，直接访问任何元素 |
| deque | 从前面或后面快速的插入与删除，直接访问任何元素 |
| list | 双链表，从任何地方快速插入与删除 |
| 关联容器 | |
| set | 快速查找，不允许重复值 |
| multiset | 快速查找，允许重复值 |
| map | 一对多映射，基于关键字快速查找，不允许重复值 |
| multimap | 一对多映射，基于关键字快速查找，允许重复值 |
| 容器适配器 | |
| stack | 后进先出 |
| queue | 先进先出 |
| priority_queue | 最高优先级元素总是第一个出列 |
容器类型
| vector | 容器，支持快速随机访问（连续存储） |
| list | 链表，支持快速插入/删除 |
| deque | 双端队列，支持随机访问（连续存储），两端能快速插入和删除 |
| stack | 栈 |
| queue | 队列 |
| priority_queue | 优先级队列 |
| *iter | 返回类型iter所指向的元素的引用 |
| iter->mem | 对iter进行解引用，并取得指定成员 |
| ++iter | 给iter加1，使其指向容器中下一个元素 |
| iter++ | |
| --iter | 给iter减1，使其指向容器中前一个元素 |
| iter-- | |
| iter1 == iter2 | 当两个迭代器指向同一个容器中的同一元素，或者当它们都指向 |
| iter1 != iter2 | 同一个容器的超出末端的下一个位置时，两个迭代器相等。 |
| iter + n | 在迭代器上加（减）整数值，将产生指向容器中前面（后面）第n个元素的迭代器； |
| iter - n | 新计算出来的迭代器必须指向容器中的元素或超出容器末端的下一位置。 |
| iter1 += iter2 | 复合运算：先加（减），再赋值 |
| iter1 -= iter2 | |
| iter1 - iter2 | 只适用于vector和deque |
| >, >=, <, <= | 比较迭代器的位置关系；只适用于vector和deque |
| back() | 返回容器的最后一个元素的引用。如果容器为空，则该操作未定义 |
| front() | 返回容器的第一个元素的引用。如果容器为空，则该操作未定义 |
| c[n] | 返回下标为n的元素的引用；如果n<0 or n>=size()，则该操作未定义 |
| at[n] | 返回下标为n的元素的引用；如果下标无效，则抛出异常out_of_range异常 （注：只适用于vector和deque容器） |
| erase(p) | 删除迭代器p所指向的元素。返回一个迭代器，它指向被删除的元素后面的元素。如果p指向容器内最后一个元素，则返回的迭代器指向容器的超出末端的下一个位置；如果p本身就是指向超出末端的下一个位置的迭代器，则该函数未定义 |
| erase(b, e) | 删除[b, e)内的所有元素。返回一个迭代器，它指向被删除元素段后面的元素。如果e本身就是指向超出末端的下一个位置的迭代器，则返回的迭代器也指向超出末端的下一个位置。 |
| clear() | 删除容器内的所有元素，返回void |
| pop_back() | 删除容器内的最后一个元素，返回void。如果容器为空，则该操作未定义。 |
| pop_front() | 删除容器内的第一个元素，返回void。如果c为空容器，则该操作未定义 （注：只适用于list和deque容器） |
| c1 = c2 | 删除容器c1的所有元素，然后将c2的元素复制给c1。c1和c2的类型必须相同。 |
| c1.swap(c2) | 交换内容：调用该函数后，c1中存放的是c2原来的元素，c2中存放的是c1原来的元素。c1和c2的类型必须相同。该函数的执行速度通常要比将c2的元素复制到c1的操作快。 |
| c.assign(b, e) | 重新设置c的元素：将迭代器b和e标记的范围内所有的元素复制到c中。b和e必须不是指向c中元素的迭代器。 |
| c.assign(n, t) | 将容器c重新设置为存储n个值为t的元素。 |
vector （连续的空间存储,可以使用[]操作符）快速的访问随机的元素，快速的在末尾插入元素，但是在序列中间岁间的插入，删除元素要慢，而且如果一开始分配的空间不够的话，有一个重新分配更大空间，然后拷贝的性能开销。
deque （小片的连续，小片间用链表相连，实际上内部有一个map的指针，因为知道类型，所以还是可以使用[]，只是速度没有vector快）快速的访问随机的元素，快速的在开始和末尾插入元素，随机的插入，删除元素要慢，空间的重新分配要比vector快,重新分配空间后，原有的元素不需要拷贝。对deque的排序操作，可将deque先复制到vector，排序后在复制回deque。
list （每个元素间用链表相连）访问随机元素不如vector快，随机的插入元素比vector快，对每个元素分配空间，所以不存在空间不够，重新分配的情况。
set：内部元素唯一，用一棵平衡树结构来存储，因此遍历的时候就排序了，查找也比较快的哦。
map ：一对一的映射的结合，key不能重复。
stack ：适配器，必须结合其他的容器使用，stl中默认的内部容器是deque。先进后出，只有一个出口，不允许遍历。
queue： 是受限制的deque，内部容器一般使用list较简单。先进先出，不允许遍历。
vector<bool> 与bitset<> ,前面的可以动态改变长度。
priority_queue： 插入的元素就有优先级顺序，top出来的就是优先级最高的了
valarray 专门进行数值计算的，增加特殊的数学函数。
| s.empty() | 如果栈为这人，则true；否则返回false |
| s.size() | 返回栈中元素的个数 |
| s.pop() | 删除栈顶元素，但不返回其值 |
| s.top() | 返回栈顶元素的值，但不删除该元素 |
| s.push(item) | 在栈项压入新元素 |
| q.empty() | 如果队列为空，则返回true；否则返回false |
| q.size() | 返回队列中元素的个数 |
| q.pop() | 删除队首元素，但不返回其值 |
| q.front() | 返回队首元素的值，但不删除该元素 （注：该操作只适用于队列） |
| q.back() | 返回队尾元素的值，但不删除该元素 （注：该操作只适用于队列） |
| q.top() | 返回具有最高优先级的元素值，但不删除该元素 |
| q.push(item) | 对于queue，在队尾压入一个新元素； 对于priority_queue，在基于优先级的适当位置插入新元素 |
STL各个容器的实现:
(1) vector
内部数据结构：数组。
随机访问每个元素，所需要的时间为常量。
在末尾增加或删除元素所需时间与元素数目无关，在中间或开头增加或删除元素所需时间随元素数目呈线性变化。
可动态增加或减少元素，内存管理自动完成，但程序员可以使用reserve()成员函数来管理内存。
vector的迭代器在内存重新分配时将失效（它所指向的元素在该操作的前后不再相同）。当把超过capacity()-size()个元素插入vector中时，内存会重新分配，所有的迭代器都将失效；否则，指向当前元素以后的任何元素的迭代器都将失效。当删除元素时，指向被删除元素以后的任何元素的迭代器都将失效。
(2)deque
内部数据结构：数组。
随机访问每个元素，所需要的时间为常量。
在开头和末尾增加元素所需时间与元素数目无关，在中间增加或删除元素所需时间随元素数目呈线性变化。
可动态增加或减少元素，内存管理自动完成，不提供用于内存管理的成员函数。
增加任何元素都将使deque的迭代器失效。在deque的中间删除元素将使迭代器失效。在deque的头或尾删除元素时，只有指向该元素的迭代器失效。
(3)list
内部数据结构：双向环状链表。
不能随机访问一个元素。
可双向遍历。
在开头、末尾和中间任何地方增加或删除元素所需时间都为常量。
可动态增加或减少元素，内存管理自动完成。
增加任何元素都不会使迭代器失效。删除元素时，除了指向当前被删除元素的迭代器外，其它迭代器都不会失效。
(4)slist
内部数据结构：单向链表。
不可双向遍历，只能从前到后地遍历。
其它的特性同list相似。
(5)stack
适配器，它可以将任意类型的序列容器转换为一个堆栈，一般使用deque作为支持的序列容器。
元素只能后进先出（LIFO）。
不能遍历整个stack。
(6)queue
适配器，它可以将任意类型的序列容器转换为一个队列，一般使用deque作为支持的序列容器。
元素只能先进先出（FIFO）。
不能遍历整个queue。
(7)priority_queue
适配器，它可以将任意类型的序列容器转换为一个优先级队列，一般使用vector作为底层存储方式。
只能访问第一个元素，不能遍历整个priority_queue。
第一个元素始终是优先级最高的一个元素。
(8)set
键和值相等。
键唯一。
元素默认按升序排列。
如果迭代器所指向的元素被删除，则该迭代器失效。其它任何增加、删除元素的操作都不会使迭代器失效。
(9)multiset
键可以不唯一。
其它特点与set相同。
(10)hash_set
与set相比较，它里面的元素不一定是经过排序的，而是按照所用的hash函数分派的，它能提供更快的搜索速度（当然跟hash函数有关）。
其它特点与set相同。
(11)hash_multiset
键可以不唯一。
其它特点与hash_set相同。
(12)map
键唯一。
元素默认按键的升序排列。
如果迭代器所指向的元素被删除，则该迭代器失效。其它任何增加、删除元素的操作都不会使迭代器失效。
(13)multimap
键可以不唯一。
其它特点与map相同。
(14)hash_map
与map相比较，它里面的元素不一定是按键值排序的，而是按照所用的hash函数分派的，它能提供更快的搜索速度（当然也跟hash函数有关）。
其它特点与map相同。
(15)hash_multimap
键可以不唯一。
其它特点与hash_map相同。
ＳＴＬ 容器详解