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::map
或std::unordered_map
等等。