Namespaces
Variants

std:: flat_set

From cppreference.net
C++
Containers library
std::flat_set
Member types
Member functions
Helper classes
Tags
Deduction guides
Определено в заголовочном файле <flat_set>
template <

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

> class flat_set ;
(начиная с C++23)

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

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

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

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

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

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

Все функции-члены std::flat_set являются constexpr : возможно создавать и использовать объекты std::flat_set при вычислении константного выражения.

Однако, объекты std::flat_set обычно не могут быть constexpr , поскольку любая динамически выделенная память должна быть освобождена в том же вычислении константного выражения.

(since C++26)

Содержание

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

Этот раздел не завершён

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

Key - Тип хранимых элементов. Программа является некорректной, если Key не является тем же типом, что и KeyContainer::value_type .
Compare - Тип Compare , предоставляющий строгое слабое упорядочение.
KeyContainer - Тип базового SequenceContainer для хранения элементов. Итераторы такого контейнера должны удовлетворять требованиям LegacyRandomAccessIterator или моделировать random_access_iterator .

Стандартные контейнеры std::vector и std::deque удовлетворяют этим требованиям.

Типы членов

Тип Определение
container_type Key Container
key_type Key
value_type Key
key_compare Compare
value_compare Compare
reference value_type &
const_reference const value_type &
size_type typename KeyContainer :: size_type
difference_type typename KeyContainer :: difference_type
iterator определяемый реализацией LegacyRandomAccessIterator , ConstexprIterator (начиная с C++26) и random_access_iterator для value_type
const_iterator определяемый реализацией LegacyRandomAccessIterator , ConstexprIterator (начиная с C++26) и random_access_iterator для const value_type
reverse_iterator std:: reverse_iterator < iterator >
const_reverse_iterator std:: reverse_iterator < const_iterator >

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

Участник Описание
container_type c (private) адаптированный контейнер
( объект-член только для демонстрации* )
key_compare compare (private) функциональный объект сравнения
( объект-член только для демонстрации* )

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

конструирует flat_set
(публичная функция-член)
(destructor)
(implicitly declared)
уничтожает каждый элемент адаптера контейнера
(public member function)
присваивает значения адаптеру контейнера
(публичная функция-член)
Итераторы
возвращает итератор на начало
(публичная функция-член)
возвращает итератор на конец
(публичная функция-член)
возвращает обратный итератор на начало
(публичная функция-член)
возвращает обратный итератор на конец
(публичная функция-член)
Ёмкость
проверяет, является ли адаптер контейнера пустым
(публичная функция-член)
возвращает количество элементов
(public member function)
возвращает максимально возможное количество элементов
(публичная функция-член)
Модификаторы
создаёт элемент на месте
(публичная функция-член)
создаёт элементы на месте с использованием подсказки
(публичная функция-член)
вставляет элементы
(публичная функция-член)
вставляет диапазон элементов
(публичная функция-член)
извлекает базовый контейнер
(публичная функция-член)
заменяет базовый контейнер
(публичная функция-член)
удаляет элементы
(public member function)
обменивает содержимое
(public member function)
очищает содержимое
(публичная функция-член)
Поиск
находит элемент с указанным ключом
(публичная функция-член)
возвращает количество элементов, соответствующих заданному ключу
(публичная функция-член)
проверяет, содержит ли контейнер элемент с указанным ключом
(публичная функция-член)
возвращает итератор на первый элемент не меньший чем заданный ключ
(публичная функция-член)
возвращает итератор на первый элемент больший чем заданный ключ
(публичная функция-член)
возвращает диапазон элементов, соответствующих заданному ключу
(публичная функция-член)
Наблюдатели
возвращает функцию, которая сравнивает ключи
(public member function)
возвращает функцию, которая сравнивает ключи в объектах типа value_type
(публичная функция-член)

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

(C++23)
лексикографически сравнивает значения двух flat_set ов
(шаблон функции)
(C++23)
специализирует алгоритм std::swap
(шаблон функции)
(C++23)
удаляет все элементы, удовлетворяющие определённым критериям
(шаблон функции)

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

(C++23)
специализирует std::uses_allocator type trait
(специализация шаблона класса)

Теги

(C++23)
указывает, что элементы диапазона отсортированы и уникальны
(тег)

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

Примечания

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

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

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

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

  • Нестабильные итераторы (итераторы становятся недействительными при вставке и удалении элементов).
  • Невозможно хранить значения некопируемых и неперемещаемых типов.
  • Ослабленная гарантия безопасности исключений (конструкторы копирования/перемещения могут выбрасывать исключения при сдвиге значений при удалениях и вставках).
  • Более медленные (т.е. линейные) вставка и удаление, особенно для неперемещаемых типов.
Макрос тестирования возможностей Значение Стандарт Функция
__cpp_lib_flat_set 202207L (C++23) std::flat_set и std::flat_multiset
__cpp_lib_constexpr_flat_set 202502L (C++26) constexpr std::flat_set

Пример

Этот раздел не завершён
Причина: отсутствует пример

Смотрите также

(C++23)
адаптирует контейнер для предоставления коллекции ключей, отсортированных по ключам
(шаблон класса)
коллекция уникальных ключей, отсортированных по ключам
(шаблон класса)
(C++11)
коллекция уникальных ключей, хэшированных по ключам
(шаблон класса)