| логарифмическая | |||
| a.equal_range(k) | pair‹iterator, itеrator›; pair‹const_iterator, const_iterator› для константы a | эквивалент make_pair(lower_bound(k), upper_bound(k)). | логарифмическая |
Основным свойством итераторов ассоциативных контейнеров является то, что они выполняют итерации через контейнеры в порядке неубывания ключей, где неубывание определено сравнением, которое использовалось для их создания. Для любых двух разыменованных итераторов 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)
