datastructures::detail::avl_iterator< TTree, is_const > Class Template Reference

The AVL tree iterator type. More...

#include <_avl_iterator.hpp>

Public Types
using	iterator_category = std::bidirectional_iterator_tag
	Tells the compiler that this iterator is bidirectional, needed by STL.
using	value_type = typename tree_type::item_type
	The tree item type, needed by STL.
using	difference_type = typename alloc_traits::difference_type
	Item pointer difference type, needed by STL.
using	pointer = std::conditional_t< is_const, typename alloc_traits::const_pointer, typename alloc_traits::pointer >
	Item pointer, needed by STL.
using	reference = std::conditional_t< is_const, const value_type &, value_type & >
	Item pointer, needed by STL.
using	iterator_concept = std::bidirectional_iterator_tag
	Tells the compiler that this iterator is bidirectional, needed by STL.

Public Member Functions
	avl_iterator (tree_ptr tree, node_ptr node) noexcept
	Creates a new iterator to the given tree.
	avl_iterator () noexcept
	Same as avl_iterator(nullptr, nullptr).
	avl_iterator (const avl_iterator &other) noexcept
avl_iterator &	operator= (const avl_iterator &other) noexcept
	~avl_iterator () noexcept=default
	avl_iterator (const avl_iterator< tree_type, false > &other) noexcept
reference	operator* () const noexcept
pointer	operator-> () const noexcept
avl_iterator &	operator++ () noexcept
avl_iterator	operator++ (int) noexcept
avl_iterator &	operator-- () noexcept
avl_iterator	operator-- (int) noexcept
bool	operator== (const avl_iterator &other) const noexcept
bool	operator!= (const avl_iterator &other) const noexcept

Friends
class	avl_iterator< tree_type, true >
template<class , class , class , class >
class	::datastructures::map

Detailed Description

template<class TTree, bool is_const>
class datastructures::detail::avl_iterator< TTree, is_const >

The AVL tree iterator type.

A bidirectional itertator to iterate through the tree using the successor fnuction, which amortizes to O(1) per node when iterating through the whole tree.

Implements both the normal and constant variant using the is_const compile-time flag.

Compatible with the STL.

Template Parameters

TTree	The internal tree type.
is_const	When true this will be a const_iterator; iterator otherwise.

Member Typedef Documentation

difference_type

template<class TTree , bool is_const>

using datastructures::detail::avl_iterator< TTree, is_const >::difference_type = typename alloc_traits::difference_type

Item pointer difference type, needed by STL.

iterator_category

template<class TTree , bool is_const>

using datastructures::detail::avl_iterator< TTree, is_const >::iterator_category = std::bidirectional_iterator_tag

Tells the compiler that this iterator is bidirectional, needed by STL.

iterator_concept

template<class TTree , bool is_const>

using datastructures::detail::avl_iterator< TTree, is_const >::iterator_concept = std::bidirectional_iterator_tag

Tells the compiler that this iterator is bidirectional, needed by STL.

pointer

template<class TTree , bool is_const>

using datastructures::detail::avl_iterator< TTree, is_const >::pointer = std::conditional_t<is_const, typename alloc_traits::const_pointer, typename alloc_traits::pointer>

Item pointer, needed by STL.

Usually value_type * or the constant variant.

reference

template<class TTree , bool is_const>

using datastructures::detail::avl_iterator< TTree, is_const >::reference = std::conditional_t<is_const, const value_type &, value_type &>

Item pointer, needed by STL.

Usually value_type & or the constant variant.

value_type

template<class TTree , bool is_const>

using datastructures::detail::avl_iterator< TTree, is_const >::value_type = typename tree_type::item_type

The tree item type, needed by STL.

Constructor & Destructor Documentation

avl_iterator() [1/4]

template<class TTree , bool is_const>

datastructures::detail::avl_iterator< TTree, is_const >::avl_iterator ( tree_ptr  tree, node_ptr  node  )

inlinenoexcept

Creates a new iterator to the given tree.

Parameters

tree	Can be a nullptr in that case the the iterator will not belong to any tree and will not be equal to any past-the-end iterators of any object and every subsequent operation is UB.
node	Can be a nullptr, in that case the iterator will be a past-the-end iterator of the given tree.

avl_iterator() [2/4]

template<class TTree , bool is_const>

datastructures::detail::avl_iterator< TTree, is_const >::avl_iterator ( )

inlinenoexcept

Same as avl_iterator(nullptr, nullptr).

avl_iterator() [3/4]

template<class TTree , bool is_const>

datastructures::detail::avl_iterator< TTree, is_const >::avl_iterator ( const avl_iterator< TTree, is_const > &  other )

inlinenoexcept

~avl_iterator()

template<class TTree , bool is_const>

datastructures::detail::avl_iterator< TTree, is_const >::~avl_iterator ( )

defaultnoexcept

avl_iterator() [4/4]

template<class TTree , bool is_const>

datastructures::detail::avl_iterator< TTree, is_const >::avl_iterator ( const avl_iterator< tree_type, false > &  other )

inlinenoexcept

Member Function Documentation

operator!=()

template<class TTree , bool is_const>

bool datastructures::detail::avl_iterator< TTree, is_const >::operator!= ( const avl_iterator< TTree, is_const > &  other ) const

inlinenoexcept

operator*()

template<class TTree , bool is_const>

reference datastructures::detail::avl_iterator< TTree, is_const >::operator* ( ) const

inlinenoexcept

operator++() [1/2]

template<class TTree , bool is_const>

avl_iterator & datastructures::detail::avl_iterator< TTree, is_const >::operator++ ( )

inlinenoexcept

operator++() [2/2]

template<class TTree , bool is_const>

avl_iterator datastructures::detail::avl_iterator< TTree, is_const >::operator++ ( int  )

inlinenoexcept

operator--() [1/2]

template<class TTree , bool is_const>

avl_iterator & datastructures::detail::avl_iterator< TTree, is_const >::operator-- ( )

inlinenoexcept

operator--() [2/2]

template<class TTree , bool is_const>

avl_iterator datastructures::detail::avl_iterator< TTree, is_const >::operator-- ( int  )

inlinenoexcept

operator->()

template<class TTree , bool is_const>

pointer datastructures::detail::avl_iterator< TTree, is_const >::operator-> ( ) const

inlinenoexcept

operator=()

template<class TTree , bool is_const>

avl_iterator & datastructures::detail::avl_iterator< TTree, is_const >::operator= ( const avl_iterator< TTree, is_const > &  other )

inlinenoexcept

operator==()

template<class TTree , bool is_const>

bool datastructures::detail::avl_iterator< TTree, is_const >::operator== ( const avl_iterator< TTree, is_const > &  other ) const

inlinenoexcept

Friends And Related Symbol Documentation

::datastructures::map

template<class TTree , bool is_const>

template<class , class , class , class >

friend class ::datastructures::map

friend

avl_iterator< tree_type, true >

template<class TTree , bool is_const>

friend class avl_iterator< tree_type, true >

friend

---

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

• include/datastructures/_avl_iterator.hpp