Александр Степанов - РУКОВОДСТВО ПО СТАНДАРТНОЙ БИБЛИОТЕКЕ ШАБЛОНОВ (STL)

Основным свойством итераторов ассоциативных контейнеров является то, что они выполняют итерации через контейнеры в порядке неубывания ключей, где неубывание определено сравнением, которое использовалось для их создания. Для любых двух разыменованных итераторов i и j таких, что расстояние от i до j является положительным, value_comp (*j, *i)==false. Для ассоциативных контейнеров с уникальными ключами выдерживается более сильное условие value_comp(*i, *j)==true.

Множество (Set)

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

template ‹class Key, class Compare = less‹Key›, template ‹class U› class Allocator = allocator›

class set {

public:

 // typedefs:

 typedef Key key_type;

 typedef Key value_type;

 typedef Allocator‹Key›::pointer pointer;

 typedef Allocator‹Key›::reference reference;

 typedef Allocator‹Key›::const_reference const_reference;

 typedef Compare key_compare;

 typedef Compare value_compare;

 typedef iterator;

 typedef iterator const_iterator;

 typedef size_type;

 typedef difference_type;

 typedef reverse_iterator;

 typedef const_reverse_iterator;

 // allocation/deallocation:

 set(const Compare& comp = Compare());

 template ‹class InputIterator›

 set(InputIterator first, InputIterator last, const Compare& comp = Compare());

 set(const set‹Key, Compare, Allocator›& x);

 ~set();

 set‹Key, Compare, Allocator›& operator=(const set‹Key, Compare, Allocator›& x);

 void swap(set‹Key, Compare, Allocator›& x);

 // accessors:

 key_compare key_comp() const;

 value_compare value_comp() const;

 iterator begin() const;

 iterator end() const;

 reverse_iterator rbegin() const;

 reverse_iterator rend() const;

 bool empty() const;

 size_type size() const;

 size_type max_size() const;

 // insert/erase

 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);

 void erase(iterator position);

 size_type erase(const key_type& x);

 void erase(iterator first, iterator last);

 // set operations:

 iterator find(const key_type& x) const;

 size_type count(const key_type& x) const;

 iterator lower_bound(const key_type& x) const;

 iterator upper_bound(const key_type& x) const;

 pair‹iterator, iterator› equal_range(const key_type& x) const;

};

template ‹class Key, class Compare, class Allocator›

bool operator==(const set‹Key, Compare, Allocator›& x, const set‹Key, Compare, Allocator›& y);

template ‹class Key, class Compare, class Allocator›

bool operator‹(const set‹Key, Compare, Allocator›& x, const set‹Key, Compare, Allocator›& y);

iterator - постоянный двунаправленный итератор, указывающий на const value_type. Точный тип зависит от реализации и определяется в Allocator.

сonst_iterator - тот же самый тип, что и iterator.

size_type - целочисленный тип без знака. Точный тип зависит от реализации и определяется в Allocator.

difference_type - целочисленный тип со знаком. Точный тип зависит от реализации и определяется в Allocator.

Множество с дубликатами (Multiset)

multiset - это ассоциативный контейнер, который поддерживает равные ключи (возможно, содержит множественные копии того же самого значения ключа) и обеспечивает быстрый поиск ключей.

template ‹class Key, class Compare = less‹Key›, template ‹class U› class Allocator = allocator›

class multiset {

public:

 // typedefs:

 typedef Key key_type;

 typedef Key value_type;

 typedef Allocator‹Key›::pointer pointer;

 typedef Aliocator‹Key›::reference reference;

 typedef Allocator‹Key›::const_reference const_reference;

 typedef Compare key_compare;

 typedef Compare value_compare;

 typedef iterator;

 typedef iterator const_iterator;

 typedef size_type;

 typedef difference_type;

 typedef reverse_iterator;

 typedef const_reverse_iterator;

 // allocation/deallocation:

 multiset(const Compare& comp = Compare());

 template ‹class InputIterator›

 multiset(InputIterator first, InputIterator last, const Compare& comp = Compare());

 multiset(const multiset‹Key, Compare, Allocator›& x);

 ~multiset();

 multiset‹Key, Compare, Allocator›& operator=(const multiset‹Key, Compare, Allocator›& x);

 void swap(multiset‹Key, Compare, Allocator›& x);

 // accessors:

 key_compare key_comp() const;

 value_compare value_comp() const;

 iterator begin() const;

 iterator end() const;

 reverse_iterator rbegin();

 reverse_iterator rend();

 bool empty() const;

 size_type size() const;

 size_type max_size() const;

 // insert/erase:

 iterator insert(const value_type& x);

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

 template ‹class InputIterator›

 void insert(InputIterator first, InputIterator last);

 void erase(iterator position);

 size_type erase(const key_type& x);

 void erase(iterator first, iterator last);

 // multiset operations:

 iterator find(const key_type& x) const;

 size_type count(const key_type& x) const;

 iterator lower_bound(const key_type& x) const;

 iterator upper_bound(const key_type& x) const;

 pair‹iterator, iterator› equal_range(const key_type& x) const;

};

template ‹class Key, class Compare, class Allocator›

bool operator==(const multiset‹Key, Compare, Allocator›& x, const multiset‹Key, Compare, Allocator›& y);

template ‹class Key, class Compare, class Allocator›

bool operator‹(const multiset‹Key, Compare, Allocator›& x, const multiset‹Key, Compare, Allocator›& y);

iterator - постоянный двунаправленный итератор, указывающий на const value_type. Точный тип зависит от реализации и определяется в Allocator.

сonst_iterator - тот же самый тип, что и iterator.

size_type - целочисленный тип без знака. Точный тип зависит от реализации и определяется в Allocator.

difference_type - целочисленный тип со знаком. Точный тип зависит от реализации и определяется в Allocator.

Словарь (Map)

map - ассоциативный контейнер, который поддерживает уникальные ключи (не содержит ключи с одинаковыми значениями) и обеспечивает быстрый поиск значений другого типа T, связанных с ключами.

template ‹class Key, class T, class Compare = less‹Key›, template ‹class U› class Allocator = allocator›

class map {

public:

 // typedefs:

 typedef Key key_type;

 typedef pair‹const Key, T› value_type;

 typedef Compare key_compare;

 class value_compare : public binary_function‹value_type, value_type, bool› {

  friend class map;

 protected:

  Compare comp;

  value_compare(Compare c): comp(c) {}

 public:

  bool operator()(const value_type& x, const value_type& y) {

   return comp(x.first, y.first);

  }

 };

 typedef iterator;

 typedef const_iterator;

 typedef Allocator‹value_type›::pointer pointer;

 typedef Allocator‹value_type›::reference reference;

 typedef Allocator‹value_type›::const_reference const_reference;

 typedef size_type;

 typedef difference_type;

 typedef reverse_iterator;

 typedef const_reverse_iterator;

 // allocation/deallocation:

 map(const Compare& comp = Compare());

 template ‹class InputIterator›

 map(InputIterator first, InputIterator last, const Compare& comp = Compare());

 map(const map‹Key, T, Compare, Allocator›& x);

 ~map();

 map‹Key, T, Compare, Allocator›& operator=(const map‹Key, T, Compare, Allocator›& x);

 void swap(map‹Key, T, Compare, Allocator›& x);

 // accessors:

 key_compare key_comp() const;

 value_compare value_comp() const;

 iterator begin();

 const_iterator begin() const;

 iterator end();

 const_iterator end() const;

 reverse_iterator rbegin();

 const_reverse_iterator rbegin();

 reverse_iterator rend();

 const_reverse_iterator rend();

 bool empty() const;

 size_type size() const;

 size_type max_size() const;

 Allocator‹T›::reference operator[](const key_type& x);

 // insert/erase:

 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);

 void erase(iterator position);

 size_type erase(const key_type& x);

 void erase(iterator first, iterator last);

 // map operations:

 iterator find(const key_type& x);

 const_iterator find(const key_type& x) const;

 size_type count(const key_type& x) const;

 iterator lower_bound(const key_type& x);

 const_iterator lower_bound(const key_type& x) const;

 iterator upper_bound(const key_type& x);

 const_iterator upper_bound(const key_type& x) const;

 pair‹iterator, iterator› equal_range(const key_type& x);

 pair‹const_iterator, const_iterator› equal_range(const key_type& x)const;

};

template ‹class Key, class T, class Compare, class Allocator›

bool operator==(const map‹Key, T, Compare, Allocator›& x, const map‹Key, T, Compare, Allocator›& y);

template ‹class Key, class T, class Compare, class Allocator›