std::flat_set

template<
    class Key,
    class Compare = std::less<Key>,
    class KeyContainer = std::vector<Key>
> class flat_set;

Плоское множество — это адаптер контейнера, предоставляющий функциональность ассоциативного контейнера, в котором хранится отсортированный набор уникальных объектов типа Key. Сортировка выполняется с помощью функции сравнения ключей Compare.

Шаблон класса flat_set служит оболочкой для базового отсортированного контейнера, передаваемого как объект типа KeyContainer.

Везде, где стандартная библиотека использует требования Compare, уникальность определяется с помощью отношения эквивалентности. Неформально, два объекта a и b считаются эквивалентными, если ни один из них не сравнивается как меньший другого: !comp(a, b) && !comp(b, a).

std::flat_set соответствует требованиям Container, ReversibleContainer, необязательным требованиям к контейнерам и всем требованиям AssociativeContainer (включая логарифмическую сложность поиска), за исключением следующего:

• требования, относящиеся к узлам, неприменимы;
• требования к инвалидированию итераторов отличаются;
• сложность операций вставки и удаления линейна.

Плоское множество поддерживает большинство операций AssociativeContainer, использующих уникальные ключи.

Инвалидирование итераторов

Параметры шаблона

Типы-члены

Объекты-члены

Функции-члены

Функции, не являющиеся членами

Вспомогательные классы

Теги

Руководства по выведению аргументов шаблона

Примечания

Типы-члены iterator и const_iterator могут быть псевдонимами одного и того же типа. Это означает, что определение пары перегруженных функций, использующих эти два типа в качестве типов параметров, может нарушать правило одного определения. Поскольку iterator преобразуется в const_iterator, вместо этого подойдёт одна функция с параметром типа const_iterator.

Некоторые преимущества плоского множества по сравнению с другими стандартными адаптерами контейнеров:

• Потенциально более быстрый поиск (несмотря на логарифмическую сложность операций поиска).
• Значительно более быстрая итерация: итераторы произвольного доступа вместо двунаправленных итераторов.
• Меньшее потребление памяти для небольших объектов (а также для больших объектов, если доступен KeyContainer::shrink_to_fit()).
• Более эффективное использование кэша (в зависимости от KeyContainer, ключи хранятся в одном или нескольких непрерывных блоках памяти).

Некоторые недостатки плоского множества:

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

Пример

См. также