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