A clean way to iterate over connections?
I have 2 instances of std :: set, for examples, one instance corresponds to the state of the set at time t and the other at t + 1.
I want to iterate over the concatenation (in a mathematical sense) of these two sets, for example:
- each union element is processed once
- for each item I can specify in constant time if it is in the first set, the second set, or both
Here's an example of what I am currently doing:
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
}
}
As you can see, it is missing the part where we handle the elements in both sets, and also the complexity is not good enough. I think there must be a way to do what I want by simply iterating over all the elements of the set
Does anyone have any ideas?
thank
source to share
You can do something like:
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);
}
}
source to share
After all the counting, it might be more efficient to create a union in a swift container like std::vector
, and iterate over it:
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';
}
}
source to share
One idea is to write your own iterator that can iterate over containers and concatenate them this way:
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}
};
For simplicity, you can use std :: vector <ContainerType> instead of tuple and T as the type of the variable in the container. I'm not sure if there is something already in the boost or other libraries ...
What is the best way to iterate over two or more containers at the same time
source to share