155 / 137 / 46
Регистрация: 15.02.2010
Сообщений: 750
|
||||||||||||||||
1 | ||||||||||||||||
multimap (просмотр по ключу)01.05.2020, 11:48. Показов 15600. Ответов 30
Метки нет (Все метки)
Здравствуйте.
Имеется заполненный контейнер:
Конечно, можно тупо перебрать все пары и выести значения по ключу:
Можно ли сделать последовательный просмотр через поиск типа такого:
Или всё-таки без полного прохода по всем элементам не обойтись?
0
|
01.05.2020, 11:48 | |
Ответы с готовыми решениями:
30
Удаление записи по ключу в multimap Доступ к элементам multimap по ключу Multimap. Как получить кол-во элементов по ключу? Multimap. Ошибка operator+ not implemented in type multimap |
155 / 137 / 46
Регистрация: 15.02.2010
Сообщений: 750
|
|
13.05.2020, 15:39 [ТС] | 21 |
Ну, а если это строковый тип, то уже не пара тактов...
У меня как раз строки. Хотя... чтобы найти окончание нужного диапазона по значению... те же строки будут сравниваться в процессе upper_bound.
0
|
Вездепух
11691 / 6370 / 1723
Регистрация: 18.10.2014
Сообщений: 16,052
|
|
13.05.2020, 17:40 | 22 |
Я уже писал именно об этом выше.
upper_bound делает эффективный поиск. И вполне может оказаться так, что для нахождения конца диапазона upper_bound потребует намного меньше сравнений, чем линейный перебор всех элементов в процессе просмотра от lower_bound и далее. То есть сравниваться будут не "те же строки", а существенно меньшее количество строк. Поэтому если ключи в вашем контейнере являются "тяжелыми", то запросто может оказаться, что для нахождения конца диапазона все таки лучше применить upper_bound . Или, разумеется, equal_range , который фактически является комбинацией lower_bound и upper_bound .В исходном примере ключ был "легким " ( int ). При таком легком ключе (именно при таком легком ключе) лучше, наверное, искать конец диапазона простым сравнением ключей в процессе просмотра диапазона, а не через upper_bound .
1
|
155 / 137 / 46
Регистрация: 15.02.2010
Сообщений: 750
|
||||||
13.05.2020, 18:26 [ТС] | 24 | |||||
Выглядит "красивше"
А что эффективнее?
0
|
Вездепух
11691 / 6370 / 1723
Регистрация: 18.10.2014
Сообщений: 16,052
|
|
13.05.2020, 18:31 | 25 |
Тему с начала читали?
Теоретически эффективнее equal_range , потому что он "знает", что upper_bound нужно делать не во всем контейнере, а только в его части: справа от уже полученного результата lower_bound .А пользуется ли ваша реализация equal_range этой оптимизационной возможностью или нет - зависит от реализации. Вполне может быть, что и не пользуется, ибо не обязана.
0
|
155 / 137 / 46
Регистрация: 15.02.2010
Сообщений: 750
|
|||||||||||
13.05.2020, 18:55 [ТС] | 26 | ||||||||||
Меня мучает еще один вопрос.
Если map или multimap содержатся в структуре, то понятно, что lower_bound, upper_bound, equal_range будут применимы. Но у меня в map находится структура, и нужно эффективно просмотреть определённые элементы по значению. Например, код неправильный но хотелось бы
0
|
13.05.2020, 19:44 | 27 | ||||||||||
все две страницы выше мы говорили про multimap с какого перепуга вдруг мы применяем equal range к строкам? где в этом коде multimap? Добавлено через 2 минуты может имелось в виду
0
|
155 / 137 / 46
Регистрация: 15.02.2010
Сообщений: 750
|
|
13.05.2020, 21:49 [ТС] | 28 |
Да, Kuzia domovenok, запутался я чуток. В одну тему загнал map и multimap.
Вопрос снят.
0
|
What a waste!
1608 / 1300 / 180
Регистрация: 21.04.2012
Сообщений: 2,729
|
|
13.05.2020, 22:35 | 29 |
find может вернуть итератор на любой элемент с подходящим ключом. Тут нужен именно lower_bound .
1
|
Комп_Оратор)
|
|
13.05.2020, 22:52 | 30 |
LVV,
Это абсолютно нормально. Мултимэп может быть реализован как дерево и это значит что поиск бинарными методами lower/upper _bound имеют логарифмическую скорость. Становится ясно, что если возможны цепи повторов соизмеримые с размером контейнера, то выигрывать будет поиск по границам (тот что вы говорите). Но если количество повторов пренебрежимо мало по сравнению с общим размером, то выгоднее будет найти левую границу и пройти последовательно как вам уже подсказали. Моё мнение, - если не известно, то поиск по 2 границам не так уж рискован. Логарифмическое время это не больно. Но резко улучшит ситуацию если возможны длинные цепи повторов.
1
|
Вездепух
11691 / 6370 / 1723
Регистрация: 18.10.2014
Сообщений: 16,052
|
|
14.05.2020, 02:11 | 31 |
Кстати, ценнейшее замечание. Я наивно пошел на поводу, полагая, что
find возвращает именно первый. А на самом деле std::multimap::find возвращает любой, а не первый. Так что find тут неприменим, если только вы не хотите искать границы диапазона в обе стороны от найденного элемента.
1
|
14.05.2020, 02:11 | |
14.05.2020, 02:11 | |
Помогаю со студенческими работами здесь
31
Сгруппировать элементы указанного массива по ключу и вернуть multimap ключей MyDictionary: сортировка по ключу, поиск значения по ключу, поиск ключа по значению MultiMap multimap сортировка в multimap Multimap зацикливается Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |