Description
template<typename T>
class Sawyer::Container::DenseIntegerSet< T >
Unordered set of densely-packed integers.
This set is optimized to store integers from a range whose size is close to the cardinality of the set. For instance, if the set is intended to store integers in the range [100,199] and contains nearly 100 values at least at some point in its lifetime, then this is an appropriate container class to use for the set. Insert, erase, and existence testing are constant time, as are obtaining the beginning and end iterators and incrementing an iterator.
It is traditional to use an array or vector of Booleans to represent dense sets, but that approach results in poor iterator performance when the set happens to be sparse. This container avoids the poor iterator performance by also storing the members as a linked list (although it does so in a way that doesn't actually store the member values explicitly). But the "cost" of constant-time iteration is that the members of the set are not traversed in any particular order.
The combination of constant-time insert/erase/lookup and constant-time iterator increment makes this an ideal container for tree search algorithms where the set initially contains all vertex IDs but for most of the search the set is sparse.
Definition at line 39 of file DenseIntegerSet.h.
#include <DenseIntegerSet.h>
Classes | |
| class | ConstIterator |
| Bidirectional iterates over members of a set. More... | |
| struct | Member |
Public Types | |
| typedef T | Value |
| Type of values stored in this container. | |
Public Member Functions | |
| DenseIntegerSet () | |
| Construct an empty set that cannot store any members. More... | |
| DenseIntegerSet (const DenseIntegerSet &other) | |
| Copy constructor. | |
| DenseIntegerSet & | operator= (const DenseIntegerSet &other) |
| Assignment operator. More... | |
| boost::iterator_range< ConstIterator > | values () const |
| Iterator range for set members. More... | |
| bool | isEmpty () const |
| Whether the set is empty. More... | |
| size_t | size () const |
| Number of members present. More... | |
| Interval< Value > | domain () const |
| Domain of storable values. More... | |
| bool | isStorable (Value v) const |
| Determines if a value is storable. More... | |
| bool | exists (const Value &value) const |
| Determines whether a value is stored. More... | |
| template<class SawyerContainer > | |
| bool | existsAny (const SawyerContainer &other) const |
| Whether any value exists. More... | |
| template<class SawyerContainer > | |
| bool | existsAll (const SawyerContainer &other) const |
| Whether all values exist. More... | |
| template<class SawyerContainer > | |
| bool | operator== (const SawyerContainer &other) const |
| Whether two sets contain the same members. More... | |
| template<class SawyerContainer > | |
| bool | operator!= (const SawyerContainer &other) const |
| Whether two sets do not contain the same members. More... | |
| void | clear () |
| Remove all members from this set. More... | |
| bool | insert (Value value) |
| Insert a value. More... | |
| void | insertAll () |
| Insert all possible members. More... | |
| template<class SawyerContainer > | |
| DenseIntegerSet | operator& (const SawyerContainer &other) const |
| Compute the intersection of this set with another. More... | |
| template<class SawyerContainer > | |
| DenseIntegerSet | operator| (const SawyerContainer &other) const |
| Compute the union of this set with another. More... | |
| template<class SawyerContainer > | |
| DenseIntegerSet | operator- (const SawyerContainer &other) const |
| Compute the difference of this set with another. More... | |
| Value | deref (const ConstIterator &iter) const |
| DenseIntegerSet (const Interval< Value > &domain) | |
| Construct an empty set that can hold values from the specified domain. More... | |
| DenseIntegerSet (Value least, Value greatest) | |
| Construct an empty set that can hold values from the specified domain. More... | |
| DenseIntegerSet (Value n) | |
| Construct an empty set that can hold values from the specified domain. More... | |
| template<class SawyerContainer > | |
| void | insertMany (const SawyerContainer &other) |
| Insert many values from another set. More... | |
| template<class SawyerContainer > | |
| DenseIntegerSet & | operator|= (const SawyerContainer &other) |
| Insert many values from another set. More... | |
| bool | erase (Value value) |
| Erase a value. More... | |
| ConstIterator | erase (const ConstIterator &iter) |
| Erase a value. More... | |
| template<class SawyerContainer > | |
| void | eraseMany (const SawyerContainer &other) |
| Erase many values. More... | |
| template<class SawyerContainer > | |
| DenseIntegerSet & | operator-= (const SawyerContainer &other) |
| Erase many values. More... | |
| template<class SawyerContainer > | |
| void | intersect (const SawyerContainer &other) |
| Intersect this set with another. More... | |
| template<class SawyerContainer > | |
| DenseIntegerSet & | operator&= (const SawyerContainer &other) |
| Intersect this set with another. More... | |
Constructor & Destructor Documentation
◆ DenseIntegerSet() [1/4]
|
inline |
Construct an empty set that cannot store any members.
This object can only represent the empty set, but it's useful to have this default constructor in order to create a set that can be stored in a vector of sets, among other things.
Definition at line 65 of file DenseIntegerSet.h.
◆ DenseIntegerSet() [2/4]
|
inlineexplicit |
Construct an empty set that can hold values from the specified domain.
Constructs a set whose members can be chosen from the specified domain. The domain can be specified as an interval, as a least and greated value, or as the number of values. If specified as the number of values, N, then the domain is zero through N-1, inclusive. The set is initially empty.
Definition at line 75 of file DenseIntegerSet.h.
◆ DenseIntegerSet() [3/4]
|
inline |
Construct an empty set that can hold values from the specified domain.
Constructs a set whose members can be chosen from the specified domain. The domain can be specified as an interval, as a least and greated value, or as the number of values. If specified as the number of values, N, then the domain is zero through N-1, inclusive. The set is initially empty.
Definition at line 82 of file DenseIntegerSet.h.
◆ DenseIntegerSet() [4/4]
|
inlineexplicit |
Construct an empty set that can hold values from the specified domain.
Constructs a set whose members can be chosen from the specified domain. The domain can be specified as an interval, as a least and greated value, or as the number of values. If specified as the number of values, N, then the domain is zero through N-1, inclusive. The set is initially empty.
Definition at line 89 of file DenseIntegerSet.h.
Member Function Documentation
◆ operator=()
|
inline |
Assignment operator.
Assignment does not change the domain of the destination. If one of the members of other is outside the domain of this container then an Exception::Domain error is thrown and this object is not modified.
Definition at line 110 of file DenseIntegerSet.h.
◆ values()
|
inline |
Iterator range for set members.
Returns an iterator range consiting of the begin and end iterators, in constant time.
Definition at line 255 of file DenseIntegerSet.h.
Referenced by Sawyer::Container::DenseIntegerSet< size_t >::DenseIntegerSet(), Sawyer::Container::Algorithm::graphFindConnectedComponents(), Sawyer::Container::Algorithm::graphIsConnected(), and Sawyer::Container::DenseIntegerSet< size_t >::operator=().
◆ isEmpty()
|
inline |
Whether the set is empty.
Returns true if the set is empty, false if not empty. This is a constant-time operation.
Definition at line 266 of file DenseIntegerSet.h.
Referenced by Sawyer::Container::DenseIntegerSet< size_t >::exists(), Sawyer::Container::Algorithm::graphFindConnectedComponents(), and Sawyer::Container::Algorithm::graphIsConnected().
◆ size()
|
inline |
Number of members present.
Returns the number of values currently contained in this set. This is a constant-time operation.
Definition at line 273 of file DenseIntegerSet.h.
Referenced by Sawyer::Container::DenseIntegerSet< size_t >::operator!=(), and Sawyer::Container::DenseIntegerSet< size_t >::operator==().
◆ domain()
|
inline |
Domain of storable values.
Returns the set's domain, which is an interval describing which values can be possible members of this set.
Definition at line 280 of file DenseIntegerSet.h.
Referenced by Sawyer::Container::DenseIntegerSet< size_t >::DenseIntegerSet(), Sawyer::Container::DenseIntegerSet< size_t >::isStorable(), and Sawyer::Container::DenseIntegerSet< size_t >::operator=().
◆ isStorable()
|
inline |
Determines if a value is storable.
Returns true if the specified value can be stored in this set, and false otherwise. A storable value is a value that falls within this set's domain.
Definition at line 288 of file DenseIntegerSet.h.
Referenced by Sawyer::Container::DenseIntegerSet< size_t >::exists(), and Sawyer::Container::DenseIntegerSet< size_t >::insert().
◆ exists()
|
inline |
Determines whether a value is stored.
Returns true if the specified value is a member of this set, false if the value is not stored in this set. This method returns false if the value is outside this set's domain.
Definition at line 296 of file DenseIntegerSet.h.
Referenced by Sawyer::Container::DenseIntegerSet< size_t >::erase(), Sawyer::Container::DenseIntegerSet< size_t >::existsAll(), Sawyer::Container::DenseIntegerSet< size_t >::existsAny(), and Sawyer::Container::DenseIntegerSet< size_t >::intersect().
◆ existsAny()
|
inline |
Whether any value exists.
Returns true if any of the specified values exist in this set. This operation takes time that is linearly proportional to the number of items in the other container.
Definition at line 308 of file DenseIntegerSet.h.
◆ existsAll()
|
inline |
Whether all values exist.
Returns true if all specified values exist in this set. This operation takes time that is linearly proportaional to teh number of items in the other container.
Definition at line 321 of file DenseIntegerSet.h.
Referenced by Sawyer::Container::DenseIntegerSet< size_t >::operator!=(), and Sawyer::Container::DenseIntegerSet< size_t >::operator==().
◆ operator==()
|
inline |
Whether two sets contain the same members.
Returns true if this set and other contain exactly the same members.
Definition at line 333 of file DenseIntegerSet.h.
◆ operator!=()
|
inline |
Whether two sets do not contain the same members.
Returns true if this set and the other set are not equal.
Definition at line 341 of file DenseIntegerSet.h.
◆ clear()
|
inline |
Remove all members from this set.
This operation is linear in the number of members currently present in the set.
Definition at line 352 of file DenseIntegerSet.h.
Referenced by Sawyer::Container::DenseIntegerSet< size_t >::intersect().
◆ insert()
|
inline |
Insert a value.
Inserts the specified value in constant time. Returns true if the value was inserted and false if the value already existed. If the value is outside the domain then an Exception::DomainError is thrown.
Definition at line 366 of file DenseIntegerSet.h.
Referenced by Sawyer::Container::DenseIntegerSet< size_t >::DenseIntegerSet(), Sawyer::Container::Algorithm::graphFindConnectedComponents(), Sawyer::Container::Algorithm::graphIsConnected(), Sawyer::Container::DenseIntegerSet< size_t >::insertMany(), Sawyer::Container::DenseIntegerSet< size_t >::intersect(), and Sawyer::Container::DenseIntegerSet< size_t >::operator=().
◆ insertAll()
|
inline |
Insert all possible members.
Causes the set to contain all elements that are part of its domain.
Definition at line 392 of file DenseIntegerSet.h.
Referenced by Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< GraphA, GraphB, SolutionProcessor, EquivalenceP >::reset().
◆ insertMany()
|
inline |
Insert many values from another set.
Inserts all values of the other container into this set.
Definition at line 418 of file DenseIntegerSet.h.
Referenced by Sawyer::Container::DenseIntegerSet< size_t >::operator|=().
◆ operator|=()
|
inline |
Insert many values from another set.
Inserts all values of the other container into this set.
Definition at line 424 of file DenseIntegerSet.h.
◆ erase() [1/2]
|
inline |
Erase a value.
If a value is specified, then the value is erased and this method returns true if the value existed and false if it didn't exist (in which case this is a no-op). If a non-end iterator is specified, then the pointed to value is erased and the next iterator is returned.
Erasing is a constant-time operation.
Definition at line 439 of file DenseIntegerSet.h.
Referenced by Sawyer::Container::DenseIntegerSet< size_t >::eraseMany(), Sawyer::Container::Algorithm::graphFindConnectedComponents(), and Sawyer::Container::Algorithm::graphIsConnected().
◆ erase() [2/2]
|
inline |
Erase a value.
If a value is specified, then the value is erased and this method returns true if the value existed and false if it didn't exist (in which case this is a no-op). If a non-end iterator is specified, then the pointed to value is erased and the next iterator is returned.
Erasing is a constant-time operation.
Definition at line 451 of file DenseIntegerSet.h.
◆ eraseMany()
|
inline |
Erase many values.
Erase those values from this set that are members of the other container.
Definition at line 473 of file DenseIntegerSet.h.
Referenced by Sawyer::Container::DenseIntegerSet< size_t >::operator-=().
◆ operator-=()
|
inline |
Erase many values.
Erase those values from this set that are members of the other container.
Definition at line 479 of file DenseIntegerSet.h.
◆ intersect()
|
inline |
Intersect this set with another.
Replaces this set with members that are only in this set and the other set.
Definition at line 491 of file DenseIntegerSet.h.
Referenced by Sawyer::Container::DenseIntegerSet< size_t >::operator&=().
◆ operator&=()
|
inline |
Intersect this set with another.
Replaces this set with members that are only in this set and the other set.
Definition at line 501 of file DenseIntegerSet.h.
◆ operator&()
|
inline |
Compute the intersection of this set with another.
Returns a new set which has only those members that are common to this set and the other set.
Definition at line 515 of file DenseIntegerSet.h.
◆ operator|()
|
inline |
Compute the union of this set with another.
Returns a new set containing the union of all members of this set and the other set.
Definition at line 525 of file DenseIntegerSet.h.
◆ operator-()
|
inline |
Compute the difference of this set with another.
Returns a new set containing those elements of this set that are not members of the other set.
Definition at line 535 of file DenseIntegerSet.h.
The documentation for this class was generated from the following file:
