LINUX.ORG.RU

[C++] про map и set


0

2

Вопрос следующий:
есть некий map<type1, type2> mymap и есть set<type1> myset.
В set-е находится список ключей, пары с которыми надо убрать из map-a.
(т.е. сделать что-то вроде set_difference). Если необходимо, известно, то все пары ключ-значение в mymap, где ключ - элемент myset - существуют. Тупое решение очевидно: идём итератором по mymap, смотрим, есть ли i->first в myset, если есть, пару удаляем. А есть ли более правильное/лучшее/быстрое решение (myset и mymap могут быть довольно длинными)?


Ответ на: комментарий от anonymous

Т.е, идти одним по map, другим по set, и учитывать, что они хранятся отсортированными?

Viglim ()
Ответ на: комментарий от anonymous

требует полного перебора данных, для удаления 10-20 значений из map на 10000 элементов, например, это явно неэффективно

anonymous ()
Ответ на: комментарий от anonymous

> эффективно, если деревья рукописные и есть left/right.

согласен, возможно ТС стоит потратить время на поиск такой реализации

anonymous ()
Ответ на: комментарий от anonymous

А как? Из того, что первым приходит в голову: устроить дихтомию, но я слабо представляю, как это реализовать.

Viglim ()

достаточного такого map-а, у которого можно find-у передать итератор, начиная с которого нужно искать (как в insert()).

тогда бежать по set-у, искать по ключу итератор map-а, а следующий искать начиная с него

anonymous ()
Ответ на: комментарий от Viglim

std::find линейный как немного кривой вариант можно использовать boost::intrusive (для поиска insert_check() с параметром hint). или найти вариант по-лучше

anonymous ()
Ответ на: комментарий от JFreeM

> Идти по сету и удалять из мапы имхо.
Плюсую, ибо чтобы удалить из дерева надо же неизбежно сначала найти, а так совместим два поиска. Еще лучше, если не использовать set, а какой-нибудь список/вектор, ибо по дереву для итератора ++ происходит за O(logN) — тогда получится улучшить асимптотику с O(N*log²N) до O(N*logN), а не просто уменьшить скрытые за О-символикой константы.

С другой стороны, если лишний логарифм (!) для ТС - проблема, то стоило бы в постановке и саму природу задачи озвучить, чтоб знать, за что бороться.

metar ★★★ ()

дык файнд по ключу же ) Соответственно операций по одной на элемент сета

ну или наоборот если сет большой, а мап маленький...

Jetty ★★★★★ ()
Ответ на: комментарий от Jetty

Кстати, можно взять размеры и сравнить, и в одном случае идти по map, а в другом по set.
Правда, это длиннее

KUser ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.