gum::List< Val, Alloc > Class Template Reference

Generic doubly linked lists. More...

#include <agrum/tools/core/list.h>

Public Member Functions
template<typename OtherAlloc >
INLINE	List (const List< Val, OtherAlloc > &src)
template<typename OtherAlloc >
INLINE List< Val, Alloc > &	operator= (const List< Val, OtherAlloc > &src)
template<typename... Args>
INLINE ListBucket< Val > *	_createEmplaceBucket_ (Args &&... args) const
template<typename... Args>
INLINE Val &	push_front (Args &&... args)
template<typename... Args>
INLINE Val &	emplaceFront (Args &&... args)
template<typename... Args>
INLINE Val &	push_back (Args &&... args)
template<typename... Args>
INLINE Val &	emplaceBack (Args &&... args)
template<typename... Args>
INLINE Val &	emplace (const const_iterator &iter, Args &&... args)
template<typename... Args>
INLINE Val &	emplace (const const_iterator_safe &iter, Args &&... args)
template<typename OtherAlloc >
INLINE bool	operator== (const List< Val, OtherAlloc > &src) const
template<typename OtherAlloc >
INLINE bool	operator!= (const List< Val, OtherAlloc > &src) const
Constructors / Destructors
	List ()
	A basic constructor that creates an empty list. More...
	List (const List< Val, Alloc > &src)
	Copy constructor. More...
template<typename OtherAlloc >
	List (const List< Val, OtherAlloc > &src)
	Ceneralized copy constructor. More...
	List (List< Val, Alloc > &&src)
	Move constructor. More...
	List (std::initializer_list< Val > list)
	Initializer_list constructor. More...
	~List ()
	Class destructor. More...
Iterators
const const_iterator_safe &	cendSafe () const noexcept
	Returns a safe const iterator pointing to the end of the List. More...
const iterator_safe &	endSafe () noexcept
	Returns a safe iterator pointing to the end of the List. More...
const const_iterator_safe &	crendSafe () const noexcept
	Return a safe const iterator pointing just before the beginning of the List. More...
const iterator_safe &	rendSafe () noexcept
	Returns a safe iterator pointing just before the beginning of the List. More...
const_iterator_safe	cbeginSafe () const
	Returns a safe const iterator pointing to the beginning of the List. More...
iterator_safe	beginSafe ()
	Returns a safe iterator pointing to the beginning of the List. More...
const_iterator_safe	crbeginSafe () const
	Returns a safe const iterator pointing to the last element of the List. More...
iterator_safe	rbeginSafe ()
	Returns a safe iterator pointing to the last element of the List. More...
const const_iterator &	cend () const noexcept
	Returns an unsafe const iterator pointing to the end of the List. More...
const iterator &	end () noexcept
	Returns an unsafe iterator pointing to the end of the List. More...
const const_iterator &	end () const noexcept
	Returns an unsafe const iterator pointing to the end of the List. More...
const const_iterator &	crend () const noexcept
	Returns an unsafe const iterator pointing just before the beginning of the List. More...
const iterator &	rend () noexcept
	Returns an unsafe iterator pointing just before the beginning of the List. More...
const const_iterator &	rend () const noexcept
	Returns an unsafe const iterator pointing just before the beginning of the List. More...
const_iterator	cbegin () const
	Returns an unsafe const iterator pointing to the beginning of the List. More...
iterator	begin ()
	Returns an unsafe iterator pointing to the beginning of the List. More...
const_iterator	begin () const
	Returns an unsafe const iterator pointing to the beginning of the List. More...
const_iterator	crbegin () const
	Returns an unsafe const iterator pointing to the last element of the List. More...
iterator	rbegin ()
	Returns an unsafe iterator pointing to the last element of the List. More...
const_iterator	rbegin () const
	Returns an unsafe const iterator pointing to the last element of the List. More...
Accessors / Modifiers
Val &	pushFront (const Val &val)
	Inserts a new element (a copy) at the beginning of the chained list. More...
Val &	pushFront (Val &&val)
	Inserts a new element (a move) at the beginning of the chained list. More...
template<typename... Args>
Val &	push_front (Args &&... args)
	An alias for pushFront used for STL compliance. More...
template<typename... Args>
Val &	emplaceFront (Args &&... args)
	Emplace elements at the beginning of the chained list. More...
Val &	pushBack (const Val &val)
	Inserts a new element (a copy) at the end of the chained list. More...
Val &	pushBack (Val &&val)
	Inserts a new element (a move) at the end of the chained list. More...
template<typename... Args>
Val &	push_back (Args &&... args)
	An alias for pushBack used for STL compliance. More...
template<typename... Args>
Val &	emplaceBack (Args &&... args)
	Emplace elements at the end of the chained list. More...
Val &	insert (const Val &val)
	Inserts a new element at the end of the chained list (alias of pushBack). More...
Val &	insert (Val &&val)
	Inserts a new element at the end of the chained list (alias of pushBack). More...
Val &	insert (Size pos, const Val &val)
	Inserts a new element at the ith pos of the chained list. More...
Val &	insert (Size pos, Val &&val)
	Insert an rvalue at the ith pos of the chained list. More...
Val &	insert (const const_iterator_safe &iter, const Val &val, location place=location::BEFORE)
	Inserts a new element before or after a given iterator. More...
Val &	insert (const const_iterator_safe &iter, Val &&val, location place=location::BEFORE)
	Inserts an rvalue before or after a given iterator. More...
Val &	insert (const const_iterator &iter, const Val &val, location place=location::BEFORE)
	Inserts a new element before or after a given iterator. More...
Val &	insert (const const_iterator &iter, Val &&val, location place=location::BEFORE)
	Inserts an rvalue before or after a given iterator. More...
template<typename... Args>
Val &	emplace (const const_iterator &iter, Args &&... args)
	Emplace a new element before a given iterator. More...
template<typename... Args>
Val &	emplace (const const_iterator_safe &iter, Args &&... args)
	Emplace a new element before a given safe iterator. More...
Val &	front () const
	Returns a reference to first element of a list, if any. More...
Val &	back () const
	Returns a reference to last element of a list, if any. More...
Size	size () const noexcept
	Returns the number of elements in the list. More...
bool	exists (const Val &val) const
	Checks whether there exists a given element in the list. More...
void	erase (Size i)
	Erases the ith element of the List (the first one is in position 0). More...
void	erase (const iterator_safe &iter)
	Erases the element of the List pointed to by the safe iterator. More...
void	erase (const const_iterator_safe &iter)
	Erases the element of the List pointed to by the safe const iterator. More...
void	eraseByVal (const Val &val)
	erases the first element encountered with a given value. More...
void	eraseAllVal (const Val &val)
	erases all the elements encountered with a given value More...
void	popBack ()
	Removes the last element of a List, if any. More...
void	popFront ()
	Removes the first element of a List, if any. More...
void	clear ()
	Deletes all the elements of a chained list. More...
bool	empty () const noexcept
	Returns a boolean indicating whether the chained list is empty. More...
void	swap (List &other_list)
	Swap the current list with another one. More...
std::string	toString () const
	Converts a list into a string. More...
template<typename Mount , typename OtherAlloc = std::allocator< Mount >>
List< Mount, OtherAlloc >	map (Mount(*f)(Val)) const
	Creates a list of mountains from a list of val. More...
template<typename Mount , typename OtherAlloc = std::allocator< Mount >>
List< Mount, OtherAlloc >	map (Mount(*f)(Val &)) const
	Creates a list of mountains from a list of val. More...
template<typename Mount , typename OtherAlloc = std::allocator< Mount >>
List< Mount, OtherAlloc >	map (Mount(*f)(const Val &)) const
	Creates a list of mountains from a list of val. More...
template<typename Mount , typename OtherAlloc = std::allocator< Mount >>
List< Mount, OtherAlloc >	map (const Mount &mount) const
	Creates a list of mountains with a given value from a list of val. More...
Operators
List< Val, Alloc > &	operator= (const List< Val, Alloc > &src)
	Copy operator. More...
template<typename OtherAlloc >
List< Val, Alloc > &	operator= (const List< Val, OtherAlloc > &src)
	Generalized copy operator. More...
List< Val, Alloc > &	operator= (List< Val, Alloc > &&src)
	Move operator. More...
Val &	operator+= (const Val &val)
	Inserts a new element at the end of the list (alias of pushBack). More...
Val &	operator+= (Val &&val)
	Inserts a new element at the end of the list (alias of pushBack). More...
template<typename OtherAlloc >
bool	operator== (const List< Val, OtherAlloc > &src) const
	Checks whether two lists are identical (same elements in the same order). More...
template<typename OtherAlloc >
bool	operator!= (const List< Val, OtherAlloc > &src) const
	Checks whether two lists are different (different elements or orders). More...
Val &	operator[] (const Size i)
	Returns the ith element in the current chained list. More...
const Val &	operator[] (const Size i) const
	Returns the const ith element in the current chained list. More...

Public Types
enum	location { location::BEFORE, location::AFTER }
	Locations around iterators where insertions of new elements can take / place. More...
using	BucketAllocator = typename Alloc::template rebind< ListBucket< Val > >::other
	Type of the allocator for ListBuckets. More...
using	value_type = Val
	Types for STL compliance. More...
using	reference = Val &
	Types for STL compliance. More...
using	const_reference = const Val &
	Types for STL compliance. More...
using	pointer = Val *
	Types for STL compliance. More...
using	const_pointer = const Val *
	Types for STL compliance. More...
using	size_type = Size
	Types for STL compliance. More...
using	difference_type = std::ptrdiff_t
	Types for STL compliance. More...
using	allocator_type = Alloc
	Types for STL compliance. More...
using	iterator = ListIterator< Val >
	Types for STL compliance. More...
using	const_iterator = ListConstIterator< Val >
	Types for STL compliance. More...
using	iterator_safe = ListIteratorSafe< Val >
	Types for STL compliance. More...
using	const_iterator_safe = ListConstIteratorSafe< Val >
	Types for STL compliance. More...

Friends
class	ListIterator< Val >
	ListIterator should be a friend to optimize access to elements. More...
class	ListConstIterator< Val >
	ListIterator should be a friend to optimize access to elements. More...
class	ListIteratorSafe< Val >
	ListIterator should be a friend to optimize access to elements. More...
class	ListConstIteratorSafe< Val >
	ListIterator should be a friend to optimize access to elements. More...

Detailed Description

template<typename Val, typename Alloc = std::allocator< Val >>
class gum::List< Val, Alloc >

Generic doubly linked lists.

List enables fast and safe manipulation of chained lists. Unless the elements are rvalues, the insertions of new elements into the lists are ALWAYS performed by copy, i.e., each time we add a new element X to the List, a copy of X is actually created and this very copy is stored into the list. For rvalues, move operations are performed.

The List iterators are implemented so as to avoid segmentation faults when elements of the list are deleted while some safe iterators are pointing on them. Moreover they ensure that, when elements are removed from a List, iterators on that list will never access these elements (which is not the case for the iterators in the C++ standard library). Note that this guarantee is ensured at low cost as experimental results show that List and ListIterator are as efficient as their STL counterparts. However, this guarantee can hold only if List is aware of all of the iterators pointing to it: thus, when List erases one element, it can parse the list of its iterators and update those that point toward the now deleted element. When parsing elements without removing any element, you can use unsafe iterators instead of safe ones because they are slightly faster. But those will most certainly segfault if they perform some operations on deleted elements.

Usage example:

// creation of an empty list
List<int> list1;
List<int> list2 { 3, 4, 5 }; // initializer list

// adding elements to the list
list1.pushFront (23);
list1.pushBack (10);
list1 += 25;
list1.insert (12);

// getting the second element of the list
cerr << "10 = " << list1[1] << endl;

// getting the first and last elements
cerr << "first = " << list1.front() << " last = " << list1.back() << endl;

// get the number of elements in the list
cerr << "number of elements = " << list1.size () << endl;

// display the content of the list
cerr << list1 << endl;

// copy the list
List<int> list2 = list1, list3;
list3 = list1;

// delete the second element from the list
list1.erase (1);

// delete the first and last elements
list1.popFront ();
list1.popBack ();

// delete element whose value is 25
list1.eraseByVal (25);

// check whether the list is empty
if (list1.empty()) cerr << "empty list" << endl;

// remove all elements from the list
list1.clear ();

// parse all the elements of a list using unsafe iterators
for (List<int>::iterator iter = list2.begin();
     iter != list2.end(); ++iter)
  cerr << *iter << endl;
for (List<int>::iterator iter = list2.rbegin();
     iter != list2.rend(); --iter)
  cerr << *iter << endl;
for (List<int>::const_iterator iter = list2.cbegin();
     iter != list2.cend(); ++iter)
  cerr << *iter << endl;
for (List<int>::const_iterator iter = list2.crbegin();
     iter != list2.crend(); --iter)
  cerr << *iter << endl;

// parse all the elements of a list using safe iterators
for (List<int>::iterator_safe iter = list2.beginSafe();
     iter != list2.endSafe(); ++iter)
  cerr << *iter << endl;
for (List<int>::iterator_safe iter = list2.rbeginSafe();
     iter != list2.rendSafe(); --iter)
  cerr << *iter << endl;
for (List<int>::const_iterator_safe iter = list2.cbeginSafe();
     iter != list2.cendSafe(); ++iter)
  cerr << *iter << endl;
for (List<int>::const_iterator_safe iter = list2.crbeginSafe();
     iter != list2.crendSafe(); --iter)
  cerr << *iter << endl;

// use an iterator to point the element we wish to erase
List<int>::iterator_safe iter = list2.beginSafe();
List2.erase ( iter );
List<int>::iterator iter2 = list2.begin() + 4; // 5th element of the list
iter2 = iter + 4;

// map a list into another list (assuming function f is defined as
// float f (int x) { return (2.5 * x); } )
List<float> flist = list2.map (f);

Template Parameters

Val	The values type stored in the gum::List.
Alloc	The allocator for the values stored in the gum::List.

Definition at line 372 of file list.h.

Member Typedef Documentation

allocator_type

template<typename Val, typename Alloc = std::allocator< Val >>

using gum::List< Val, Alloc >::allocator_type = Alloc

Types for STL compliance.

Definition at line 383 of file list.h.

BucketAllocator

template<typename Val, typename Alloc = std::allocator< Val >>

using gum::List< Val, Alloc >::BucketAllocator = typename Alloc::template rebind< ListBucket< Val > >::other

Type of the allocator for ListBuckets.

Definition at line 391 of file list.h.

const_iterator

template<typename Val, typename Alloc = std::allocator< Val >>

using gum::List< Val, Alloc >::const_iterator = ListConstIterator< Val >

Types for STL compliance.

Definition at line 385 of file list.h.

const_iterator_safe

template<typename Val, typename Alloc = std::allocator< Val >>

using gum::List< Val, Alloc >::const_iterator_safe = ListConstIteratorSafe< Val >

Types for STL compliance.

Definition at line 387 of file list.h.

const_pointer

template<typename Val, typename Alloc = std::allocator< Val >>

using gum::List< Val, Alloc >::const_pointer = const Val*

Types for STL compliance.

Definition at line 380 of file list.h.

const_reference

template<typename Val, typename Alloc = std::allocator< Val >>

using gum::List< Val, Alloc >::const_reference = const Val&

Types for STL compliance.

Definition at line 378 of file list.h.

difference_type

template<typename Val, typename Alloc = std::allocator< Val >>

using gum::List< Val, Alloc >::difference_type = std::ptrdiff_t

Types for STL compliance.

Definition at line 382 of file list.h.

iterator

template<typename Val, typename Alloc = std::allocator< Val >>

using gum::List< Val, Alloc >::iterator = ListIterator< Val >

Types for STL compliance.

Definition at line 384 of file list.h.

iterator_safe

template<typename Val, typename Alloc = std::allocator< Val >>

using gum::List< Val, Alloc >::iterator_safe = ListIteratorSafe< Val >

Types for STL compliance.

Definition at line 386 of file list.h.

pointer

template<typename Val, typename Alloc = std::allocator< Val >>

using gum::List< Val, Alloc >::pointer = Val*

Types for STL compliance.

Definition at line 379 of file list.h.

reference

template<typename Val, typename Alloc = std::allocator< Val >>

using gum::List< Val, Alloc >::reference = Val&

Types for STL compliance.

Definition at line 377 of file list.h.

size_type

template<typename Val, typename Alloc = std::allocator< Val >>

using gum::List< Val, Alloc >::size_type = Size

Types for STL compliance.

Definition at line 381 of file list.h.

value_type

template<typename Val, typename Alloc = std::allocator< Val >>

using gum::List< Val, Alloc >::value_type = Val

Types for STL compliance.

Definition at line 376 of file list.h.

Member Enumeration Documentation

location

template<typename Val, typename Alloc = std::allocator< Val >>

enum gum::List::location

strong

Locations around iterators where insertions of new elements can take / place.

Enumerator
BEFORE
AFTER

Definition at line 395 of file list.h.

    {
      BEFORE,
      AFTER
    };

Constructor & Destructor Documentation

List() [1/6]

template<typename Val , typename Alloc >

INLINE gum::List< Val, Alloc >::List

(

)

A basic constructor that creates an empty list.

Definition at line 1141 of file list_tpl.h.

                                  {
    // for debugging purposes
    GUM_CONSTRUCTOR(List);

    // reserve space for only the default number of iterators
    _safe_iterators_.reserve(GUM_DEFAULT_ITERATOR_NUMBER);
  }

List() [2/6]

template<typename Val, typename Alloc>

INLINE gum::List< Val, Alloc >::List

(

const List< Val, Alloc > &

src

)

Copy constructor.

The new list and that which is copied do not share their elements: the new list contains new instances of the values stored in the list to be copied. Of course if these values are pointers, the new values point toward the same elements. This constructor runs in linear time.

Parameters

src	the list the contents of which is copied into the current one.

Definition at line 1151 of file list_tpl.h.

                                                               {
    // for debugging purposes
    GUM_CONS_CPY(List);

    // copy the elements
    _copy_elements_(src);

    // reserve space for only the default number of iterators
    _safe_iterators_.reserve(GUM_DEFAULT_ITERATOR_NUMBER);
  }

List() [3/6]

template<typename Val, typename Alloc = std::allocator< Val >>

template<typename OtherAlloc >

gum::List< Val, Alloc >::List

(

const List< Val, OtherAlloc > &

src

)

Ceneralized copy constructor.

The new list and that which is copied do not share their elements: the new list contains new instances of the values stored in the list to be copied. Of course if these values are pointers, the new values point toward the same elements. This constructor runs in linear time.

Parameters

src	the list the contents of which is copied into the current one.

Template Parameters

OtherAlloc

The other allocator.

List() [4/6]

template<typename Val, typename Alloc>

INLINE gum::List< Val, Alloc >::List

(

List< Val, Alloc > &&

src

)

Move constructor.

Parameters

src	The gum::List to move.

Definition at line 1178 of file list_tpl.h.

                                                          :
      _deb_list_{std::move(src._deb_list_)}, _end_list_{std::move(src._end_list_)},
      _nb_elements_{std::move(src._nb_elements_)},
      _safe_iterators_{std::move(src._safe_iterators_)}, _alloc_bucket_{
                                                            std::move(src._alloc_bucket_)} {
    // for debugging purposes
    GUM_CONS_MOV(List);

    src._deb_list_    = nullptr;
    src._end_list_    = nullptr;
    src._nb_elements_ = 0;
    src._safe_iterators_.clear();
  }

List() [5/6]

template<typename Val, typename Alloc>

INLINE gum::List< Val, Alloc >::List

(

std::initializer_list< Val >

list

)

Initializer_list constructor.

Parameters

list	The initializer list.

Definition at line 1194 of file list_tpl.h.

                                                                 {
    // for debugging purposes
    GUM_CONSTRUCTOR(List);

    // adding all the elements
    for (const auto& val: list) {
      pushBack(val);
    }

    // reserve space for only the default number of iterators
    _safe_iterators_.reserve(GUM_DEFAULT_ITERATOR_NUMBER);
  }

~List()

template<typename Val , typename Alloc >

INLINE gum::List< Val, Alloc >::~List

(

)

Class destructor.

Definition at line 1209 of file list_tpl.h.

                                   {
    // for debugging (although this program is bug-free)
    GUM_DESTRUCTOR(List);

    // we detach all the safe iterators attached to the current List and we
    // remove all the elements from the list
    clear();
  }

List() [6/6]

template<typename Val, typename Alloc = std::allocator< Val >>

template<typename OtherAlloc >

INLINE gum::List< Val, Alloc >::List

(

const List< Val, OtherAlloc > &

src

)

Definition at line 1165 of file list_tpl.h.

                                                                    {
    // for debugging purposes
    GUM_CONS_CPY(List);

    // copy the elements
    _copy_elements_(src);

    // reserve space for only the default number of iterators
    _safe_iterators_.reserve(GUM_DEFAULT_ITERATOR_NUMBER);
  }

Member Function Documentation

_copy_elements_()

template<typename Val, typename Alloc >

template<typename OtherAlloc >

void gum::List< Val, Alloc >::_copy_elements_ ( const List< Val, OtherAlloc > &  src )

private

A function used to perform copies of elements of Lists.

Before performing the copy, we assume in this function that the current list (this) is empty (else there would be memory leak).

Template Parameters

OtherAlloc

The other allocator.

Parameters

src	The gum::List to copy.

Definition at line 1071 of file list_tpl.h.

                                                                             {
    ListBucket< Val >* ptr;
    ListBucket< Val >* old_ptr = nullptr;
    ListBucket< Val >* new_elt = nullptr;

    // copy src's list
    try {
      for (ptr = src._deb_list_; ptr != nullptr; ptr = ptr->_next_) {
        // create a copy bucket
        new_elt = _alloc_bucket_.allocate(1);

        try {
          _alloc_bucket_.construct(new_elt, *ptr);
        } catch (...) {
          _alloc_bucket_.deallocate(new_elt, 1);
          throw;
        }

        // rechain properly the new list (the next field is already initialized
        // with nullptr)
        new_elt->_prev_ = old_ptr;

        if (old_ptr)
          old_ptr->_next_ = new_elt;
        else
          _deb_list_ = new_elt;

        old_ptr = 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_ = const_cast< ListBucket< Val >* >(ptr)) {
        ptr = _deb_list_->_next_;
        _alloc_bucket_.destroy(_deb_list_);
        _alloc_bucket_.deallocate(_deb_list_, 1);
      }

      _deb_list_ = nullptr;
      throw;
    }

    // update properly the end of the chained list and the number of elements
    _end_list_    = old_ptr;
    _nb_elements_ = src._nb_elements_;
  }

_createBucket_() [1/2]

template<typename Val, typename Alloc >

INLINE ListBucket< Val > * gum::List< Val, Alloc >::_createBucket_ ( const Val &  val ) const

private

Create a new bucket with a given value.

Parameters

val	The value of the new bucket.

Returns

Returns the bucket holding val.

Definition at line 1419 of file list_tpl.h.

                                                                                   {
    // create a new bucket (catch allocation and construction exceptions)
    ListBucket< Val >* new_elt = _alloc_bucket_.allocate(1);

    try {
      _alloc_bucket_.construct(new_elt, val);
    } catch (...) {
      _alloc_bucket_.deallocate(new_elt, 1);
      throw;
    }

    return new_elt;
  }

_createBucket_() [2/2]

template<typename Val, typename Alloc >

INLINE ListBucket< Val > * gum::List< Val, Alloc >::_createBucket_ ( Val &&  val ) const

private

Create a new bucket with a given value.

Parameters

val	The value of the new bucket.

Returns

Returns the bucket holding val.

Definition at line 1435 of file list_tpl.h.

                                                                              {
    // create a new bucket (catch allocation and construction exceptions)
    ListBucket< Val >* new_elt = _alloc_bucket_.allocate(1);

    try {
      _alloc_bucket_.construct(new_elt, std::move(val));
    } catch (...) {
      _alloc_bucket_.deallocate(new_elt, 1);
      throw;
    }

    return new_elt;
  }

_createEmplaceBucket_() [1/2]

template<typename Val, typename Alloc = std::allocator< Val >>

template<typename... Args>

ListBucket< Val >* gum::List< Val, Alloc >::_createEmplaceBucket_ ( Args &&...  args ) const

private

Create an emplace bucket.

Template Parameters

Args	The emplace arguments types.

Parameters

args	The emplace arguments.

Returns

Returns the bucket holding the new value.

_createEmplaceBucket_() [2/2]

template<typename Val, typename Alloc = std::allocator< Val >>

template<typename... Args>

INLINE ListBucket< Val >* gum::List< Val, Alloc >::_createEmplaceBucket_

(

Args &&...

args

)

const

Definition at line 1452 of file list_tpl.h.

                                                                                          {
    // create a new bucket (catch allocation and construction exceptions)
    ListBucket< Val >* new_elt = _alloc_bucket_.allocate(1);

    try {
      _alloc_bucket_.construct(new_elt,
                               ListBucket< Val >::Emplace::EMPLACE,
                               std::forward< Args >(args)...);
    } catch (...) {
      _alloc_bucket_.deallocate(new_elt, 1);
      throw;
    }

    return new_elt;
  }

_erase_()

template<typename Val, typename Alloc >

INLINE void gum::List< Val, Alloc >::_erase_ ( ListBucket< Val > *  bucket )

private

Removes an element from a chained list.

If parameter bucket is equal to 0, then the method does not perform anything, else the bucket is deleted. In the latter case, no test is ever performed to check that the bucket does actually belong to the List. The method runs in constant time.

Parameters

bucket

A pointer on the bucket in the chained list we wish to remove.

Definition at line 1794 of file list_tpl.h.

                                                                   {
    // perform deletion only if there is a bucket to remove
    if (bucket != nullptr) {
      // update the iterators pointing on this element
      for (const auto ptr_iter: _safe_iterators_) {
        if (ptr_iter->_bucket_ == bucket) {
          ptr_iter->_next_current_bucket_ = bucket->_prev_;
          ptr_iter->_prev_current_bucket_ = bucket->_next_;
          ptr_iter->_bucket_              = nullptr;
          ptr_iter->_null_pointing_       = true;
        } else {
          if (ptr_iter->_null_pointing_) {
            if (ptr_iter->_next_current_bucket_ == bucket)
              ptr_iter->_next_current_bucket_ = bucket->_prev_;

            if (ptr_iter->_prev_current_bucket_ == bucket)
              ptr_iter->_prev_current_bucket_ = bucket->_next_;
          }
        }
      }

      // set properly the begin and end of the chained list (the other chainings
      // will be performed by operator delete)
      if (bucket->_prev_ == nullptr)
        _deb_list_ = bucket->_next_;
      else
        bucket->_prev_->_next_ = bucket->_next_;

      if (bucket->_next_ == nullptr)
        _end_list_ = bucket->_prev_;
      else
        bucket->_next_->_prev_ = bucket->_prev_;

      // remove the current element src the list
      _alloc_bucket_.destroy(bucket);
      _alloc_bucket_.deallocate(bucket, 1);

      --_nb_elements_;
    }
  }

_getBucket_()

template<typename Val, typename Alloc >

INLINE ListBucket< Val > * gum::List< Val, Alloc >::_getBucket_ ( const Val &  val ) const

privatenoexcept

Returns the bucket corresponding to a given value.

Actually, this is the first bucket of value val encountered in the list, if any, that is returned. If the element cannot be found, 0 is returned. This method enables fast removals of buckets. It runs in linear time.

Comparisons between Val instances are performed through == operators.

Parameters

val	The value of the element the bucket of which we wish to return.

Returns

Returns the bucket corresponding to a given value.

Definition at line 1858 of file list_tpl.h.

                                                                                         {
    for (ListBucket< Val >* ptr = _deb_list_; ptr != nullptr; ptr = ptr->_next_)
      if (ptr->_val_ == val) return ptr;

    return nullptr;
  }

_getIthBucket_()

template<typename Val , typename Alloc >

INLINE ListBucket< Val > * gum::List< Val, Alloc >::_getIthBucket_ ( Size  i ) const

privatenoexcept

Returns the bucket corresponding to the ith position in the list.

This method assumes that the list contains at least i+1 elements. The index of the first element of the list is 0.

Parameters

i	The position of the returned element.

Returns

Returns the gum::ListBucket of the ith element.

Definition at line 1574 of file list_tpl.h.

                                                                                    {
    ListBucket< Val >* ptr;

    if (i < _nb_elements_ / 2) {
      for (ptr = _deb_list_; i; --i, ptr = ptr->_next_) {}
    } else {
      for (ptr = _end_list_, i = _nb_elements_ - i - 1; i; --i, ptr = ptr->_prev_) {}
    }

    return ptr;
  }

_insert_() [1/2]

template<typename Val, typename Alloc >

INLINE Val & gum::List< Val, Alloc >::_insert_ ( const const_iterator_safe &  iter, ListBucket< Val > *  new_elt, location  place  )

private

Inserts a new bucket before or after the location pointed to by an iterator.

Parameters

iter	An iterator pointing where to insert a new element.
new_elt	The new element ot insert in the gum::List.
place	Where to insert the new element relatively to the iterator.

Returns

Returns a reference over the value stored in the gum::List.

Definition at line 1647 of file list_tpl.h.

                                                                             {
    // find the location around which the new element should be inserted
    ListBucket< Val >* ptr;

    if (iter._null_pointing_) {
      if (place == location::BEFORE) {
        ptr = iter._next_current_bucket_;
      } else {
        ptr = iter._prev_current_bucket_;
      }
    } else {
      ptr = iter._getBucket_();
    }

    if (ptr == nullptr) {
      // here, we are at the end of the list
      return _pushBack_(new_elt);
    } else {
      switch (place) {
        case location::BEFORE:
          return _insertBefore_(new_elt, ptr);

        case location::AFTER:
          return _insertAfter_(new_elt, ptr);

        default:
          GUM_ERROR(FatalError, "List insertion for this location unimplemented")
      }
    }
  }

_insert_() [2/2]

template<typename Val, typename Alloc >

INLINE Val & gum::List< Val, Alloc >::_insert_ ( const const_iterator &  iter, ListBucket< Val > *  new_elt, location  place  )

private

Inserts a new bucket before or after the location pointed to by an iterator.

Parameters

iter	An iterator pointing where to insert a new element.
new_elt	The new element ot insert in the gum::List.
place	Where to insert the new element relatively to the iterator.

Returns

Returns a reference over the value stored in the gum::List.

Definition at line 1683 of file list_tpl.h.

                                                                        {
    // find the location around which the new element should be inserted
    ListBucket< Val >* ptr = iter._getBucket_();

    if (ptr == nullptr) {
      // here, we are at the end of the list
      return _pushBack_(new_elt);
    } else {
      switch (place) {
        case location::BEFORE:
          return _insertBefore_(new_elt, ptr);

        case location::AFTER:
          return _insertAfter_(new_elt, ptr);

        default:
          GUM_ERROR(FatalError, "List insertion for this location unimplemented")
      }
    }
  }

_insertAfter_()

template<typename Val, typename Alloc >

INLINE Val & gum::List< Val, Alloc >::_insertAfter_ ( ListBucket< Val > *  new_elt, ListBucket< Val > *  current_elt  )

private

Insert a new bucket after another one.

Parameters

new_elt	The new element to insert in the gum::List.
current_elt	The element before which new_elt will be inserted.

Returns

Returns a reference over the value stored in the gum::List.

Definition at line 1608 of file list_tpl.h.

                                                                                {
    new_elt->_prev_     = current_elt;
    new_elt->_next_     = current_elt->_next_;
    current_elt->_next_ = new_elt;

    if (new_elt->_next_ == nullptr)
      _end_list_ = new_elt;
    else
      new_elt->_next_->_prev_ = new_elt;

    // update the number of elements
    ++_nb_elements_;

    // returns the current value
    return new_elt->_val_;
  }

_insertBefore_()

template<typename Val, typename Alloc >

INLINE Val & gum::List< Val, Alloc >::_insertBefore_ ( ListBucket< Val > *  new_elt, ListBucket< Val > *  current_elt  )

private

Insert a new bucket before another one.

Parameters

new_elt	The new element to insert in the gum::List.
current_elt	The element before which new_elt will be inserted.

Returns

Returns a reference over the value stored in the gum::List.

Definition at line 1588 of file list_tpl.h.

                                                                                 {
    new_elt->_next_     = current_elt;
    new_elt->_prev_     = current_elt->_prev_;
    current_elt->_prev_ = new_elt;

    if (new_elt->_prev_ == nullptr)
      _deb_list_ = new_elt;
    else
      new_elt->_prev_->_next_ = new_elt;

    // update the number of elements
    ++_nb_elements_;

    // returns the current value
    return new_elt->_val_;
  }

_pushBack_()

template<typename Val, typename Alloc >

INLINE Val & gum::List< Val, Alloc >::_pushBack_ ( ListBucket< Val > *  new_elt )

private

Insert a bucket at the end of the list.

Parameters

new_elt

The new element pushed at the end of the gum::List.

Returns

Returns a refefence over the value stored in the gum::List.

Definition at line 1489 of file list_tpl.h.

                                                                       {
    // place the bucket at the end of the list
    new_elt->_prev_ = _end_list_;

    if (_end_list_ != nullptr)
      _end_list_->_next_ = new_elt;
    else
      _deb_list_ = new_elt;

    _end_list_ = new_elt;

    // update the number of elements
    ++_nb_elements_;

    // returns the current value
    return new_elt->_val_;
  }

_pushFront_()

template<typename Val, typename Alloc >

INLINE Val & gum::List< Val, Alloc >::_pushFront_ ( ListBucket< Val > *  new_elt )

private

Insert a bucket at the front of the list.

Parameters

new_elt

The new element pushed at the front of the gum::List.

Returns

Returns a refefence over the value stored in the gum::List.

Definition at line 1470 of file list_tpl.h.

                                                                        {
    new_elt->_next_ = _deb_list_;

    if (_deb_list_ != nullptr)
      _deb_list_->_prev_ = new_elt;
    else
      _end_list_ = new_elt;

    _deb_list_ = new_elt;

    // update the number of elements
    ++_nb_elements_;

    // return the inserted element
    return new_elt->_val_;
  }

back()

template<typename Val , typename Alloc >

INLINE Val & gum::List< Val, Alloc >::back

(

)

const

Returns a reference to last element of a list, if any.

Exceptions

NotFound

exception is thrown if the list is empty.

Definition at line 1771 of file list_tpl.h.

                                             {
    if (_nb_elements_ == Size(0)) { GUM_ERROR(NotFound, "not enough elements in the chained list") }

    return _end_list_->_val_;
  }

begin() [1/2]

template<typename Val , typename Alloc >

INLINE ListIterator< Val > gum::List< Val, Alloc >::begin

(

)

Returns an unsafe iterator pointing to the beginning of the List.

Unsafe iterators are a little bit faster than safe iterators and they consume less memory. However, if the element they point to is erased, their dereference or their increment/decrement will produce a mess, probably a segfault. You should use them only when performance is an issue and if you are sure that they will never point to an element erased.

Returns

Returns an unsafe iterator pointing to the beginning of the List.

Definition at line 1362 of file list_tpl.h.

                                                       {
    return ListIterator< Val >{*this};
  }

begin() [2/2]

template<typename Val , typename Alloc >

INLINE ListConstIterator< Val > gum::List< Val, Alloc >::begin

(

)

const

Returns an unsafe const iterator pointing to the beginning of the List.

Unsafe const iterators are a little bit faster than safe const iterators and they consume less memory. However, if the element they point to is erased, their dereference or their increment/decrement will produce a mess, probably a segfault. You should use them only when performance is an issue and if you are sure that they will never point to an element erased.

Returns an unsafe const iterator pointing to the beginning of the List.

Definition at line 1368 of file list_tpl.h.

                                                                  {
    return ListConstIterator< Val >{*this};
  }

beginSafe()

template<typename Val , typename Alloc >

INLINE ListIteratorSafe< Val > gum::List< Val, Alloc >::beginSafe

(

)

Returns a safe iterator pointing to the beginning of the List.

Safe iterators are iterators whose state is updated by the list when the element they point to is erased. As such, in this case, they can throw an exception when we try to derefence them and they are able to perform a valid ++ or – step.

Returns

Returns a safe iterator pointing to the beginning of the List.

Definition at line 1350 of file list_tpl.h.

                                                               {
    return ListIteratorSafe< Val >{*this};
  }

cbegin()

template<typename Val , typename Alloc >

INLINE ListConstIterator< Val > gum::List< Val, Alloc >::cbegin

(

)

const

Returns an unsafe const iterator pointing to the beginning of the List.

Unsafe const iterators are a little bit faster than safe const iterators and they consume less memory. However, if the element they point to is erased, their dereference or their increment/decrement will produce a mess, probably a segfault. You should use them only when performance is an issue and if you are sure that they will never point to an element erased.

Returns

Returns an unsafe const iterator pointing to the beginning of the List.

Definition at line 1356 of file list_tpl.h.

                                                                   {
    return ListConstIterator< Val >{*this};
  }

cbeginSafe()

template<typename Val , typename Alloc >

INLINE ListConstIteratorSafe< Val > gum::List< Val, Alloc >::cbeginSafe

(

)

const

Returns a safe const iterator pointing to the beginning of the List.

Safe const iterators are const iterators whose state is updated by the list when the element they point to is erased. As such, in this case, they can throw an exception when we try to derefence them and they are able to perform a valid ++ or – step.

Returns

Returns a safe const iterator pointing to the beginning of the List.

Definition at line 1344 of file list_tpl.h.

                                                                           {
    return ListConstIteratorSafe< Val >{*this};
  }

cend()

template<typename Val , typename Alloc >

INLINE const ListConstIterator< Val > & gum::List< Val, Alloc >::cend ( ) const

noexcept

Returns an unsafe const iterator pointing to the end of the List.

Unsafe const iterators are a little bit faster than safe const iterators and they consume less memory. However, if the element they point to is erased, their dereference or their increment/decrement will produce a mess, probably a segfault. You should use them only when performance is an issue and if you are sure that they will never point to an element erased.

Returns an unsafe const iterator pointing to the end of the List.

Definition at line 1296 of file list_tpl.h.

                                                                                 {
    return *(reinterpret_cast< const ListConstIterator< Val >* >(_list_end_));
  }

cendSafe()

template<typename Val , typename Alloc >

INLINE const ListConstIteratorSafe< Val > & gum::List< Val, Alloc >::cendSafe ( ) const

noexcept

Returns a safe const iterator pointing to the end of the List.

Safe const iterators are const iterators whose state is updated by the list when the element they point to is erased. As such, in this case, they can throw an exception when we try to derefence them and they are able to perform a valid ++ or – step

Returns a safe const iterator pointing to the end of the List.

Definition at line 1284 of file list_tpl.h.

                                                                                         {
    return *(reinterpret_cast< const ListConstIteratorSafe< Val >* >(_list_end_safe_));
  }

clear()

template<typename Val , typename Alloc >

void gum::List< Val, Alloc >::clear

(

)

Deletes all the elements of a chained list.

All the iterators of the list will be resetted to rend. The method runs in linear time of both the size of the list and the number of iterators attached to the List.

Definition at line 1120 of file list_tpl.h.

                                 {
    // first we update all the safe iterators of the list : they should now
    // point to end/rend
    for (const auto ptr_iter: _safe_iterators_) {
      ptr_iter->clear();
    }

    // clear all the values
    for (ListBucket< Val >*ptr = _deb_list_, *next_ptr = nullptr; ptr != nullptr; ptr = next_ptr) {
      next_ptr = ptr->_next_;
      _alloc_bucket_.destroy(ptr);
      _alloc_bucket_.deallocate(ptr, 1);
    }

    _nb_elements_ = 0;
    _deb_list_    = nullptr;
    _end_list_    = nullptr;
  }

crbegin()

template<typename Val , typename Alloc >

INLINE ListConstIterator< Val > gum::List< Val, Alloc >::crbegin

(

)

const

Returns an unsafe const iterator pointing to the last element of the List.

Unsafe iterators are a little bit faster than safe iterators and they consume less memory. However, if the element they point to is erased, their dereference or their increment/decrement will produce a mess, probably a segfault. You should use them only when performance is an issue and if you are sure that they will never point to an element erased.

Returns

Returns an unsafe const iterator pointing to the last element of the List.

Definition at line 1392 of file list_tpl.h.

                                                                    {
    if (_nb_elements_)
      return ListConstIterator< Val >{*this, _nb_elements_ - 1};
    else
      return ListConstIterator< Val >{};
  }

crbeginSafe()

template<typename Val , typename Alloc >

INLINE ListConstIteratorSafe< Val > gum::List< Val, Alloc >::crbeginSafe

(

)

const

Returns a safe const iterator pointing to the last element of the List.

Safe const iterators are const iterators whose state is updated by the list when the element they point to is erased. As such, in this case, they can throw an exception when we try to derefence them and they are able to perform a valid ++ or – step.

Returns

Returns a safe const iterator pointing to the last element of the List.

Definition at line 1374 of file list_tpl.h.

                                                                            {
    if (_nb_elements_)
      return ListConstIteratorSafe< Val >{*this, _nb_elements_ - 1};
    else
      return ListConstIteratorSafe< Val >{};
  }

crend()

template<typename Val , typename Alloc >

INLINE const ListConstIterator< Val > & gum::List< Val, Alloc >::crend ( ) const

noexcept

Returns an unsafe const iterator pointing just before the beginning of the List.

Unsafe const iterators are a little bit faster than safe const iterators and they consume less memory. However, if the element they point to is erased, their dereference or their increment/decrement will produce a mess, probably a segfault. You should use them only when performance is an issue and if you are sure that they will never point to an element erased.

Returns

Returns an unsafe const iterator pointing just before the beginning of the List

Definition at line 1326 of file list_tpl.h.

                                                                                  {
    return *(reinterpret_cast< const ListConstIterator< Val >* >(_list_end_));
  }

crendSafe()

template<typename Val , typename Alloc >

INLINE const ListConstIteratorSafe< Val > & gum::List< Val, Alloc >::crendSafe ( ) const

noexcept

Return a safe const iterator pointing just before the beginning of the List.

Safe const iterators are const iterators whose state is updated by the list when the element they point to is erased. As such, in this case, they can throw an exception when we try to derefence them and they are able to perform a valid ++ or – step.

Return a safe const iterator pointing just before the beginning of the List.

Definition at line 1314 of file list_tpl.h.

                                                                                          {
    return *(reinterpret_cast< const ListConstIteratorSafe< Val >* >(_list_end_safe_));
  }

emplace() [1/4]

template<typename Val, typename Alloc = std::allocator< Val >>

template<typename... Args>

Val& gum::List< Val, Alloc >::emplace	(	const const_iterator &	iter,
		Args &&...	args
	)

Emplace a new element before a given iterator.

Emplace is a method that allows to construct directly an element of type Val by passing to its constructor all the arguments it needs. The first element of the list is at pos 0. After the insert, the element is placed precisely at pos if pos is less than the size of the list before insertion, else it is inserted at the end of the list.

Parameters

iter	The position in the list
args	The arguments passed to the constructor

Returns

Returns a reference on the copy inserted into the list.

emplace() [2/4]

template<typename Val, typename Alloc = std::allocator< Val >>

template<typename... Args>

Val& gum::List< Val, Alloc >::emplace	(	const const_iterator_safe &	iter,
		Args &&...	args
	)

Emplace a new element before a given safe iterator.

Emplace is a method that allows to construct directly an element of type Val by passing to its constructor all the arguments it needs. The first element of the list is at pos 0. After the insert, the element is placed precisely at pos if pos is less than the size of the list before insertion, else it is inserted at the end of the list.

Parameters

iter	The position in the list.
args	the arguments passed to the constructor.

Returns

Returns a reference on the copy inserted into the list.

emplace() [3/4]

template<typename Val, typename Alloc = std::allocator< Val >>

template<typename... Args>

INLINE Val& gum::List< Val, Alloc >::emplace	(	const const_iterator &	iter,
		Args &&...	args
	)

Definition at line 1750 of file list_tpl.h.

                                                                                    {
    return _insert_(iter, _createEmplaceBucket_(std::forward< Args >(args)...), location::BEFORE);
  }

emplace() [4/4]

template<typename Val, typename Alloc = std::allocator< Val >>

template<typename... Args>

INLINE Val& gum::List< Val, Alloc >::emplace	(	const const_iterator_safe &	iter,
		Args &&...	args
	)

Definition at line 1757 of file list_tpl.h.

                                                                                         {
    return _insert_(iter, _createEmplaceBucket_(std::forward< Args >(args)...), location::BEFORE);
  }

emplaceBack() [1/2]

template<typename Val, typename Alloc = std::allocator< Val >>

template<typename... Args>

Val& gum::List< Val, Alloc >::emplaceBack

(

Args &&...

args

)

Emplace elements at the end of the chained list.

Emplace is a method that allows to construct directly an element of type Val by passing to its constructor all the arguments it needs

Template Parameters

Args	The emplaced arguments types.

Parameters

args	The arguments passed to the constructor

Returns

A reference on the copy inserted into the list.

emplaceBack() [2/2]

template<typename Val, typename Alloc = std::allocator< Val >>

template<typename... Args>

INLINE Val& gum::List< Val, Alloc >::emplaceBack

(

Args &&...

args

)

Definition at line 1555 of file list_tpl.h.

                                                            {
    return _pushBack_(_createEmplaceBucket_(std::forward< Args >(args)...));
  }

emplaceFront() [1/2]

template<typename Val, typename Alloc = std::allocator< Val >>

template<typename... Args>

Val& gum::List< Val, Alloc >::emplaceFront

(

Args &&...

args

)

Emplace elements at the beginning of the chained list.

Emplace is a method that allows to construct directly an element of type Val by passing to its constructor all the arguments it needs

Parameters

args	The arguments passed to the constructor.

Returns

Returns a reference on the copy inserted into the list.

emplaceFront() [2/2]

template<typename Val, typename Alloc = std::allocator< Val >>

template<typename... Args>

INLINE Val& gum::List< Val, Alloc >::emplaceFront

(

Args &&...

args

)

Definition at line 1529 of file list_tpl.h.

                                                             {
    return _pushFront_(_createEmplaceBucket_(std::forward< Args >(args)...));
  }

empty()

template<typename Val , typename Alloc >

INLINE bool gum::List< Val, Alloc >::empty ( ) const

noexcept

Returns a boolean indicating whether the chained list is empty.

Returns

Returns a boolean indicating whether the chained list is empty.

Definition at line 1896 of file list_tpl.h.

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

end() [1/2]

template<typename Val , typename Alloc >

INLINE const ListIterator< Val > & gum::List< Val, Alloc >::end ( )

noexcept

Returns an unsafe iterator pointing to the end of the List.

Unsafe iterators are a little bit faster than safe iterators and they consume less memory. However, if the element they point to is erased, their dereference or their increment/decrement will produce a mess, probably a segfault. You should use them only when performance is an issue and if you are sure that they will never point to an element erased.

Returns

Returns an unsafe iterator pointing to the end of the List.

Definition at line 1302 of file list_tpl.h.

                                                                     {
    return *(reinterpret_cast< const ListIterator< Val >* >(_list_end_));
  }

end() [2/2]

template<typename Val , typename Alloc >

INLINE const ListConstIterator< Val > & gum::List< Val, Alloc >::end ( ) const

noexcept

Returns an unsafe const iterator pointing to the end of the List.

Unsafe const iterators are a little bit faster than safe const iterators and they consume less memory. However, if the element they point to is erased, their dereference or their increment/decrement will produce a mess, probably a segfault. You should use them only when performance is an issue and if you are sure that they will never point to an element erased.

Returns

Returns an unsafe const iterator pointing to the end of the List.

Definition at line 1308 of file list_tpl.h.

                                                                                {
    return *(reinterpret_cast< const ListConstIterator< Val >* >(_list_end_));
  }

endSafe()

template<typename Val , typename Alloc >

INLINE const ListIteratorSafe< Val > & gum::List< Val, Alloc >::endSafe ( )

noexcept

Returns a safe iterator pointing to the end of the List.

Safe iterators are iterators whose state is updated by the list when the element they point to is erased. As such, in this case, they can throw an exception when we try to derefence them and they are able to perform a valid ++ or – step.

Ceturns a safe iterator pointing to the end of the List.

Definition at line 1290 of file list_tpl.h.

                                                                             {
    return *(reinterpret_cast< const ListIteratorSafe< Val >* >(_list_end_safe_));
  }

erase() [1/3]

template<typename Val , typename Alloc >

INLINE void gum::List< Val, Alloc >::erase

(

Size

i

)

Erases the ith element of the List (the first one is in position 0).

If the element cannot be found, the function returns without throwing any exception. It runs in linear time in the size of the list.

Parameters

i	The position in the list of the element we wish to remove.

Definition at line 1837 of file list_tpl.h.

                                              {
    if (i >= _nb_elements_) return;

    // erase the ith bucket
    _erase_(_getIthBucket_(i));
  }

erase() [2/3]

template<typename Val , typename Alloc >

INLINE void gum::List< Val, Alloc >::erase

(

const iterator_safe &

iter

)

Erases the element of the List pointed to by the safe iterator.

If the element cannot be found, i.e., it has already been erased or the iterator points to end/rend, the function returns without throwing any exception. It runs in linear time in the size of the list.

Parameters

iter	An iterator pointing to the element to remove.

Definition at line 1846 of file list_tpl.h.

                                                                 {
    _erase_(iter._getBucket_());
  }

erase() [3/3]

template<typename Val , typename Alloc >

INLINE void gum::List< Val, Alloc >::erase

(

const const_iterator_safe &

iter

)

Erases the element of the List pointed to by the safe const iterator.

If the element cannot be found, i.e., it has already been erased or the iterator points to end/rend, the function returns without throwing any exception. It runs in linear time in the size of the list.

Parameters

iter	An iterator pointing to the element to remove.

Definition at line 1852 of file list_tpl.h.

                                                                       {
    _erase_(iter._getBucket_());
  }

eraseAllVal()

template<typename Val, typename Alloc >

INLINE void gum::List< Val, Alloc >::eraseAllVal

(

const Val &

val

)

erases all the elements encountered with a given value

If no element equal to val can be found, the function returns without throwing any exception.

Comparisons between Val instances are performed through == operators.

Parameters

val	the value of the element we wish to remove.

Definition at line 1873 of file list_tpl.h.

                                                            {
    for (ListBucket< Val >*iter = _deb_list_, *next_bucket = nullptr; iter != nullptr;
         iter = next_bucket) {
      next_bucket = iter->_next_;

      if (val == iter->_val_) _erase_(iter);
    }
  }

eraseByVal()

template<typename Val, typename Alloc >

INLINE void gum::List< Val, Alloc >::eraseByVal

(

const Val &

val

)

erases the first element encountered with a given value.

If no element equal to val can be found, the function returns without throwing any exception. It runs in linear time both in the size of the list and in the number of iterators referenced in the list. Comparisons between Val instances are performed through == operators.

Parameters

val	The value of the element we wish to remove.

Definition at line 1867 of file list_tpl.h.

                                                           {
    _erase_(_getBucket_(val));
  }

exists()

template<typename Val, typename Alloc >

INLINE bool gum::List< Val, Alloc >::exists

(

const Val &

val

)

const

Checks whether there exists a given element in the list.

This method runs in linear time.

Comparisons between Val instances are performed through == operators.

Parameters

val	the value of the element we wish to check the existence of.

Returns

Returns true if val is in the gum::List.

Definition at line 1785 of file list_tpl.h.

                                                             {
    for (ListBucket< Val >* ptr = _deb_list_; ptr != nullptr; ptr = ptr->_next_)
      if (ptr->_val_ == val) return true;

    return false;
  }

front()

template<typename Val , typename Alloc >

INLINE Val & gum::List< Val, Alloc >::front

(

)

const

Returns a reference to first element of a list, if any.

Exceptions

NotFound

exception is thrown if the list is empty.

Definition at line 1763 of file list_tpl.h.

                                              {
    if (_nb_elements_ == Size(0)) { GUM_ERROR(NotFound, "not enough elements in the chained list") }

    return _deb_list_->_val_;
  }

insert() [1/8]

template<typename Val, typename Alloc >

INLINE Val & gum::List< Val, Alloc >::insert

(

const Val &

val

)

Inserts a new element at the end of the chained list (alias of pushBack).

Parameters

val	The value inserted.

Returns

a reference on the copy inserted into the list.

Warning

Note that val is not actually inserted into the list. Rather, it is a copy of val that is inserted.

Definition at line 1562 of file list_tpl.h.

                                                       {
    return pushBack(val);
  }

insert() [2/8]

template<typename Val, typename Alloc >

INLINE Val & gum::List< Val, Alloc >::insert

(

Val &&

val

)

Inserts a new element at the end of the chained list (alias of pushBack).

Parameters

val	The value inserted.

Returns

a reference on the copy inserted into the list.

Warning

Note that val is not actually inserted into the list. Rather, it is a copy of val that is inserted.

Definition at line 1568 of file list_tpl.h.

                                                  {
    return pushBack(std::move(val));
  }

insert() [3/8]

template<typename Val, typename Alloc >

INLINE Val & gum::List< Val, Alloc >::insert	(	Size	pos,
		const Val &	val
	)

Inserts a new element at the ith pos of the chained list.

The first element of the list is at pos 0. After the insert, the element is placed precisely at pos if pos is less than the size of the list before insertion, else it is inserted at the end of the list.

Parameters

pos	The position where to inser the new element.
val	The value to insert.

Returns

a reference on the copy inserted into the list.

Warning

Note that val is not actually inserted into the list. Rather, it is a copy of val that is inserted.

Definition at line 1628 of file list_tpl.h.

                                                                 {
    // if ther are fewer elements than pos, put the value at the end of the list
    if (_nb_elements_ <= pos) { return pushBack(val); }

    return _insertBefore_(_createBucket_(val), _getIthBucket_(pos));
  }

insert() [4/8]

template<typename Val, typename Alloc >

INLINE Val & gum::List< Val, Alloc >::insert	(	Size	pos,
		Val &&	val
	)

Insert an rvalue at the ith pos of the chained list.

The first element of the list is at pos 0. After the insert, the element is placed precisely at pos if pos is less than the size of the list before insertion, else it is inserted at the end of the list.

Parameters

pos	The position where to inser the new element.
val	The value to insert.

Returns

Returns a reference on the copy inserted into the list.

Definition at line 1637 of file list_tpl.h.

                                                            {
    // if ther are fewer elements than pos, put the value at the end of the list
    if (_nb_elements_ <= pos) { return pushBack(std::move(val)); }

    return _insertBefore_(_createBucket_(std::move(val)), _getIthBucket_(pos));
  }

insert() [5/8]

template<typename Val, typename Alloc >

INLINE Val & gum::List< Val, Alloc >::insert	(	const const_iterator_safe &	iter,
		const Val &	val,
		location	place = location::BEFORE
	)

Inserts a new element before or after a given iterator.

Parameters

iter	The iterator pointing where to inser the new element.
val	The value to insert.
place	Defines where to insert the new element relatively to iter.

Returns

Returns a reference on the copy inserted into the list.

Warning

Note that val is not actually inserted into the list. Rather, it is a copy of val that is inserted.

Definition at line 1710 of file list_tpl.h.

                                                                                               {
    // if the iterator does not point to the list, raise an exception
    if (iter._list_ != this) {
      GUM_ERROR(InvalidArgument, "the iterator does not point to the correct list")
    }

    return _insert_(iter, _createBucket_(val), place);
  }

insert() [6/8]

template<typename Val, typename Alloc >

INLINE Val & gum::List< Val, Alloc >::insert	(	const const_iterator_safe &	iter,
		Val &&	val,
		location	place = location::BEFORE
	)

Inserts an rvalue before or after a given iterator.

Parameters

iter	The iterator pointing where to inser the new element.
val	The value to insert.
place	Defines where to insert the new element relatively to iter.

Returns

Returns a reference on the copy inserted into the list.

Warning

Note that val is not actually inserted into the list. Rather, it is a copy of val that is inserted.

Definition at line 1723 of file list_tpl.h.

                                                                                              {
    // if the iterator does not point to the list, raise an exception
    if (iter._list_ != this) {
      GUM_ERROR(InvalidArgument, "the iterator does not point to the correct list")
    }

    return _insert_(iter, _createBucket_(std::move(val)), place);
  }

insert() [7/8]

template<typename Val, typename Alloc >

INLINE Val & gum::List< Val, Alloc >::insert	(	const const_iterator &	iter,
		const Val &	val,
		location	place = location::BEFORE
	)

Inserts a new element before or after a given iterator.

Parameters

iter	The iterator pointing where to inser the new element.
val	The value to insert.
place	Defines where to insert the new element relatively to iter.

Returns

Returns a reference on the copy inserted into the list.

Warning

Note that val is not actually inserted into the list. Rather, it is a copy of val that is inserted.

Definition at line 1736 of file list_tpl.h.

                                                                                              {
    return _insert_(iter, _createBucket_(val), place);
  }

insert() [8/8]

template<typename Val, typename Alloc >

INLINE Val & gum::List< Val, Alloc >::insert	(	const const_iterator &	iter,
		Val &&	val,
		location	place = location::BEFORE
	)

Inserts an rvalue before or after a given iterator.

Parameters

iter	The iterator pointing where to inser the new element.
val	The value to insert.
place	Defines where to insert the new element relatively to iter.

Returns

Returns a reference on the copy inserted into the list.

Warning

Note that val is not actually inserted into the list. Rather, it is a copy of val that is inserted.

Definition at line 1743 of file list_tpl.h.

                                                                                              {
    return _insert_(iter, _createBucket_(std::move(val)), place);
  }

map() [1/4]

template<typename Val, typename Alloc >

template<typename Mount , typename OtherAlloc >

List< Mount, OtherAlloc > gum::List< Val, Alloc >::map

(

Mount(*)(Val)

f

)

const

Creates a list of mountains from a list of val.

Parameters

f	A function that maps any Val element into a Mount

Returns

Returns a lsit of mountains.

Template Parameters

Mount	The type of mountains.
OtherAlloc	The mountains type allocator.

Definition at line 1921 of file list_tpl.h.

                                                                         {
    // create a new empty list
    List< Mount, OtherAlloc > list;

    // fill the new list
    for (const_iterator iter = begin(); iter != end(); ++iter) {
      list.pushBack(f(*iter));
    }

    return list;
  }

map() [2/4]

template<typename Val, typename Alloc >

template<typename Mount , typename OtherAlloc >

List< Mount, OtherAlloc > gum::List< Val, Alloc >::map

(

Mount(*)(Val &)

f

)

const

Creates a list of mountains from a list of val.

Parameters

f	A function that maps any Val element into a Mount

Returns

Returns a lsit of mountains.

Template Parameters

Mount	The type of mountains.
OtherAlloc	The mountains type allocator.

Definition at line 1936 of file list_tpl.h.

                                                                          {
    // create a new empty list
    List< Mount, OtherAlloc > list;

    // fill the new list
    for (const_iterator iter = begin(); iter != end(); ++iter) {
      list.pushBack(f(*iter));
    }

    return list;
  }

map() [3/4]

template<typename Val, typename Alloc >

template<typename Mount , typename OtherAlloc >

List< Mount, OtherAlloc > gum::List< Val, Alloc >::map

(

Mount(*)(const Val &)

f

)

const

Creates a list of mountains from a list of val.

Parameters

f	A function that maps any Val element into a Mount

Returns

Returns a lsit of mountains.

Template Parameters

Mount	The type of mountains.
OtherAlloc	The mountains type allocator.

Definition at line 1951 of file list_tpl.h.

                                                                                {
    // create a new empty list
    List< Mount, OtherAlloc > list;

    // fill the new list
    for (const_iterator iter = begin(); iter != end(); ++iter) {
      list.pushBack(f(*iter));
    }

    return list;
  }

map() [4/4]

template<typename Val, typename Alloc >

template<typename Mount , typename OtherAlloc >

List< Mount, OtherAlloc > gum::List< Val, Alloc >::map

(

const Mount &

mount

)

const

Creates a list of mountains with a given value from a list of val.

Parameters

mount

the value taken by all the elements of the resulting list

Returns

Returns a lsit of mountains.

Template Parameters

Mount	The type of mountains.
OtherAlloc	The mountains type allocator.

Definition at line 1966 of file list_tpl.h.

                                                                            {
    // create a new empty list
    List< Mount, OtherAlloc > list;

    // fill the new list
    for (Size i = Size(0); i < _nb_elements_; ++i)
      list.pushBack(mount);

    return list;
  }

operator!=() [1/2]

template<typename Val, typename Alloc = std::allocator< Val >>

template<typename OtherAlloc >

bool gum::List< Val, Alloc >::operator!=

(

const List< Val, OtherAlloc > &

src

)

const

Checks whether two lists are different (different elements or orders).

This method runs in time linear in the number of elements of the list.

Returns

Returns true if src and this gum::List are identical.

Template Parameters

OtherAlloc

The other allocator.

operator!=() [2/2]

template<typename Val, typename Alloc = std::allocator< Val >>

template<typename OtherAlloc >

INLINE bool gum::List< Val, Alloc >::operator!=

(

const List< Val, OtherAlloc > &

src

)

const

Definition at line 2009 of file list_tpl.h.

                                                                                     {
    return !operator==(src);
  }

operator+=() [1/2]

template<typename Val, typename Alloc >

INLINE Val & gum::List< Val, Alloc >::operator+=

(

const Val &

val

)

Inserts a new element at the end of the list (alias of pushBack).

This enables writing code like list += xxx; to add element xxx to the list.

Warning

Note that val is not actually inserted into the list. Rather, it is a copy of val that is inserted.

Parameters

val	Tha value inserted int the list.

Returns

Returns a reference on the copy inserted into the list.

Definition at line 1980 of file list_tpl.h.

                                                           {
    return pushBack(val);
  }

operator+=() [2/2]

template<typename Val, typename Alloc >

INLINE Val & gum::List< Val, Alloc >::operator+=

(

Val &&

val

)

Inserts a new element at the end of the list (alias of pushBack).

This enables writing code like list += xxx; to add element xxx to the list.

Warning

Note that val is not actually inserted into the list. Rather, it is a copy of val that is inserted.

Parameters

val	Tha value inserted int the list.

Returns

Returns a reference on the copy inserted into the list.

Definition at line 1987 of file list_tpl.h.

                                                      {
    return pushBack(std::move(val));
  }

operator=() [1/4]

template<typename Val, typename Alloc>

INLINE List< Val, Alloc > & gum::List< Val, Alloc >::operator=

(

const List< Val, Alloc > &

src

)

Copy operator.

The new list and that which is copied do not share the elements: the new list contains new instances of the values stored in the list to be copied. Of course if these values are pointers, the new values point toward the same elements. The List on which the operator is applied keeps its iterator's list. Of course, if it previously contained some elements, those are removed prior to the copy. This operator runs in linear time.

Warning

If the current List previously contained iterators, those will be resetted to end()/rend().

Parameters

src	the list the content of which will be copied into the current List.

Returns

Returns this gum::List.

Definition at line 1220 of file list_tpl.h.

                                                                                        {
    // avoid self assignment
    if (this != &src) {
      // for debugging purposes
      GUM_OP_CPY(List);

      // remove the old content of 'this' and update accordingly the iterators
      clear();

      // perform the copy
      _copy_elements_(src);
    }

    return *this;
  }

operator=() [2/4]

template<typename Val, typename Alloc = std::allocator< Val >>

template<typename OtherAlloc >

List< Val, Alloc >& gum::List< Val, Alloc >::operator=

(

const List< Val, OtherAlloc > &

src

)

Generalized copy operator.

The new list and that which is copied do not share the elements: the new list contains new instances of the values stored in the list to be copied. Of course if these values are pointers, the new values point toward the same elements. The List on which the operator is applied keeps its iterator's list. Of course, if it previously contained some elements, those are removed prior to the copy. This operator runs in linear time.

Warning

If the current List previously contained iterators, those will be resetted to end()/rend().

Parameters

src	the list the content of which will be copied into the current List.

Returns

Returns this gum::List.

operator=() [3/4]

template<typename Val, typename Alloc>

INLINE List< Val, Alloc > & gum::List< Val, Alloc >::operator=

(

List< Val, Alloc > &&

src

)

Move operator.

Parameters

src	The gum::List to move.

Returns

Returns this gum::List.

Definition at line 1257 of file list_tpl.h.

                                                                                   {
    // avoid self assignment
    if (this != &src) {
      // for debugging purposes
      GUM_OP_MOV(List);

      // remove the old content of 'this' and update accordingly the iterators
      clear();

      // perform the move
      _deb_list_       = std::move(src._deb_list_);
      _end_list_       = std::move(src._end_list_);
      _nb_elements_    = std::move(src._nb_elements_);
      _safe_iterators_ = std::move(src._safe_iterators_);
      _alloc_bucket_   = std::move(src._alloc_bucket_);

      src._deb_list_    = nullptr;
      src._end_list_    = nullptr;
      src._nb_elements_ = 0;
      src._safe_iterators_.clear();
    }

    return *this;
  }

operator=() [4/4]

template<typename Val, typename Alloc = std::allocator< Val >>

template<typename OtherAlloc >

INLINE List< Val, Alloc >& gum::List< Val, Alloc >::operator=

(

const List< Val, OtherAlloc > &

src

)

Definition at line 1239 of file list_tpl.h.

                                                                                             {
    // avoid self assignment
    if (this != reinterpret_cast< List< Val, Alloc >* >(&src)) {
      // for debugging purposes
      GUM_OP_CPY(List);

      // remove the old content of 'this' and update accordingly the iterators
      clear();

      // perform the copy
      _copy_elements_(src);
    }

    return *this;
  }

operator==() [1/2]

template<typename Val, typename Alloc = std::allocator< Val >>

template<typename OtherAlloc >

bool gum::List< Val, Alloc >::operator==

(

const List< Val, OtherAlloc > &

src

)

const

Checks whether two lists are identical (same elements in the same order).

This method runs in time linear in the number of elements of the list.

Returns

Returns true if src and this gum::List are identical.

Template Parameters

OtherAlloc

The other allocator.

operator==() [2/2]

template<typename Val, typename Alloc = std::allocator< Val >>

template<typename OtherAlloc >

INLINE bool gum::List< Val, Alloc >::operator==

(

const List< Val, OtherAlloc > &

src

)

const

Definition at line 1994 of file list_tpl.h.

                                                                                     {
    // check if the two lists have at least the same number of elements
    if (_nb_elements_ != src._nb_elements_) return false;

    // parse the two lists
    for (ListBucket< Val >*iter1 = _deb_list_, *iter2 = src._deb_list_; iter1 != nullptr;
         iter1 = iter1->_next_, iter2 = iter2->_next_)
      if (*iter1 != *iter2) return false;

    return true;
  }

operator[]() [1/2]

template<typename Val , typename Alloc >

INLINE Val & gum::List< Val, Alloc >::operator[]

(

const Size

i

)

Returns the ith element in the current chained list.

The first of the list element has index 0.

This method runs in linear time.

Parameters

i	The position of the element in the list (0 = first element).

Exceptions

NotFound

Raised if the element to be retrieved does not exist.

Returns

Returns a reference on the element stored at the ith position in the list.

Definition at line 2015 of file list_tpl.h.

                                                         {
    // check if we can return the element we ask for
    if (i >= _nb_elements_) { GUM_ERROR(NotFound, "not enough elements in the chained list") }

    return **_getIthBucket_(i);
  }

operator[]() [2/2]

template<typename Val , typename Alloc >

INLINE const Val & gum::List< Val, Alloc >::operator[]

(

const Size

i

)

const

Returns the const ith element in the current chained list.

The first of the list element has index 0.

This method runs in linear time.

Parameters

i	the position of the element in the list (0 = first element).

Exceptions

NotFound

Raised if the element to be retrieved does not exist.

Returns

Returns a reference on the element stored at the ith position in the list.

Definition at line 2024 of file list_tpl.h.

                                                                     {
    // check if we can return the element we ask for
    if (i >= _nb_elements_) { GUM_ERROR(NotFound, "not enough elements in the chained list") }

    return **_getIthBucket_(i);
  }

popBack()

template<typename Val , typename Alloc >

INLINE void gum::List< Val, Alloc >::popBack

(

)

Removes the last element of a List, if any.

When the list is empty, it does not do anything.

Definition at line 1884 of file list_tpl.h.

                                          {
    _erase_(_end_list_);
  }

popFront()

template<typename Val , typename Alloc >

INLINE void gum::List< Val, Alloc >::popFront

(

)

Removes the first element of a List, if any.

When the list is empty, it does not do anything.

Definition at line 1890 of file list_tpl.h.

                                           {
    _erase_(_deb_list_);
  }

push_back() [1/2]

template<typename Val, typename Alloc = std::allocator< Val >>

template<typename... Args>

Val& gum::List< Val, Alloc >::push_back

(

Args &&...

args

)

An alias for pushBack used for STL compliance.

Defining push_back allows using, for instance, BackInserters.

Template Parameters

Args	The emplace arguments type.

Parameters

args	The emplace arguments values.

Returns

Returns a reference on the copy inserted into the list.

push_back() [2/2]

template<typename Val, typename Alloc = std::allocator< Val >>

template<typename... Args>

INLINE Val& gum::List< Val, Alloc >::push_back

(

Args &&...

args

)

Definition at line 1548 of file list_tpl.h.

                                                          {
    return pushBack(std::forward< Args >(args)...);
  }

push_front() [1/2]

template<typename Val, typename Alloc = std::allocator< Val >>

template<typename... Args>

Val& gum::List< Val, Alloc >::push_front

(

Args &&...

args

)

An alias for pushFront used for STL compliance.

Defining push_front allows using, for instance, FrontInserters.

Template Parameters

Args	The emplace values type.

Parameters

args	The emplace values.

Returns

Returns a reference on the copy inserted into the list.

push_front() [2/2]

template<typename Val, typename Alloc = std::allocator< Val >>

template<typename... Args>

INLINE Val& gum::List< Val, Alloc >::push_front

(

Args &&...

args

)

Definition at line 1522 of file list_tpl.h.

                                                           {
    return pushFront(std::forward< Args >(args)...);
  }

pushBack() [1/2]

template<typename Val, typename Alloc >

INLINE Val & gum::List< Val, Alloc >::pushBack

(

const Val &

val

)

Inserts a new element (a copy) at the end of the chained list.

The value passed in argument is not actually inserted into the list: this is a copy of this value that is inserted. The method runs in constant time.

Parameters

val	The value pushed back.

Returns

Returns a reference on the copy inserted into the list.

Warning

Note that val is not actually inserted into the list. Rather, it is a copy of val that is inserted.

Definition at line 1535 of file list_tpl.h.

                                                         {
    return _pushBack_(_createBucket_(val));
  }

pushBack() [2/2]

template<typename Val, typename Alloc >

INLINE Val & gum::List< Val, Alloc >::pushBack

(

Val &&

val

)

Inserts a new element (a move) at the end of the chained list.

The value passed in argument is not actually inserted into the list: this is a copy of this value that is inserted. The method runs in constant time.

Parameters

val	The value pushed back.

Returns

Returns a reference on the copy inserted into the list.

Warning

Note that val is not actually inserted into the list. Rather, it is a copy of val that is inserted.

Definition at line 1541 of file list_tpl.h.

                                                    {
    return _pushBack_(_createBucket_(std::move(val)));
  }

pushFront() [1/2]

template<typename Val, typename Alloc >

INLINE Val & gum::List< Val, Alloc >::pushFront

(

const Val &

val

)

Inserts a new element (a copy) at the beginning of the chained list.

The value passed in argument is not actually inserted into the list: this is a copy of this value that is inserted. The method runs in constant time.

Parameters

val	The valus pushed at the front.

Returns

Returns a reference on the copy inserted into the list.

Warning

Note that val is not actually inserted into the list. Rather, it is a copy of val that is inserted.

Definition at line 1509 of file list_tpl.h.

                                                          {
    return _pushFront_(_createBucket_(val));
  }

pushFront() [2/2]

template<typename Val, typename Alloc >

INLINE Val & gum::List< Val, Alloc >::pushFront

(

Val &&

val

)

Inserts a new element (a move) at the beginning of the chained list.

Parameters

val	The valus pushed at the front.

Returns

Returns a reference on the copy inserted into the list.

Warning

Note that val is not actually inserted into the list. Rather, it is a copy of val that is inserted.

Definition at line 1515 of file list_tpl.h.

                                                     {
    return _pushFront_(_createBucket_(std::move(val)));
  }

rbegin() [1/2]

template<typename Val , typename Alloc >

INLINE ListIterator< Val > gum::List< Val, Alloc >::rbegin

(

)

Returns an unsafe iterator pointing to the last element of the List.

Unsafe iterators are a little bit faster than safe iterators and they consume less memory. However, if the element they point to is erased, their dereference or their increment/decrement will produce a mess, probably a segfault. You should use them only when performance is an issue and if you are sure that they will never point to an element erased.

Returns

Returns an unsafe iterator pointing to the last element of the List.

Definition at line 1401 of file list_tpl.h.

                                                        {
    if (_nb_elements_)
      return ListIterator< Val >{*this, _nb_elements_ - 1};
    else
      return ListIterator< Val >{};
  }

rbegin() [2/2]

template<typename Val , typename Alloc >

INLINE ListConstIterator< Val > gum::List< Val, Alloc >::rbegin

(

)

const

Returns an unsafe const iterator pointing to the last element of the List.

Unsafe iterators are a little bit faster than safe iterators and they consume less memory. However, if the element they point to is erased, their dereference or their increment/decrement will produce a mess, probably a segfault. You should use them only when performance is an issue and if you are sure that they will never point to an element erased.

Returns

Returns an unsafe const iterator pointing to the last element of the List.

Definition at line 1410 of file list_tpl.h.

                                                                   {
    if (_nb_elements_)
      return ListConstIterator< Val >{*this, _nb_elements_ - 1};
    else
      return ListConstIterator< Val >{};
  }

rbeginSafe()

template<typename Val , typename Alloc >

INLINE ListIteratorSafe< Val > gum::List< Val, Alloc >::rbeginSafe

(

)

Returns a safe iterator pointing to the last element of the List.

Safe iterators are iterators whose state is updated by the list when the element they point to is erased. As such, in this case, they can throw an exception when we try to derefence them and they are able to perform a valid ++ or – step.

Returns

Returns a safe iterator pointing to the last element of the List.

Definition at line 1383 of file list_tpl.h.

                                                                {
    if (_nb_elements_)
      return ListIteratorSafe< Val >{*this, _nb_elements_ - 1};
    else
      return ListIteratorSafe< Val >{};
  }

rend() [1/2]

template<typename Val , typename Alloc >

INLINE const ListIterator< Val > & gum::List< Val, Alloc >::rend ( )

noexcept

Returns an unsafe iterator pointing just before the beginning of the List.

Unsafe iterators are a little bit faster than safe iterators and they consume less memory. However, if the element they point to is erased, their dereference or their increment/decrement will produce a mess, probably a segfault. You should use them only when performance is an issue and if you are sure that they will never point to an element erased.

Returns an unsafe iterator pointing just before the beginning of the List.

Definition at line 1332 of file list_tpl.h.

                                                                      {
    return *(reinterpret_cast< const ListIterator< Val >* >(_list_end_));
  }

rend() [2/2]

template<typename Val , typename Alloc >

INLINE const ListConstIterator< Val > & gum::List< Val, Alloc >::rend ( ) const

noexcept

Returns an unsafe const iterator pointing just before the beginning of the List.

Unsafe const iterators are a little bit faster than safe const iterators and they consume less memory. However, if the element they point to is erased, their dereference or their increment/decrement will produce a mess, probably a segfault. You should use them only when performance is an issue and if you are sure that they will never point to an element erased.

Returns

Returns an unsafe const iterator pointing just before the beginning of the List.

Definition at line 1338 of file list_tpl.h.

                                                                                 {
    return *(reinterpret_cast< const ListConstIterator< Val >* >(_list_end_));
  }

rendSafe()

template<typename Val , typename Alloc >

INLINE const ListIteratorSafe< Val > & gum::List< Val, Alloc >::rendSafe ( )

noexcept

Returns a safe iterator pointing just before the beginning of the List.

Safe iterators are iterators whose state is updated by the list when the element they point to is erased. As such, in this case, they can throw an exception when we try to derefence them and they are able to perform a valid ++ or – step.

Returns

Returns a safe iterator pointing just before the beginning of the List.

Definition at line 1320 of file list_tpl.h.

                                                                              {
    return *(reinterpret_cast< const ListIteratorSafe< Val >* >(_list_end_safe_));
  }

size()

template<typename Val , typename Alloc >

INLINE Size gum::List< Val, Alloc >::size ( ) const

noexcept

Returns the number of elements in the list.

This method runs in constant time.

Definition at line 1779 of file list_tpl.h.

                                                      {
    return _nb_elements_;
  }

swap()

template<typename Val , typename Alloc >

INLINE void gum::List< Val, Alloc >::swap

(

List< Val, Alloc > &

other_list

)

Swap the current list with another one.

Parameters

other_list

The list to swap elements with.

Definition at line 2033 of file list_tpl.h.

                                                       {
    std::swap(_deb_list_, other_list._deb_list_);
    std::swap(_end_list_, other_list._end_list_);
    std::swap(_nb_elements_, other_list._nb_elements_);
    std::swap(_safe_iterators_, other_list._safe_iterators_);
    std::swap(_alloc_bucket_, other_list._alloc_bucket_);
  }

toString()

template<typename Val , typename Alloc >

std::string gum::List< Val, Alloc >::toString

(

)

const

Converts a list into a string.

Returns

Returns a std::string representation of the gum::List.

Definition at line 1902 of file list_tpl.h.

                                               {
    bool              deja = false;
    std::stringstream stream;
    stream << "[";

    for (ListBucket< Val >* ptr = _deb_list_; ptr != nullptr; ptr = ptr->_next_, deja = true) {
      if (deja) stream << " --> ";

      stream << ptr->_val_;
    }

    stream << "]";

    return stream.str();
  }

Friends And Related Function Documentation

ListConstIterator< Val >

template<typename Val, typename Alloc = std::allocator< Val >>

friend class ListConstIterator< Val >

friend

ListIterator should be a friend to optimize access to elements.

Definition at line 1438 of file list.h.

ListConstIteratorSafe< Val >

template<typename Val, typename Alloc = std::allocator< Val >>

friend class ListConstIteratorSafe< Val >

friend

ListIterator should be a friend to optimize access to elements.

Definition at line 1440 of file list.h.

ListIterator< Val >

template<typename Val, typename Alloc = std::allocator< Val >>

friend class ListIterator< Val >

friend

ListIterator should be a friend to optimize access to elements.

Definition at line 1437 of file list.h.

ListIteratorSafe< Val >

template<typename Val, typename Alloc = std::allocator< Val >>

friend class ListIteratorSafe< Val >

friend

ListIterator should be a friend to optimize access to elements.

Definition at line 1439 of file list.h.

Member Data Documentation

_alloc_bucket_

template<typename Val, typename Alloc = std::allocator< Val >>

BucketAllocator gum::List< Val, Alloc >::_alloc_bucket_

mutableprivate

The allocator for the buckets.

Definition at line 1309 of file list.h.

_deb_list_

template<typename Val, typename Alloc = std::allocator< Val >>

ListBucket< Val >* gum::List< Val, Alloc >::_deb_list_ {nullptr}

private

A pointer on the first element of the chained list.

Definition at line 1297 of file list.h.

_end_list_

template<typename Val, typename Alloc = std::allocator< Val >>

ListBucket< Val >* gum::List< Val, Alloc >::_end_list_ {nullptr}

private

A pointer on the last element of the chained list.

Definition at line 1300 of file list.h.

_nb_elements_

template<typename Val, typename Alloc = std::allocator< Val >>

Size gum::List< Val, Alloc >::_nb_elements_ {Size(0)}

private

The number of elements in the list.

Definition at line 1303 of file list.h.

_safe_iterators_

template<typename Val, typename Alloc = std::allocator< Val >>

std::vector< const_iterator_safe* > gum::List< Val, Alloc >::_safe_iterators_

mutableprivate

The list of "safe" iterators attached to the list.

Definition at line 1306 of file list.h.

---

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

• agrum/tools/core/list.h
• agrum/tools/core/list_tpl.h