code::SetVector< K, bNoDuplicates, Pr, A > Class Template Reference

List of all members.

---

Detailed Description

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>
class code::SetVector< K, bNoDuplicates, Pr, A >

std::set implemented as a sorted vector.

This can give a significant memory improvement over std::set, which is implemented as a tree. The tradeoff is that insertion and removal is slow, so this is best used on sets whose contents change infrequently.

This class was written by Martin Holzherr and is in the public domain.

Public Types
typedef SetVector< K, bNoDuplicates, Pr, A >	Myt_
typedef std::vector< K, A >	Cont
typedef Cont::allocator_type	allocator_type
typedef Cont::size_type	size_type
typedef Cont::difference_type	difference_type
typedef Cont::reference	reference
typedef Cont::const_reference	const_reference
typedef Cont::value_type	value_type
typedef K	key_type
typedef Cont::iterator	iterator
typedef Cont::const_iterator	const_iterator
typedef Pr	key_compare
typedef Pr	value_compare
typedef Cont::const_reverse_iterator	const_reverse_iterator
typedef Cont::reverse_iterator	reverse_iterator
typedef std::pair< iterator, iterator >	Pairii_
typedef std::pair< const_iterator, const_iterator >	Paircc_
typedef std::pair< iterator, bool >	Pairib_
Public Member Functions
	SetVector (const Pr &pred=Pr(), const A &al=A())
template<class It>
	SetVector (It first, It beyond, const Pr &pred=Pr(), const A &al=A())
	SetVector (const Myt_ &x)
	~SetVector ()
Myt_ &	operator= (const Myt_ &x)
Myt_ &	operator= (const Cont &x)
void	reserve (size_type n)
iterator	begin ()
const_iterator	begin () const
iterator	end ()
const_iterator	end () const
reverse_iterator	rbegin ()
const_reverse_iterator	rbegin () const
reverse_iterator	rend ()
const_reverse_iterator	rend () const
size_type	size () const
size_type	max_size () const
bool	empty () const
A	get_allocator () const
const_reference	at (size_type p) const
reference	at (size_type p)
const_reference	operator[] (size_type p) const
reference	operator[] (size_type p)
reference	front ()
const_reference	front () const
reference	back ()
const_reference	back () const
void	pop_back ()
void	assign (const_iterator first, const_iterator beyond)
void	assign (size_type n, const K &x=K())
Pairib_	insert (const value_type &x)
iterator	insert (iterator it, const value_type &x)
template<class It>
void	insert (It first, It beyond)
iterator	erase (iterator p)
iterator	erase (iterator first, iterator beyond)
size_type	erase (const K &key)
void	clear ()
bool	Eq_ (const Myt_ &x) const
bool	Lt_ (const Myt_ &x) const
void	swap (Myt_ &x)
key_compare	key_comp () const
value_compare	value_comp () const
template<class KeyType>
iterator	find (const KeyType &k)
template<class KeyType>
const_iterator	find (const KeyType &k) const
size_type	count (const K &k) const
template<class KeyType>
iterator	lower_bound (const KeyType &k)
template<class KeyType>
const_iterator	lower_bound (const KeyType &k) const
template<class KeyType>
iterator	upper_bound (const KeyType &k)
template<class KeyType>
const_iterator	upper_bound (const KeyType &k) const
template<class KeyType>
Pairii_	equal_range (const KeyType &k)
template<class KeyType>
Paircc_	equal_range (const KeyType &k) const
Cont &	get_container ()
void	sort ()
void	stable_sort ()
Protected Member Functions
iterator	Unique_ ()
iterator	InsertImpl_ (iterator p, const value_type &x)
bool	KeyCompare_Leq_ (const K &ty0, const K &ty1)
bool	KeyCompare_Geq_ (const K &ty0, const K &ty1)
bool	KeyCompare_Gt_ (const K &ty0, const K &ty1)
Protected Attributes
key_compare	key_compare_
Cont	vec_
Friends
void	swap (Myt_ &x, Myt_ &Y_)

---

Member Typedef Documentation

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

typedef Cont::allocator_type code::SetVector< K, bNoDuplicates, Pr, A >::allocator_type

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

typedef Cont::const_iterator code::SetVector< K, bNoDuplicates, Pr, A >::const_iterator

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

typedef Cont::const_reference code::SetVector< K, bNoDuplicates, Pr, A >::const_reference

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

typedef Cont::const_reverse_iterator code::SetVector< K, bNoDuplicates, Pr, A >::const_reverse_iterator

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

typedef std::vector<K,A> code::SetVector< K, bNoDuplicates, Pr, A >::Cont

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

typedef Cont::difference_type code::SetVector< K, bNoDuplicates, Pr, A >::difference_type

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

typedef Cont::iterator code::SetVector< K, bNoDuplicates, Pr, A >::iterator

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

typedef Pr code::SetVector< K, bNoDuplicates, Pr, A >::key_compare

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

typedef K code::SetVector< K, bNoDuplicates, Pr, A >::key_type

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

typedef SetVector<K,bNoDuplicates,Pr,A> code::SetVector< K, bNoDuplicates, Pr, A >::Myt_

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

typedef std::pair<const_iterator, const_iterator> code::SetVector< K, bNoDuplicates, Pr, A >::Paircc_

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

typedef std::pair<iterator, bool> code::SetVector< K, bNoDuplicates, Pr, A >::Pairib_

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

typedef std::pair<iterator, iterator> code::SetVector< K, bNoDuplicates, Pr, A >::Pairii_

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

typedef Cont::reference code::SetVector< K, bNoDuplicates, Pr, A >::reference

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

typedef Cont::reverse_iterator code::SetVector< K, bNoDuplicates, Pr, A >::reverse_iterator

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

typedef Cont::size_type code::SetVector< K, bNoDuplicates, Pr, A >::size_type

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

typedef Pr code::SetVector< K, bNoDuplicates, Pr, A >::value_compare

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

typedef Cont::value_type code::SetVector< K, bNoDuplicates, Pr, A >::value_type

---

Constructor & Destructor Documentation

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

code::SetVector< K, bNoDuplicates, Pr, A >::SetVector	(	const Pr &	pred = Pr(),
		const A &	al = A()
	)			[inline, explicit]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

template<class It>

code::SetVector< K, bNoDuplicates, Pr, A >::SetVector	(	It	first,
		It	beyond,
		const Pr &	pred = Pr(),
		const A &	al = A()
	)			[inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

code::SetVector< K, bNoDuplicates, Pr, A >::SetVector

(

const Myt_ &

x

)

[inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

code::SetVector< K, bNoDuplicates, Pr, A >::~SetVector

(

)

[inline]

---

Member Function Documentation

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

void code::SetVector< K, bNoDuplicates, Pr, A >::assign	(	size_type	n,
		const K &	x = K()
	)			[inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

void code::SetVector< K, bNoDuplicates, Pr, A >::assign	(	const_iterator	first,
		const_iterator	beyond
	)			[inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

reference code::SetVector< K, bNoDuplicates, Pr, A >::at

(

size_type

p

)

[inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

const_reference code::SetVector< K, bNoDuplicates, Pr, A >::at

(

size_type

p

)

const [inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

const_reference code::SetVector< K, bNoDuplicates, Pr, A >::back

(

)

const [inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

reference code::SetVector< K, bNoDuplicates, Pr, A >::back

(

)

[inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

const_iterator code::SetVector< K, bNoDuplicates, Pr, A >::begin

(

)

const [inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

iterator code::SetVector< K, bNoDuplicates, Pr, A >::begin

(

)

[inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

void code::SetVector< K, bNoDuplicates, Pr, A >::clear

(

)

[inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

size_type code::SetVector< K, bNoDuplicates, Pr, A >::count

(

const K &

k

)

const [inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

bool code::SetVector< K, bNoDuplicates, Pr, A >::empty

(

)

const [inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

const_iterator code::SetVector< K, bNoDuplicates, Pr, A >::end

(

)

const [inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

iterator code::SetVector< K, bNoDuplicates, Pr, A >::end

(

)

[inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

bool code::SetVector< K, bNoDuplicates, Pr, A >::Eq_

(

const Myt_ &

x

)

const [inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

template<class KeyType>

Paircc_ code::SetVector< K, bNoDuplicates, Pr, A >::equal_range

(

const KeyType &

k

)

const [inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

template<class KeyType>

Pairii_ code::SetVector< K, bNoDuplicates, Pr, A >::equal_range

(

const KeyType &

k

)

[inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

size_type code::SetVector< K, bNoDuplicates, Pr, A >::erase

(

const K &

key

)

[inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

iterator code::SetVector< K, bNoDuplicates, Pr, A >::erase	(	iterator	first,
		iterator	beyond
	)			[inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

iterator code::SetVector< K, bNoDuplicates, Pr, A >::erase

(

iterator

p

)

[inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

template<class KeyType>

const_iterator code::SetVector< K, bNoDuplicates, Pr, A >::find

(

const KeyType &

k

)

const [inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

template<class KeyType>

iterator code::SetVector< K, bNoDuplicates, Pr, A >::find

(

const KeyType &

k

)

[inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

const_reference code::SetVector< K, bNoDuplicates, Pr, A >::front

(

)

const [inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

reference code::SetVector< K, bNoDuplicates, Pr, A >::front

(

)

[inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

A code::SetVector< K, bNoDuplicates, Pr, A >::get_allocator

(

)

const [inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

Cont& code::SetVector< K, bNoDuplicates, Pr, A >::get_container

(

)

[inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

template<class It>

void code::SetVector< K, bNoDuplicates, Pr, A >::insert	(	It	first,
		It	beyond
	)			[inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

iterator code::SetVector< K, bNoDuplicates, Pr, A >::insert	(	iterator	it,
		const value_type &	x
	)			[inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

Pairib_ code::SetVector< K, bNoDuplicates, Pr, A >::insert

(

const value_type &

x

)

[inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

iterator code::SetVector< K, bNoDuplicates, Pr, A >::InsertImpl_	(	iterator	p,
		const value_type &	x
	)			[inline, protected]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

key_compare code::SetVector< K, bNoDuplicates, Pr, A >::key_comp

(

)

const [inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

bool code::SetVector< K, bNoDuplicates, Pr, A >::KeyCompare_Geq_	(	const K &	ty0,
		const K &	ty1
	)			[inline, protected]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

bool code::SetVector< K, bNoDuplicates, Pr, A >::KeyCompare_Gt_	(	const K &	ty0,
		const K &	ty1
	)			[inline, protected]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

bool code::SetVector< K, bNoDuplicates, Pr, A >::KeyCompare_Leq_	(	const K &	ty0,
		const K &	ty1
	)			[inline, protected]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

template<class KeyType>

const_iterator code::SetVector< K, bNoDuplicates, Pr, A >::lower_bound

(

const KeyType &

k

)

const [inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

template<class KeyType>

iterator code::SetVector< K, bNoDuplicates, Pr, A >::lower_bound

(

const KeyType &

k

)

[inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

bool code::SetVector< K, bNoDuplicates, Pr, A >::Lt_

(

const Myt_ &

x

)

const [inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

size_type code::SetVector< K, bNoDuplicates, Pr, A >::max_size

(

)

const [inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

Myt_& code::SetVector< K, bNoDuplicates, Pr, A >::operator=

(

const Cont &

x

)

[inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

Myt_& code::SetVector< K, bNoDuplicates, Pr, A >::operator=

(

const Myt_ &

x

)

[inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

reference code::SetVector< K, bNoDuplicates, Pr, A >::operator[]

(

size_type

p

)

[inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

const_reference code::SetVector< K, bNoDuplicates, Pr, A >::operator[]

(

size_type

p

)

const [inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

void code::SetVector< K, bNoDuplicates, Pr, A >::pop_back

(

)

[inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

const_reverse_iterator code::SetVector< K, bNoDuplicates, Pr, A >::rbegin

(

)

const [inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

reverse_iterator code::SetVector< K, bNoDuplicates, Pr, A >::rbegin

(

)

[inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

const_reverse_iterator code::SetVector< K, bNoDuplicates, Pr, A >::rend

(

)

const [inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

reverse_iterator code::SetVector< K, bNoDuplicates, Pr, A >::rend

(

)

[inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

void code::SetVector< K, bNoDuplicates, Pr, A >::reserve

(

size_type

n

)

[inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

size_type code::SetVector< K, bNoDuplicates, Pr, A >::size

(

)

const [inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

void code::SetVector< K, bNoDuplicates, Pr, A >::sort

(

)

[inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

void code::SetVector< K, bNoDuplicates, Pr, A >::stable_sort

(

)

[inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

void code::SetVector< K, bNoDuplicates, Pr, A >::swap

(

Myt_ &

x

)

[inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

iterator code::SetVector< K, bNoDuplicates, Pr, A >::Unique_

(

)

[inline, protected]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

template<class KeyType>

const_iterator code::SetVector< K, bNoDuplicates, Pr, A >::upper_bound

(

const KeyType &

k

)

const [inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

template<class KeyType>

iterator code::SetVector< K, bNoDuplicates, Pr, A >::upper_bound

(

const KeyType &

k

)

[inline]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

value_compare code::SetVector< K, bNoDuplicates, Pr, A >::value_comp

(

)

const [inline]

---

Friends And Related Function Documentation

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

void swap	(	Myt_ &	x,
		Myt_ &	Y_
	)			[friend]

---

Member Data Documentation

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

key_compare code::SetVector< K, bNoDuplicates, Pr, A >::key_compare_ [protected]

template<class K, bool bNoDuplicates = false, class Pr = std::less<K>, class A = std::allocator<K>>

Cont code::SetVector< K, bNoDuplicates, Pr, A >::vec_ [protected]

---