23.常见容器性质总结?

来源: 博客园

23.常见容器性质总结?

C++ STL(Standard Template Library)提供了多种容器,用于存储和操作各种类型的数据。以下是一些常见容器的特性总结:

1.std::vector:动态数组,能高效地在末尾进行插入和删除操作,能直接访问任何元素。但在中间位置进行插入或删除操作则需要移动元素,效率较低。此外,当插入的元素超过当前分配的空间时,会重新分配内存,可能导致大规模元素移动。底层数据结构为数组

2.std::deque:双端队列,支持高效的头部和尾部插入和删除操作,并能直接访问任何元素。与std::vector相比,std::deque不保证元素在内存中的连续存储,因此当插入的元素超过当前分配的空间时,不需要移动其他元素。


(相关资料图)

3.std::queue:基于其它容器(如std::deque)实现的队列,支持两端的插入和删除操作。

4.std::priority_queue:基于其它容器(如std::vector)实现的优先队列,堆(heap)为处理规则来管理底层容器实现,元素按优先级排序。

5.std::list:底层数据结构为双向链表,能在任何位置高效地进行插入和删除操作。但不支持直接访问元素,只能通过迭代器进行访问。

6.std::forward_list:单向链表,只能从头部开始遍历,并只支持头部和后面的高效插入和删除操作。

7.std::array:固定大小的数组,提供与std::vector类似的接口,但其大小在编译时确定,无法动态改变。

8.std::set:底层数据结构为红黑树实现的有序集合,元素按排序顺序存储,每个元素只能出现一次。插入和查找操作的复杂度为对数级别。

9.std::multiset:与std::set类似,底层数据结构为红黑树,有序,允许元素重复。

10.std::map:底层数据结构为红黑树实现的有序映射表,存储键值对,键是唯一的,插入和查找操作的复杂度为对数级别。

11.std::unordered_map:基于哈希表实现的无序映射表,存储键值对,键是唯一的。在理想情况下,插入和查找操作的复杂度为常数级别。

12.std::multimap:与std::map类似,但允许键重复。

13.std::unordered_multimap:与std::unordered_map类似,但允许键重复。

14.std::unordered_set:基于哈希表实现的无序集合,每个元素只能出现一次。在理想情况下,插入和查找操作的复杂度为常数级别。

15.std::unordered_multiset:与std::unordered_set类似,但允许元素重复。

16.std::stack:基于其它容器(如std::deque)实现的栈,只支持顶部的插入和删除操作。

这些容器各有优劣,应根据实际的需求和场景来选择合适的容器。例如,如果需要频繁地在序列中间插入或删除元素,应使用std::list;如果需要存储键值对,并且键是唯一的,应使用std::mapstd::unordered_map等等。

相关新闻
体教融合大有可为

胡凯(2005年伊兹密尔大运会男子100米冠军、清华大学体育部副主任)【