C++常用容器介绍

连续的容器

vector

可以动态增长的数据,仅限于在back增长;

vector事先分配一定量的存储空间,该空间比vector size显示的空间要大,以便于push_back能在常数时间内完成。

如果预分配的空间用完,则重新分配一块足够大的空间,将数据拷贝到新空间内。

有不同的策略可以平衡重新分配带来的时间开销和预分配过多的空间导致的空间浪费。

deque

deque 发音为"deck",是Double Ended Queue的缩写。其可以通过下标随机存取,和vector不同的是,其可以在front和back两个位置高效的插入数据或者删除数据。

deque不保证物理存储空间的连续性,所以如果想通过deque中某个已有数据的偏移量获取数据的话,可能导致未定义的错误。

因为deque的数据散布在内存空间的不同地方,为了保持随机存取能在常数时间内完成,所以deque的内部要比vector复杂,但是如果需要一个很长的序列,并且动态增加长度会显得代价很高,deque可以在这种情况下高效运行。

对于不是在front或者back的频繁的插入删除都会导致deque的性能下降。此种情况下可以选择使用list或者forward-list。

list <-- 双链表

forward_list <-- 单链表

Container adaptors

stack <-- LIFO stack

stack是其他容器如list,vector,deque等容器的封装,一般来说只要具有 back,push_back 和pop_back接口的容器都可以实现stack,如果没有特别指定其实现容器,默认的实现方式是deque。

queue <-- FIFO queue

queue也是其他容器的封装,具有front,back, push_back和pop_front的容器都可以是其实现,deque和list满足要求,默认为deque实现。

priority_queue 优先级队列

优先队列也是其他容器的封装,具有front,push_back和pop_back的容器都可以满足要求,如vector和deque,默认为vetor。

优先级队列需要维护一个堆,该过程是调用algorithm中的make_heap,push_heap和pop_heap完成的。

关联容器

set

set用来存储元素,其中不可以有重复的元素。

一旦插入不可修改,只能删除。
其顺序按照内部约定的比较函数得出的比较结果确定。
一般来说set的实现是二叉查找树。

multiset <-- multiple-key set

允许重复元素的set

map

map用来存储键值对,其中key唯一。
可以通过[]直接存取map中数据,通常用二叉查找树实现。

multimap <-- multiple-key map

允许重复key的map。

无序关联容器 C++11

unordered_set

和set相比,unordered_set中的元素没有特定的顺序,他们是按照其hash值存储在bucket中的,因此unordered_set比set的存取单个元素的时间要快,但是如果要遍历整个set,速度就比不上set了。

unordered_multiset

元素可以重复的unordered_set,需要注意的是其没有单独的header,和unordered_set共享

unordered_map

key按照hash值存放的map。

unordered_multimap

key可以重复的unordered_map,和unordered_map共享header

其他

bitset

valarray

|| 容器 || 头文件 || 特点 || 存储方法 || 时间复杂度||
|| 栈 || -20 || 30 || 连续空间 || N ||
|| 1920 || -10 || 32 || 连续空间 || N ||
|| 1920 || -10 || 25 || 连续空间 || N ||