unordered_set_of Reference . Boost , Chapter 1. Boost.Bimap , Reference

namespace boost {
namespace bimaps {
template
<
    class KeyType,
    class HashFunctor   = hash< KeyType >,
    class EqualKey      = std::equal_to< KeyType >
>
struct unordered_set_of;
template
<
    class HashFunctor   = hash< _relation >,
    class EqualKey      = std::equal_to< _relation >
>
struct unordered_set_of_relation;
} // namespace bimap
} // namespace boost

Header "boost/bimap/unordered_multiset_of.hpp" synopsis

namespace boost {
namespace bimaps {
template
<
    class KeyType,
    class HashFunctor   = hash< KeyType >,
    class EqualKey      = std::equal_to< KeyType >
>
struct unordered_multiset_of;
template
<
    class HashFunctor   = hash< _relation >,
    class EqualKey      = std::equal_to< _relation >
>
struct unordered_multiset_of_relation;
} // namespace bimap
} // namespace boost

Collection type specifiers unordered_set_of and unordered_multiset_of

Эти спецификаторы типов сбора позволяют устанавливать представления без и с учетом дублирующих элементов, соответственно. Синтаксис set_of и multiset_of совпадают, поэтому мы описываем их сгруппированным образом.

unordered_[multi]set_of Views

Complexity signature
Instantiation types
Nested types
Constructors, copy and assignment
Modifiers
Lookup
at(), info_at() and operator[] - set_of only
Hash policy
Serialization

Неупорядоченный_[multi]set_of set view представляет собой tr1::неупорядоченный [multi]set signature compatible interface к лежащей в основе куче элементов, содержащихся в bimap.

Интерфейс и семантика просмотров неупорядоченный_[мульти]set_of моделируются в соответствии с предложением для неупорядоченных ассоциативных контейнеров, приведенным в C++ Стандартный библиотечный технический отчет , также известный как TR1. неупорядоченный_[multi]set_of вид конкретизируется согласно заданному Hash функциональному объекту, который возвращает хеш-значения для ключей и двоичному предикату Pred, действующему как отношение эквивалентности на значения Ключа.

Существует два варианта: unordered_set_of, которые не допускают дублирования элементов (по отношению к связанному с ним предикату сравнения) и unordered_multiset_of, которые принимают эти дубликаты. Интерфейс этих двух вариантов в значительной степени одинаков, поэтому они документируются вместе с их различиями, явно отмеченными при их существовании.

Если вы посмотрите на карту сбоку, вы будете использовать вид карты, и если вы посмотрели ее в целом, вы будете использовать заданный вид.

За исключением отмеченных случаев, неупорядоченный_[мульти]набор_of просмотров (как уникальных, так и неуникальных) являются моделями Неупорядоченный ассоциативный контейнер. Действительность итераторов и отсылок к элементам сохраняется во всех случаях. Иногда предоставленные гарантии безопасности исключения на самом деле сильнее, чем требуется проектом продления. Мы предоставляем только описания тех типов и операций, которые либо не присутствуют в моделируемых концепциях, либо не соответствуют требованиям к неупорядоченным ассоциативным контейнерам.

namespace boost {
namespace bimap {
namespace views {
template< -implementation defined parameter list- >
class -implementation defined view name-
{
    public:
    // types
    typedef -unspecified- key_type;
    typedef -unspecified- value_type;
    typedef -unspecified- key_compare;
    typedef -unspecified- value_compare;
    typedef -unspecified- hasher;
    typedef -unspecified- key_equal;
    typedef -unspecified- allocator_type;
    typedef -unspecified- reference;
    typedef -unspecified- const_reference;
    typedef -unspecified- iterator;
    typedef -unspecified- const_iterator;
    typedef -unspecified- size_type;
    typedef -unspecified- difference_type;
    typedef -unspecified- pointer;
    typedef -unspecified- const_pointer;
    typedef -unspecified- local_iterator;
    typedef -unspecified- const_local_iterator;
    typedef -unspecified- info_type;
    // construct/destroy/copy:
    this_type & operator=(const this_type & x);
    allocator_type get_allocator() const;
    // size and capacity
    bool      empty() const;
    size_type size() const;
    size_type max_size() const;
    // iterators
    iterator       begin();
    const_iterator begin() const;
    iterator       end();
    const_iterator end() const;
    // modifiers
    std::pair< iterator, bool > insert(const value_type & x);
    iterator insert(iterator position, const value_type & x);
    template< class InputIterator >
    void insert(InputIterator first, InputIterator last);
    iterator erase(iterator position);
    template< class CompatibleKey >
    size_type erase(const CompatibleKey & x);
    iterator erase(iterator first, iterator last);
    bool replace(iterator position, const value_type & x);
    // Only in map views
    // {
      typedef -unspecified- mapped_type;
      typedef -unspecified- data_type; // Equal to mapped_type
      template< class CompatibleKey >
      bool replace_key(iterator position, const CompatibleKey & x);
      template< class CompatibleData >
      bool replace_data(iterator position, const CompatibleData & x);
      template< class KeyModifier >
      bool modify_key(iterator position, KeyModifier mod);
      template< class DataModifier >
      bool modify_data(iterator position, DataModifier mod);
    // }
    void clear();
    // observers
    key_from_value key_extractor() const;
    hasher         hash_function() const;
    key_equal      key_eq() const;
    // lookup
    template< class CompatibleKey >
    iterator find(const CompatibleKey & x);
    template< class CompatibleKey >
    const_iterator find(const CompatibleKey & x) const;
    template< class CompatibleKey >
    size_type count(const CompatibleKey & x) const;
    template< class CompatibleKey >
    std::pair<iterator,iterator>
        equal_range(const CompatibleKey & x);
    template< class CompatibleKey >
    std::pair<const_iterator,const_iterator>
        equal_range(const CompatibleKey & x) const;
    // bucket interface
    size_type bucket_count() const;
    size_type max_bucket_count() const;
    size_type bucket_size(size_type n) const;
    size_type bucket(const key_type & k) const;
    local_iterator       begin(size_type n);
    const_local_iterator begin(size_type n) const;
    local_iterator       end(size_type n);
    const_local_iterator end(size_type n) const;
    // hash policy
    float load_factor() const;
    float max_load_factor() const;
    void  max_load_factor(float z);
    void  rehash(size_type n);
    // Only in maps views
    // {
    typedef -unspecified- mapped_type;
      // Only in for `unordered_set_of` collection type
      // {
      template<class CompatibleKey>
      const mapped_type & at(const CompatibleKey & k) const;
        // Only if the other collection type is mutable
        // {
        template<class CompatibleKey>
        mapped_type & operator[](const CompatibleKey & k);
        template<class CompatibleKey>
        mapped_type & at(const CompatibleKey & k);
        // }
        // Only if info_hook is used
        // {
        template< class CompatibleKey >
        info_type & info_at(const CompatibleKey & k);
        template< class CompatibleKey >
        const info_type & info_at(const CompatibleKey & k) const;
      // }
    // }
};
} // namespace views
} // namespace bimap
} // namespace boost

В случае bimap<{multi}set_of<Left>,>

В представленном виде:

typedef signature-compatible with relation<       Left, ... > key_type;
typedef signature-compatible with relation< const Left, ... > value_type;

На левой карте вид:

typedef  Left  key_type;
typedef  ...   mapped_type;
typedef signature-compatible with std::pair< const Left, ... > value_type;

В правильном виде карты:

typedef  ...  key_type;
typedef  Left mapped_type;
typedef signature-compatible with std::pair< ... ,const Left > value_type;

Complexity signature

Здесь и в описаниях операций просмотров неупорядоченный_[мульти]set_of мы принимаем схему, изложенную в разделе сложность подписи. Сигнатура сложности неупорядоченный_[мульти]set_of вид:

копирование: c(n)=n ,
вставка: средний случай i(n) =1 (постоянный), наихудший случай i(n)n,
намек на вставку: средний случай h(n)= (постоянный), наихудший случай h(n)n,
удаление: средний случай d(n) =1 (постоянный), наихудший случай d(n)n,
замена:
- , если ключ нового элемента эквивалентен оригиналу, r(n) = 1 (постоянный),
- в противном случае средний случай r(n)= (постоянный), наихудший случай r(n)n,
модифицировать: средний случай m(n)=1 (постоянный), наихудший случай m(n)n.

Instantiation types

неупорядоченный_[multi]set_of просмотры инстанцируются внутренне к bimap, заданной посредством спецификаторов типа сбора и самой bimap. Обоснования зависят от следующих видов:

Ценность из bimap,
Allocator из bimap,
Hash из спецификатора типа сбора,
Pred из спецификатора типа сбора.

Hash представляет собой Унитарная функция, принимающая один аргумент типа key_type и возвращающая значение типа std::size_t в диапазоне [0::size_t>::max()). Pred представляет собой Binary Predicate, индуцирующий отношение эквивалентности на элементах key_type. Требуется, чтобы объект Hash возвращал одинаковое значение для ключей, эквивалентных Pred.

Nested types

iterator
const_iterator
local_iterator
const_local_iterator

Эти типы являются моделями Forward Iterator.

Constructors, copy and assignment

Как поясняется в разделе «Концепции», во взглядах нет публичных конструкторов или деструкторов. Присвоение, с другой стороны, предусмотрено. При построении max_load_factor() равен 1,0.

this_type & operator=(const this_type & x);

Эффекты: a=b; где a и b - объекты bimap, к которым * относятся соответственно и x.
Возврат: *Это.

Modifiers

std::pair<iterator,bool> insert(const value_type & x);

Эффекты: Вставить x в bimap, к которой относится вид, если
- вид не является уникальным или не существует другого элемента с эквивалентным ключом,
- И вставка допускается всеми другими видами bimap.
Возврат: Возвратное значение представляет собой пару p. p.секунда является истинной, если и только если вставка состоялась. При успешной вставке p.первый указывает на вставленный элемент; в противном случае p.первый указывает на элемент, из-за которого вставка была запрещена. Обратите внимание, что более одного элемента может привести к тому, что вставка не допускается.
Сложность: O(I(n)).
Безопасность исключения: Сильная.

iterator insert(iterator position, const value_type & x);

Требуется: Положение является действительным итератором представления.
Эффекты: Положение используется в качестве подсказки для повышения эффективности операции. Вставляет x в bimap, к которой относится вид, если
- вид не является уникальным или не существует другого элемента с эквивалентным ключом,
- И вставка допускается всеми другими видами bimap.
Возврат: При успешной вставке итератора к вновь вставленному элементу. В противном случае итератор к элементу, который вызвал вставку, будет запрещен. Обратите внимание, что более одного элемента может привести к тому, что вставка не допускается.
Сложность: O(H(n)).
Безопасность исключения: Сильная.

template< class InputIterator>
void insert(InputIterator first, InputIterator last);

Требуется: InputIterator представляет собой модель Input Iterator над элементами типа value_type. first и last не являются итераторами в любых представлениях bimap, к которым относится это представление. last доступен с первого раза.
Эффекты: hintend();в то время как(первый!= последнийlast)вставить(первый++);
Сложность: O(m*H(n+m)), где m - число элементов в [первый, последний).
Безопасность исключения: Базовая.

iterator erase(iterator position);

Требуется: Положение является действительным dereferenceable iterator представления.
Последствия:Удалить элемент, на который указывает позиция.
Возврат: iterator, указывающий на элемент, непосредственно следующий за тем, который был удален, или end(), если такого элемента не существует.
Сложность: O(D(n)).
Безопасность исключения: нотроу.

template< class CompatibleKey >
size_type erase(const CompatibleKey & x);

Последствия:Удалить элементы с ключевым эквивалентом x.
Возврат: Количество удаленных элементов.
Сложность: Средний случай, O(1 + m*D(n)), наихудший случай O(n + m*D(n)), где m - количество удаленных элементов.
Безопасность исключения: Базовая.

iterator erase(iterator first, iterator last);

Требуется: [first,last) является допустимым диапазоном представления.
Последствия:Удалить элементы в [первый,последний).
Возврат: Последний.
Сложность: O(m*D(n)), где m - число элементов в [первый,последний).
Безопасность исключения: нотроу.

bool replace(iterator position, const value_type & x);

Требуется: Положение является действительным dereferenceable iterator представления.
Эффекты: Назначает значение x на элемент, на который указывает позиция в бимап, к которому относится вид, если для значения x
- вид не является уникальным или не существует другого элемента с эквивалентным ключом (за исключением, возможно, позиция),
- И замена допускается всеми другими представлениями bimap.

Постусловия: Действительность позиции сохраняется во всех случаях.

Возврат: Правда, если замена состоялась, ложно в противном случае.

Сложность: O(R(n)).

Безопасность исключения: Сильная. Если какое-либо пользовательское действие забрасывает исключение, то bimap, которому принадлежит вид, остается в исходном состоянии.

template< class CompatibleKey >
bool replace_key(iterator position, const CompatibleKey & x);

Требуется: Положение является действительным итератором сносного представления. Совместимый ключ может быть назначен key_type.
Эффекты: Назначает значение x e. является элементом, на который указывает позиция в бимап, если
- вид карты не является уникальным или не существует другого элемента с эквивалентным ключом (за исключением, возможно, позиция),
- И замена допускается всеми другими представлениями bimap.
Постусловия: Действительность позиции сохраняется во всех случаях.
Возврат: Правда, если замена состоялась, ложно в противном случае.
Сложность: O(R(n)).
Безопасность исключения: Сильная. Если какое-либо пользовательское действие забрасывает исключение, то карта bimap, к которой относится заданный вид, остается в исходном состоянии.

template< class CompatibleData >
bool replace_data(iterator position, const CompatibleData & x);

Требуется: Положение является действительным итератором сносного представления. Совместимый ключ может быть назначен mapped_type.
Эффекты: Назначает значение x e.second, где e является элементом, на который указывает позиция в bimap, если
- вид карты не является уникальным или не существует другого элемента с эквивалентным ключом (за исключением, возможно, позиция),
- И замена допускается всеми другими представлениями bimap.
Постусловия: Действительность позиции сохраняется во всех случаях.
Возврат: Правда, если замена состоялась, ложно в противном случае.
Сложность: O(R(n)).
Безопасность исключения: Сильная. Если какое-либо пользовательское действие забрасывает исключение, то карта bimap, к которой относится заданный вид, остается в исходном состоянии.

template< class KeyModifier >
bool modify_key(iterator position, KeyModifier mod);

Требуется: KeyModifier представляет собой модель Unary Function, принимающую аргументы типа: key_type&; позиционирование является действительным сносным итератором представления.
Эффекты: Звонки mod(e.первый), где e является элементом, указанным по положению и перестраивает *позиция во все представления bimap. Если перегруппировка не удается, элемент стирается. Перестройка является успешной, если
- вид карты не является уникальным или не существует другого элемента с эквивалентным ключом,
- И перегруппировка допускается всеми другими видами bimap.
Постусловия: Срок действия Положение сохраняется при успешном выполнении операции.
Возврат: истинно, если операция удалась, ложно в противном случае.
Сложность: O(M(n)).
Безопасность исключения: Базовая. Если исключение выбрасывается какой-либо пользовательской операцией (за исключением, возможно, мода), то элемент, указанный позицией, стирается.
Примечание: Только для просмотра карт.

template< class DataModifier >
bool modify_data(iterator position, DataModifier mod);

Требуется: DataModifier представляет собой модель Unary Function, принимающую аргументы типа: mapped_type&; позиционирование является действительным итератором представления.
Последствия:Звонки mod(e.второй), где e является элементом, указанным по положению и перестраивает *положение во все представления бимап. Если перегруппировка не удается, элемент стирается. Перестройка является успешной, если
- вид карты противоположности не является уникальным или не существует другого элемента с эквивалентным ключом в этом виде,
- И перегруппировка допускается всеми другими видами bimap.
Постусловия: Срок действия Положение сохраняется при успешном выполнении операции.
Возврат: истинно, если операция удалась, ложно в противном случае.
Сложность: O(M(n)).
Безопасность исключения: Базовая. Если исключение выбрасывается какой-либо пользовательской операцией (за исключением, возможно, мода), то элемент, указанный позицией, стирается.
Примечание: Только для просмотра карт.

Lookup

неупорядоченный_[multi]set_of просмотры обеспечивают полную функциональность поиска, требуемую неупорядоченными ассоциативными контейнерами, а именно find, count и equal_range. Кроме того, эти функции членов шаблонизированы, чтобы обеспечить нестандартные аргументы, таким образом расширяя типы разрешенных поисковых операций. Вид аргументов, допустимых при вызове функций поиска, определяется следующей концепцией.

Тип Совместимый ключ называется Совместимый ключ (,Pred), если (Совместимый ключ,Pred). Это означает, что Hash и Pred принимают аргументы типа CompatibleKey, что обычно означает, что они имеют несколько перегрузок своих соответствующих функций-членов оператор().


template< class CompatibleKey >
iterator find(const CompatibleKey & x);
template< class CompatibleKey >
const_iterator find(const CompatibleKey & x) const;


 Эффекты: Возвращает указатель на элемент, ключ которого эквивалентен x, или end(), если такого элемента не существует.
 Сложность: Средний случай O(1) (постоянный), наихудший случай O(n).

template< class CompatibleKey >
size_type count(const CompatibleKey & x) const;


 Эффекты: Возвращает число элементов с ключевым эквивалентом x.
 Сложность: Средний случай O(count(x)), наихудший случай O(n).

template< class CompatibleKey >
std::pair<iterator,iterator>
    equal_range(const CompatibleKey & x);
template< class CompatibleKey >
std::pair<const_iterator,const_iterator>
    equal_range(const CompatibleKey & x) const;


 Эффекты: Возвращает диапазон, содержащий все элементы с ключами, эквивалентными x (и только те).
 Сложность: Средний случай O(count(x)), наихудший случай O(n).




at(),
          info_at() and operator[] - set_of only

template< class CompatibleKey >
const mapped_type & at(const CompatibleKey & k) const;


 Требуется:  Совместимый ключ  является совместимым ключом key_compare.
Возвращает ссылку mapped_type, связанную с k, или бросает std::out_of_range, если такой ключ не существует.

 Сложность: Средний случай O(1) (постоянный), наихудший случай O(n).
Примечание: Предоставляется только при использовании неупорядоченного_set_of.

Симметрия бимапа накладывает некоторые ограничения на оператор[] и непостоянную версию at(), которые не встречаются в std::карты. Тей предоставляется только в том случае, если другой тип сбора является изменчивым (list_of, vector_of и unconstrained_set_of).
template< class CompatibleKey >
mapped_type & operator[](const CompatibleKey & k);


 Требуется:  Совместимый ключ  является совместимым ключом key_compare.
 Эффекты: Возвратвставка(значение_тип(k,карта_тип()))->второй;
 Сложность: Если вставка выполняется O(I(n)), то другое: средний случай O(1) (постоянный), наихудший случай O(n).
Примечание: Предоставляется только при использовании неупорядоченного_set_of и при изменении другого типа сбора.

template< class CompatibleKey >
mapped_type & at(const CompatibleKey & k);


 Требуется:  Совместимый ключ  является совместимым ключом key_compare.
 Эффекты:  Возвращает ссылку mapped_type, связанную с k, или бросает std::out_of_range, если такой ключ не существует.
 Сложность: Средний случай O(1) (постоянный), наихудший случай O(n).
Примечание: Предоставляется только при использовании неупорядоченного_set_of и при изменении другого типа сбора.

template< class CompatibleKey >
info_type & info_at(const CompatibleKey & k);
template< class CompatibleKey >
const info_type & info_at(const CompatibleKey & k) const;


 Требуется:  Совместимый ключ  является совместимым ключом key_compare.
Возвращает ссылку info_type, связанную с k, или бросает std::out_of_range, если такой ключ не существует.

 Сложность: Средний случай O(1) (постоянный), наихудший случай O(n).
Примечание: Только при использовании неупорядоченного_set_of и info_hook




Hash
          policy

void rehash(size_type n);


 Эффекты: Увеличивает при необходимости количество внутренних ведер так, что размер ()/bucket_count() не превышает максимального коэффициента нагрузки, и bucket_count()>=n.
Постусловия: Сохраняется достоверность итераторов и ссылок на содержащиеся в них элементы.
 Сложность: Средний случай O(size()), худший случай O(size(n)2).
 Безопасность исключения: Сильная.




Serialization

Виды не могут быть сериализованы сами по себе, но только как часть bimap, в которую они встроены. При описании дополнительных предварительных условий и гарантий, связанных с представлениями  неупорядоченного_[мульти]set_of в отношении сериализации их встраиваемых контейнеров, мы используем понятия, определенные в разделе сериализации bimap.


Операция: сохранение bimapb в выходной архив (архив XML) ar.

 Требуется: Никаких дополнительных требований к тем, которые предъявляются контейнером.


Операция: загрузка bimapb' из входного архива (архив XML) ar.


 Требуется: Дополнительно к общим требованиям, key_eq() должна быть сериализация-совместима с m.i>().key_eq()multiset_of вид в контейнере.
Постусловия: При успешной загрузке диапазон [начало(),конец[3>м.getiначало(),м>().geti>().конец()), хотя и не обязательно в том же порядке.



Операция: сохранение iterator или const_iteratorit в выходной архив (архив XML) ar.

 Требуется:  it является действительным iterator. Ранее была сохранена связанная карта bimap.


 Операция:  загрузка итератора или const_iterator it' из входного архива (архив XML) ar.


Постусловия: При успешной загрузке, если it было сносно, то *it' является восстановленной копией *itit, в противном случае it==end().
Примечание: Допускается, что it будет const_iterator и восстановленный it iterator или наоборот.



Операция: сохранение локального_iterator или const_local_iterator в выходной архив (архив XML) ar.

 Требуется:  it является действительным локальным итератором представления. Ранее была сохранена связанная карта bimap.


Операция: загрузка local_iterator или const_local_iteratorit' из входного архива (архив XML) ar.


Постусловия: При успешной загрузке, если it было m.get для некоторого n, то .get (где b его восстановленная копия и i является порядком индекса)
Примечание: Допускается, что it будет const_local_iterator и восстановленный it local_iterator или наоборот.

unordered_set_of Reference

Boost , Chapter 1. Boost.Bimap , Reference

Boost C++ Libraries