Шаблон класса unordered_set представляет собой интрузивный контейнер, имитирующий большую часть интерфейса std::tr1::unordered_set, как описано в C++ TR1.
unordered_set представляет собой полуинтрузивный контейнер: каждый объект, подлежащий хранению в контейнере, должен содержать надлежащий крючок, но контейнер также нуждается в дополнительной вспомогательной памяти для работы: unordered_set нуждается в указателе на массив типа bucket_type, который должен быть передан в конструкторе. Этот массив ведра должен иметь, по крайней мере, тот же срок службы, что и контейнер. Это делает использование неупорядоченного_set более сложным, чем чисто навязчивые контейнеры. bucket_type является по умолчанию конструктивным, копируемым и присваиваемым
Параметр шаблона T - это тип, которым должен управлять контейнер. Пользователь может указать дополнительные опции и, если опции не предусмотрены, используются опции по умолчанию.
Контейнер поддерживает следующие опции: base_hook<>/member_hook<>/value_traits<>, constant_time_size<>, size_type<>, hash<> и equal<>, power_2_buckets<> и cache_begin<>.
unordered_set предоставляет только передовые итераторы, но предоставляет 4 типа итераторов: итератор и const_iterator для навигации по всему контейнеру и local_iterator и const_local_iterator для навигации по значениям, хранящимся в одном ведре. Местные итераторы быстрее и меньше.
Не рекомендуется использовать неупорядоченные_множества непостоянного времени, поскольку несколько ключевых функций, таких как «пустое()», становятся непостоянными функциями времени. Непостоянный размер unordered_sets в основном предоставляется для поддержки автоматических крючков.
unordered_set, в отличие от std::unordered_set, не производит автоматические перенастройки и не предлагает функции, связанные с коэффициентом загрузки. Перенастройка может быть явно запрошена, и пользователь должен предоставить новый массив ковша, который будет использоваться с этого момента.
Поскольку автоматическая перетасовка не выполняется, итераторы никогда не аннулируются при вставке или стирании элементов. Итераторы признаются недействительными только при восстановлении.
templatetypenameнеупорядоченный_setИтератор,bucket_traits,bcket_traitsbucket_traitsbucket_traits,bucket_traits,ИтераторСложность: N - расстояние(b, e): 2>=2>равный_funcравно>2>,значение_traitsНужно использовать ведра:Если N Средний случай - O(N) (с хорошей хеш-функцией и с ведрами_len >= N), худший случай O(N^2).
Броски: Если значение_черты::node_traits::node_traits::node constructor throws (это не происходит с предопределенными Boost.Intrusive hooks) или копи-конструктор или вызов хэшера или ключа_equal throws.
Заметки: массив ведер должен быть утилизирован только после *это утилизировано.
Последствия: Отделяет все элементы от этого. Объекты в unordered_set не удаляются (т.е. не называются деструкторы).
Комплексность: Линейный по количеству элементов в unordered_set, если это значение безопасного режима или авто-отсоединения. В противном случае константа.
Броски: Если ключ_равный копи-конструктор бросает.
boolempty()const;
: Эффекты: Возвращает истинное значение, если контейнер пуст.
Комплексность: если значение постоянного времени и cache_begin опции отключены, среднее постоянное время (наихудший случай, с пустым() == истинно: O(this->bucket_count()). В противном случае константа.
: Эффекты: Построение пустого неупорядоченный_set, сохранение ссылки на ковшеобразный массив и копии ключа_hasher и равных_func-функторов.
:Константа.
Броски : Если значение_traits::node_traits::node_traits::node_traits::node-traits::node-traits::node-traits::node-traits::node-constructor или вызов хеш_func или равных_func-бросков.
: Disposer::оператор()(указатель) должен уступить узлам, которые сравнивают равные и производят одинаковый хэш, чем исходный узел.
: Стирает все элементы из *этого вызывающего дисплея::оператор()(const_reference) и вставляет их на *это. Функция хеширования и предикат равенства скопированы из источника.
Если опция store_hash верна, этот метод не использует функцию хеширования.
Если какая-либо операция бросает, все клонированные элементы несвязаны и расположены, вызывая Disposer::operator()(pointer).
Сложность: Linear to erased plus inserted elements.
Throws: Если клонер или хешер бросок или хеш или равенство предикат копирования бросок. Базовая гарантия.
: Disposer::operator():Effects: Erases all the elements from src call Cloner::operator()(reference) и inserts them on *this. Функция хеширования и предикат равенства копируются из источника.
Если опция store_hash верна, этот метод не использует хеш-функцию.
Если какая-либо операция бросает, все клонированные элементы являются несвязанными и утилизируются, вызывая Disposer::operator()(pointer).
Вернет его и возвращает пару, содержащую итератор, к новому значению и истинному. Если есть эквивалентное значение возвращает пару, содержащую итератор, к уже существующему значению и ложному.
Комплексность: Средний случай O(1), наихудший случай O(this->size()).
Броски: Если бросает внутренний хешер или функтор равенства. Сильная гарантия.
Примечание : Не влияет на действительность итераторов и ссылок. Копировальными конструкторами не называются.
templatetypenamevoidinert,Iterator;
: Требуется : Отклоняющийся итератор должен давать lзначение значения типа_типа.
: Эффекты: Эквивалентно этому->insert_unique(t) для каждого элемента в [b, e].
: Средний случай O(N), где N - расстояние(b, e). Наихудший случай O(N*this->size()).
: Если внутренний хэшер или броски функтора равенства. Основная гарантия.
Примечание : Не влияет на действительность итераторов и ссылок. Копировальными конструкторами не называются.
Эффекты неупорядоченный_set с использованием предоставленного пользователем ключа вместо самого значения.
Возврат пары, содержащей итератор, к уже имеющемуся значению и ложному. Если значение может быть вставлено, возвращает истинное значение в возвращаемую пару boolean и заполняет «commit_data», которое предназначено для использования с функцией «insert_commit».
Комплексность: Средний случай O(1), наихудший случай O(this->size()).
Броски: Если есть хэшер или key_compare бросок. Сильная гарантия.
Примечания: Эта функция используется для повышения производительности при построении значения_типа дорого: при наличии эквивалентного значения построенный объект должен быть отброшен. Много раз часть узла, которая используется для наложения хэша или равенства, намного дешевле для построения, чем значение_тип, и эта функция предлагает возможность использовать эту часть для проверки, будет ли вставка успешной.
Если проверка будет успешной, пользователь может построить значение_тип и использовать "insert_commit" для вставки объекта в постоянное время.
"commit_data" остается действительным для последующего "insert_commit" только в том случае, если больше объектов не вставлено или стерто из неупорядоченного_set.
После успешного перенастройки вставка_commit_data остается действительной.
: «hash_func» вызывает те же хэш-значения, что и хранимый хэш-значения. Разница в том, что «hash_func» хэширует данный ключ вместо значения_type.
«equal_func» должен быть функцией равенства, которая вызывает то же равенство, что и ключ_equal. Разница заключается в том, что «equal_func» сравнивает произвольный ключ с содержащимися значениями.
Эффекты: Проверяет, можно ли вставить значение в неупорядоченный_set, используя предоставленный пользователем ключ вместо самого значения.
Возврат : При наличии эквивалентного значения возвращает пару, содержащую итератор, к уже имеющемуся значению и ложному. Если значение может быть вставлено, возвращает истинное значение в возвращенной паре boolean и заполняет «commit_data», которое предназначено для использования с функцией «insert_commit».
Комплексность: Средний случай O(1), наихудший случай O(this->size()).
Бросок: Если хеш_func или равно_func бросок. Сильная гарантия.
Примечания: Эта функция используется для повышения производительности при построении значения_типа дорого: при наличии эквивалентного значения построенный объект должен быть отброшен. Много раз часть узла, которая используется для наложения хэша или равенства, намного дешевле для построения, чем значение_тип, и эта функция предлагает возможность использовать эту часть для проверки того, будет ли вставка успешной.
Если проверка будет успешной, пользователь может построить значение_тип и использовать "insert_commit" для вставки объекта в постоянное время.
"commit_data" остается действительной для последующего "insert_commit" только в том случае, если больше объектов не вставлено или удалено из неупорядоченного_set.
После успешного перенастройки вставка_commit_data остается действительной.
iteratorinert_commit(ссылка значение ,constinert_commit_data& commit_data);
: значение должно быть значением типа value_type. commit_data должны быть получены из предыдущего вызова на «insert_check». Никакие объекты не должны были быть вставлены или удалены из неупорядоченного_набора между "insert_check", который заполнил "commit_data" и вызовом "insert_commit".
: Вставляется значение в неупорядоченного_набора с использованием информации, полученной из "commit_check", которую заполнил предыдущий "insert_check".
: Постоянное время.
: Ничто.
Заметки: Эта функция имеет смысл только в том случае, если "insert_check" ранее выполнялась для заполнения "commit_data". Значение не должно быть вставлено или стерто между вызовами «insert_check» и «insert_commit».
После успешного перенастройки вставка_commit_data остается в силе.
void(const_iterator i;
: Стирает элемент, на который указывает i.
: Средний случай O(1), наихудший случай O(this->size()).
: Ничего.
Примечание: Инвалидирует итераторы (но не ссылки) на стертый элемент. Деструкторы не называются.
voidconst_iterator b,const_iterator e;
: Стирает диапазон, указанный на конце b.
: Средний случай O(расстояние(b, e)), наихудший случай O(это->size()).
: Ничего.
Примечание: Инвалидирует итераторы (но не ссылки) на стертые элементы. Деструкторы не называются.
size_typeeraseconstkey_type&;
: Эффекты: Стирает все элементы с заданным значением.
: Количество стертых элементов.
: Средний случай O(это->счет(значение)). Худший случай O(this->size()).
Бросает: Если бросает внутренний шайба или функтор равенства. Основная гарантия.
Примечание: Недействительны итераторы (но не ссылки) на стертые элементы. Деструкторы не называются.
: «hash_func» должен представлять собой хеш-функцию, индуцирующую те же хеш-значения, что и хранимый хэшер. Разница в том, что «hash_func» хэширует данный ключ вместо значения_type.
«equal_func» должен быть функцией равенства, которая вызывает то же равенство, что и ключ_equal. Разница в том, что «equal_func» сравнивает произвольный ключ с содержащимися значениями.
Эффекты: Стирает все элементы, которые имеют одинаковый хеш и сравнивает с заданным ключом.
Возврат: Количество стертых элементов.
Комплексность: Средний случай O(это->счет(значение)). Наихудший случай O(this->size()).
Броски: Если хеш_func или равно_func бросок. Основная гарантия.
Примечание: Недействительны итераторы (но не ссылки) на стертые элементы. Деструкторы не называются.
templatetypenamevoidconst_iterator i,disposer;
: Disposer: : Disposer:
: Стирает элемент, на который указывает i. Disposer::operator():Complexity: Average case O(1), worst case O(this->: Nothing.
: Инвалидирует итераторы в стертые элементы.
templatetypenamevoidconst_iterator b,const_iterator e, Disposer;
: Disposer: : Disposer:
Сложность: Средний случай O(расстояние(b, e)), наихудший случай O(это->размер()).
: Disposer::operator()(52): Стирает все элементы с заданным ключом. Сравнительный функтор «equal_func». Диспозитор::оператор()(указатель) вызывается для удаленных элементов.
Возврат: Количество стертых элементов.
Комплексность: Средний случай O(это->счет(значение)). Худший случай O(this->size()).
Броски: Если хеш_func или равно_func бросок. Основная гарантия.
Примечание: Недействительны итераторы к стертым элементам.
voidclear;
: Эффекты: Стирает все элементы.
Комплексность: Линейное количество элементов на контейнере. Если это безопасный режим или авто-разъединить значение_тип. Постоянное время в противном случае.
Броски: Ничего.
Примечание: Инвалидирует итераторы (но не ссылки) на стертые элементы. Деструкторы не называются.
templatetypename Disposer>voidclear_and_dispose;
: Disposer::operator()(указатель)
: Erases all of the elements.
Комплексность: Линейный по количеству элементов на контейнере. Диспозитор::оператор()(указатель) вызывается для удаленных элементов.
Броски: Ничего.
Примечание: Недействительность итераторов (но не ссылок) на стертые элементы. Деструкторы не называются.
size_typecountkey_type &const;
: Возвращает количество содержащихся элементов с заданным значением
: Средний случай O(1), наихудший случай O(this->size()).
Бросок: Если бросает внутренний хешер или функтор равенства.
: хэш-функция индуцирует те же хэш-значения, что и хранимый хэшер. Разница в том, что «hash_func» хэширует данный ключ вместо значения_type.
«equal_func» должен быть функцией равенства, которая вызывает то же равенство, что и ключ_equal. Разница в том, что «equal_func» сравнивает произвольный ключ с содержащимися значениями.
: Возвращает число содержащихся элементов с заданным ключом
Комплексность: Средний случай O(1), наихудший случай O(this->size()).
Броски: Если хеш_func или равный бросок.
iteratorfind(constkey_type& key);
Effects: Найденный итератор к первому элементу равен "значению" или концу(), если этот элемент не существует.
Комплексность: Средний случай O(1), наихудший случай O(это->size()).
Бросает: Если бросает внутренний хешер или функтор равенства.
: «hash_func» должен представлять собой хеш-функцию, индуцирующую те же хеш-значения, что и хранимый хеш-функция. Разница в том, что «hash_func» хэширует данный ключ вместо значения_type.
«equal_func» должен быть функцией равенства, которая вызывает то же равенство, что и ключ_equal. Разница в том, что «equal_func» сравнивает произвольный ключ с содержащимися значениями.
Эффекты: Найден итератор к первому элементу, ключ которого является «ключом» в соответствии с заданным хэш-функтором равенства или концом(), если этот элемент не существует.
Сложность: Средний случай O(1), наихудший случай O(this->size()).
Броски: Если хеш_func или равно_func бросок.
Примечание: Эта функция используется при построении значения_типа дорого и значение_тип можно сравнить с более дешевым типом ключа. Обычно этот ключ является частью значения_типа.
const_iteratorfindconst&const;
: Возвращает количество содержащихся элементов с заданным значением
: Средний случай O(1), наихудший случай O(this->size()).
Бросок: Если бросает внутренний хешер или функтор равенства.
: «hash_func» должен быть хэш-функцией, индуцирующей те же хэш-значения, что и хранимый хэшер. Разница в том, что «hash_func» хэширует данный ключ вместо значения_type.
«equal_func» должен быть функцией равенства, которая вызывает то же равенство, что и ключ_equal. Разница заключается в том, что «equal_func» сравнивает произвольный ключ с содержащимися значениями.
: Найден итератор первого элемента, ключ которого является «ключом» в соответствии с заданным хешером и функтором равенства или концом(), если этот элемент не существует.
Сложность: Средний случай O(1), наихудший случай O(this->size()).
: Броски: Если хеш_func или равно_func бросок.
Примечание: Эта функция используется при построении значения_типа дорого и значение_тип можно сравнить с более дешевым типом ключа. Обычно этот ключ является частью значения_типа.
std::,iterator>equal_range(constkey_type&;
: Возвращает диапазон, содержащий все элементы со значениями, эквивалентными значению. Возвращает std::make_pair(this->end(), this->end()), если таких элементов не существует.
Сложность: Средний случай O(this->count(value)). Наихудший случай O(this->size()).
Бросает: Если бросает внутренний шайба или функтор равенства.
: «hash_func» должен представлять собой хэш-функцию, индуцирующую те же хэш-значения, что и хранимый хэш-функция. Разница в том, что «hash_func» хэширует данный ключ вместо значения_type.
«equal_func» должен быть функцией равенства, которая вызывает то же равенство, что и ключ_equal. Разница в том, что «equal_func» сравнивает произвольный ключ с содержащимися значениями.
Эффекты: Возвращает диапазон, содержащий все элементы с эквивалентными ключами. Возвращает std::make_pair(this->end(), this->end()), если таких элементов не существует.
Комплексность: Средний случай O(this->count(key, hash_func, equal_func)). Худший случай O(this->size()).
Броски: Если хеш_func или равно_func бросок.
Примечание: Эта функция используется при построении значения_типа дорого и значение_тип можно сравнить с более дешевым ключевым типом. Обычно этот ключ является частью значения_типа.
: Возвращает диапазон, содержащий все элементы со значениями, эквивалентными значению. Возвращает std::make_pair(this->end(), this->end()), если таких элементов не существует.
Сложность: Средний случай O(this->count(value)). Худший случай O(this->size()).
Бросает: Если бросает внутренний хешер или функтор равенства.
: «hash_func» должен представлять собой хеш-функцию, индуцирующую те же хеш-значения, что и хранимый хеш-функция. Разница в том, что «hash_func» хэширует данный ключ вместо значения_type.
«equal_func» должен быть функцией равенства, которая вызывает то же равенство, что и ключ_equal. Разница в том, что «equal_func» сравнивает произвольный ключ с содержащимися значениями.
Эффекты: возвращает диапазон, содержащий все элементы с эквивалентными ключами. Возвращает std::make_pair(this->end(), this->end()), если таких элементов не существует.
Комплексность: Средний случай O(this->count(key, hash_func, equal_func)). Наихудший случай O(this->size()).
Броски: Если хешер или равный_func бросок.
Примечание: Эта функция используется при построении значения_типа дорого и значение_тип можно сравнить с более дешевым ключевым типом. Обычно этот ключ является частью значения_типа.
iteratoriterator_to(ссылказначение);
Требования: Значение должно быть lvalue и должно быть в неупорядоченный_set соответствующего типа. В противном случае поведение не определено.
Эффекты: Возврат: действительный итератор, принадлежащий неупорядоченный_set, который указывает на значение
: «hash_func» должен представлять собой хеш-функцию, индуцирующую те же хеш-значения, что и хранимый хэш-функция. Разница в том, что «hash_func» хэширует данный ключ вместо значения_type.
: Возвращает индекс ведра, в котором были бы найдены элементы с ключами, эквивалентными k, если бы такой элемент существовал.
: Constant.
Броски: Если хеш_func бросает.
Примечание: значение возврата находится в диапазоне [0, this->bucket_count()).
bucket_ptrbucket_pointerconst;
: Эффекты: Возвращает указатель массива ковша, прошедший в конструкторе или последней функции рехэша.
: Константа.
Броски: Ничего.
local_iteratorbeginsize_type;
: n находится в диапазоне [0, this->bucket_count()]
Комплексность:Константа.
:Ничего.
Примечание: [this->begin(n), this->end(n)) представляет собой допустимый диапазон, содержащий все элементы в n-м ведре.
const_local_iteratorbeginsize_typen)const;
: n находится в диапазоне [0, this->bucket_count()]
Комплексность:Константа.
:Ничего.
Примечание: [this->begin(n), this->end(n)) представляет собой допустимый диапазон, содержащий все элементы в n-м ведре.
: new_bucket_traits может содержать указатель на новый ковшовый массив или такой же, как старый ковшовый массив с другой длиной. new_size — длина массива, на который указывают new_buckets. Если new_bucket_traits.bucket_begin() == this->bucket_pointer() new_bucket_traits.bucket_count() может быть больше или меньше, чем this->bucket_count(). Конструктор копий 'new_bucket_traits' не должен бросать.
Effects: Если new_bucket_traits.bucket_begin() == this->bucket_pointer() == this->bucket_pointer() является ложным, нессылки значений из старого ковша и вставок то в новом согласно хеш-значению значений.
new_bucket_traits.bucket_pointer() == this->bucket_pointer() верны, реализации избегают перемещения значений настолько, насколько это возможно.
Bucket traits hold by * Если контейнер сконфигурирован как incremental<>, разделённое ведро устанавливается на новую bucket_count().
Если опция store_hash верна, этот метод не использует хеш-функцию. Если ложно, реализация пытается минимизировать вызовы к хеш-функции (например, один раз для эквивалентных значений, если оптимизация_multikey верна).
Если рехэш успешно обновляет внутренние bucket_traits с новыми_bucket_traits.
Комплексность: Средний линейный случай в этом->size(), худший случай квадратичен.
Броски: Если бросает хеш-функтор. Базовая гарантия.
voidfull_rehash;
Примечание: Эта функция используется при изменении ключей от вставленных элементов (например, при изменении языка, когда ключом является строка), но при этом сохраняется уникальность и свойства хэша, поэтому быстрое полное восстановление рехэша восстанавливает инварианты для * этого без извлечения и повторного вставки всех элементов.
Требуется: Звонки, производимые для хеш-функции, не должны изменять значения свойств уникальности уже вставленных элементов. Если гашер(ключ1) == гашер(ключ2) был верен при вставке элементов, то он должен быть верен при вызовах, произведенных при выполнении этой функции.
key_equal не называется внутри этой функции, поэтому предполагается, что ключ_equal(значение1, значение2) должен давать те же результаты, что и раньше для вставленных элементов.
Эффекты: Перерабатывает все значения, удерживаемые этим, пересчитывая их хеш-значения и перераспределяя их через ведра.
store_hash опция верна, этот метод использует хеш-функцию
Средняя линейная в этом->size(), худший случай квадратичен.
Броски: Если кидает функтор гашера. Базовая гарантия.
boolincremental_rehashbool grow =true;
Требования:
:2>Комплексность::Примечание: Данный способ доступен только при активации опции incremental.
bool>bucket_traits;
: Если new_bucket_traits.bucket_count() или this->bucket_count()*2, или this->split_bucket()!= new_bucket_traits.bucket_count() возвращает ложные и ничего не делает.
bucket_traits и переносит все объекты из старых ведерКомплексность: Ничто
Примечание: этот способ доступен только при активации опции incremental.
size_typesplit_countconst;
Требования: инкрементальный<> опция должна быть установлена
Возвращает ближайшее новое количество ведра, оптимизированное для контейнера, который больше или равен n. Это предложение может быть использовано для создания ковшовых массивов с размером, который обычно улучшает производительность контейнера. Если такого значения не существует, возвращается более высокое возможное значение.
Возвращает ближайшее новое количество ведра, оптимизированное для контейнера, который меньше или равен n. Это предложение может быть использовано для создания ковшовых массивов с размером, который обычно улучшает производительность контейнера. Если такого значения не существует, возвращается наименьшее возможное значение.
Сложность: Амортизированное постоянное время.
Броски: Ничего.
Статья Class template unordered_set раздела The Boost C++ Libraries BoostBook Documentation Subset Reference может быть полезна для разработчиков на c++ и boost.
