Если кто хорошо знаком с std::multimap::lower_bound(key), объясните, пожалуйста, в каком случае метод может вернуть iterator, указывающий на элемент с ключом большим key, тогда как мне нужны элементы только с ключом key?
Здравствуйте, <Аноним>, Вы писали:
А>Если кто хорошо знаком с std::multimap::lower_bound(key), объясните, пожалуйста, в каком случае метод может вернуть iterator, указывающий на элемент с ключом большим key, тогда как мне нужны элементы только с ключом key?
В двух случаях.
Штатный случай: когда элементов == key нет, зато есть элементы > key.
lower_bound возвращает итератор на первый элемент, больший-или-равный ключу. Это место является точкой вставки в начало серии равных элементов.
upper_bound, кстати говоря, вернёт итератор на этот же элемент (строго-больший ключа).
А последовательность элементов, равных ключу — полуинтервал [lower_bound(key), upper_bound(key)) — окажется пустой, что и следовало ожидать.
Нештатный случай: всякое неопределённое и неспецифицированное поведение
— криво написанный предикат, не удовлетворяющий аксиоматике строгого порядка
— предикат (параметризуемый в рантайме) смогли поменять на ходу
— сломали константность ключей у элементов и поменяли ключи
Здравствуйте, Аноним, Вы писали:
А>Если кто хорошо знаком с std::multimap::lower_bound(key), объясните, пожалуйста, в каком случае метод может вернуть iterator, указывающий на элемент с ключом большим key, тогда как мне нужны элементы только с ключом key?
Например в таком случае:
#include <set>
#include <iostream>
using namespace std;
int main()
{
set< string > s;
s.insert ("bb");
s.insert ("b");
s.insert ("c");
set< string >::iterator i = s.lower_bound("a");
if (i != s.end()) {
printf(" *s.lower_bound(\"a\") == %s\n", i->c_str());
}
system("PAUSE");
}
Здравствуйте, Аноним, Вы писали:
А>Если кто хорошо знаком с std::multimap::lower_bound(key), объясните, пожалуйста, в каком случае метод может вернуть iterator, указывающий на элемент с ключом большим key, тогда как мне нужны элементы только с ключом key?
Для понимания lower_bound, uppper_bound, equal_range лучше представлять итераторы не как указатели на элементы, а как указатели позиций вставки новых элементов. Если в контейнере n элементов, то итераторов будет n+1: begin() обозначает вставку перед первым элементом, end() — после последнего, begin() + i — между элементами с номерами i-1 и i. Сравни с двумя вариантами отображения курсора для ввода с клавиатуры, который изображают вертикальной или горизонтальной чертой:
Теперь (надеюсь) определения lower_bound и upper_bound в стандарте станут предельно понятны:
[lower_bound] Finds the first position into which value can be inserted without violating the ordering.
[upper_bound] Finds the furthermost position into which value can be inserted without violating the ordering.
Здравствуйте, Николай. Спасибо Вам за ответ. Но ведь, согласно документации, в первом случае метод вернет итератор == multimap.end().
Андрей
К>Здравствуйте, <Аноним>, Вы писали:
А>>Если кто хорошо знаком с std::multimap::lower_bound(key), объясните, пожалуйста, в каком случае метод может вернуть iterator, указывающий на элемент с ключом большим key, тогда как мне нужны элементы только с ключом key?
К>В двух случаях.
К>Штатный случай: когда элементов == key нет, зато есть элементы > key. К>lower_bound возвращает итератор на первый элемент, больший-или-равный ключу. Это место является точкой вставки в начало серии равных элементов. К>upper_bound, кстати говоря, вернёт итератор на этот же элемент (строго-больший ключа). К>А последовательность элементов, равных ключу — полуинтервал [lower_bound(key), upper_bound(key)) — окажется пустой, что и следовало ожидать.
К>Нештатный случай: всякое неопределённое и неспецифицированное поведение К>- криво написанный предикат, не удовлетворяющий аксиоматике строгого порядка К>- предикат (параметризуемый в рантайме) смогли поменять на ходу К>- сломали константность ключей у элементов и поменяли ключи
Здравствуйте, Пабло (Warturtle).
Спасибо Вам за ответ. Ваш код на машине не прогонял, но, согласно документации, i == s.end().
W>Здравствуйте, Аноним, Вы писали:
А>>Если кто хорошо знаком с std::multimap::lower_bound(key), объясните, пожалуйста, в каком случае метод может вернуть iterator, указывающий на элемент с ключом большим key, тогда как мне нужны элементы только с ключом key?
W>Например в таком случае:
W>
Здравствуйте, Роман! Ценю Ваш художественный подход при ответе на вопрос. Спасибо. Могли бы Вы прокомментировать случай VZ для lower_bound? Вернет ли метод lower_bound(ключ к V, пусть 1) итератор на Z?
Андрей
RO>Здравствуйте, Аноним, Вы писали:
А>>Если кто хорошо знаком с std::multimap::lower_bound(key), объясните, пожалуйста, в каком случае метод может вернуть iterator, указывающий на элемент с ключом большим key, тогда как мне нужны элементы только с ключом key?
RO>Для понимания lower_bound, uppper_bound, equal_range лучше представлять итераторы не как указатели на элементы, а как указатели позиций вставки новых элементов. Если в контейнере n элементов, то итераторов будет n+1: begin() обозначает вставку перед первым элементом, end() — после последнего, begin() + i — между элементами с номерами i-1 и i. Сравни с двумя вариантами отображения курсора для ввода с клавиатуры, который изображают вертикальной или горизонтальной чертой:
RO>
RO>Теперь (надеюсь) определения lower_bound и upper_bound в стандарте станут предельно понятны: RO>
RO>[lower_bound] Finds the first position into which value can be inserted without violating the ordering.
RO>[upper_bound] Finds the furthermost position into which value can be inserted without violating the ordering.
RO> RO>Зеленым цветом — lower_bound('x'), красным цветом — upper_bound('x').
RO>Для reverse_iterator тоже есть картинка
Здравствуйте, Шинкевич Андрей Михайлович, Вы писали:
ШАМ>Здравствуйте, Николай. Спасибо Вам за ответ. Но ведь, согласно документации, в первом случае метод вернет итератор == multimap.end().
Например, MSDN:
multimap::lowerbound
Returns an iterator to the first element in a multimap that with a key that is equal to or greater than a specified key.
Return value
An iterator or const_iterator that addresses the location of an element in a multimap that with a key that is equal to or greater than the argument key, or that addresses the location succeeding the last element in the multimap if no match is found for the key.
No match — относится не к равенству ключей, а к выполнению условия (выделено жирным).
Здравствуйте, Аноним, Вы писали:
А>Если кто хорошо знаком с std::multimap::lower_bound(key), объясните, пожалуйста, в каком случае метод может вернуть iterator, указывающий на элемент с ключом большим key, тогда как мне нужны элементы только с ключом key?
Судя по всему, вам нужен equal_range. Он вернет пару итераторов, содержащих нужный вам интервал элементов, равных key. Т.е., первый элемент можно будет использовать как begin(), второй — как end() для алгоритмов.
Одним из 33 полных кавалеров ордена "За заслуги перед Отечеством" является Геннадий Хазанов.
Здравствуйте, Шинкевич Андрей Михайлович, Вы писали:
ШАМ>Могли бы Вы прокомментировать случай 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 */);
}
Спасибо, Николай.
К>Здравствуйте, Шинкевич Андрей Михайлович, Вы писали:
ШАМ>>Здравствуйте, Николай. Спасибо Вам за ответ. Но ведь, согласно документации, в первом случае метод вернет итератор == multimap.end().
К>Например, MSDN: К>
К>
multimap::lowerbound
К>Returns an iterator to the first element in a multimap that with a key that is equal to or greater than a specified key.
К>
Return value
К>An iterator or const_iterator that addresses the location of an element in a multimap that with a key that is equal to or greater than the argument key, or that addresses the location succeeding the last element in the multimap if no match is found for the key.
К>No match — относится не к равенству ключей, а к выполнению условия (выделено жирным).
Перекуём баги на фичи!
