顺序容器、关联容器和无序容器是C++标准库中的三种不同类型的容器，它们在元素存储和访问方式上有所区别。下面是它们的异同点：
1. 顺序容器（Sequence Containers）
-
定义：顺序容器是按照元素插入的顺序存储元素的容器。
-
常见容器：
std::vector,std::deque,std::list,std::array,std::forward_list -
特点：
- 元素顺序：元素按插入顺序排列，可以通过索引（对于
std::vector）或迭代器访问元素。 - 访问方式：支持顺序访问，
std::vector支持快速的随机访问，而std::list等容器则是基于链表实现的。 - 插入与删除：顺序容器支持在容器两端进行插入和删除操作（如
std::deque支持两端操作，std::list支持任意位置操作）。 - 例子：
std::vector适用于频繁访问和修改尾部元素的场景；std::list适合需要高效插入和删除的场景。
- 元素顺序：元素按插入顺序排列，可以通过索引（对于
2. 关联容器（Associative Containers）
- 定义：关联容器根据某个键值（key）来组织和存储元素，容器中的元素按照某种特定的顺序（通常是键的顺序）排列。
- 常见容器：
std::map,std::multimap,std::set,std::multiset - 特点：
- 元素存储：关联容器的元素通常按键值的顺序排列，通常基于红黑树（平衡二叉搜索树）实现。
- 访问方式：通过键访问元素，查找效率为O(log n)，并且保证元素有序。
- 插入与删除：插入和删除元素的效率一般是O(log n)，插入时会自动保持顺序。
- 例子：
std::map存储唯一键值对，按键值排序。std::set存储唯一的键，按键值排序。std::multimap和std::multiset与map和set相似，但允许键重复。
3. 无序容器（Unordered Containers）
-
定义：无序容器根据哈希值存储元素，元素没有特定顺序，通常插入和查找操作的时间复杂度较低。
-
常见容器：
std::unordered_map,std::unordered_multimap,std::unordered_set,std::unordered_multiset -
特点：
-
元素存储：无序容器基于哈希表实现，元素在容器中的存储位置由哈希函数决定，因此不保证元素顺序。
-
访问方式：元素通过键访问，查找的平均时间复杂度为O(1)，但最坏情况下可能是O(n)。
-
插入与删除：插入和删除元素的平均时间复杂度为O(1)，在哈希冲突时可能退化为O(n)。
-
例子：
std::unordered_map和std::unordered_multimap存储键值对，但无序。std::unordered_set和std::unordered_multiset存储不重复的元素，且元素无序。
-
| 特性/容器类型 | 顺序容器 | 关联容器 | 无序容器 |
|---|---|---|---|
| 存储顺序 | 按照插入顺序，或固定顺序（如数组） | 自动排序（通常按键值排序） | 无序（通过哈希表实现） |
| 访问方式 | 通过位置或索引访问（如std::vector） |
通过键访问，按排序顺序 | 通过哈希值访问，不保证顺序 |
| 时间复杂度 | 随容器类型不同：std::vector O(1)随机访问，std::list O(n)查找 |
查找、插入和删除 O(log n) | 查找、插入和删除平均 O(1)（最坏O(n)） |
| 容器类型 | std::vector, std::deque, std::list 等 |
std::set, std::map, std::multiset, std::multimap 等 |
std::unordered_set, std::unordered_map 等 |
| 支持重复元素 | std::list 和 std::deque支持重复元素，std::vector也可以（但不去重） |
std::set不支持重复元素，std::multiset支持 |
std::unordered_set不支持重复元素，std::unordered_multiset支持 |
主要区别：
- 顺序容器保持元素插入顺序，支持顺序访问和修改，但查找可能较慢（对于
std::list等）。 - 关联容器根据键排序元素，查找和插入的时间复杂度通常为O(log n)，适合需要保持元素有序的场景。
- 无序容器通过哈希表存储元素，查找和插入通常具有更高的性能（O(1)平均时间复杂度），但不保证元素顺序，适合高效查找和插入。
文章评论