STL 容器中优先级队列 deque 的底层原理
时间: 2023-03-31 13:03:43 浏览: 122
优先级队列 deque 的底层原理是使用一个双端队列来存储元素,并使用一个堆来维护队列中元素的优先级。堆是一种完全二叉树,可以使用数组来实现。在 deque 中,每个元素都有一个优先级,优先级高的元素会被先出队列。当插入一个新元素时,会根据其优先级将其插入到堆中的合适位置,保证堆的性质。而当弹出元素时,会弹出堆顶元素,然后将队列中最后一个元素移到堆顶,并通过堆的下滤操作将其下沉到合适位置,保证堆的性质。这样就实现了优先级队列的功能。
相关问题
c++中的stl中的容器
C++中的STL(Standard Template Library)是一组通用的模板类和函数,它们可用于实现许多常用的数据结构和算法,其中包括许多容器类。下面是STL中常见的容器类:
1. vector:向量容器,用于存储动态大小的元素序列,支持快速随机访问和尾部插入/删除操作。
2. list:链表容器,用于存储动态大小的元素序列,支持快速插入/删除操作,但不支持随机访问。
3. deque:双端队列容器,用于存储动态大小的元素序列,支持快速随机访问和头部/尾部插入/删除操作。
4. set/multiset:集合容器,用于存储一组不重复的元素,支持快速查找、插入和删除操作。multiset允许重复元素。
5. map/multimap:映射容器,用于存储一个键值对的集合,支持快速查找、插入和删除操作。multimap允许键重复。
6. stack:栈容器,用于存储一组元素,支持在末尾插入和删除元素,遵循先进后出(LIFO)的原则。
7. queue:队列容器,用于存储一组元素,支持在末尾插入和头部删除元素,遵循先进先出(FIFO)的原则。
8. priority_queue:优先队列容器,用于存储一组元素,支持在末尾插入和弹出元素,但弹出的元素总是具有最高优先级。
这些容器类都是模板类,因此可以存储不同类型的数据。它们提供了许多有用的成员函数和迭代器,可以方便地操作元素序列。
C++STL的容器中,那些没有迭代器
在C++ STL(标准模板库)的容器中,以下几种容器是没有迭代器的:
1. std::array:std::array 是一个固定大小的数组容器,它的元素类型和大小在编译时就确定了。由于它是连续存储的,可以通过下标直接访问元素,但没有提供迭代器。
2. std::forward_list:std::forward_list 是单向链表容器,只能单向遍历,每个节点只指向下一个节点,不提供反向遍历能力,因此没有提供迭代器。
3. std::stack:std::stack 是一个适配器容器,基于其他底层容器(如 std::deque 或 std::list)实现。它是一种后进先出(LIFO)结构,只能在栈顶进行插入和删除操作,因此不需要提供迭代器。
4. std::queue:std::queue 也是一个适配器容器,基于其他底层容器(如 std::deque 或 std::list)实现。它是一种先进先出(FIFO)结构,只能在队列的前端进行插入操作,在队列的后端进行删除操作,不需要提供迭代器。
5. std::priority_queue:std::priority_queue 是一个适配器容器,基于其他底层容器(如 std::vector 或 std::deque)实现。它是一个优先级队列,按照一定的排序规则自动调整元素的顺序,不需要提供迭代器。
以上这些容器没有提供迭代器是因为它们的特性或设计目标不需要支持迭代操作。