std::flat_set

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

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

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

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

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

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

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

Аннулирование итераторов

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

Типы членов

Члены-объекты

Члены-функции

Нечленные функции

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

Метки

Руководства по выводу типов

Примечания

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

Некоторые преимущества flat set над другими стандартными ассоциативными контейнерами:

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

Некоторые недостатки flat set:

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

Пример

См. также