A chained list used by gum::HashTable. More...

#include <agrum/base/core/hashTable.h>

Public Types

using	key_type = Key
	types for STL compliance
using	mapped_type = Val
	types for STL compliance
using	value_type = std::pair< const Key, Val >
	types for STL compliance
using	reference = value_type&
	types for STL compliance
using	const_reference = const value_type&
	types for STL compliance
using	pointer = value_type*
	types for STL compliance
using	const_pointer = const value_type*
	types for STL compliance
using	size_type = Size
	types for STL compliance
using	Bucket = HashTableBucket< Key, Val >
	types for STL compliance

Public Member Functions
Constructors / Destructors
	HashTableList () noexcept
	Basic constructor that creates an empty list.
	HashTableList (const HashTableList< Key, Val > &from)
	Copy constructor.
	HashTableList (HashTableList< Key, Val > &&from) noexcept
	Move constructor.
	~HashTableList ()
	Class destructor.
Operators
HashTableList< Key, Val > &	operator= (const HashTableList< Key, Val > &from)
	Assignment operator.
HashTableList< Key, Val > &	operator= (HashTableList< Key, Val > &&from) noexcept
	Move operator.
Accessors / Modifiers
value_type &	at (Size i)
	Function at returns the ith element in the current chained list.
const value_type &	at (Size i) const
	Function at returns the ith element in the current chained list.
mapped_type &	operator[] (const key_type &key)
	Returns the value corresponding to a given key.
const mapped_type &	operator[] (const key_type &key) const
	Returns the value corresponding to a given key.
bool	exists (const key_type &key) const
	Returns true if a value with the given key exists.
void	insert (Bucket *new_elt) noexcept
	Inserts a new element in the chained list.
void	erase (Bucket *ptr)
	Removes an element from this chained list.
void	clear ()
	Removes all the elements of this chained list.
bool	empty () const noexcept
	Returns true if this chained list is empty.
Bucket *	bucket (const Key &key) const
	A method to get the bucket corresponding to a given key.

Private Member Functions
void	_copy_ (const HashTableList< Key, Val > &from)
	A function used to perform copies of HashTableLists.

Private Attributes
HashTableBucket< Key, Val > *	_deb_list_ {nullptr}
	A pointer on the first element of the chained list.
HashTableBucket< Key, Val > *	_end_list_ {nullptr}
	A pointer on the last element of the chained list.
Size	_nb_elements_ {Size(0)}
	The number of elements in the chained list.

Friends

class	HashTable< Key, Val >
	Friend for faster access.
class	HashTableIterator< Key, Val >
	Friend for faster access.
class	HashTableConstIterator< Key, Val >
	Friend for faster access.
class	HashTableIteratorSafe< Key, Val >
	Friend for faster access.
class	HashTableConstIteratorSafe< Key, Val >
	Friend for faster access.
std::ostream &	operator<< (std::ostream &s, const HashTableList< Key, Val > &list)
	Prints the content of a gum::HashTableList in the stream.
std::ostream &	operator<< (std::ostream &s, const HashTableList< Key *, Val > &list)
	Prints the content of a gum::HashTableList with pointers key in the stream.
std::ostream &	operator<< (std::ostream &s, const HashTable< Key, Val > &table)
	Prints the content of a gum::HashTable in the stream.
std::ostream &	operator<< (std::ostream &s, const HashTable< Key *, Val > &table)
	Prints the content of a gum::HashTable with pointers key in the stream.

Detailed Description

template<typename Key, typename Val>
class gum::HashTableList< Key, Val >

A chained list used by gum::HashTable.

Template Parameters

Key	The type for keys in a gum::HashTable.
Val	The type for values in a gum::HashTable.

Definition at line 317 of file hashTable.h.

Member Typedef Documentation

◆ Bucket

template<typename Key, typename Val>

using gum::HashTableList< Key, Val >::Bucket = HashTableBucket< Key, Val >

types for STL compliance

Definition at line 329 of file hashTable.h.

◆ const_pointer

template<typename Key, typename Val>

using gum::HashTableList< Key, Val >::const_pointer = const value_type*

types for STL compliance

Definition at line 327 of file hashTable.h.

◆ const_reference

template<typename Key, typename Val>

using gum::HashTableList< Key, Val >::const_reference = const value_type&

types for STL compliance

Definition at line 325 of file hashTable.h.

◆ key_type

template<typename Key, typename Val>

using gum::HashTableList< Key, Val >::key_type = Key

types for STL compliance

Definition at line 321 of file hashTable.h.

◆ mapped_type

template<typename Key, typename Val>

using gum::HashTableList< Key, Val >::mapped_type = Val

types for STL compliance

Definition at line 322 of file hashTable.h.

◆ pointer

template<typename Key, typename Val>

using gum::HashTableList< Key, Val >::pointer = value_type*

types for STL compliance

Definition at line 326 of file hashTable.h.

◆ reference

template<typename Key, typename Val>

using gum::HashTableList< Key, Val >::reference = value_type&

types for STL compliance

Definition at line 324 of file hashTable.h.

◆ size_type

template<typename Key, typename Val>

using gum::HashTableList< Key, Val >::size_type = Size

types for STL compliance

Definition at line 328 of file hashTable.h.

◆ value_type

template<typename Key, typename Val>

using gum::HashTableList< Key, Val >::value_type = std::pair< const Key, Val >

types for STL compliance

Definition at line 323 of file hashTable.h.

Constructor & Destructor Documentation

◆ HashTableList() [1/3]

template<typename Key, typename Val>

INLINE gum::HashTableList< Key, Val >::HashTableList ( )

noexcept

Basic constructor that creates an empty list.

This is what is used basically by gum::HashTable.

Definition at line 134 of file hashTable_tpl.h.

134{}

Referenced by HashTable< Key, Val >, and operator<<.

Here is the caller graph for this function:

◆ HashTableList() [2/3]

template<typename Key, typename Val>

INLINE gum::HashTableList< Key, Val >::HashTableList ( const HashTableList< Key, Val > & from )

Copy constructor.

The new list and that which is copied do not share elements: the new list contains new instances of the keys and values stored in the copied list. Of course, if these values are pointers, the new values point toward the same elements.

Parameters

from	The gum::HashTableList to copy.

Definition at line 137 of file hashTable_tpl.h.

                                                                                       {
    _copy_(from);
  }

References _copy_().

Here is the call graph for this function:

◆ HashTableList() [3/3]

template<typename Key, typename Val>

INLINE gum::HashTableList< Key, Val >::HashTableList ( HashTableList< Key, Val > && from )

noexcept

Move constructor.

Parameters

from	The gum::HashTableList to move.

Definition at line 142 of file hashTable_tpl.h.

                                                                                           :
      _deb_list_{from._deb_list_}, _end_list_{from._end_list_}, _nb_elements_{from._nb_elements_} {
    from._deb_list_ = nullptr;
  }

References _deb_list_.

◆ ~HashTableList()

template<typename Key, typename Val>

INLINE gum::HashTableList< Key, Val >::~HashTableList ( )

Class destructor.

Definition at line 148 of file hashTable_tpl.h.

                                                   {
    for (Bucket *next_ptr, *ptr = _deb_list_; ptr != nullptr; ptr = next_ptr) {
      next_ptr = ptr->next;
      delete ptr;
    }
  }

References _deb_list_, and gum::HashTableBucket< Key, Val >::next.

Member Function Documentation

◆ _copy_()

template<typename Key, typename Val>

void gum::HashTableList< Key, Val >::_copy_ ( const HashTableList< Key, Val > & from )

private

A function used to perform copies of HashTableLists.

This code is shared by the copy constructor and the copy operator. If it cannot perform the necessary allocations, no memory leak occurs and the list is set to the empty list.

Parameters

from	The gum::HashTableList to copy.

Definition at line 64 of file hashTable_tpl.h.

                                                                              {
    Bucket *ptr, *old_ptr{nullptr}, *new_elt{nullptr};
    // set the defaults
    _deb_list_ = nullptr;
 
    // copy from's list
    try {
      for (ptr = from._deb_list_; ptr != nullptr; ptr = ptr->next) {
        // copy the current from's bucket (may throw an exception either because
        // new cannot allocate the bucket or because the copy constructor of Val
        // throws an exception)
        new_elt = new Bucket(*ptr);
 
        // rechain properly the new list
        new_elt->prev = old_ptr;
 
        if (old_ptr != nullptr) old_ptr->next = new_elt;
        else _deb_list_ = new_elt;
 
        old_ptr = new_elt;
      }
 
      if (old_ptr != nullptr) old_ptr->next = nullptr;
 
      // update the number of elements stored into the list and the end of the
      // list
      _nb_elements_ = from._nb_elements_;
      _end_list_    = new_elt;
    } catch (...) {
      // problem: we could not allocate an element in the list => we delete
      // the elements created so far and we throw an exception
      for (; _deb_list_ != nullptr; _deb_list_ = new_elt) {
        new_elt = _deb_list_->next;
        delete _deb_list_;
      }
 
      _nb_elements_ = 0;
      _end_list_    = nullptr;
 
      throw;
    }
  }

References _deb_list_, _end_list_, _nb_elements_, and gum::HashTableBucket< Key, Val >::next.

Referenced by HashTableList(), and operator=().

Here is the caller graph for this function:

◆ at() [1/2]

template<typename Key, typename Val>

INLINE HashTableList< Key, Val >::value_type & gum::HashTableList< Key, Val >::at ( Size i )

Function at returns the ith element in the current chained list.

The first element has index 0.

Parameters

i	The index to look up.

Returns: Returns the value at index i.

Exceptions

NotFound Raised if the list has fewer than i elements.

Definition at line 194 of file hashTable_tpl.h.

                                                                                           {
    if (i >= _nb_elements_) { GUM_ERROR(NotFound, "not enough elements in the chained list") }
 
    Bucket* ptr;
 
    for (ptr = _deb_list_; i; --i, ptr = ptr->next) {}
 
    return ptr->elt();
  }

References _deb_list_, _nb_elements_, gum::HashTableBucket< Key, Val >::elt(), GUM_ERROR, and gum::HashTableBucket< Key, Val >::next.

Here is the call graph for this function:

◆ at() [2/2]

template<typename Key, typename Val>

INLINE const HashTableList< Key, Val >::value_type & gum::HashTableList< Key, Val >::at ( Size i ) const

Function at returns the ith element in the current chained list.

The first element has index 0.

Parameters

i	The index to look up.

Returns: Returns the value at index i.

Exceptions

NotFound Raised if the list has fewer than i elements.

Definition at line 206 of file hashTable_tpl.h.

                                                {
    if (i >= _nb_elements_) { GUM_ERROR(NotFound, "not enough elements in the chained list") }
 
    Bucket* ptr;
 
    for (ptr = _deb_list_; i; --i, ptr = ptr->next) {}
 
    return ptr->elt();
  }

References _deb_list_, _nb_elements_, gum::HashTableBucket< Key, Val >::elt(), GUM_ERROR, and gum::HashTableBucket< Key, Val >::next.

Here is the call graph for this function:

◆ bucket()

template<typename Key, typename Val>

INLINE HashTableBucket< Key, Val > * gum::HashTableList< Key, Val >::bucket ( const Key & key ) const

A method to get the bucket corresponding to a given key.

This enables efficient removals of buckets.

Parameters

key	The key of the bucket to return.

Returns: Returns the buckket matching key.

Definition at line 108 of file hashTable_tpl.h.

                                                                                            {
    for (Bucket* ptr = _deb_list_; ptr != nullptr; ptr = ptr->next)
      if (ptr->key() == key) return ptr;
 
    return nullptr;
  }

References _deb_list_.

Referenced by HashTable< Key, Val >.

Here is the caller graph for this function:

◆ clear()

template<typename Key, typename Val>

INLINE void gum::HashTableList< Key, Val >::clear ( )

Removes all the elements of this chained list.

Definition at line 156 of file hashTable_tpl.h.

                                               {
    for (Bucket *next_ptr, *ptr = _deb_list_; ptr != nullptr; ptr = next_ptr) {
      next_ptr = ptr->next;
      delete ptr;
    }
 
    _nb_elements_ = Size(0);
    _deb_list_    = nullptr;
    _end_list_    = nullptr;
  }

References _deb_list_, _end_list_, _nb_elements_, and gum::HashTableBucket< Key, Val >::next.

Referenced by operator=().

Here is the caller graph for this function:

◆ empty()

template<typename Key, typename Val>

INLINE bool gum::HashTableList< Key, Val >::empty ( ) const

noexcept

Returns true if this chained list is empty.

Returns: Returns true if this chained list is empty.

Definition at line 244 of file hashTable_tpl.h.

                                                              {
    return (_nb_elements_ == Size(0));
  }

References _nb_elements_.

◆ erase()

template<typename Key, typename Val>

INLINE void gum::HashTableList< Key, Val >::erase ( Bucket * ptr )

Removes an element from this chained list.

Parameters

ptr	The element to remove.

Definition at line 116 of file hashTable_tpl.h.

                                                                               {
    // check that the pointer is not nullptr
    if (ptr == nullptr) { GUM_ERROR(NullElement, "trying to erase a nullptr bucket") }
 
    // relink properly the doubly chained list
    if (ptr->prev != nullptr) ptr->prev->next = ptr->next;
    else _deb_list_ = ptr->next;
 
    if (ptr->next != nullptr) ptr->next->prev = ptr->prev;
    else _end_list_ = ptr->prev;
 
    // remove the current element from the list
    delete ptr;
 
    --_nb_elements_;
  }

References _deb_list_, _end_list_, _nb_elements_, GUM_ERROR, gum::HashTableBucket< Key, Val >::next, and gum::HashTableBucket< Key, Val >::prev.

◆ exists()

template<typename Key, typename Val>

INLINE bool gum::HashTableList< Key, Val >::exists ( const key_type & key ) const

Returns true if a value with the given key exists.

Checks whether there exists an element with a given key in the list.

Parameters

key	The key to test for existence.

Returns: Returns true if a value with the given key exists.

Definition at line 235 of file hashTable_tpl.h.

                                                                    {
    for (Bucket* ptr = _deb_list_; ptr != nullptr; ptr = ptr->next) {
      if (ptr->key() == key) { return true; }
    }
 
    return false;
  }

References _deb_list_.

◆ insert()

template<typename Key, typename Val>

INLINE void gum::HashTableList< Key, Val >::insert ( Bucket * new_elt )

noexcept

Inserts a new element in the chained list.

The element is inserted at the beginning of the list.

Parameters

new_elt The element to add in the gum::HashTableList.

Definition at line 249 of file hashTable_tpl.h.

                                                                                             {
    // place the bucket at the beginning of the list
    new_elt->prev = nullptr;
    new_elt->next = _deb_list_;
 
    if (_deb_list_ != nullptr) _deb_list_->prev = new_elt;
    else _end_list_ = new_elt;
 
    _deb_list_ = new_elt;
 
    ++_nb_elements_;
  }

References _deb_list_, _end_list_, and _nb_elements_.

◆ operator=() [1/2]

template<typename Key, typename Val>

INLINE HashTableList< Key, Val > & gum::HashTableList< Key, Val >::operator= ( const HashTableList< Key, Val > & from )

Assignment operator.

The new list and that which is copied do not share elements: the new list contains new instances of the keys and values stored in the copied list. Of course, if these values are pointers, the new values point toward the same elements.

If some allocation problem occurs or if copying the Val elements cannot be performed properly, exceptions may be raised. In this case, the function guarantees that no memory leak occurs and that the list is kept in a coherent state (that of an empty list).

Parameters

from	The gum::HashTableList to copy.

Returns: Returns this gum::HashTableList.

Definition at line 169 of file hashTable_tpl.h.

                                                                                 {
    // avoid self assignment
    if (this != &from) {
      clear();
      _copy_(from);
    }
 
    return *this;
  }

References _copy_(), and clear().

Here is the call graph for this function:

◆ operator=() [2/2]

template<typename Key, typename Val>

INLINE HashTableList< Key, Val > & gum::HashTableList< Key, Val >::operator= ( HashTableList< Key, Val > && from )

noexcept

Move operator.

Parameters

from	The gum::HashTableList to copy.

Returns: Returns this gum::HashTableList.

Definition at line 181 of file hashTable_tpl.h.

                                                                                     {
    // avoid self assignment
    if (this != &from) {
      _deb_list_      = from._deb_list_;
      _end_list_      = from._end_list_;
      _nb_elements_   = from._nb_elements_;
      from._deb_list_ = nullptr;
    }
 
    return *this;
  }

References _deb_list_, _end_list_, and _nb_elements_.

◆ operator[]() [1/2]

template<typename Key, typename Val>

INLINE HashTableList< Key, Val >::mapped_type & gum::HashTableList< Key, Val >::operator[] ( const key_type & key )

Returns the value corresponding to a given key.

Parameters

key	The key for which a value is returned.

Returns: Returns the value corresponding to a given key.

Exceptions

NotFound is raised if the element cannot be found

Definition at line 227 of file hashTable_tpl.h.

                                                          {
    for (Bucket* ptr = _deb_list_; ptr != nullptr; ptr = ptr->next)
      if (ptr->key() == key) return ptr->val();
 
    GUM_ERROR(NotFound, "No element with the key <" << key << ">")
  }

References _deb_list_, and GUM_ERROR.

◆ operator[]() [2/2]

template<typename Key, typename Val>

INLINE const HashTableList< Key, Val >::mapped_type & gum::HashTableList< Key, Val >::operator[] ( const key_type & key ) const

Returns the value corresponding to a given key.

Parameters

key	The key for which a value is returned.

Returns: Returns the value corresponding to a given key.

Exceptions

NotFound is raised if the element cannot be found

Definition at line 218 of file hashTable_tpl.h.

                                                                {
    for (Bucket* ptr = _deb_list_; ptr != nullptr; ptr = ptr->next)
      if (ptr->key() == key) return ptr->val();
 
    GUM_ERROR(NotFound, "No element with the key <" << key << ">")
  }

References _deb_list_, and GUM_ERROR.

◆ HashTable< Key, Val >

template<typename Key, typename Val>

friend class HashTable< Key, Val >

friend

Friend for faster access.

Definition at line 481 of file hashTable.h.

References HashTableList(), and bucket().

Referenced by operator<<.

◆ HashTableConstIterator< Key, Val >

template<typename Key, typename Val>

friend class HashTableConstIterator< Key, Val >

friend

Friend for faster access.

Definition at line 481 of file hashTable.h.

◆ HashTableConstIteratorSafe< Key, Val >

template<typename Key, typename Val>

friend class HashTableConstIteratorSafe< Key, Val >

friend

Friend for faster access.

Definition at line 481 of file hashTable.h.

◆ HashTableIterator< Key, Val >

template<typename Key, typename Val>

friend class HashTableIterator< Key, Val >

friend

Friend for faster access.

Definition at line 481 of file hashTable.h.

◆ HashTableIteratorSafe< Key, Val >

template<typename Key, typename Val>

friend class HashTableIteratorSafe< Key, Val >

friend

Friend for faster access.

Definition at line 481 of file hashTable.h.

◆ operator<< [1/4]

template<typename Key, typename Val>

std::ostream & operator<<	(	std::ostream &	s,
		const HashTable< Key *, Val > &	table )

friend

Prints the content of a gum::HashTable with pointers key in the stream.

Definition at line 990 of file hashTable_tpl.h.

                                                                                  {
    bool deja = false;
    stream << "{";
 
    for (Size i = Size(0); i < table._size_; ++i)
      for (auto ptr = table._nodes_[i]._deb_list_; ptr; ptr = ptr->next) {
        if (deja) stream << " , ";
 
        stream << ptr->key() << "=>" << ptr->val();
 
        deja = true;
      }
 
    stream << "}";
 
    return stream;
  }

References gum::HashTable< Key, Val >::_nodes_, and gum::HashTable< Key, Val >::_size_.

◆ operator<< [2/4]

template<typename Key, typename Val>

std::ostream & operator<<	(	std::ostream &	s,
		const HashTable< Key, Val > &	table )

friend

Prints the content of a gum::HashTable in the stream.

Definition at line 971 of file hashTable_tpl.h.

                                                                                 {
    bool deja = false;
    stream << "{";
 
    for (Size i = Size(0); i < table._size_; ++i)
      for (auto ptr = table._nodes_[i]._deb_list_; ptr; ptr = ptr->next) {
        if (deja) stream << " , ";
 
        stream << ptr->key() << "=>" << ptr->val();
 
        deja = true;
      }
 
    stream << "}";
 
    return stream;
  }

References gum::HashTable< Key, Val >::_nodes_, gum::HashTable< Key, Val >::_size_, and HashTable< Key, Val >.

◆ operator<< [3/4]

template<typename Key, typename Val>

std::ostream & operator<<	(	std::ostream &	s,
		const HashTableList< Key *, Val > &	list )

friend

Prints the content of a gum::HashTableList with pointers key in the stream.

Definition at line 954 of file hashTable_tpl.h.

                                                                                     {
    bool deja = false;
    stream << "[";
 
    for (HashTableBucket< Key, Val >* ptr = list._deb_list_; ptr;
         ptr = ptr->list.next, deja = true) {
      if (deja) stream << " , ";
 
      stream << ptr->key() << "=>" << ptr->val();
    }
 
    stream << "]";
 
    return stream;
  }

References HashTableList(), and _deb_list_.

◆ operator<< [4/4]

template<typename Key, typename Val>

std::ostream & operator<<	(	std::ostream &	s,
		const HashTableList< Key, Val > &	list )

friend

Prints the content of a gum::HashTableList in the stream.

Definition at line 937 of file hashTable_tpl.h.

                                                                                    {
    bool deja = false;
    stream << "[";
 
    for (HashTableBucket< Key, Val >* ptr = list._deb_list_; ptr;
         ptr = ptr->list.next, deja = true) {
      if (deja) stream << " , ";
 
      stream << ptr->key() << "=>" << ptr->val();
    }
 
    stream << "]";
 
    return stream;
  }

Member Data Documentation

◆ _deb_list_

template<typename Key, typename Val>

HashTableBucket< Key, Val >* gum::HashTableList< Key, Val >::_deb_list_ {nullptr}

private

A pointer on the first element of the chained list.

Definition at line 500 of file hashTable.h.

500{nullptr};

Referenced by HashTableList(), ~HashTableList(), _copy_(), at(), at(), bucket(), clear(), erase(), exists(), insert(), operator<<, operator=(), operator[](), and operator[]().

◆ _end_list_

template<typename Key, typename Val>

HashTableBucket< Key, Val >* gum::HashTableList< Key, Val >::_end_list_ {nullptr}

private

A pointer on the last element of the chained list.

Definition at line 503 of file hashTable.h.

503{nullptr};

Referenced by _copy_(), clear(), erase(), insert(), and operator=().

◆ _nb_elements_

template<typename Key, typename Val>

Size gum::HashTableList< Key, Val >::_nb_elements_ {Size(0)}

private

The number of elements in the chained list.

Definition at line 506 of file hashTable.h.

506{Size(0)};

Referenced by _copy_(), at(), at(), clear(), empty(), erase(), insert(), and operator=().

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

agrum/base/core/hashTable.h
agrum/base/core/hashTable_tpl.h

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ Bucket

◆ const_pointer

◆ const_reference

◆ key_type

◆ mapped_type

◆ pointer

◆ reference

◆ size_type

◆ value_type

Constructor & Destructor Documentation

◆ HashTableList() [1/3]

◆ HashTableList() [2/3]

◆ HashTableList() [3/3]

◆ ~HashTableList()

Member Function Documentation

◆ _copy_()

◆ at() [1/2]

◆ at() [2/2]

◆ bucket()

◆ clear()

◆ empty()

◆ erase()

◆ exists()

◆ insert()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator[]() [1/2]

◆ operator[]() [2/2]

Friends And Related Symbol Documentation

◆ HashTable< Key, Val >

◆ HashTableConstIterator< Key, Val >

◆ HashTableConstIteratorSafe< Key, Val >

◆ HashTableIterator< Key, Val >

◆ HashTableIteratorSafe< Key, Val >

◆ operator<< [1/4]

◆ operator<< [2/4]

◆ operator<< [3/4]

◆ operator<< [4/4]

Member Data Documentation

◆ _deb_list_

◆ _end_list_

◆ _nb_elements_