claw 1.9.0
 
Loading...
Searching...
No Matches
claw::avl_base< K, Comp > Class Template Reference

Binary search tree base AVL implementation. More...

#include <avl_base.hpp>

Classes

class  avl_const_iterator
 AVL iterator. More...
 
class  avl_iterator
 AVL iterator. More...
 

Public Types

typedef K value_type
 
typedef K key_type
 
typedef K referent_type
 
typedef Comp key_less
 
typedef const K & const_reference
 
typedef avl_iterator iterator
 
typedef avl_const_iterator const_iterator
 

Public Member Functions

 avl_base (const avl_base< K, Comp > &that)
 
void insert (const K &key)
 
template<typename Iterator>
void insert (Iterator first, Iterator last)
 
void erase (const K &key)
 
void clear ()
 
unsigned int size () const
 
bool empty () const
 
iterator begin ()
 
const_iterator begin () const
 
iterator end ()
 
const_iterator end () const
 
iterator find (const K &key)
 
const_iterator find (const K &key) const
 
iterator find_nearest_greater (const K &key)
 
const_iterator find_nearest_greater (const K &key) const
 
iterator find_nearest_lower (const K &key)
 
const_iterator find_nearest_lower (const K &key) const
 
iterator lower_bound ()
 
const_iterator lower_bound () const
 
iterator upper_bound ()
 
const_iterator upper_bound () const
 
avl_base< K, Comp > & operator= (const avl_base< K, Comp > &that)
 
bool operator== (const avl_base< K, Comp > &that) const
 
bool operator!= (const avl_base< K, Comp > &that) const
 
bool operator< (const avl_base< K, Comp > &that) const
 
bool operator> (const avl_base< K, Comp > &that) const
 
bool operator<= (const avl_base< K, Comp > &that) const
 
bool operator>= (const avl_base< K, Comp > &that) const
 
void swap (avl_base< K, Comp > &that)
 

Static Public Attributes

static key_less s_key_less
 Function object used to compare keys.
 

Detailed Description

template<class K, class Comp = std::less<K>>
class claw::avl_base< K, Comp >

Binary search tree base AVL implementation.

Each key appears only once. Nodes are sorted as left_child < node < right_child.

Invariant
this->empty() <==> (this->size() == 0)
this is an AVL.
Remarks
Type requirements :
  • K is LessThanComparable ;
  • Comp is a binary predicate such that Comp(K a, K b) == true if a < b.
Code is taken from a C implementation, so perhaps it doesn't really look nice for C++. Nevertheless it works perfectly and it's fast conversion : that good things.
Author
Julien Jorge

Definition at line 57 of file avl_base.hpp.

Member Typedef Documentation

◆ const_iterator

template<class K, class Comp = std::less<K>>
typedef avl_const_iterator claw::avl_base< K, Comp >::const_iterator

Definition at line 205 of file avl_base.hpp.

◆ const_reference

template<class K, class Comp = std::less<K>>
typedef const K& claw::avl_base< K, Comp >::const_reference

Definition at line 203 of file avl_base.hpp.

◆ iterator

template<class K, class Comp = std::less<K>>
typedef avl_iterator claw::avl_base< K, Comp >::iterator

Definition at line 204 of file avl_base.hpp.

◆ key_less

template<class K, class Comp = std::less<K>>
typedef Comp claw::avl_base< K, Comp >::key_less

Definition at line 202 of file avl_base.hpp.

◆ key_type

template<class K, class Comp = std::less<K>>
typedef K claw::avl_base< K, Comp >::key_type

Definition at line 200 of file avl_base.hpp.

◆ referent_type

template<class K, class Comp = std::less<K>>
typedef K claw::avl_base< K, Comp >::referent_type

Definition at line 201 of file avl_base.hpp.

◆ value_type

template<class K, class Comp = std::less<K>>
typedef K claw::avl_base< K, Comp >::value_type

Definition at line 199 of file avl_base.hpp.

Member Data Documentation

◆ s_key_less

template<class K, class Comp = std::less<K>>
key_less claw::avl_base< K, Comp >::s_key_less
static

Function object used to compare keys.

Definition at line 303 of file avl_base.hpp.


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