为什么c ++中的堆被实现为算法而不是容器？

Question

我想知道为什么堆概念作为算法(实现make_heap,pop_heap, push_heap,sort_heap),而不是一个容器.我特别感兴趣的是一些人的解决方案也可以解释为什么set和map容器而不是类似的算法集合(make_set add_set rm_set等).

Answer 1

STL确实以std :: priority_queue的形式提供堆.make_heap等功能就在那里,因为它们在数据结构本身的范围之外有用(例如排序),并且允许在自定义结构之上构建堆(如"保持前10名"的堆栈数组)容器).

通过类比,您可以使用std :: set来存储已排序的列表,或者您可以在带有std :: adjacent_find的向量上使用std :: sort; std :: sort是更通用的,并且对底层数据结构做了很少的假设.

(注意,std :: priority_queue实现实际上并不提供自己的存储;默认情况下,它创建一个std :: vector作为其后备存储.)

Answer 2

一个明显的原因是您可以将元素作为堆放在另一个容器中.
所以你可以调用make_heap()一个vector或一个deque甚至是一个C数组.