dai::SmallSet< T > Class Template Reference

Represents a set; the implementation is optimized for a small number of elements. More...

#include <dai/smallset.h>

Inheritance diagram for dai::SmallSet< T >:

dai::VarSet dai::Region

List of all members.

Public Types

typedef std::vector< T >
::const_iterator 
const_iterator
 Constant iterator over the elements.
typedef std::vector< T >::iterator iterator
 Iterator over the elements.
typedef std::vector< T >
::const_reverse_iterator 
const_reverse_iterator
 Constant reverse iterator over the elements.
typedef std::vector< T >
::reverse_iterator 
reverse_iterator
 Reverse iterator over the elements.

Public Member Functions

Constructors and destructors
 SmallSet ()
 Default constructor (constructs an empty set).
 SmallSet (const T &t)
 Construct a set consisting of one element.
 SmallSet (const T &t1, const T &t2)
 Construct a set consisting of two elements.
template<typename TIterator>
 SmallSet (TIterator begin, TIterator end, size_t sizeHint=0)
 Construct a SmallSet from a range of elements.
Operators for set-theoretic operations
SmallSet operator/ (const SmallSet &x) const
 Set-minus operator: returns all elements in *this, except those in x.
SmallSet operator| (const SmallSet &x) const
 Set-union operator: returns all elements in *this, plus those in x.
SmallSet operator & (const SmallSet &x) const
 Set-intersection operator: returns all elements in *this that are also contained in x.
SmallSetoperator/= (const SmallSet &x)
 Erases from *this all elements in x.
SmallSetoperator/= (const T &t)
 Erases one element.
SmallSetoperator|= (const SmallSet &x)
 Adds to *this all elements in x.
SmallSetoperator|= (const T &t)
 Adds one element.
SmallSetoperator &= (const SmallSet &x)
 Erases from *this all elements not in x.
bool operator<< (const SmallSet &x) const
 Returns true if *this is a subset of x.
bool operator>> (const SmallSet &x) const
 Returns true if x is a subset of *this.
Queries
bool intersects (const SmallSet &x) const
 Returns true if *this and x have elements in common.
bool contains (const T &t) const
 Returns true if *this contains the element t.
std::vector< T >::size_type size () const
 Returns number of elements.
bool empty () const
 Returns whether *this is empty.
std::vector< T > & elements ()
 Returns reference to the elements.
const std::vector< T > & elements () const
 Returns constant reference to the elements.
Iterator interface
iterator begin ()
 Returns iterator that points to the first element.
const_iterator begin () const
 Returns constant iterator that points to the first element.
iterator end ()
 Returns iterator that points beyond the last element.
const_iterator end () const
 Returns constant iterator that points beyond the last element.
reverse_iterator rbegin ()
 Returns reverse iterator that points to the last element.
const_reverse_iterator rbegin () const
 Returns constant reverse iterator that points to the last element.
reverse_iterator rend ()
 Returns reverse iterator that points beyond the first element.
const_reverse_iterator rend () const
 Returns constant reverse iterator that points beyond the first element.
T & front ()
 Returns reference to first element.
const T & front () const
 Returns constant reference to first element.

Private Attributes

std::vector< T > _elements
 The elements in this set.

Friends

Comparison operators
bool operator== (const SmallSet &a, const SmallSet &b)
 Returns true if a and b are identical.
bool operator!= (const SmallSet &a, const SmallSet &b)
 Returns true if a and b are not identical.
bool operator< (const SmallSet &a, const SmallSet &b)
 Lexicographical comparison of elements.


Detailed Description

template<typename T>
class dai::SmallSet< T >

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.

Template Parameters:
T Should be less-than-comparable.

Member Typedef Documentation

template<typename T>
typedef std::vector<T>::const_iterator dai::SmallSet< T >::const_iterator

Constant iterator over the elements.

template<typename T>
typedef std::vector<T>::iterator dai::SmallSet< T >::iterator

Iterator over the elements.

template<typename T>
typedef std::vector<T>::const_reverse_iterator dai::SmallSet< T >::const_reverse_iterator

Constant reverse iterator over the elements.

template<typename T>
typedef std::vector<T>::reverse_iterator dai::SmallSet< T >::reverse_iterator

Reverse iterator over the elements.


Constructor & Destructor Documentation

template<typename T>
dai::SmallSet< T >::SmallSet (  )  [inline]

Default constructor (constructs an empty set).

template<typename T>
dai::SmallSet< T >::SmallSet ( const T &  t  )  [inline]

Construct a set consisting of one element.

template<typename T>
dai::SmallSet< T >::SmallSet ( const T &  t1,
const T &  t2 
) [inline]

Construct a set consisting of two elements.

template<typename T>
template<typename TIterator>
dai::SmallSet< T >::SmallSet ( TIterator  begin,
TIterator  end,
size_t  sizeHint = 0 
) [inline]

Construct a SmallSet from a range of elements.

Template Parameters:
TIterator Iterates over instances of type T.
Parameters:
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.


Member Function Documentation

template<typename T>
SmallSet dai::SmallSet< T >::operator/ ( const SmallSet< T > &  x  )  const [inline]

Set-minus operator: returns all elements in *this, except those in x.

template<typename T>
SmallSet dai::SmallSet< T >::operator| ( const SmallSet< T > &  x  )  const [inline]

Set-union operator: returns all elements in *this, plus those in x.

template<typename T>
SmallSet dai::SmallSet< T >::operator & ( const SmallSet< T > &  x  )  const [inline]

Set-intersection operator: returns all elements in *this that are also contained in x.

template<typename T>
SmallSet& dai::SmallSet< T >::operator/= ( const SmallSet< T > &  x  )  [inline]

Erases from *this all elements in x.

template<typename T>
SmallSet& dai::SmallSet< T >::operator/= ( const T &  t  )  [inline]

Erases one element.

template<typename T>
SmallSet& dai::SmallSet< T >::operator|= ( const SmallSet< T > &  x  )  [inline]

Adds to *this all elements in x.

template<typename T>
SmallSet& dai::SmallSet< T >::operator|= ( const T &  t  )  [inline]

Adds one element.

template<typename T>
SmallSet& dai::SmallSet< T >::operator &= ( const SmallSet< T > &  x  )  [inline]

Erases from *this all elements not in x.

template<typename T>
bool dai::SmallSet< T >::operator<< ( const SmallSet< T > &  x  )  const [inline]

Returns true if *this is a subset of x.

template<typename T>
bool dai::SmallSet< T >::operator>> ( const SmallSet< T > &  x  )  const [inline]

Returns true if x is a subset of *this.

template<typename T>
bool dai::SmallSet< T >::intersects ( const SmallSet< T > &  x  )  const [inline]

Returns true if *this and x have elements in common.

template<typename T>
bool dai::SmallSet< T >::contains ( const T &  t  )  const [inline]

Returns true if *this contains the element t.

template<typename T>
std::vector<T>::size_type dai::SmallSet< T >::size (  )  const [inline]

Returns number of elements.

Examples:
example_permute.cpp.

template<typename T>
bool dai::SmallSet< T >::empty (  )  const [inline]

Returns whether *this is empty.

template<typename T>
std::vector<T>& dai::SmallSet< T >::elements (  )  [inline]

Returns reference to the elements.

template<typename T>
const std::vector<T>& dai::SmallSet< T >::elements (  )  const [inline]

Returns constant reference to the elements.

template<typename T>
iterator dai::SmallSet< T >::begin (  )  [inline]

Returns iterator that points to the first element.

Examples:
example_permute.cpp.

template<typename T>
const_iterator dai::SmallSet< T >::begin (  )  const [inline]

Returns constant iterator that points to the first element.

template<typename T>
iterator dai::SmallSet< T >::end (  )  [inline]

Returns iterator that points beyond the last element.

template<typename T>
const_iterator dai::SmallSet< T >::end (  )  const [inline]

Returns constant iterator that points beyond the last element.

template<typename T>
reverse_iterator dai::SmallSet< T >::rbegin (  )  [inline]

Returns reverse iterator that points to the last element.

template<typename T>
const_reverse_iterator dai::SmallSet< T >::rbegin (  )  const [inline]

Returns constant reverse iterator that points to the last element.

template<typename T>
reverse_iterator dai::SmallSet< T >::rend (  )  [inline]

Returns reverse iterator that points beyond the first element.

template<typename T>
const_reverse_iterator dai::SmallSet< T >::rend (  )  const [inline]

Returns constant reverse iterator that points beyond the first element.

template<typename T>
T& dai::SmallSet< T >::front (  )  [inline]

Returns reference to first element.

template<typename T>
const T& dai::SmallSet< T >::front (  )  const [inline]

Returns constant reference to first element.


Friends And Related Function Documentation

template<typename T>
bool operator== ( const SmallSet< T > &  a,
const SmallSet< T > &  b 
) [friend]

Returns true if a and b are identical.

template<typename T>
bool operator!= ( const SmallSet< T > &  a,
const SmallSet< T > &  b 
) [friend]

Returns true if a and b are not identical.

template<typename T>
bool operator< ( const SmallSet< T > &  a,
const SmallSet< T > &  b 
) [friend]

Lexicographical comparison of elements.


Member Data Documentation

template<typename T>
std::vector<T> dai::SmallSet< T >::_elements [private]

The elements in this set.


The documentation for this class was generated from the following file:

Generated on Thu Feb 11 12:26:07 2010 for libDAI by  doxygen 1.5.5