序列容器
vector
用途:动态数组,支持随机访问。
特性:
元素连续存储。
插入和删除操作在尾部效率较高,中间操作较慢。
常用方法:
push_back():在容器末尾添加元素。
pop_back():移除容器末尾的元素。
at(index):通过索引访问元素。
size():返回容器大小。
list
用途:双向链表,支持高效的插入和删除操作。
特性:
元素非连续存储。
支持双向迭代器。
随机访问效率低。
常用方法:
push_back(value):在容器末尾添加元素。
push_front(value):在容器前端添加元素。
pop_back():移除容器末尾的元素。
pop_front():移除容器前端的元素。
insert(iterator position, value):在指定位置插入元素。
deque
用途:双端队列,两端都可以进行高效的插入和删除操作。
特性:
元素可以连续或非连续存储。
支持随机访问。
常用方法:
push_back(value):在容器末尾添加元素。
push_front(value):在容器前端添加元素。
pop_back():移除容器末尾的元素。
pop_front():移除容器前端的元素。
at(index):通过索引访问元素。
forward_list
用途:单向链表,只支持从前到后遍历。
特性:
元素非连续存储。
只支持单向迭代器。
常用方法:
push_front(value):在容器前端添加元素。
pop_front():移除容器前端的元素。
insert_after(iterator position, value):在指定位置插入元素。
关联容器
set 和 multiset
用途:存储唯一元素或允许重复元素。
特性:
自动排序。
支持高效查找。
常用方法:
insert(value):插入元素。
find(key):查找元素。
erase(key):删除元素。
size():返回容器大小。
map 和 multimap
用途:存储键值对。
特性:
键值自动排序。
支持高效查找。
常用方法:
insert(pair<key_type, value_type>):插入键值对。
find(key):查找键对应的值。
erase(key):删除键值对。
size():返回容器大小。
无序关联容器
unordered_set 和 unordered_multiset
用途:存储唯一元素或允许重复元素。
特性:
无序存储。
基于哈希表实现,查找速度快。
常用方法:
insert(value):插入元素。
find(key):查找元素。
erase(key):删除元素。
size():返回容器大小。
unordered_map 和 unordered_multimap
用途:存储键值对。
特性:
无序存储。
基于哈希表实现,查找速度快。
常用方法:
insert(pair<key_type, value_type>):插入键值对。
find(key):查找键对应的值。
erase(key):删除键值对。
size():返回容器大小。
vector
作用:动态数组,可以随机访问元素,支持快速的插入和删除操作(尤其是尾部操作)。
特点:连续内存分配,支持快速随机访问,但中间插入和删除操作可能较慢。
list
作用:双向链表,适合频繁的插入和删除操作,但不支持随机访问。
特点:节点间通过指针连接,插入和删除操作非常快,但访问特定位置的元素需要从头或尾遍历。
deque(双端队列)
作用:两端都可以进行高效的插入和删除操作,支持随机访问。
特点:内部实现为分块的数组,支持两端的快速插入和删除,以及快速随机访问。
forward_list
作用:单向链表,适合需要单向遍历的情况。
特点:只支持从头到尾的遍历,插入和删除操作非常快,但无法反向遍历。
关联容器(Associative Containers)
set 和 multiset
作用:存储唯一的元素(set)或允许重复元素(multiset),元素按顺序自动排序。
特点:元素按照键值排序,插入、查找和删除操作的时间复杂度较低。
map 和 multimap
作用:存储键值对(map)或允许重复键值对(multimap),键值对按顺序自动排序。
特点:键值对按照键值排序,查找、插入和删除操作基于键值进行,时间复杂度较低。
无序关联容器(Unordered Associative Containers)
unordered_set 和 unordered_multiset
作用:存储唯一的元素(unordered_set)或允许重复元素(unordered_multiset),元素无序存储。
特点:使用哈希表实现,平均情况下插入、查找和删除操作的时间复杂度接近常数时间。
unordered_map 和 unordered_multimap
作用:存储键值对(unordered_map)或允许重复键值对(unordered_multimap),键值对无序存储。
特点:使用哈希表实现,平均情况下插入、查找和删除操作的时间复杂度接近常数时间。