LINUX.ORG.RU

с++: совместный обход двух упорядоченных контейнеров, есть ли такое в типовых либах?

 


0

1

Есть ли такое, что бы совместно обходить скажем два std::map в типовых библиотеках? Что бы использовать вместо такого цикла:


std::map<int,T> a;
std::map<int,V> b;

...

for (auto &itr_a : a) {
    auto itr_b = b.find(itr_a.first);
    
    // обработка itr_a & itr_b (если есть) по одному ключу
    ...
}

for (auto &itr_b : b) {
    if (!a.count(itr_b.first)) continue;
 
    // обработка itr_b которых не было в a
    ...
}

В некоторых случаях нужно что бы все элементы обойти, в некоторых только имеющиеся в обоих контейнерах.

======================================================

По итогам обсуждений посмотрел я функции set_union, set_intersection, и прочие, и реализовал свой вариант, который можно посмотреть здесь:

https://github.com/victorprogrammist/tool_iterate_ordered_containers



Последнее исправление: cetjs2 (всего исправлений: 2)

Виктор, я намекаю, что на лоре есть специальный форум под названием «Development». Может, уже догадаешься, что постить плюсовые вопросы в форум «General» не комильфо?

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

Лишь бы что-то написать, да?

anonymous
()

Ближайшее в STL это set_intersection, set_union, set_difference и set_symmetric_difference. Если лень, можно прямо их заюзать, обернув свой код в класс-обёртку, прикидывающуюся OutputIterator. В Boost есть готовый код, который делает такое из любой анонимной функции.

Если не лень, то итерируйся по двум итераторам. Код будет аналогичен проходу классической сортировки слиянием (mergesort). На cppreference в статье про set_difference даже есть примерная реализация. Не забудь про краевые случаи.

i-rinat ★★★★★
()

Вы не хотите так делать. Вы только что превратили O(N+M) задачу в O(N+N*log(M)). Обходите «ручками» по двум контейнерам сразу.

bugfixer ★★★★
()
Последнее исправление: bugfixer (всего исправлений: 1)
Ответ на: комментарий от bugfixer

Вы не хотите так делать.

Хотя конечно от мат ожидания N и M многое зависит…

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

O(N+N*log(M))

это при наивной реализации, map-ы же упорядочены, последовательно обходя их можно понять есть очередной элемент из первого во втором за O(1).

Begemoth ★★★★★
()
Ответ на: комментарий от i-rinat

Ближайшее в STL это set_intersection, set_union, set_difference и set_symmetric_difference.

Спасибо.

victor79
() автор топика
Ответ на: комментарий от debugger

Виктор, я намекаю, что на лоре есть специальный форум под названием «Development».

Я очень стараюсь выбирать соответствующий вопросу раздел. К разделу Development приписка, что «под Linux/Unix». Данный вопрос не касается только линукс, и одинаково выглядит под любую другую ОС, и при разработке под веб. Почему бы тогда не в Web-development?

А для группы General приписка «не подходящих в другие группы», из чего я делаю вывод, что нужно сюда.

victor79
() автор топика
Последнее исправление: victor79 (всего исправлений: 1)
Ответ на: комментарий от Begemoth

можно понять есть очередной элемент из первого во втором за O(1).

Всё правильно, чем и достигается O(N+M).

Только если N маленькая а M большая то выгоднее будет lookup во втором контейнере делать каждый раз.

bugfixer ★★★★
()
Последнее исправление: bugfixer (всего исправлений: 2)

проще было хранить значением мапы вектор, массив, что угодно что можно дополнить и в нем уже искать что надо по одному ключу и вообще сет использовать а не мапу чтобы гарантированно не дублировать ключ, ты сам себе геморрой создал наклепав мап под каждый условный T или V или етц. Просто переделай нормально или напиши свой оберточный код на это безобразие которое распихивает по отдельным мапам. Раз ты сводишь эти значения значит они взаимосвязаны.

Ну и возвращаясь к вопросу, даже если бы что-то такое было внутри такой реализации была бы реализация подобной твоей, если тебя только корявый вид смущает, то не смущайся.

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

проще было хранить значением мапы вектор, массив, что угодно что можно дополнить и в нем уже искать что надо по одному ключу и вообще сет использовать а не мапу чтобы гарантированно не дублировать ключ

Моя мозга взорвалась. Не смог распарсить. Вы бы не могли перефразировать?

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