Существует ли класс sorted_vector, который поддерживает insert () и т. Д.?

Question

Часто более эффективно использовать отсортированный std::vector вместо std::set. Кто-нибудь знает библиотечный класс sorted_vector, который в основном имеет интерфейс, аналогичный std::set, но вставляет элементы в отсортированный вектор (чтобы не было дубликатов), использует двоичный поиск для find элементов и т. Д .?

Я знаю, что писать не сложно, но, вероятно, лучше не тратить время и в любом случае использовать существующую реализацию.

Обновление: Причина использования отсортированного вектора вместо набора: если у вас есть сотни тысяч маленьких наборов, содержащих по 10 или более членов в каждом, это более эффективно для памяти, чем просто вместо этого используйте отсортированные векторы.

Answer 1

Boost.Container flat_set

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, если диапазон [первый, последний) уже отсортирован с использованием comp, в противном случае N * log (N) , где N - последний - первый.

Answer 2

Причина, по которой такой контейнер не является частью стандартной библиотеки, заключается в том, что он будет неэффективным. Использование вектора для хранения означает, что объекты должны быть перемещены, если что-то вставлено в середину вектора. Делать это на каждой вставке становится излишне дорого. (В среднем, половину объектов придется перемещать для каждой вставки. Это довольно дорого)

Если вы хотите отсортированный вектор, то, вероятно, лучше вставить все элементы и затем вызвать std::sort() один раз после вставок.

Answer 3

Я думаю, что в STL нет адаптера «отсортированный контейнер», потому что уже есть соответствующие ассоциативные контейнеры для хранения отсортированных вещей, которые можно было бы использовать почти во всех случаях. Честно говоря, единственной причиной, по которой я могу придумать, что у меня отсортированный контейнер vector<>, может быть взаимодействие с функциями C, которые ожидают отсортированный массив. Конечно, я могу что-то упустить.

Если вы считаете, что отсортированный vector<> будет более подходящим для ваших нужд (учитывая недостатки вставки элементов в вектор), вот реализация кода проекта:

• STL-совместимый отсортированный вектор. Автор Martin Holzherr

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

Кажется, стоит присмотреться.

Answer 4

Если вы решите бросить свой собственный, вы также можете проверить boost: ublas. В частности:

#include <boost/numeric/ublas/vector_sparse.hpp>

и посмотрите на координату-вектор, которая реализует вектор значений и индексов. Эта структура данных поддерживает вставку O (1) (нарушая сортировку), но затем сортирует Omega по требованию (n log n). Конечно, после того, как он отсортирован, поиск O (logn). Если часть массива отсортирована, алгоритм распознает это и сортирует только недавно добавленные элементы, а затем выполняет слияние на месте. Если вы заботитесь об эффективности, это, вероятно, лучшее, что вы можете сделать.

Answer 5

Локи Александресу имеет сортированную векторную реализацию, если вы не хотите проходить через несущественную релятивистскую работу по раскрутке своего собственного.

http://loki -lib.sourceforge.net / html / a00025.html

Answer 6

Здесь - это мой класс sorted_vector, который я использовал в производственном коде годами. Он перегружен, чтобы позволить вам использовать пользовательский предикат. Я использовал его для контейнеров указателей, что может быть действительно хорошим решением во многих случаях использования.