Здравствуйте, Шинкевич Андрей Михайлович, Вы писали:

ШАМ>Могли бы Вы прокомментировать случай VZ для lower_bound? Вернет ли метод lower_bound(ключ к V, пусть 1) итератор на Z?

А куда он денется.

Для [multi](map|set) операции бинарного поиска определяются эквивалентным образом (см. выше), но другими словами:

a.lower_bound(k) returns an iterator pointing to the first element with key not less than k.
a.upper_bound(k) returns an iterator pointing to the first element with key greater than k.

Если в [multi]map есть элемент(ы) с ключом k, то lower_bound покажет на первый k, а upper_bound — на элемент, идущий за последним k. Таким образом, [ lower_bound(k), upper_bound(k) ), она же equal_range(k) — подпоследовательность элементов с ключом k, заданная по правилам STL. Если же элементов k нет, то подпоследовательность должна быть пуста, что задается парой равных итераторов; и оба они указывают на элемент, перед которым окажется k, если его добавят. Поэтому 0123356.equal_range(4) = [5, 5). Четверку здесь можно добавить только в одном месте: между тройками и пятеркой. Если бы там четверки уже были бы, то было бы больше одного варианта (поставить перед другими четверками, после них, в середине), тогда lower_bound != upper_bound.

Для multimap редко используют (lower|upper)_bound; типичная задача — «выполнить такое-то действие для всех элементов multimap с ключом, равным данному», и решается она просто:

typedef std::multimap<X, Y> M;
M m;

. . .

std::pair<M::iterator, M::iterator> r = m.equal_range(key);
for(M::iterator i = r.first; i != r.second; ++i)
{
    . . .
}

или даже так:

BOOST_FOREACH(M::value_type& i, m.equal_range(key))
{
    foo(i.first /* X */, i.second /* Y */);
}