Почему кучи в 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 и т. Д. Существуют потому, что они используют за пределами самой структуры данных (например, сортировку) и позволяют строить кучи поверх пользовательских структур (например, стековых массивов для "keep the top 10").контейнер).

По аналогии, вы можете использовать std :: set для хранения отсортированного списка, или вы можете использовать std :: sort для вектора с помощью std ::acent_find;std :: sort является более универсальным и делает несколько предположений о базовой структуре данных.

(Как примечание, реализация std :: priority_queue фактически не обеспечивает свое собственное хранилище; по умолчанию она создаетstd :: vector в качестве резервного хранилища.)

Answer 2

Одна очевидная причина в том, что вы можете расположить элементы как кучу внутри другого контейнера.
Таким образом, вы можете вызвать make_heap() для vector или deque или даже для массива C.

Answer 3

Кучи * почти всегда реализуются с использованием массива в качестве базовой структуры данных.В качестве такового можно рассматривать набор алгоритмов, которые оперируют структурой данных массива.Это путь, по которому STL пошел при реализации кучи - он будет работать с любой структурой данных, имеющей итераторы произвольного доступа (стандартный массив, вектор, deque и т. Д.).

Вы также заметите, чтоSTL priority_queue требует контейнера (который по умолчанию является вектором).По сути, это ваш контейнер кучи - он реализует кучу в вашей базовой структуре данных и предоставляет контейнер-оболочку для всех типичных операций кучи.

* В частности, двоичные кучи.Других форм кучи (биномиальные, фибоначчи и т. Д.) Нет.

Answer 4

Куча - это специфическая структура данных. Стандартные контейнеры имеют требования к сложности, но не указывают, как они должны быть реализованы. Это хорошее, но важное различие. Вы можете make_heap использовать несколько разных контейнеров, включая тот, который вы написали сами. Но set или map означают не просто способ упорядочения данных.

С другой стороны, стандартный контейнер - это не просто базовая структура данных.

Answer 5

Ну, кучи на самом деле не являются универсальным контейнером в том же смысле, что и набор или карта.Обычно вы используете кучу для реализации какого-то другого абстрактного типа данных.(Наиболее очевидной является очередь с приоритетами.) Я подозреваю, что это является причиной другого подхода.