[C++] про map и set

идти двумя итераторами параллельно

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

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

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

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

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

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

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

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

Тогда, наверное, можно приспособить find() из algorithm?

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

у map и set есть upper_bound и lower_bound, которые делают то, что нужно

наоборот надо. Идти по сету и удалять из мапы имхо.

только upper_bound нельзя дать hint

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

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

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

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

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