Part of the Base package.
This part of the manual describes how to perform set operations (union, intersection, difference, symmetric difference) on arbitrary containers.
The following programs are related to this documentation: testSetFunctions.cpp
The STL library provides algorithm for performing set operations (std::set_union, std::set_intersection, std::set_difference, std::set_symmetric_difference). These algorithms are generic given iterators on an ordered range and an output iterator. So, in circumstances where you have two sorted vectors with unique elements, you could/should use directly STL set operations. You could also do this when you have two sets.
However, there are several cases when you cannot use them straightforwardly:
Therefore we propose functions to perform set operations on arbitrary containers. At compile time, the compiler chooses the most adequate way to compute the set operations, depending on the container type. It uses the traits class ContainerTraits to determine the type of container and to select the appropriate code. For the user, this is totally transparent, at least when he uses the binary operators |, &, -, ^ or |=, &=, -=, ^=.
If you dislike operators, you may also use functions (defined in namespace DGtal::functions):
There are templated versions of these functions that are useful if you know that, at this point in the program, your container is sorted (for instance your list or vector is already sorted). You may thus give the hint to set operations at this point.
We benchmark set operations for different kind of containers. In each case, we do not take into account the time for constructing containers A and B, we only measure the time to perform the operation. For each container, we compare the running time of our implementation and the running time obtained by first converting the container to a vector and perform STL set operation and converting back. Running times are in milliseconds.
|N = approx. size of A,B||10000||100000||1000000||10000000|
We have chosen not to overload operators == (equality), <= (subset), >= (supset), != (difference), because there is a big risk of mess up with other standard operator overloading (for instance, it poses a problem with catch test framework). You may use functions::isEqual and functions::isSubset to compare sets.
In order to have set operations that can be indifferently applied to many kind of containers, we use a mechanism called traits. The class ContainerTraits is used to define the category for each container. There are several categories, which form a kind of hierarchy. Each ContainerTraits should contain an inner type called
Category that defines the type of container. By default, it is NotContainerCategory. But the ContainerTraits class is specialized for every STL container, for instance with:
If you define a new container, you may associate its correct Category by specializing its ContainerTraits class with the correct category among NotContainerCategory, ContainerCategory, SequenceCategory, AssociativeCategory, SimpleAssociativeCategory, PairAssociativeCategory, UniqueAssociativeCategory, MultipleAssociativeCategory, OrderedAssociativeCategory, UnorderedAssociativeCategory, SetAssociativeCategory, MultisetAssociativeCategory, MapAssociativeCategory, MultimapAssociativeCategory, UnorderedSetAssociativeCategory, UnorderedMultisetAssociativeCategory, UnorderedMapAssociativeCategory, UnorderedMultimapAssociativeCategory.