当前位置：首页 > news >正文

stl容器

news 2025/8/3 8:59:41

大部分容器的size的复杂度如下：

std::vector：时间复杂度为(1).

std::deque：时间复杂度为 O(1). 双端队列

std::list：时间复杂度为 O(1)（C++11 及以后的版本）。

std::forward_list：时间复杂度为 O(N)，其中 N 是容器中的元素数。由于 `forward_list 是单向列表，计算大小需要遍历整个列表。

std::array：时间复杂度为 O(1)。实际上，std::array 是一个静态数组，其大小在编译时已确定。

std::stack 和 std::queue：它们是容器适配器，实际上依赖于其他容器实现（例如 vector, deque, 或 list），因此其 size 复杂度与底层容器的 size()` 复杂度相同

std::priority_queue：时间复杂度为 O(1).

std::map 和 std::multimap：时间复杂度为 O(1)（C++11 及以后的版本）。

std::unordered_map 和 std::unordered_multimap：时间复杂度为 O(1)。

std::set 和 std::multiset：时间复杂度为 O(1)（C++11 及以后的版本）。

std::unordered_set 和 std::unordered_multiset：时间复杂度为 O(1)。

std::valarray：size成员函数时间复杂度为O(1)

std::bitset：size成员函数时间复杂度是O(1)

STL（标准模板库）中的 deque 和 queue 是两个不同的容器，它们之间有以下的区别：

底层数据结构不同：deque 的底层是由一段一段的定长数组构成的，相当于连续多个数组拼接而成，而 queue 的底层可以是 deque 或其他序列式容器。
支持的操作不同：deque 可以在两端进行插入和删除操作，支持随机访问；而 queue 只支持队尾插入、队首删除，不支持随机访问。
应用场景不同：deque 适用于需要在头部和尾部频繁插入和删除元素的场景，例如实现双端队列（deque），而 queue 适用于遵循先进先出 (FIFO) 原则的场景，例如实现消息队列等。
迭代器的类型不同：deque 的迭代器是随机访问迭代器，可以像普通指针一样进行加减操作，而 queue 的迭代器只支持前向迭代器，只能进行单步移动。