STL 容器基于红黑树的插入、删除、查找复杂度

1. map

  • 插入:O(log n)
    插入时根据键值调整红黑树，保持平衡。
  • 删除:O(log n)
    删除某节点后需要调整红黑树结构以维持平衡。
  • 查找:O(log n)
    通过键值在树中查找对应的元素。

2. multimap

  • 插入：O(log n)
    允许键值重复，但依然保持红黑树结构平衡。
  • 删除：O(log n)
    删除某个特定键值对，红黑树会自动调整平衡。
  • 查找：O(log n)
    查找特定键值对应的所有元素。

3. set

  • 插入：O(log n)
    不允许重复元素，插入时会检查是否已存在。
  • 删除：O(log n)
    删除元素后调整红黑树以维持平衡。
  • 查找：O(log n)
    根据键值查找特定元素。

4. multiset

  • 插入：O(log n)
    允许重复元素，插入时红黑树保持平衡。
  • 删除：O(log n)
    删除某个元素后需要调整树的平衡。
  • 查找：O(log n)
    查找所有匹配的键值元素。

总结

红黑树提供了高效的 对数复杂度，保证了插入、删除和查找操作的性能。这些容器适用于需要自动排序和快速查找的场景。

STL 容器的复杂度分析

5. list

  • 插入：O(1)
    在已知位置进行插入操作，效率为常数时间。
  • 删除：O(1)
    在已知位置进行删除操作，效率为常数时间。
  • 查找：O(n)
    需要遍历链表查找目标元素。

6. vector

  • 插入：O(1) (均摊) / O(n) (在中间插入)
    • 末尾插入：均摊 O(1)。
    • 中间插入：需要移动元素，复杂度为 O(n)。
  • 删除：O(n)
    需要移动元素以保持连续存储。
  • 查找：O(1) (通过索引) / O(n) (通过值)
    • 索引访问：常数时间。
    • 值查找：需要遍历数组。

7. deque

  • 插入：O(1) (均摊) / O(n) (在中间插入)
    • 头部或尾部插入：均摊 O(1)。
    • 中间插入：需要移动元素，复杂度为 O(n)。
  • 删除：O(1) (头部或尾部) / O(n) (在中间删除)
    • 头部或尾部删除：常数时间。
    • 中间删除：需要移动元素。
  • 查找：O(1) (通过索引) / O(n) (通过值)
    • 索引访问：常数时间。
    • 值查找：需要遍历。

8. pair

  • 操作：O(1)
    • pair 是一个简单的二元组，所有操作都是常数时间。
    • 通常用于关联容器（如 map）中的键值对。

9. stack

  • 插入 (push)：O(1)
    始终在栈顶插入元素，效率为常数时间。
  • 删除 (pop)：O(1)
    始终从栈顶删除元素，效率为常数时间。
  • 访问栈顶 (top)：O(1)
    直接访问栈顶元素。

10. heap

  • 插入：O(log n)
    需要调整堆的结构以保持堆序性。
  • 删除 (删除堆顶)：O(log n)
    删除堆顶元素后需要重新调整堆。
  • 访问堆顶：O(1)
    堆顶元素直接可访问。

11. 队列 (queue)

  • 插入 (push)：O(1)
    始终在队列尾部插入，效率为常数时间。
  • 删除 (pop)：O(1)
    始终从队列头部删除，效率为常数时间。
  • 访问队首：O(1)
    直接访问队列头部元素。

12. 优先级队列 (priority_queue)

  • 插入：O(log n)
    插入新元素后需要维护堆的性质。
  • 删除 (删除最大或最小值)：O(log n)
    删除堆顶元素后重新调整堆。
  • 访问堆顶：O(1)
    直接访问优先级最高的元素。

总结

STL 容器提供了多种结构，适用于不同场景：

  • 动态数组：vector
  • 双端队列：deque
  • 链表：list
  • 栈与队列：stack、queue
  • 堆结构：priority_queue
  • 键值对：pair

选择容器时应根据操作频率和复杂度需求，权衡效率和灵活性。