Мне было интересно, почему концепция кучи реализована в виде алгоритмов (make_heap, pop_heap, push_heap, sort_heap) вместо контейнера. Меня особенно интересует какое-то одно решение, которое также может объяснить, почему set и map являются контейнерами вместо похожих наборов алгоритмов (make_set add_set rm_set и т.д.).
Почему кучи в С++ реализованы как алгоритмы вместо контейнеров?
Ответ 1
STL предоставляет кучу в виде std:: priority_queue. Функции make_heap и т.д. Существуют потому, что они используют вне области самой структуры данных (например, сортировку) и позволяют создавать кучи поверх настраиваемых структур (например, массивы стеков для "держать верхние 10" ) контейнер).
По аналогии, вы можете использовать std:: set для хранения отсортированного списка, или вы можете использовать std:: sort для вектора с std:: adj_find; std:: sort является более универсальным и делает несколько предположений о базовой структуре данных.
(В качестве примечания, реализация std:: priority_queue на самом деле не обеспечивает его собственное хранилище, по умолчанию он создает std::vector в качестве хранилища поддержки.)
Ответ 2
Одна очевидная причина заключается в том, что вы можете расположить элементы как кучу внутри другого контейнера.
Таким образом, вы можете вызвать make_heap() в vector или deque или даже в массиве C.
Ответ 3
Куча - это конкретная структура данных. Стандартные контейнеры имеют требования к сложности, но не указывают, как они должны быть реализованы. Это прекрасное, но важное различие. Вы можете make_heap на нескольких разных контейнерах, включая тот, который вы написали сами. Но set или map означают больше, чем просто способ организации данных.
С другой стороны, стандартный контейнер больше, чем просто его базовая структура данных.
Ответ 4
Heaps * почти всегда реализуются с использованием массива в качестве базовой структуры данных. Таким образом, это можно рассматривать как набор алгоритмов, которые работают с структурой данных массива. Это путь, который STL взял при реализации кучи - он будет работать с любой структурой данных, в которой есть итераторы с произвольным доступом (стандартный массив, вектор, deque и т.д.).
Вы также заметите, что для STL priority_queue требуется контейнер (который по умолчанию является вектором). Это по сути ваш контейнер кучи - он реализует кучу в вашей базовой структуре данных и предоставляет контейнер-оболочку для всех типичных операций кучи.
* Бинарные кучи в частности. Другие формы куч (Биномиальный, Фибоначчи и т.д.) Не являются.
Ответ 5
Ну, кучи на самом деле не являются общим контейнером в том же смысле, что и набор или карта. Обычно вы используете кучу для реализации другого абстрактного типа данных. (Наиболее очевидным является очередь приоритетов.) Я подозреваю, что это причина различного обращения.