Существует ли класс sorted_vector, который поддерживает insert() и т. Д.?
Часто более эффективно использовать отсортированный std::vector вместо std::set, Кто-нибудь знает класс библиотеки sorted_vectorкоторый в основном имеет аналогичный интерфейс std::set, но вставляет элементы в отсортированный вектор (чтобы не было дубликатов), использует бинарный поиск для find элементы и т. д.?
Я знаю, что это не сложно написать, но, вероятно, лучше не тратить время и в любом случае использовать существующую реализацию.
Обновление. Причина использования отсортированного вектора вместо набора: если у вас есть сотни тысяч маленьких наборов, содержащих по 10 или более членов каждый, то вместо использования памяти будет более эффективно использовать отсортированные векторы.
6 ответов
Контейнеры Boost.Container flat_[multi]map/set представляют собой ассоциативные контейнеры на основе упорядоченного вектора, основанные на рекомендациях Аустерна и Александреску. Эти упорядоченные векторные контейнеры также недавно получили выгоду благодаря добавлению семантики перемещения в C++, что значительно ускоряет вставку и стирание. Плоские ассоциативные контейнеры имеют следующие атрибуты:
- Более быстрый поиск, чем стандартные ассоциативные контейнеры
- Гораздо более быстрая итерация, чем у стандартных ассоциативных контейнеров.
- Меньшее потребление памяти для маленьких объектов (и для больших объектов, если используется shrink_to_fit)
- Улучшена производительность кеша (данные хранятся в непрерывной памяти)
- Нестабильные итераторы (итераторы недействительны при вставке и удалении элементов)
- Не копируемые и неподвижные типы значений не могут быть сохранены
- Более низкая безопасность исключений по сравнению со стандартными ассоциативными контейнерами (конструкторы копирования / перемещения могут выдавать при смещении значений в стираниях и вставках)
- Более медленная вставка и стирание, чем у стандартных ассоциативных контейнеров (особенно для неподвижных типов)
#include <boost/container/flat_set.hpp>
#include <iostream>
#include <ostream>
using namespace std;
int main()
{
boost::container::flat_set<int> s;
s.insert(1);
s.insert(2);
s.insert(3);
cout << (s.find(1)!=s.end()) << endl;
cout << (s.find(4)!=s.end()) << endl;
}
jalf: Если вы хотите отсортированный вектор, вероятно, лучше вставить все элементы и затем вызвать std::sort() один раз, после вставки.
boost:: flat_set может сделать это автоматически:
template<typename InputIterator>
flat_set(InputIterator first, InputIterator last,
const Compare & comp = Compare(),
const allocator_type & a = allocator_type());
Эффекты: Создает пустой набор, используя указанный объект сравнения и распределитель, и вставляет элементы из диапазона [first, last).
Сложность: Линейный по N, если диапазон [first, last) уже отсортирован с использованием comp, в противном случае N * log (N), где N - last - first.
Причина, по которой такой контейнер не является частью стандартной библиотеки, заключается в том, что он будет неэффективным. Использование вектора для хранения означает, что объекты должны быть перемещены, если что-то вставлено в середину вектора. Делать это на каждой вставке становится излишне дорого. (В среднем, половину объектов придется перемещать для каждой вставки. Это довольно дорого)
Если вы хотите отсортированный вектор, вероятно, лучше вставить все элементы, а затем вызвать std::sort() один раз, после вставок.
Я думаю, что в STL нет адаптера "отсортированный контейнер", потому что уже есть соответствующие ассоциативные контейнеры для хранения отсортированных вещей, которые было бы целесообразно использовать почти во всех случаях. Честно говоря, об единственной причине, которую я могу придумать из головы за то, что я сортировал vector<> Контейнер может взаимодействовать с функциями C, которые ожидают отсортированный массив. Конечно, я могу что-то упустить.
Если вы чувствуете, что отсортировано vector<> было бы более подходящим для ваших потребностей (учитывая недостатки вставки элементов в вектор), вот реализация на Code Project:
Я никогда не использовал его, поэтому я не могу ручаться за него (или его лицензию - если таковая указана). Но быстро прочитайте статью и похоже, что автор, по крайней мере, приложил немало усилий, чтобы контейнерный адаптер имел соответствующий интерфейс STL.
Кажется, стоит присмотреться.
Если вы решите бросить свой собственный, вы также можете проверить boost:ublas. В частности:
#include <boost/numeric/ublas/vector_sparse.hpp>
и посмотрите на координаты_вектора, который реализует вектор значений и индексов. Эта структура данных поддерживает вставку O(1) (нарушая сортировку), но затем сортирует Omega по требованию (n log n). Конечно, после того, как это отсортировано, поиск O(logn). Если часть массива отсортирована, алгоритм распознает это и сортирует только недавно добавленные элементы, а затем выполняет слияние на месте. Если вы заботитесь об эффективности, это, вероятно, лучшее, что вы можете сделать.
Локи Александресу имеет сортированную векторную реализацию, если вы не хотите проходить через несущественное усилие по релятивистскому движению.
Вот мой класс sorted_vector, который я использовал в производственном коде в течение многих лет. Он перегружен, чтобы позволить вам использовать пользовательский предикат. Я использовал его для контейнеров указателей, которые могут быть действительно хорошим решением во многих случаях использования.