dai::SmallSet< T > Class Template Reference

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

#include <dai/smallset.h>

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)
	Construct a SmallSet from a range of elements.
Operators for set-theoretic operations
SmallSet &	insert (const T &t)
	Inserts t into *this.
SmallSet &	erase (const T &t)
	Erases t from *this.
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.
SmallSet &	operator/= (const SmallSet &x)
	Erases from *this all elements in x.
SmallSet &	operator/= (const T &t)
	Erases one element.
SmallSet &	operator|= (const SmallSet &x)
	Adds to *this all elements in x.
SmallSet &	operator|= (const T &t)
	Adds one element.
SmallSet &	operator&= (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.
T &	back ()
	Returns reference to last element.
const T &	back () const
	Returns constant reference to last 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.
Streaming input/output
std::ostream &	operator<< (std::ostream &os, const SmallSet &x)
	Writes a SmallSet to an output stream.

---

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
	)		[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.

Note:

The sizeHint parameter used to be optional in libDAI versions 0.2.4 and earlier.

---

Member Function Documentation

template<typename T>

SmallSet& dai::SmallSet< T >::insert

(

const T &

t

)

[inline]

Inserts t into *this.

template<typename T>

SmallSet& dai::SmallSet< T >::erase

(

const T &

t

)

[inline]

Erases t from *this.

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.

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.

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.

template<typename T>

T& dai::SmallSet< T >::back

(

)

[inline]

Returns reference to last element.

template<typename T>

const T& dai::SmallSet< T >::back

(

)

const [inline]

Returns constant reference to last 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.

template<typename T>

std::ostream& operator<<	(	std::ostream &	os,
		const SmallSet< T > &	x
	)		[friend]

Writes a SmallSet to an output stream.

---

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:

• include/dai/smallset.h