возможно ли установить std :: vector в качестве основного хранилища для хранения его элементов?

Question

Для небольших коллекций std :: vector почти наверняка является лучшим контейнером, независимо от того, какие операции к нему применяются. Возможно ли использовать std :: vector в качестве основного хранилища для контейнера набора элементов вместо красно-черного дерева, включающего много выделений кучи (может быть, в boost есть что-то?), Или я должен сам его изобрести?

Обычные std :: vector и std :: sort не доступны по соображениям производительности, а std :: inplace_merge подвержен ошибкам кодирования (аннулирование итераторов и т. Д.).

РЕДАКТИРОВАТЬ : уточнил вопрос

Answer 1

Нет способа указать базовую структуру набора STL.В лучшем случае вы можете написать распределитель, который использует вектор для предоставления памяти, используемой множеством, что может быть, а может и не быть тем, что вы хотите.

Answer 2

Я думаю, вы ищете boost :: container :: flat_set

flat_set похож на std :: set, но реализован как упорядоченный вектор.

Answer 3

для небольших размеров все контейнеры довольно эффективны; просто используйте set, если вы не знаете, что у вас проблемы с производительностью

в вашем случае

с использованием функции векторных торгов (сортировка, уникальность) для размера хранилища

использование набора делает противоположное

Если вам нужна сортировка и уникальность, выберите контейнер с этой функцией, если вы не уверены, что это плохая сделка

Answer 4

Если вы имеете в виду, можете ли вы иметь

std::set<std::vector<MyType> > myIdealContainer;

, тогда ответ - да, при условии, что вы можете осмысленно обернуть вектор во что-то, что делает его сортируемым (поэтому set может упорядочить его члены).Однако остерегайтесь неэффективного копирования.

Если вы имеете в виду, могу ли я создать экземпляр set с вектором в качестве хранилища для пользовательского распределителя, тогда я не знаю, как вы это сделаете (или почему вы этого захотите).

Если вы имеете в виду, можете ли вы относиться к вектору так же, как к набору, то ответ - нет.если ваш набор данных небольшой и соответствующий элемент контейнера дешев, используйте вектор, сохраняйте порядок на вставках и сканируйте линейно на совпадения, используя std :: find.Если набор данных большой и / или сопоставление дорогое, используйте set.

Answer 5

Возможно, я вас неправильно понял, но если вы пытаетесь использовать std :: set, который имеет std :: vector для хранения данных (поэтому все данные набора на самом деле хранятся в векторе), тогда ответ должен быть "нет".
Причина этого в том, что реализация c ++ std :: set представляет собой двоичное дерево поиска, а std :: vector управляет простым блоком массива / памяти.

Answer 6

Нет, невозможно указать контейнер для использования для std::set, это можно сделать только с помощью адаптеров контейнера, таких как std::queue или std::stack. std::set является одним из базовых контейнеров со своими требованиями к производительности. std::vector может быть не лучшим контейнером для всех случаев. Например, если вам нужна хорошая производительность поиска, вы бы выбрали set, так как find равно O(log n), а для вектора - O(n)