STL-容器的比较与操作

72 阅读 0 评论 48 点赞

我是靠谱客的博主悦耳小刺猬，最近开发中收集的这篇文章主要介绍STL-容器的比较与操作，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

STL-容器的比较与操作

设计库的目的是为容器类型提供通用接口。如果两种容器提供相似的操作，则为它们定义的这个操作应该完全相同。例如，所有容器都有返回容器内元素个数的操作，于是所有容器都将操作命名为size，并将size返回值的类型都指定为size_type类型。类似地，算法具有一致的接口。例如，大部分算法都作用在由一对迭代器指定的元素范围上。

1.STL容器分类

顺序容器： 将单一类型元素聚集起来成为容器，然后根据位置来存储和访问这些元素。主要有vector、list、deque（双端队列）。顺序容器包含顺序容器适配器： stack、queue 和 priority_queue 。

关联容器：支持通过键来高效地查找和读取元素。主要有：pair、set、map、multiset、multimap和bitset,hash_set,hash_map, hash_multiset, hash_multimap由于顺序容器，顺序容器适配器和关联容器在接口上存在较大的差异，因此分类进行总结。

2.容器比较

	vector	deque	list	set	multiset	map	multimap
名称	向量容器	双向队列容器	列表容器	集合	多重集合	映射	多重映射
内部数据结构	连续存储的数组形式（一端开口的组）	连续或分段连续存储数组（两端开口的数组）	双向环状链表	红黑树（平衡检索二叉树）	红黑树	红黑树	红黑树

头文件	#include <vector>	#include <deque>	#include <list>	#include <set>	#include <set>	#include <map>	#include <map>
操作元素的方式	下标运算符：[0]（可以用迭代器，但插入删除操作时会失效）	下标运算符或迭代器	只能用迭代器(不断用变量值来递推新值，相当于指针)，不支持使用下标运算符	迭代器	迭代器	迭代器	迭代器
插入删除操作迭代器是否失效	插入和删除元素都会使迭代器失效	插入任何元素都会使迭代器失效。删除头和尾元素，指向被删除节点迭代器失效，而删除中间元素会使所有迭代器失效	插入，迭代器不会失效。删除，指向被删除节点迭代器失效	插入，迭代器不会失效。删除，指向被删除节点迭代器失效	插入，迭代器不会失效。删除，指向被删除节点迭代器失效	插入，迭代器不会失效。删除，指向被删除节点迭代器失效	插入，迭代器不会失效。删除，指向被删除节点迭代器失效

3.各容器特点比较以及选择

	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;

4.顺序容器vector、list、deque的通用操作

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

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

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

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

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

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

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

赋值操作

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

算术运算符

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

关系运算符

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

常用迭代器运算

5.顺序容器的操作（除通用操作外）

顺序容器定义和初始化

添加和删除元素

容器大小

访问元素

赋值

6.容器适配器stack、queue和priority_queue的操作

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

栈和队列的操作基本类似

7.关联容器的操作

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

1.pair