чистый способ перебора соединений наборы?

У меня есть 2 экземпляра std :: set, для примеров один экземпляр соответствует состоянию набора в момент времени t, а другой - при t + 1.чистый способ перебора соединений наборы?

Я хочу перебрать союза (в математическом смысле) этих 2-х комплектов, так что:

каждый элемент объединения обрабатывается один раз
для каждого элемента я могу сказать в постоянном время, если он находится в первом сете, второй набор, или как

Вот пример того, что я сейчас делаю:

std::set<A> old_set, new_set; 
for(auto it = old_set.begin(); it != old_set.end(); ++it) { 
     if(new_set.count(*it) == 0) { 
      //only in old set but not in new set 
     } 
    } 

for(auto it = new_set.begin(); it != new_set.end(); ++it) { 
    if(old_set.count(*it) == 0) { 
     //only in new set but not in old set 
    } 
}

Как вы можете видеть, в нем отсутствует часть, где мы обрабатываем элементы в обоих наборах, а также сложность недостаточно. Я думаю, что должен быть способ сделать то, что я хочу, просто перебирая все элементы набора

У кого-нибудь есть идея?

Благодаря

источник

2014-12-21 lezebulon

Как это дубликат? В другом вопросе явно говорится: «Опять я использую только« вектор »,« std :: set »не разрешен». Ответ может быть таким же, но вопрос не в этом! – TonyK

Вы можете сделать что-то вроде:

template <typename T, typename D> 
void iterate(std::set<T>& s1, std::set<T>& s2, D d) 
{ 
    auto it1 = s1.begin(); 
    auto it2 = s2.begin(); 

    while (it1 != s1.end() && it2 != s2.end()) { 
     if (*it1 < *it2) { 
      // only in set1 
      d.visit1(*it1); 
      ++it1; 
     } else if (*it2 < *it1) { 
      // only in set2 
      d.visit2(*it2); 
      ++it2; 
     } else { 
      // in both 
      d.visitboth(*it1, *it2); 
      ++it1; 
      ++it2; 
     } 
    } 
    for (; it1 != s1.end(); ++it1) { 
     // only in set1 
     d.visit1(*it1); 
    } 
    for (; it2 != s2.end(); ++it2) { 
     // only in set2 
     d.visit2(*it2); 
    } 
}

источник

2014-12-21 21:50:06 Jarod42

спасибо, это, кажется, именно то, что я искал! Я попробую запустить несколько тестов, чтобы убедиться, что это работает по назначению. – lezebulon

есть ли причина, по которой d.visitboth (* it1, * it2) принимает 2 аргумента? так как они сравнивают равные, не может ли он принимать только один аргумент? – lezebulon

@lezebulon Если методы 'visitx'' D' принимают свои аргументы по ссылке, 'visitboth' может изменять один или другой или оба из них – wakjah

В конце концов, что подсчет может быть более эффективным, чтобы создать союз в быстром контейнере, как std::vector и перебирать, что:

int main() 
{ 
    std::set<int> s1 {1, 2, 4, 6, 9}; 
    std::set<int> s2 {2, 3, 4, 6, 11}; 

    std::vector<int> u; 

    u.reserve(s1.size() + s2.size()); 

    std::set_union(s1.begin(), s1.end(), s2.begin(), s2.end() 
     , std::back_inserter(u)); 

    for(auto it = u.begin(); it != u.end(); ++it) 
    { 
     // do stuff on union 
     std::cout << "u: " << *it << '\n'; 
    } 
}

источник

2014-12-21 21:46:50 Galik

Фактически, OP хочет 'std :: set_intersection' и два различия, выполненные через' std :: set_difference'. – Jarod42

Одна из идей - написать собственный итератор, который может выполнять итерацию по контейнерам и объединить их таким образом:

template<typename... T> 
class MergeIterator{ 
MergeIterator(T... constainers):m_containers(std::forward(containers)...){} 
std::tuple<T...> m_containers; 
/// implement the operators here. 
MergeIterator operator ++(){///... here switch the tuple if needed until it is not on the last element} 
};

Для простоты вы можете использовать STD :: Вектор < ContainerType> вместо кортежа и T в качестве переменной типа в контейнере. Я не уверен, если есть что-то уже имеется в подталкивании или других библиотеках ...

What's the best way to iterate over two or more containers simultaneously

источник

2014-12-21 21:59:47 AlexTheo

чистый способ перебора соединений наборы?

ответ

Смежные вопросы