libDAI
|
Represents a set; the implementation is optimized for a small number of elements. More...
#include <dai/smallset.h>
Public Types | |
typedef std::vector< T >::const_iterator | const_iterator |
Constant iterator over the elements. More... | |
typedef std::vector< T >::iterator | iterator |
Iterator over the elements. More... | |
typedef std::vector< T >::const_reverse_iterator | const_reverse_iterator |
Constant reverse iterator over the elements. More... | |
typedef std::vector< T >::reverse_iterator | reverse_iterator |
Reverse iterator over the elements. More... | |
Public Member Functions | |
Constructors and destructors | |
SmallSet () | |
Default constructor (constructs an empty set) More... | |
SmallSet (const T &t) | |
Construct a set consisting of one element. More... | |
SmallSet (const T &t1, const T &t2) | |
Construct a set consisting of two elements. More... | |
template<typename TIterator > | |
SmallSet (TIterator begin, TIterator end, size_t sizeHint) | |
Construct a SmallSet from a range of elements. More... | |
Operators for set-theoretic operations | |
SmallSet & | insert (const T &t) |
Inserts t into *this . More... | |
SmallSet & | erase (const T &t) |
Erases t from *this . More... | |
SmallSet | operator/ (const SmallSet &x) const |
Set-minus operator: returns all elements in *this , except those in x. More... | |
SmallSet | operator| (const SmallSet &x) const |
Set-union operator: returns all elements in *this , plus those in x. More... | |
SmallSet | operator& (const SmallSet &x) const |
Set-intersection operator: returns all elements in *this that are also contained in x. More... | |
SmallSet & | operator/= (const SmallSet &x) |
Erases from *this all elements in x. More... | |
SmallSet & | operator/= (const T &t) |
Erases one element. More... | |
SmallSet & | operator|= (const SmallSet &x) |
Adds to *this all elements in x. More... | |
SmallSet & | operator|= (const T &t) |
Adds one element. More... | |
SmallSet & | operator&= (const SmallSet &x) |
Erases from *this all elements not in x. More... | |
bool | operator<< (const SmallSet &x) const |
Returns true if *this is a subset of x. More... | |
bool | operator>> (const SmallSet &x) const |
Returns true if x is a subset of *this . More... | |
Queries | |
bool | intersects (const SmallSet &x) const |
Returns true if *this and x have elements in common. More... | |
bool | contains (const T &t) const |
Returns true if *this contains the element t. More... | |
std::vector< T >::size_type | size () const |
Returns number of elements. More... | |
bool | empty () const |
Returns whether *this is empty. More... | |
std::vector< T > & | elements () |
Returns reference to the elements. More... | |
const std::vector< T > & | elements () const |
Returns constant reference to the elements. More... | |
Iterator interface | |
iterator | begin () |
Returns iterator that points to the first element. More... | |
const_iterator | begin () const |
Returns constant iterator that points to the first element. More... | |
iterator | end () |
Returns iterator that points beyond the last element. More... | |
const_iterator | end () const |
Returns constant iterator that points beyond the last element. More... | |
reverse_iterator | rbegin () |
Returns reverse iterator that points to the last element. More... | |
const_reverse_iterator | rbegin () const |
Returns constant reverse iterator that points to the last element. More... | |
reverse_iterator | rend () |
Returns reverse iterator that points beyond the first element. More... | |
const_reverse_iterator | rend () const |
Returns constant reverse iterator that points beyond the first element. More... | |
T & | front () |
Returns reference to first element. More... | |
const T & | front () const |
Returns constant reference to first element. More... | |
T & | back () |
Returns reference to last element. More... | |
const T & | back () const |
Returns constant reference to last element. More... | |
Private Attributes | |
std::vector< T > | _elements |
The elements in this set. More... | |
Friends | |
Comparison operators | |
bool | operator== (const SmallSet &a, const SmallSet &b) |
Returns true if a and b are identical. More... | |
bool | operator!= (const SmallSet &a, const SmallSet &b) |
Returns true if a and b are not identical. More... | |
bool | operator< (const SmallSet &a, const SmallSet &b) |
Lexicographical comparison of elements. More... | |
Input/output | |
std::string | toString () const |
Formats a SmallSet as a string. More... | |
std::ostream & | operator<< (std::ostream &os, const SmallSet &x) |
Writes a SmallSet to an output stream. More... | |
Represents a set; the implementation is optimized for a small number of elements.
SmallSet uses an ordered std::vector<
T>
to represent a set; this is faster than using a std::set<
T>
if the number of elements is small.
T | Should be less-than-comparable. |
typedef std::vector<T>::const_iterator dai::SmallSet< T >::const_iterator |
Constant iterator over the elements.
typedef std::vector<T>::iterator dai::SmallSet< T >::iterator |
Iterator over the elements.
typedef std::vector<T>::const_reverse_iterator dai::SmallSet< T >::const_reverse_iterator |
Constant reverse iterator over the elements.
typedef std::vector<T>::reverse_iterator dai::SmallSet< T >::reverse_iterator |
Reverse iterator over the elements.
|
inline |
Default constructor (constructs an empty set)
|
inline |
Construct a set consisting of one element.
|
inline |
Construct a set consisting of two elements.
|
inline |
Construct a SmallSet from a range of elements.
TIterator | Iterates over instances of type T. |
begin | Points to first element to be added. |
end | Points just beyond last element to be added. |
sizeHint | For efficiency, the number of elements can be speficied by sizeHint. |
|
inline |
Inserts t into *this
.
|
inline |
Erases t from *this
.
|
inline |
Set-minus operator: returns all elements in *this
, except those in x.
|
inline |
Set-union operator: returns all elements in *this
, plus those in x.
|
inline |
Set-intersection operator: returns all elements in *this
that are also contained in x.
|
inline |
Erases from *this
all elements in x.
|
inline |
Erases one element.
|
inline |
Adds to *this
all elements in x.
|
inline |
Adds one element.
|
inline |
Erases from *this
all elements not in x.
|
inline |
Returns true
if *this
is a subset of x.
|
inline |
Returns true
if x is a subset of *this
.
|
inline |
Returns true
if *this
and x have elements in common.
|
inline |
Returns true
if *this
contains the element t.
|
inline |
Returns number of elements.
|
inline |
Returns whether *this
is empty.
|
inline |
Returns reference to the elements.
|
inline |
Returns constant reference to the elements.
|
inline |
Returns iterator that points to the first element.
|
inline |
Returns constant iterator that points to the first element.
|
inline |
Returns iterator that points beyond the last element.
|
inline |
Returns constant iterator that points beyond the last element.
|
inline |
Returns reverse iterator that points to the last element.
|
inline |
Returns constant reverse iterator that points to the last element.
|
inline |
Returns reverse iterator that points beyond the first element.
|
inline |
Returns constant reverse iterator that points beyond the first element.
|
inline |
Returns reference to first element.
|
inline |
Returns constant reference to first element.
|
inline |
Returns reference to last element.
|
inline |
Returns constant reference to last element.
|
inline |
Formats a SmallSet as a string.
Returns true
if a and b are identical.
Returns true
if a and b are not identical.
Lexicographical comparison of elements.
|
friend |
Writes a SmallSet to an output stream.
|
private |
The elements in this set.