#include <yat/utility/Ranking.h>

Public Types
typedef T	value_type
	value type

typedef Compare	key_compare
	type used to compare elements

typedef const T &	reference
	reference

typedef const T &	const_reference
	reference

typedef const T *	pointer
	pointer

typedef const T *	const_pointer
	const pointer

typedef size_t	size_type
	size type

typedef ranking::Iterator< T >	iterator
	iterator

typedef ranking::Iterator< T >	const_iterator
	iterator

typedef std::reverse_iterator< iterator >	reverse_iterator
	reverse iterator

typedef std::reverse_iterator< const_iterator >	const_reverse_iterator
	reverse iterator

Public Member Functions
	Ranking (void)=default
	Default constructor.

	~Ranking (void)
	Destructor.

	Ranking (const Compare &c)

	Ranking (const Ranking &other)
	Copy constructor.

	Ranking (Ranking &&other)
	move constructor

Ranking &	operator= (const Ranking &other)
	assignment operator

Ranking &	operator= (Ranking &&other)
	move assignment

iterator	begin (void)

const_iterator	begin (void) const

const_iterator	cbegin (void) const

iterator	end (void)

const_iterator	end (void) const

const_iterator	cend (void) const

reverse_iterator	rbegin (void)

reverse_iterator	rend (void)

const_reverse_iterator	rend (void) const

const_reverse_iterator	rbegin (void) const

const_reverse_iterator	crbegin (void) const

const_reverse_iterator	crend (void) const

void	clear (void)

const Compare &	compare (void) const

bool	empty (void) const

iterator	erase (const_iterator position)

size_type	erase (const T &value)

iterator	erase (const_iterator first, const_iterator last)

const_iterator	find (const T &x) const

iterator	insert (const T &element)
	insert an element More...

iterator	insert (T &&element)
	insert an element More...

iterator	insert (const_iterator hint, const T &element)
	insert with hint More...

iterator	insert (const_iterator hint, T &&element)
	insert with hint More...

template<typename InputIterator >
void	insert (InputIterator first, InputIterator last)
	insert range More...

const_iterator	lower_bound (const T &x) const

const_iterator	upper_bound (const T &x) const

size_t	ranking (const_iterator it) const

size_t	size (void) const

Detailed Description

template<typename T, class Compare = std::less<T>>
class theplu::yat::utility::Ranking< T, Compare >

Class is a binary tree with the special extension that it allows fast access to the rank of an element in the tree.

Since: New in yat 0.19

Constructor & Destructor Documentation

◆ Ranking()

template<typename T , class Compare = std::less<T>>

theplu::yat::utility::Ranking< T, Compare >::Ranking ( const Compare & c )

inline

Construct empty container with comparison function c.

Member Function Documentation

◆ begin() [1/2]

template<typename T , class Compare = std::less<T>>

iterator theplu::yat::utility::Ranking< T, Compare >::begin ( void )

inline

Returns: iterator pointing to the first element, i.e., the node with the smallest value.

◆ begin() [2/2]

template<typename T , class Compare = std::less<T>>

const_iterator theplu::yat::utility::Ranking< T, Compare >::begin ( void ) const

inline

Returns: iterator pointing to the first element

◆ cbegin()

template<typename T , class Compare = std::less<T>>

const_iterator theplu::yat::utility::Ranking< T, Compare >::cbegin ( void ) const

inline

Returns: iterator pointing to the first element

◆ cend()

template<typename T , class Compare = std::less<T>>

const_iterator theplu::yat::utility::Ranking< T, Compare >::cend ( void ) const

inline

Returns: iterator pointing to one-passed-last element

◆ clear()

template<typename T , class Compare = std::less<T>>

void theplu::yat::utility::Ranking< T, Compare >::clear ( void )

inline

Remove all nodes

◆ compare()

template<typename T , class Compare = std::less<T>>

const Compare& theplu::yat::utility::Ranking< T, Compare >::compare ( void ) const

inline

access comparison function which is used to sort elements

◆ crbegin()

template<typename T , class Compare = std::less<T>>

const_reverse_iterator theplu::yat::utility::Ranking< T, Compare >::crbegin ( void ) const

inline

Returns: reverse iterator pointing to first element

◆ crend()

template<typename T , class Compare = std::less<T>>

const_reverse_iterator theplu::yat::utility::Ranking< T, Compare >::crend ( void ) const

inline

Returns: reverse iterator pointing to the one-passed-last element

◆ empty()

template<typename T , class Compare = std::less<T>>

bool theplu::yat::utility::Ranking< T, Compare >::empty ( void ) const

inline

Returns: true if (and only if) container has zero elements

◆ end() [1/2]

template<typename T , class Compare = std::less<T>>

iterator theplu::yat::utility::Ranking< T, Compare >::end ( void )

inline

Returns: iterator pointing to one-passed-last element

◆ end() [2/2]

template<typename T , class Compare = std::less<T>>

const_iterator theplu::yat::utility::Ranking< T, Compare >::end ( void ) const

inline

Returns: iterator pointing to one-passed-last element

◆ erase() [1/3]

template<typename T , class Compare = std::less<T>>

iterator theplu::yat::utility::Ranking< T, Compare >::erase ( const_iterator position )

Remove node pointed to by position.

Returns: An iterator pointing to the element that follows the last element removed.

Complexity: constant time.

◆ erase() [2/3]

template<typename T , class Compare = std::less<T>>

size_type theplu::yat::utility::Ranking< T, Compare >::erase ( const T & value )

Erase all elements that are equivalent with value

Returns: number of elements removed

Complexity: logarithmic in size of container.

◆ erase() [3/3]

template<typename T , class Compare = std::less<T>>

iterator theplu::yat::utility::Ranking< T, Compare >::erase	(	const_iterator	first,
		const_iterator	last
	)

Remove elements in range [first, last).

Returns: An iterator pointing to the element that follows the last element removed.

Complexity: Linear in number of elements erased.

◆ find()

template<typename T , class Compare = std::less<T>>

const_iterator theplu::yat::utility::Ranking< T, Compare >::find ( const T & x ) const

Find an element that is equivalent to x.

Returns: end() if no such element exists

Complexity: logarithmic in size of container.

◆ insert() [1/5]

template<typename T , class Compare = std::less<T>>

iterator theplu::yat::utility::Ranking< T, Compare >::insert ( const T & element )

inline

insert an element

Returns: a n iterator pointing to just inserted element

Complexity: logarithmic in size of container.

◆ insert() [2/5]

template<typename T , class Compare = std::less<T>>

iterator theplu::yat::utility::Ranking< T, Compare >::insert ( T && element )

inline

insert an element

Same as insert(const T& element) but moves rather than copy element.

◆ insert() [3/5]

template<typename T , class Compare = std::less<T>>

iterator theplu::yat::utility::Ranking< T, Compare >::insert	(	const_iterator	hint,
		const T &	element
	)

inline

insert with hint

If hint will follow the inserted element, the insertion is done in constant time. Otherwise, the usual insert function is called which takes logN.

◆ insert() [4/5]

template<typename T , class Compare = std::less<T>>

iterator theplu::yat::utility::Ranking< T, Compare >::insert	(	const_iterator	hint,
		T &&	element
	)

inline

insert with hint

Same as as insert(const_iterator, const T&) but move instead of copy element.

◆ insert() [5/5]

template<typename T , class Compare = std::less<T>>

template<typename InputIterator >

void theplu::yat::utility::Ranking< T, Compare >::insert	(	InputIterator	first,
		InputIterator	last
	)

inline

insert range

Complexity: N log S, where S is size of container and N is number of inserted elements. If inserted range is sorted, complexity linear, N.

◆ lower_bound()

template<typename T , class Compare = std::less<T>>

const_iterator theplu::yat::utility::Ranking< T, Compare >::lower_bound ( const T & x ) const

inline

Returns: the first element which is equal (or greater) to x

Complexity: logarithmic in size of container.

◆ ranking()

template<typename T , class Compare = std::less<T>>

size_t theplu::yat::utility::Ranking< T, Compare >::ranking ( const_iterator it ) const

inline

Returns: number of elements smaller than it

Complexity: logarithmic in size of container.

◆ rbegin() [1/2]

template<typename T , class Compare = std::less<T>>

reverse_iterator theplu::yat::utility::Ranking< T, Compare >::rbegin ( void )

inline

Returns: reverse iterator pointing to first element, i.e., the node with the largest value.

◆ rbegin() [2/2]

template<typename T , class Compare = std::less<T>>

const_reverse_iterator theplu::yat::utility::Ranking< T, Compare >::rbegin ( void ) const

inline

Returns: reverse iterator pointing to first element

◆ rend() [1/2]

template<typename T , class Compare = std::less<T>>

reverse_iterator theplu::yat::utility::Ranking< T, Compare >::rend ( void )

inline

Returns: reverse iterator pointing to one-passed-last element

◆ rend() [2/2]

template<typename T , class Compare = std::less<T>>

const_reverse_iterator theplu::yat::utility::Ranking< T, Compare >::rend ( void ) const

inline

Returns: reverse iterator pointing to one-passed-last element

◆ size()

template<typename T , class Compare = std::less<T>>

size_t theplu::yat::utility::Ranking< T, Compare >::size ( void ) const

inline

Returns: number of elements in container

Complexity: constant time

◆ upper_bound()

template<typename T , class Compare = std::less<T>>

const_iterator theplu::yat::utility::Ranking< T, Compare >::upper_bound ( const T & x ) const

inline

Returns: the first element which is greater than x

Complexity: logarithmic in size of container.

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

yat/utility/Ranking.h

Public Types

Public Member Functions

Detailed Description

template<typename T, class Compare = std::less<T>> class theplu::yat::utility::Ranking< T, Compare >

Constructor & Destructor Documentation

◆ Ranking()

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ cbegin()

◆ cend()

◆ clear()

◆ compare()

◆ crbegin()

◆ crend()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ erase() [1/3]

◆ erase() [2/3]

◆ erase() [3/3]

◆ find()

◆ insert() [1/5]

◆ insert() [2/5]

◆ insert() [3/5]

◆ insert() [4/5]

◆ insert() [5/5]

◆ lower_bound()

◆ ranking()

◆ rbegin() [1/2]

◆ rbegin() [2/2]

◆ rend() [1/2]

◆ rend() [2/2]

◆ size()

◆ upper_bound()

template<typename T, class Compare = std::less<T>>
class theplu::yat::utility::Ranking< T, Compare >