Существует ли sorted_vector класс, который поддержки вставляют () и т.д.?
Часто, более эффективно использовать отсортированный std::vector вместо a std::set. Делает любой знает класс библиотеки sorted_vector, который в основном имеет подобный интерфейс к std::set, но вставляет элементы в отсортированный вектор (так, чтобы не было никаких дубликатов), двоичный поиск использования к find элементы, и т.д.?
Я знаю, что не трудно записать, но вероятно лучше не напрасно тратить время и использовать существующую реализацию так или иначе.
Обновление: причина использовать отсортированный вектор вместо набора: Если у Вас есть сотни тысяч небольших наборов, которые содержат только приблизительно 10 участников каждый, более эффективно памятью просто использовать отсортированные векторы вместо этого.
4 ответа
Причина, по которой такой контейнер не является частью стандартной библиотеки, заключается в том, что он был бы неэффективным. Использование вектора для хранения означает, что объекты должны быть перемещены, если что-то вставлено в середину вектора. Выполнение этого на при каждой вставке становится излишне дорогостоящим. (В среднем половину объектов придется перемещать при каждой вставке. Это довольно дорого.)
Если вам нужен отсортированный вектор, вероятно, лучше вставить все элементы, а затем вызвать std :: sort () один раз , после прошивок.
Я думаю, что в STL нет адаптера «сортированного контейнера», потому что уже есть соответствующие ассоциативные контейнеры для сортировки вещей, которые можно было бы использовать почти в все дела. Честно говоря, единственная причина, по которой я могу прийти в голову для наличия отсортированного контейнера vector <> , может заключаться в взаимодействии с функциями C, которые ожидают отсортированный массив. Конечно, я могу чего-то упустить.
Если вы считаете, что отсортированный вектор <> будет более подходящим для ваших нужд (учитывая недостатки вставки элементов в вектор), вот реализация в Code Project:
Я никогда не использовал его, поэтому не могу поручиться за него (или его лицензию - если таковая указана). Но быстрое прочтение статьи, и похоже, что автор, по крайней мере, приложил все усилия, чтобы контейнерный адаптер имел соответствующий интерфейс STL.
Кажется, стоит присмотреться.
У Локи Александресу есть реализация отсортированного вектора, если вы не хотите подвергать себя незначительным относительным усилиям по прокручиванию собственных рук.
Если вы решите попробовать свои силы, вы также можете попробовать boost: ublas. В частности:
#include <boost/numeric/ublas/vector_sparse.hpp>
и посмотрите на координату_вектора, которая реализует вектор значений и индексов. Эта структура данных поддерживает вставку O (1) (нарушение сортировки), но затем сортирует по запросу Omega (n log n). Конечно, после сортировки поиск выполняется O (logn). Если часть массива сортируется, алгоритм распознает это и сортирует только недавно добавленные элементы, а затем выполняет слияние на месте. Если вы заботитесь об эффективности, это, вероятно, лучшее, что вы можете сделать.