概要
继续整理C++相关知识,阅读c++11里面新增加的容器相关内容。参考的书籍《C++标准库:第2版》 ISBN 987-7-121-26089-6
序列容器
实现顺序访问方式的数据结构。
array c++11
静态连续数组。在建立的时候需要指明大小,不能改变长度,只能修改值。允许随机访问。它能直接使用STL中的通用算法。
vector
动态连续数组。支持随机访问。尾部插入元素、移除元素都很迅速,头部,中间插入比较费时。
deque
双头队列。尾部或者头部安插元素十分迅速。中间插入比较费时,需要移动其他元素。
list
双向链表。不提供随机访问,访问链表中元素时,需要沿着链表方向访问。比起vector/deque在中段插入时候的效率要快很多。
forward_list c++11
单向链表。类似于list,只指向下一个元素的指针。不支持“后退移动”。能从头插入,或者指定的迭代器位置后插入。
关联容器
通常关联容器由二叉树实现。在无序容器中是使用了hash map方式来实现的。
set
根据value自动排序,每个元素只出现一次。
multiset
和set唯一差别就是元素可重复。
map
key/value pair,key是自动排序的。
mutilmap
和map唯一差别就是元素可重复。
unordered_map
使用hash作为底层的逻辑。
非标准序列容器
slist
rope
工具容器
Utility library
Bitset
参考
- [1] cppreference
- [2] github-test-source