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

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›

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

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

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

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

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

В дополнение к стандартному набору методов ассоциативных контейнеров, map обеспечивает операцию Allocator::reference operator[](const key_type&). Для словаря m и ключа k запись m[k] семантически эквивалентна (*((m.insert(make_pair(k, T()))).first)).second.

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

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

class multimap {

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

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:

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

template ‹class InputIterator›

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

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

~multimap();

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

void swap(multimap‹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;

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

// multimap 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 multimap‹Key, T, Compare, Allocator›& x, const multimap‹Key, T, Compare, Allocator›& y);

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

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

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

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

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

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

Чтобы шаблоны алгоритмов могли работать непосредственно с потоками ввода-вывода, предусмотрены соответствующие шаблонные классы, подобные итераторам. Например,

partial_sum_copy(istream_iterator‹double›(cin), istream_iterator‹double›(), ostream_iterator‹double›(cout, "\n"));

читает файл, содержащий числа с плавающей запятой, из cin и печатает частичные суммы в cout.

istream_iterator‹T› читает (используя operator››) последовательные элементы из входного потока, для которого он был создан. После своего создания итератор каждый раз при использовании ++ читает и сохраняет значение T. Если достигнут конец потока (operator void* () в потоке возвращает false), итератор становится равным значению end-of-stream ( конец-потока ). Конструктор без параметров istream_iterator() всегда создаёт итераторный объект конца потокового ввода, являющийся единственым законным итератором, который следует использовать для конечного условия. Результат operator* для конца потока не определён, а для любого другого значения итератора возвращается const T&.

Невозможно записывать что-либо с использованием входных итераторов. Основная особенность входных итераторов - тот факт, что операторы ++ не сохраняют равенства, то есть i==j не гарантирует вообще, что ++i==++j. Каждый раз, когда ++ используется, читается новое значение. Практическое следствие этого факта - то, что входные итераторы могут использоваться только для однопроходных алгоритмов, что действительно имеет здравый смысл, так как многопроходным алгоритмам всегда более соответствует использование структур данных в оперативной памяти.

Два итератора конец-потока всегда равны. Итератор конец-потока не равен не-конец-потока итератору. Два не-конец-потока итератора равны, когда они созданы из того же самого потока.

template ‹class T, class Distance = ptrdiff_t›

class istream_iterator: public input_iterator‹T, Distance› {

friend bool operator==(const istream_iterator‹T, Distance›& x, const istream_iterator‹T, Distance›& y);

public:

istream_iterator();

istream_iterator(istream& s);

istream_iterator(const istream_iterator‹T, Distance›& x);

~istream_iterator();

const T& operator*() const;

istream_iterator‹T, Distance›& operator++();

istream_iterator‹T, Distance› operator++(int);

};

template ‹class T, class Distance›

bool operator==(const istream_iterator‹T, Distance›& x, const istream_iterator‹T, Distance›& y);