This blog post shows and explains C++ source code implementing in-place set intersection, i.e. removing each element from a set (or another sorted container) *bc which is not also a member of container bc.
The std::intersection function template in the <algorithm> header in C++ standard template library populates a new output set, adding all elements in the intersection into it. This can be too slow and a waste of memory if one of the inputs is not needed afterwards. In this case an in-place intersection is desired instead, but unfortunately such a function template is not part of the C++ standard template library.
Here is a simple in-place implementation which looks up each element of *bc in ac, and removes (erases) it from *bc if not found:
#include <set> // Remove elements from bc which are missing from ac. // // The time required is proportional to log(ac.size()) * bc->size(), so it's // faster than IntersectionUpdate if ac is large compared to bc. template<typename Input, typename Output> static void IntersectionUpdateLargeAc( const std::set<Input> &ac, std::set<Output> *bc) { const typename std::set<Input >::const_iterator a_end = ac.end(); const typename std::set<Output>::const_iterator b_end = bc->end(); for (typename std::set<Output>::iterator b = bc->begin(); b != b_end; ) { if (ac.find(*b) == a_end) { // Not found. // Not a const_iterator, erase wouldn't accept it until C++11. const typename std::set<Output>::iterator b_old = b++; bc->erase(b_old); // erase doesn't invalidate b. } else { ++b; } } }
Removing from *bc above is a bit tricky, because we don't want to invalidate the iterator b. In C++11 erase returns a new iterator, which is just after the removed elements, but we don't use that just to be backwards-compatible. Instead of that we make use of the fact that iterators to the non-removed elements are kept intact for set, multiset and list, so we create the temporary iterator b_old, which will be invalidated, but b remains valid.
We need the typename keyword in local variable declarations, because they have a dependent type (i.e. a type whose identifier is within another type specified by a template parameter.)
The time complexity is O(log(as) · bs), so it is fast if ac is large when compared to *bc. For example, when as = 3k and bs = k, then it's O(k2).
As an alternative, we could iterate over the two sets in increasing (ascending) order at the same time, similarly to the merge operation (as implemented by std::merge in mergesort, but dropping elements from *bc if there is no corresponding element in ac. One possible implementation:
#include <set> // Remove elements from bc which are missing from ac. // // The time required is proportional to ac.size() + bc->size(). template<typename Input, typename Output> static void IntersectionUpdate( const std::set<Input> &ac, std::set<Output> *bc) { typename std::set<Input>::const_iterator a = ac.begin(); const typename std::set<Input>::const_iterator a_end = ac.begin(); typename std::set<Output>::iterator b = bc->begin(); const typename std::set<Output>::iterator b_end = bc->end(); while (a != a_end && b != b_end) { if (*a < *b) { ++a; } else if (*a > *b) { const typename std::set<Output>::iterator b_old = b++; bc->erase(b_old); // erase doesn't invalidate b. } else { // Elements are equal, keep them in the intersection. ++a; ++b; } } bc->erase(b, b_end); // Remove remaining elements in bc but not in ac. }
The time complexity of this above (IntersectionUpdate) is O(as + bs), which is faster than IntersectionUpdateLargeAc if ac is not much smaller than *bc. For example, when as = 3k and bs = k, then it's O(3k + k), so IntersectionUpdateLargeAc is faster.
Example usage of both (just to see if they compile):
int main(int, char**) { std::set<int> a, b; IntersectionUpdateLargeAc(a, &b); IntersectionUpdate(a, &b); return 0; }
It's natural to ask if these function templates can be generalized to C++ containers other than set. They take advantage of the input being sorted, so let's consider sorted std::vector, sorted std::list and std::multiset in addition to std::set. To avoid the complexity of having to distinguish keys from values, let's ignore std::map and std::multimap.
The generalization of IntersectionUpdateLargeAc from set to multiset is trivial: no code change is necessary. The std::multiset::find operation returns any matching element, which is good for us. However, with IntersectionUpdate, the last ++a; must be removed: without the removal subsequent occurrences of the same value in *bc would be removed if ac contains this value only once. No other code change is needed. It is tempting to introduce a loop in the previous (*a > *b) if branch:
for (;;) { const typename Output::iterator b_old = b++; const bool do_break = b == b_end || *b_old != *b; bc->erase(b_old); // erase doesn't invalidate b. if (do_break) break; }
However, this change is not necessary, because subsequent equal values in *bc would be removed in subsequent iterations of the outer loop.
Here are the full generalized implementations:
#if __cplusplus >= 201103 || __GXX_EXPERIMENTAL_CXX0X__ #include <type_traits> #endif // Remove elements from bc which are missing from ac. Supported containers for // bc: list (only if sorted), vector (only if sorted), set, multiset. Supported // containers for ac: set, multiset. // // The time required is proportional to log(ac.size()) * bc->size(), so it's // faster than IntersectionUpdate if ac is large compared to bc. template<typename Input, typename Output> static void IntersectionUpdateLargeAc(const Input &ac, Output *bc) { #if __cplusplus >= 201103 || __GXX_EXPERIMENTAL_CXX0X__ // We could use std::is_convertible (both ways) instead of std::is_same. static_assert(std::is_same<typename Input::value_type, typename Output::value_type>::value, "the containers passed to IntersectionUpdateLargeAc() need to " "have the same value_type"); #endif const typename Input::const_iterator a_end = ac.end(); const typename Output::const_iterator b_end = bc->end(); for (typename Output::iterator b = bc->begin(); b != b_end; ) { if (ac.find(*b) == a_end) { // Not found. // Not a const_iterator, erase wouldn't accept it until C++11. const typename Output::iterator b_old = b++; bc->erase(b_old); // erase doesn't invalidate b. } else { ++b; } } } // Remove elements from bc which are missing from ac. Supported containers for // ac and bc: list (only if sorted), vector (only if sorted), set, multiset. template<typename Input, typename Output> static void IntersectionUpdate(const Input &ac, Output *bc) { #if __cplusplus >= 201103 || __GXX_EXPERIMENTAL_CXX0X__ static_assert(std::is_same<typename Input::value_type, typename Output::value_type>::value, "the containers passed to IntersectionUpdate() need to " "have the same value_type"); #endif typename Input::const_iterator a = ac.begin(); const typename Input::const_iterator a_end = ac.end(); typename Output::iterator b = bc->begin(); // Can't be a const interator, similarly to b_old. const typename Output::iterator b_end = bc->end(); while (a != a_end && b != b_end) { if (*a < *b) { ++a; } else if (*a > *b) { const typename Output::iterator b_old = b++; bc->erase(b_old); // erase doesn't invalidate b. } else { // Elements are equal, keep it in the intersection. // Don't do ++a, in case ac is a multiset. ++b; } } bc->erase(b, b_end); // Remove remaining elements in bc but not in ac. }
These work as expected for set, multiset and sorted list. It also doesn't require that the two containers are of the same kind. For C++0x and C++11, an extra static_assert is present in the code to print a helpful compact error message if the base types are different.
However, when *bc is a vector, we get a compile error, because in C++ older than C++11, std::vector::erase doesn't return an iterator (but it returns void). Even if we could get an iterator, b_end would be invalidated by erase, because it's behind it. This is easy to fix, we should use bc->end() instead of b_end everywhere. However, if we didn't make any other changes, the algorithm would be slower than necessary, because std::vector::erase moves each element behind the erased one. So the time complexity would be O(as + bs2). To speed it up, let's swap the to-be-removed elements with the element with the last element of the vector, and to the actual removal at the end of the function:
#if __cplusplus >= 201103 || __GXX_EXPERIMENTAL_CXX0X__ #include <type_traits> #include <utility> // std::swap. #else #include <algorithm> // std::swap. #endif // Template specialization for vector output. template<typename Input, typename T> static void IntersectionUpdate(const Input &ac, std::vector<T> *bc) { #if __cplusplus >= 201103 || __GXX_EXPERIMENTAL_CXX0X__ static_assert(std::is_same<typename Input::value_type, T>::value, "the containers passed to IntersectionUpdate() need to " "have the same value_type"); #endif typename Input::const_iterator a = ac.begin(); const typename Input::const_iterator a_end = ac.end(); typename std::vector<T>::iterator b = bc->begin(); // Elements between b_high an bc->end() will be removed (erased) right before // the function returns. We defer their removal to save time. typename std::vector<T>::iterator b_high = bc->end(); while (a != a_end && b != b_high) { if (*a < *b) { ++a; } else if (*a > *b) { std::iter_swap(b, --b_high); // Works even if swapping with itself. } else { // Elements are equal, keep them in the intersection. ++a; ++b; } } bc->erase(b, bc->end()); // Remove remaining elements in bc but not in ac. }
Once we have the generic implementation and the special implementation for vector in the same file, the C++ compiler would take care of choosing the right (most specific) one depending on whether *bc is a vector or not. So all these work now:
#include <list> #include <set> #include <vector> int main(int, char**) { std::set<int> s; std::multiset<int> ms; std::vector<int> v; // std::list<unsigned> l; // Won't work in C++0x and C++11. std::list<int> l; IntersectionUpdate(s, &ms); IntersectionUpdate(ms, &v); IntersectionUpdate(v, &l); IntersectionUpdate(l, &s); IntersectionUpdateLargeAc(s, &ms); IntersectionUpdateLargeAc(ms, &v); // IntersectionUpdateLargeAc(v, &l); // v is not good as ac. // IntersectionUpdateLargeAc(l, &s); // l is not good as ac. IntersectionUpdateLargeAc(s, &l); IntersectionUpdateLargeAc(ms, &s); return 0; }
The full source code is available on GitHub.
