Класс set

Статья
06/09/2015

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

template <
    class Key, 
    class Traits=less<Key>, 
    class Allocator=allocator<Key> 
>
class set

Параметры

Key
Тип данных элемента для сохранения в наборе.
Traits
Тип, предоставляющий объект функции, который может сравнить два значения элемента как ключи сортировки, чтобы определить их относительный порядок в наборе. Этот аргумент является необязательным, и в качестве значения по умолчанию используется бинарный предикат less <Key>.
Allocator
Тип, представляющий сохраненный объект распределителя, который инкапсулирует сведения о выделении и освобождении памяти для набора. Этот аргумент является необязательным, и в качестве значения по умолчанию используется allocator*<Key>.*

Заметки

Набор STL выглядит следующим образом:

Ассоциативный контейнер, который является контейнером переменного размера, поддерживающим эффективное получение значений элементов на основе значения соответствующего ключа. Кроме того, это простой ассоциативный контейнер, поскольку его значения элементов являются значениями его ключей.
Является реверсивным, поскольку предоставляет двунаправленный итератор для получения доступа к его элементам.
Сортированный, поскольку его элементы упорядочены по значениям ключей в контейнере в соответствии с заданной функцией сравнения.
Является уникальным, поскольку каждый его элемент должен обладать уникальным ключом. Поскольку набор также является простым ассоциативным контейнером, его элементы также являются уникальными.

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

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

Набор рекомендуется использовать в качестве ассоциативного контейнера, если условия, ассоциирующие значения с ключами, удовлетворяются приложением. Элементы набора являются уникальным и используются в качестве своих собственных ключей сортировки. Модель для этого типа структуры — упорядоченный список, например, ключевых слов, в котором слова не должны повторяться. Если допускается повторное использование слов, то подходящей структурой контейнера будет multiset. Если значения вносятся в список уникальных ключевых слов, сопоставление является подходящей структурой для размещения этих данных. Если же ключи не являются уникальными, предпочтительным контейнером является множественное сопоставление.

Набор определяет порядок расположения элементов в последовательности, которой он управляет, путем обращения к сохраненному объекту функции типа key_compare. Этот сохраненный объект является функцией сравнения, доступ к которой можно получить путем вызова функции-члена key_comp. В целом, упорядочиваемые элементы должны лишь подлежать сравнению "меньше чем" для установления такого порядка, чтобы, имея любые два элемента, можно было определить, что они равны (ни один не меньше другого) или что один меньше другого. Это приводит к упорядочению неравнозначных элементов. С более технической точки зрения, функция сравнения является бинарным предикатом, который вызывает строгого слабое упорядочение в стандартном математически смысле. Бинарный предикат f(x,y) является объектом функции, обладающим двумя объектами аргументов x и y и возвращаемым значением true или false. Порядок, заданный для набора, является строгим слабым порядком, если бинарный предикат является нерефлексивным, антисимметричным и переходящим и если эквивалентность является переходящей, где два x и y объекта определяются как эквивалентные, тогда как оба параметра f(x,y) и f(y,x) имеют значение false. Если более строгое условие равенства между ключами заменяет условие эквивалентности, порядок становится общим (т.е. все элементы упорядочиваются относительно друг друга), и сопоставленные ключи будут неотличимы друг от друга.

Итератор, предоставляемый классом набора, является двусторонним итератором, но функции-члены класса insert и set обладают версиями, принимающими в качестве параметров шаблона более слабый итератор ввода, чьи функциональные требования ниже, чем гарантированные классом двунаправленных итераторов. Различные концепции итераторов образуют семейство, связанное уточнениями функциональности. Каждая концепция итератора имеет собственный набор требований, а алгоритмы, работающие с ними, должны ограничивать свои предположения согласно требованиям, предоставляемым этим типом итератора. Можно предположить, что итератор ввода может быть разыменован для обращения к определенному объекту и инкрементирован до следующего итератора в последовательности. Это минимальный набор функциональных возможностей, но его достаточно, чтобы иметь возможность осмысленно говорить о диапазоне итераторов [First, Last) в контексте функций-членов класса.

Конструкторы

set	Создает набор, который является пустым или копией части или целого другого набора.

Определения типов

allocator_type	Тип, представляющий класс allocator для объекта набора.
const_iterator	Тип, предоставляющий двунаправленный итератор, который может считывать тот или иной элемент const в наборе.
const_pointer	Тип, предоставляющий указатель на элемент const в наборе.
const_reference	Тип, предоставляющий ссылку на элемент const, хранящийся в наборе для чтения и выполнения операций const.
const_reverse_iterator	Тип, предоставляющий двунаправленный итератор, который может считывать любой элемент const в наборе.
difference_type	Тип целого числа со знаком, пригодный для использования в качестве представления количества элементов в наборе в диапазоне между элементами, на которые указывают итераторы.
iterator	Тип, предоставляющий двунаправленный итератор, который может считывать или изменять любой элемент в наборе.
key_compare	Тип, предоставляющий объект функции, который может сравнить два ключа сортировки для определения относительного порядка двух элементов в наборе.
key_type	Тип, описывающий объект, сохраненный как элемент набора в смысле его возможностей, присущих ключу сортировки.
указатель	Тип, предоставляющий указатель на элемент в наборе.
reference	Тип, предоставляющий ссылку на элемент, хранящийся в наборе.
reverse_iterator	Тип, предоставляющий двунаправленный итератор, который может считывать или изменять элемент в обращенном наборе.
size_type	Тип целого числа без знака, который может представлять число элементов в наборе.
value_compare	Тип, предоставляющий объект функции, который может сравнить два элемента, чтобы определить их относительный порядок в наборе.
value_type	Тип, описывающий объект, сохраненный как элемент набора в смысле его возможностей, присущих значению.

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

begin	Возвращает итератор, обращающийся к первому элементу в наборе.
cbegin	Возвращает итератор const, обращающийся к первому элементу в наборе.
cend	Возвращает итератор const, который обращается к месту, следующему за последним элементом в наборе.
clear	Стирает все элементы в наборе.
count	Возвращает число элементов в наборе, ключи которых соответствуют ключу, заданному параметром.
crbegin	Возвращает итератор const, который обращается к первому элементу в обращенном наборе.
crend	Возвращает итератор const, который обращается к месту, следующему за последним элементом в обращенном наборе.
emplace	Вставляет созданный на месте элемент в наборе.
emplace_hint	Вставляет созданный на месте элемент в наборе с подсказкой о размещении.
empty	Проверяет, пуст ли набор.
end	Возвращает итератор, который обращается к месту, следующему за последним элементом в наборе.
equal_range	Возвращает пару итераторов соответственно на первый элемент в наборе с ключом, который больше, чем указанный ключ, и на первый элемент в наборе с ключом, который больше или равен данному ключу.
erase	Удаляет элемент или диапазон элементов в наборе с заданных позиций или удаляет элементы, соответствующие заданному ключу.
find	Возвращает итератор, который обращается к местоположению элемента в наборе с ключом, эквивалентным указанному ключу.
get_allocator	Возвращает копию объекта allocator, который используется для создания набора.
insert	Вставляет элемент или диапазон элементов в набор.
key_comp	Извлекает копию объекта сравнения, который используется для упорядочивания ключей в наборе.
lower_bound	Возвращает итератор, указывающий на первый элемент в наборе с ключом, который больше или равен указанному ключу.
max_size	Возвращает максимальную длину набора.
rbegin	Возвращает итератор, который обращается к первому элементу в обращенном наборе.
rend	Возвращает итератор, который обращается к месту, следующему за последним элементом в обращенном наборе.
size	Возвращает количество элементов в наборе.
буфер обмена	Обмен элементами между двумя наборами.
upper_bound	Возвращает итератор, указывающий на первый элемент в наборе с ключом, который больше указанного ключа.
value_comp	Извлекает копию объекта сравнения, который используется для упорядочивания значений элементов в наборе.