Подтвердить что ты не робот

Есть класс sorted_vector, который поддерживает insert() и т.д.?

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

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

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

4b9b3361

ОТВЕТЫ

Ответ 1

Boost.Container flat_set

Boost.Container flat_ [multi] map/set контейнеры - это упорядоченные векторные ассоциативные контейнеры на основе рекомендаций Austern и Alexandrescu. Эти упорядоченные векторные контейнеры также получили выгоду в последнее время, добавив семантику перемещения в С++, значительно ускорив время вставки и стирания. Плоские ассоциативные контейнеры имеют следующие атрибуты:

  • Более быстрый поиск, чем стандартные ассоциативные контейнеры.
  • Гораздо более быстрая итерация, чем стандартные ассоциативные контейнеры.
  • Меньшее потребление памяти для небольших объектов (и для больших объектов, если используется 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());

Эффекты. Создает пустой набор с использованием указанного объекта сравнения и распределителя и вставляет элементы из диапазона [первый, последний].

Сложность: линейная в N, если диапазон [первый, последний] уже отсортирован с использованием comp и иначе N * log (N), где N - последний - первый,

Ответ 2

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

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

Ответ 3

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

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

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

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

Ответ 4

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

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

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

Ответ 5

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

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

Ответ 6

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