赞
踩
本文主要记录一下STL中一些常见的容器(包括vector、deque、queue、list、stack、set、map),及其对应的常见的操作,不涉及更深层次原理性的知识。方便以后使用、查阅。
vector 容器结构示意图:
vector:顺序存储容器,和数组非常相似,也被称为单端数组。只能从尾部增加删除元素。
vector 常见操作:
deque 容器结构示意图:
deque:顺序存储容器,两端都可插入与删除,也被称为双端数组。虽然都是顺序存储容器,但是vector访问元素的速度要比deque快。
deque内部工作原理:
deque常见操作:
queue 容器结构示意图:
queue:先进先出(First In First Out, FIFO)的存储容器(两端),只能从尾部插入、头部删除。
queue常见操作:
list 容器结构示意图:
list: 非连续的存储空间,是一个双向循环链表,动态存储分配。
list 常见操作:
stack 容器结构示意图:
stack: 一种先进后出(First In Last Out, FILO)的数据结构,只有一个出口,只能在栈顶插入与删除。
stack 常见操作:
set: 集合,一种关联性容器。底层是红黑树实现的。
特点:
1)、所有元素在插入时自动被排序;
2)、set不允许容器中有重复的值,multiset允许容器中有重复的元素;
set常见操作:
map: 一种关联性容器。底层是红黑树实现的。
特点:
1)、map中所有的元素都是pair,其中pair第一个元素为key(键值),第二个元素为value(实值);
2)、所有元素都会根据元素的key(键值)自动排序;
3)、map中不允许有重复的key值元素,multimap中允许有重复的key值元素;
map 常见操作:
名称 | 类型 | 存储结构 | 支持迭代器 | 增加元素 | 删除元素 | 支持find | 随机访问 |
---|---|---|---|---|---|---|---|
vector | 顺序容器 | 连续存储空间 (数组) | 支持 | 尾部增加 (push_back) | 尾部删除 (pop_back) | 自己不支持find | 支持快速随机访问 |
deque | 顺序容器 | 连续存储空间 (双端数组) | 支持 | 尾部增加 (push_back) 头部增加 (push_front) | 尾部删除 (pop_back) 头部删除 (pop_front) | 自己不支持find | 支持快速随机访问 |
queue | 顺序容器 | 连续存储空间 (FIFO) | 不支持 | 队尾增加 (push) | 队头删除 (pop) | 不支持 | 不支持 |
list | 顺序容器 | 非连续存储空间 (双向循环链表) | 支持 | 尾部增加 (push_back) 头部增加 (push_front) | 尾部删除 (pop_back) 头部删除 (pop_front) | 自己不支持find | 不支持 |
stack | 顺序容器 | 连续存储空间 (FILO) | 不支持 | 栈顶增加 (push) | 栈顶删除 (pop) | 不支持 | 不支持 |
set | 关联容器 | 红黑树 | 支持 | insert | erase | 支持 | —— |
map | 关联容器 | 红黑树 | 支持 | insert [] 赋值 | erase | 支持 | —— |
PS:
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。