РУКОВОДСТВО ПО СТАНДАРТНОЙ БИБЛИОТЕКЕ ШАБЛОНОВ (STL)

Множество (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: