set_of Reference . Boost , Chapter 1. Boost.Bimap , Reference

namespace boost {
namespace bimaps {
template
<
    class KeyType,
    class KeyCompare = std::less< KeyType >
>
struct set_of;
template
<
    class KeyCompare = std::less< _relation >
>
struct set_of_relation;
} // namespace bimap
} // namespace boost

Header "boost/bimap/multiset_of.hpp" synopsis

namespace boost {
namespace bimaps {
template
<
    class KeyType,
    class KeyCompare = std::less< KeyType >
>
struct multiset_of;
template
<
    class KeyCompare = std::less< _relation >
>
struct multiset_of_relation;
} // namespace bimap
} // namespace boost

Collection type specifiers set_of and multiset_of

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

[multi]set_of Views

Complexity signature
Instantiation types
Constructors, copy and assignment
Modifiers
Set operations
Range operations
at(), info_at() and operator[] - set_of only
Serialization

[multi]set_of set view - это std:: [multi]set signature-compatible interface к основной куче элементов, содержащихся в<bimap>.

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

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

namespace boost {
namespace bimaps {
namespace views {
template< -implementation defined parameter list- >
class -implementation defined view name-
{
    public:
    typedef -unspecified- key_type;
    typedef -unspecified- value_type;
    typedef -unspecified- key_compare;
    typedef -unspecified- value_compare;
    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- reverse_iterator;
    typedef -unspecified- const_reverse_iterator;
    typedef -unspecified- info_type;
    this_type & operator=(const this_type & x);
    allocator_type get_allocator() const;
    // iterators
    iterator               begin();
    const_iterator         begin() const;
    iterator               end();
    const_iterator         end() const;
    reverse_iterator       rbegin();
    const_reverse_iterator rbegin() const;
    reverse_iterator       rend();
    const_reverse_iterator rend() const;
    // capacity
    bool      empty() const;
    size_type size() const;
    size_type max_size() 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
    // {
      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 swap(this_type & x);
    void clear();
    // observers
    key_compare    key_comp() const;
    value_compare  value_comp() const;
    // set operations
    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 >
    iterator lower_bound(const CompatibleKey & x);
    template< class CompatibleKey >
    const_iterator lower_bound(const CompatibleKey & x) const;
    template< class CompatibleKey >
    iterator upper_bound(const CompatibleKey & x);
    template< class CompatibleKey >
    const_iterator upper_bound(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;
    // Only in maps views
    // {
    template< class LowerBounder, class UpperBounder>
    std::pair<iterator,iterator> range(
        LowerBounder lower, UpperBounder upper);
    template< class LowerBounder, class UpperBounder>
    std::pair<const_iterator,const_iterator> range(
        LowerBounder lower, UpperBounder upper) const;
    typedef -unspecified- mapped_type;
    typedef -unspecified- data_type; // Equal to mapped_type
      // Only in for `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;
        // }
      // }
    // }
};
// view comparison
bool operator==(const this_type & v1, const this_type & v2 );
bool operator< (const this_type & v1, const this_type & v2 );
bool operator!=(const this_type & v1, const this_type & v2 );
bool operator> (const this_type & v1, const this_type & v2 );
bool operator>=(const this_type & v1, const this_type & v2 );
bool operator<=(const this_type & v1, const this_type & v2 );
} // 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

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

копирование:<c(n)=n*log(n)>,
вставка:<i(n)=log(n)>,
намек на вставку:<h(n)=1>(постоянно), если элемент подсказки предшествует точке вставки,<h(n)=log(n)>в противном случае,
Удаление:<d(n)=1>(амортизированная постоянная),
<r(n)=1>(постоянно), если положение элемента не изменяется,<r(n)=log(n)>в противном случае,
<m(n)=1>(постоянно), если положение элемента не изменяется,<m(n)=log(n)>в противном случае.

Instantiation types

Установка взглядов инстанцируется внутренне в<bimap>. Обоснования зависят от следующих видов:

<Value>из заданного уточнения,
<Allocator>из<bimap>,
<Compare>Из заданного уточнения.

<Compare>—строгий слабый порядокна элементах<Value>.

Constructors, copy and assignment

У множества представлений нет публичных конструкторов или деструкторов. Присвоение, с другой стороны, предусмотрено.

this_type & operator=(const this_type & x);

Эффекты:<a =b;>, где a и b являются<bimap>объектами, к которым<*this>и x принадлежат соответственно.
Возвращение:<*this>.

Modifiers

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

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

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

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

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

Требуется:<InputIterator>является модельюИтератора вводанад элементами типа<value_type>или типа, конвертируемого в значение_тип.<first>и<last>не являются итераторами в любом представлении о<bimap>, к которому принадлежит этот индекс.<last>достижимо от<first>.
Эффекты:<iterator hint= end()>;<while( first!= last) hint= insert( hint, *first++);>
Сложность:O(m*H(n+m)), где m — число элементов в<[first, last)>.
Безопасность исключения:Базовая.

iterator erase(iterator position);

Требуется:<position>является действительным сносным итератором, если заданный вид.
Эффекты:Исключает элемент, на который указывает<position>.
Возвращение:Итератор, указывающий на элемент сразу после того, который был удален, или<end()>, если такой элемент не существует.
Сложность:О(D(n)).
Безопасность исключения:нехроу.

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

Требуется:<CompatibleKey>является совместимым ключом<key_compare>.
Эффекты:Исключает элементы с ключом, эквивалентным<x>.
Возвращение:Количество исключенных элементов.
Сложность:O(log(n) + m*D(n)), где m - число удаленных элементов.
Безопасность исключения:Базовая.

iterator erase(iterator first, iterator last);

Требуется:<[first,last)>является допустимым диапазоном представления.
Эффекты:Удалить элементы в<[first,last)>.
Возвращение:последнее.
Сложность:O(log(n) + m*D(n)), где m — число элементов в<[first,last)>.
Безопасность исключения:нехроу.

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

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

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

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

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

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

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

<KeyModifier>является модельюУнарная функция, принимающая аргументы типа:<key_type&>;<position>, является действительным итератором точки зрения.
Эффекты:Звонки<mod(e.first)>, где e — элемент, на который указывает положение и перестраивает<*position>во все виды<bimap>. Если перегруппировка не удается, элемент стирается. Перестройка является успешной, если
- вид карты не является уникальным или не существует другого элемента с эквивалентным ключом,
- Перестройка допускается всеми другими видами<bimap>.
Последующие условия:Срок действия<position>сохраняется, если операция увенчается успехом.
Возвращается:<true>если операция удалась,<false>в противном случае.
Сложность:О(М(n)).
Безопасность исключения:Базовая. Если исключение выбрасывается какой-либо пользовательской операцией (за исключением, возможно, мода), то элемент, указанный позицией, стирается.
Примечание:Предоставляется только для просмотра карт.

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

Требуется:<DataModifier>является модельюУнарная функция, принимающая аргументы типа:<mapped_type&>;<position>, является действительным итератором точки зрения.
Эффекты:Звонки<mod(e.second)>, где e является элементом, указанным по положению и перестраивает<*position>во все виды<bimap>. Если перегруппировка не удается, элемент стирается. Перестройка является успешной, если
- вид карты противоположности не является уникальным или не существует другого элемента с эквивалентным ключом в этом виде,
- Перестройка допускается всеми другими видами<bimap>.
Последующие условия:Срок действия<position>сохраняется, если операция увенчается успехом.
Возвращается:<true>если операция удалась,<false>в противном случае.
Сложность:О(М(n)).
Безопасность исключения:Базовая. Если исключение выбрасывается какой-либо пользовательской операцией (за исключением, возможно, мода), то элемент, указанный позицией, стирается.
Примечание:Предоставляется только для просмотра карт.

Set operations

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

Тип<CompatibleKey>называетсясовместимым ключом<Compare>, если<(CompatibleKey, Compare)>является совместимым расширением<Compare>. Это означает, что<Compare>, а также будучи строгим слабым упорядочением, принимает аргументы типа<CompatibleKey>, что обычно означает, что он имеет несколько перегрузок<operator()>.

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

Требуется:<CompatibleKey>является совместимым ключом<key_compare>.
Эффекты:Возвращает указатель на элемент, ключ которого эквивалентен<x>или<end()>, если такого элемента не существует.
Сложность:O(log(n)).

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

Требуется:<CompatibleKey>является совместимым ключом<key_compare>.
Эффекты:Возвращает число элементов с ключом, эквивалентным<x>.
Сложность:O(log(n) + count(x)).

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

Требуется:<CompatibleKey>является совместимым ключом<key_compare>.
Эффекты:Возвращает итератор, указывающий на первый элемент с ключом не менее<x>или<end()>, если такой элемент не существует.
Сложность:O(log(n)).

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

Требуется:<CompatibleKey>является совместимым ключом<key_compare>.
Эффекты:Возвращает итератор, указывающий на первый элемент с ключом больше, чем<x>, или<end()>, если такой элемент не существует.
Сложность:O(log(n)).

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

Требуется:<CompatibleKey>является совместимым ключом<key_compare>.
Эффекты:эквивалентно<make_pair(lower_bound(x),upper_bound(x))>.
Сложность:O(log(n)).

Range operations

Диапазон функций не определен для отсортированных ассоциативных контейнеров, но<[multi]set_of>вид карты обеспечивает его в качестве удобной утилиты. Диапазон или интервал определяется двумя условиями для нижней и верхней границ, которые моделируются после следующих понятий.

РассмотримСтрогое слабое упорядочивание<Compare>над значениями типа Ключ. Тип<LowerBounder>считается нижним пределом<Compare>, если

<LowerBounder>является<Predicate>более<Key>,
Если<lower(k1)>и<!comp(k2,k1)>, то<lower(k2)>

Для каждого<lower>типа<LowerBounder>,<comp>типа<Compare>и<k1>,<k2>типа<Key>. Точно так же верхняя граница является типом<UpperBounder>, который

<UpperBounder>является<Predicate>более<Key>,
Если<upper(k1)>и<!comp(k1,k2)>, то<upper(k2)>

Для каждого<upper>типа<UpperBounder>,<comp>типа<Compare>и<k1>,<k2>типа<Key>.

template< class LowerBounder, class UpperBounder>
std::pair<const_iterator,const_iterator> range(
    LowerBounder lower, UpperBounder upper) const;

Требуется:<LowerBounder>и<UpperBounder>являются нижней и верхней границей<key_compare>соответственно.
Эффекты:Возвращает пару итераторов, указывающих на начало и один прошедший конец последовательности элементов, удовлетворяющих нижнюю и верхнюю одновременно. Если таких элементов не существует, итераторы указывают на первый элемент, удовлетворяющий более низкому уровню, или равны<end()>, если этот последний элемент не существует.
Сложность:O(log(n)).
Варианты:Вместо нижнего или верхнего (или обоих) может быть предусмотрено единственное значение<boost::bimap::unbounded>. Это служит предикатом, которому удовлетворяют все значения типа<key_type>.
Примечание:Предоставляется только для просмотра карт.

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

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

Требуется:<CompatibleKey>является совместимым ключом<key_compare>.
Эффекты:Возвращает ссылку<mapped_type>, связанную с<k>, или бросает<std::out_of_range>, если такой ключ не существует.
Сложность:O(log(n)).
Примечание:Применяется только при использовании<set_of>.

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

template< class CompatibleKey >
mapped_type & operator[](const CompatibleKey & k);

Требуется:<CompatibleKey>является совместимым ключом<key_compare>.
Эффекты:<return insert(value_type(k,mapped_type()))->second;>
Сложность:O(log(n)).
Примечание:Применяется только при использовании<set_of>, а другой тип сбора является изменяемым.

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

Требуется:<CompatibleKey>является совместимым ключом<key_compare>.
Эффекты:Возвращает ссылку<mapped_type>, связанную с<k>, или бросает<std::out_of_range>, если такой ключ не существует.
Сложность:O(log(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;

Требуется:<CompatibleKey>является совместимым ключом<key_compare>.
Эффекты:Возвращает ссылку<info_type>, связанную с<k>, или бросает<std::out_of_range>, если такой ключ не существует.
Сложность:O(log(n)).
Примечание:Только в том случае, если<set_of>и<info_hook>

Serialization

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

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

Требуется:В дополнение к общим требованиям<value_comp()>должна быть сериализация-совместима с<m.get<i>().value_comp()>, где i - положение упорядоченного вида в контейнере.
Постусловия:При успешной загрузке каждый из элементов<[begin(), end())>является восстановленной копией соответствующего элемента в<[m.get<i>().begin(),m.get<i>().end())>.

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

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

Статья set_of Reference раздела Chapter 1. Boost.Bimap Reference может быть полезна для разработчиков на c++ и boost.

set_of Reference

Boost , Chapter 1. Boost.Bimap , Reference

Boost C++ Libraries