STL容器
容器部分主要由头文件<vector>,<list>,<deque>,<set>,<map>,<stack>和<queue>组成。
容器分类:
一、顺序容器
vector:向量容器,底层由数组实现,只有push_back()方法
相当于数组,但其大小可以不预先指定,并且自动扩展。它可以像数组一样被操作,由于它的特性我们完全可以将vector 看作动态数组。(扩展时以2被倍的空间扩展)
当vector保存的数据量很大时,如果此时进行插入数据导致需要更大的空间来存放这些数据量,那么将会大大的影响程序运行的效率,所以我们应该合理的使用vector。
list:双向链表容器,底层由双向循环链表实现,有push_back()方法,push_front()方法
链表相对于vector向量来说的优点在于:(a)动态的分配内存,当需要添加数据的时候不会像vector那样,先将现有的内存空间释放,在次分配更大的空间,这样的话效率就比较低了。(b)支持内部插入、头部插入和尾部插入
缺点:不能随机访问,不支持[]方式和vector.at()、占用的内存会多于vector(非有效数据占用的内存空间)
deque:双端队列容器,底层由双端队列实现,有 push_back()方法,push_front()方法
deque的各项操作只有一下两点和vector不同:deque不提供容量操作:capacity()和reverse()。deque直接提供函数完成首尾元素的插入和删除。其他均与vector相同。
二、关联容器
set:单重集合,底层由红黑树实现,(不容许元素重复)-----------》存放一组相同类型数组的集合
初始化set对象的方式:
set<int > seta; //默认是小于比较器less<int>的set
set<int, greater<int> > setb; //创建一个带大于比较器的set,需包含头文件functional
int a[5] = {1,2,3,4,5};set<int > setc(a,a+5); //数组a初始化一个set;set<int > setd(setc.begin(),setc.end()); //setc初始化一个set//上述两例均为区间初始化
set<int > sete(setd); //拷贝构造创建set
multi_set:多重集合,底层由红黑树实现,(容许元素重复)
map:单重映射,底层由红黑树实现,(不容许键重复)
初始化map对象的方式:
map<key,value>m; //创建一个名为m的空map对象,其键和值的类型分别为key和value。
map<key,value>m(m2); //创建m2的副本m,m与m2必须有相同的键类型和值类型。
map<key,value>m(b,e); //创建map类型的对象m,存储迭代器b和e标记的范围内所有元素的副本,元素的类型必须能转换为pair
multi_map:多重映射,底层由红黑树实现,(容许键重复)
multimap和map不同的地方:multimap中相同的键可以多次出现,而不像map只能出现一次。 在multimap中没有定义[]运算符,当然也没有定义at()成员函数,因此,multimap进行插入的时候,只能利用insert()函数进行插入。
三、容器适配器
1:stack
stack 模板类的定义在<stack>头文件中。
stack 模板类需要两个模板参数,一个是元素类型,一个容器类型,但只有元素类型是必要的,在不指定容器类型时,默认的容器类型为deque。
定义stack 对象的示例代码如下:
stack<int> s1;
stack<string> s2;
2:queue
queue 模板类的定义在<queue>头文件中。
与stack 模板类很相似,queue 模板类也需要两个模板参数,一个是元素类型,一个容器类
型,元素类型是必要的,容器类型是可选的,默认为deque 类型。
定义queue 对象的示例代码如下:
queue<int> q1;
queue<double> q2;
3:priority_queue
priority_queue 模板类有三个模板参数,第一个是元素类型,第二个容器类型,第三个是比较算子。其中后两个都可以省略,默认容器为vector,默认算子为less,即小的往前排,大的往后排(出队时序列尾的元素出队)。
定义priority_queue 对象的示例代码如下:
priority_queue<int> q1; priority_queue< pair<int, int> > q2; // 注意在两个尖括号之间一定要留空格。
priority_queue<int, vector<int>, greater<int> > q3; // 定义小的先出队
priority_queue 的基本操作与queue 相同。
容器优缺点
用哪种容器的选择看起来非常繁琐,头脑中如果有个每个容器大概的模型,在选择的时候会更为轻松点。
-
Vector的数据模型就是数组。
优点:内存和C完全兼容、高效随机访问、节省空间
缺点:内部插入删除元素代价巨大、动态大小查过自身容量需要申请大量内存做大量拷贝。
-
List 的数据结构模型是双向循环链表
优点:任意位置插入删除元素常量时间复杂度、两个容器融合是常量时间复杂度
缺点:不支持随机访问、比vector占用更多的存储空间
-
Deque的数据模型是双端队列:
优点:高效随机访问、内部插入删除元素效率方便、两端push pop
缺点:内存占用比较高
-
Map、set、multimap、multiset的数据结构模型是二叉树(红黑树)
优点:元素会按照键值排序、查找是对数时间复杂度、通过键值查元素、map提供了下标访问
容器特性
总结:
1) 如果需要随机访问,用vector
2) 如果存储元素的数目已知,用vector
3) 需要任意位置随机插入删除,用list
4) 只有需要更多在容器的首部尾部插入删除元素,用deque
5) 元素是复杂结构用list,也可以用vector存储指针(需要额外的精力去维护内存),看需求
6) 如果操作是基于键值,用set map
7) 如果需要经常的搜索,用map set
8) map set 的区别是map中的元素都是pair