STL-容器的比较与操作

STL-容器的比较与操作

	vector	deque	list	set	multiset	map	multimap
名称	向量容器	双向队列容器	列表容器	集合	多重集合	映射	多重映射
内部数 据结构	连续存储的数组形式（一端开口的组）	连续或分段连续存储数组（两端 开口的数组）	双向环状链表	红黑树（平衡检索二叉树）	红黑树	红黑树	红黑树
头文件	#include <vector>	#include <deque>	#include <list>	#include <set>	#include <set>	#include <map>	#include <map>
操作元素的方式	下标运算符：[0]（可以用迭代器，但插入删除操作时会失效）	下标运算符或迭代器	只能用迭代器(不断用变量值来递推新值，相当于指针)，不支持使用下标运算符	迭代器	迭代器	迭代器	迭代器
插入删除操作迭代器是否失效	插入和删除元素都会使迭代器失效	插入任何元素都会使迭代器失效。删除头和尾元素，指向被删除节点迭代器失效，而删除中间元素会使所有迭代器失效	插入，迭代器不会失效。删除，指向被删除节点迭代器失效	插入，迭代器不会失效。删除，指向被删除节点迭代器失效	插入，迭代器不会失效。删除，指向被删除节点迭代器失效	插入，迭代器不会失效。删除，指向被删除节点迭代器失效	插入，迭代器不会失效。删除，指向被删除节点迭代器失效

	vector	deque	list	set	multiset	map	multimap
名称	向量容器	双向队列容器	列表容器	集合	多重集合	映射	多重映射
特点	增加和获取元素效率 很高，插入和删除的 效率很低	增加和获取元素效率 较高，插入和删除的 效率较高	增加和获取元素效率 很低，插入和删除的 效率很高	1.键（关键字）和值（数据）相等（就是模版只有一个参数，键和值合起来） 2.键唯一 3.元素默认按升序排列	1.键和值相等 2.键可以不唯一 3.元素默认按升序排列	1.键和值分开（模版有两个参数，前面是键后面是值） 2.键唯一 3.元素默认按键的升序排列	1.键和值分开 2.键可以不唯一 3.元素默认按键的升序排列
定义容器	vector<string> book(50);	deque<string> book(50);	list<string> book;	set<string> book;	multiset<string> book;	map<int,string> book;	multimap<int,string> book;

顺序容器：vector、list、deque有很多相同的操作，因此放在这里一起说明，其他一些特有的容器操作将会在具体的容器部分介绍。c为容器对象

容器元素类型必须满足以下两个约束：

• 元素类型必须支持赋值运算；
• 元素类型的对象必须可以复制。

关系运算符依据下面的规则而定义：

（1）两个容器必须有相同的类型；

（2）两个容器相等是指它们包含的元素对应相等并且次序一致；

（3）比较一个容器小于另一个容器，要按照词典比较法进行。

赋值操作

把一个容器赋值给另一个容器，首先要删除原有的元素，然后再把源容器中的所有元素复制到目标容器。所以说容器的赋值操作对性能的代价是相当的昂贵的。如果两个容器类型相同，而且源容器不在使用，那么有一个更加优化的方法：swap()，它的执行效率将大大高于普通的容器赋值操作。

算术运算符

迭代器的算术运算返回的迭代器，指向容器中的元素位置或 容器的end()位置。

关系运算符

当两个迭代器指向同一个容器中的同一个元素，或者当它们都指向同一个容器的end()位置时，两个迭代器相等。

常用迭代器运算

顺序容器定义和初始化

添加和删除元素

容器大小

访问元素

赋值

所有适配器都定义了两个构造函数：默认构造函数用于创建空对象，而带一个容器参数的构造函数将参数容器的副本作为其基础值。默认的stack和queue都基于deque容器实现，而priority_queue则在vector容器上实现。

栈和队列的操作基本类似

关联容器（Associative containers）支持通过键来高效地查找和读取元素。两个基本的关联容器类型是map set。map的元素以键－值（key-value）对的形式组织：键用作元素在map中的索引，而值则表示所存储和读取的数据。set仅包含一个键，并有效地支持关于某个键是否存在的查询。

1.pair

2.map

map是键－值对的集合。map类型通常可理解为关联数组：可使用键作为下标来获取一个值，正如内置数组类型一样。而关联的本质在于元素的值与某个特定的键相关联，而并非通过元素在数组中的位置来获取。

map定义、初始化

对map迭代器进行解引用时，将获得一个引用，指向容器中一个pair<const kT, vT>类型的值，该类型定义为value_type，且键为const。通过pair类型的访问方式可以对map进行进行访问。

对于map类型，唯一的约束就是必须支持 < 操作符，至于是否支持其他的关系或相等运算，则不作要求。

map类定义的类型

添加元素

下标操作：如果该键已在容器中，则 map 的下标运算返回该键所关联的值。只有在所查找的键不存在时，map 容器才为该键创建一个新的素，并将它插入到此 map 对象中。

insert 操作：除容器通用操作外，m.insert(e)，e为pair类型的元素，如果e在m中不存在，则插入；否则e保持不变。

删除元素

除了通用操作利用迭代器删除元素以外，map还可以利用m.erase(k)，删除m中键为k的元素。返回size_type类型的值，表示删除的元素个数。

查找元素

3.set

set 容器的每个键都只能对应一个元素。以一段范围的元素初始化set对象，或在set对象中插入一组元素时，对于每个键，事实上都只添加了一个元素。

获取元素

与map相同，set也支持find(k)、count(k)、lower_bound(k)和upper_bound(k)函数，来查找set中元素位置和个数。

4、multimap 和 multiset

multimap 和 multiset操作与map和set类似，它们还提供下面的操作：

8.1 vector

8.2 deque

8.3 list

8.4 map/multimap

8.5 set/multiset