STL容器有序性和重复性
总结
| 容器 | 有序性 | 允许重复 | 描述 |
|---|---|---|---|
std::map |
是 | 否 | 有序的键值对，不允许重复键。 |
std::list |
否 | 是 | 按插入顺序存储，允许重复。 |
std::vector |
否 | 是 | 按插入顺序存储，允许重复。 |
std::set |
是 | 否 | 有序集合，不允许重复。 |
std::multimap |
是 | 是 | 有序的键值对，允许重复键。 |
std::multiset |
是 | 是 | 有序集合，允许重复值。 |
问题
Q1: 为什么 std::set 和 std::map 是有序的？
- 因为它们的底层数据结构是红黑树，红黑树在插入元素时会保持元素的顺序性（默认升序）。
- 插入和删除操作时，红黑树通过旋转和重新着色保持顺序和平衡。
Q2: std::vector 和 std::list 有序吗？有什么区别？
- 它们是有序的，但仅仅是 按插入顺序 保存元素。
- 区别：
std::vector是连续存储，支持随机访问，时间复杂度为O(1)。std::list是双向链表存储，支持高效的插入和删除，但随机访问时间复杂度为O(n)。
Q3: std::set 和 std::multiset 的区别？
std::set不允许重复元素。std::multiset允许重复元素，但仍然按顺序存储。
