Open 3D Engine AzCore API Reference 23.10.0
O3DE is an open-source, fully-featured, high-fidelity, modular 3D engine for building games and simulations, available to every industry.
Classes | Public Types | Public Member Functions | Protected Member Functions | Protected Attributes | List of all members
AZStd::intrusive_list< T, Hook > Class Template Reference

#include <intrusive_list.h>

Classes

class  const_iterator_impl
 
class  iterator_impl
 
class  reverse_iterator_impl
 

Public Types

typedef T * pointer
 
typedef const T * const_pointer
 
typedef T & reference
 
typedef const T & const_reference
 
typedef AZStd::size_t difference_type
 
typedef AZStd::size_t size_type
 
typedef T value_type
 
typedef T node_type
 
typedef node_type * node_ptr_type
 
typedef node_ptr_type const_node_ptr_type
 
typedef intrusive_list_node< T > hook_node_type
 
typedef hook_node_type * hook_node_ptr_type
 
typedef iterator_impl iterator
 
typedef const_iterator_impl const_iterator
 
typedef reverse_iterator_impl< iterator > reverse_iterator
 
typedef reverse_iterator_impl< const_iterator > const_reverse_iterator
 

Public Member Functions

template<class InputIterator >
AZ_FORCE_INLINE intrusive_list (const InputIterator &first, const InputIterator &last)
 
AZ_FORCE_INLINE intrusive_list (const this_type &rhs)
 
AZ_FORCE_INLINE this_type & operator= (const this_type &rhs)
 
AZ_FORCE_INLINE intrusive_list (this_type &&rhs)
 
this_type & operator= (this_type &&rhs)
 
void assign_rv (this_type &&rhs)
 
void swap (this_type &&rhs)
 
template<class InputIterator >
AZ_FORCE_INLINE void assign (const InputIterator &first, const InputIterator &last)
 
AZ_FORCE_INLINE size_type size () const
 
AZ_FORCE_INLINE size_type max_size () const
 
AZ_FORCE_INLINE bool empty () const
 
AZ_FORCE_INLINE iterator begin ()
 
AZ_FORCE_INLINE const_iterator begin () const
 
AZ_FORCE_INLINE iterator end ()
 
AZ_FORCE_INLINE const_iterator end () const
 
AZ_FORCE_INLINE reverse_iterator rbegin ()
 
AZ_FORCE_INLINE const_reverse_iterator rbegin () const
 
const_reverse_iterator crbegin () const
 
AZ_FORCE_INLINE reverse_iterator rend ()
 
AZ_FORCE_INLINE const_reverse_iterator rend () const
 
const_reverse_iterator crend () const
 
AZ_FORCE_INLINE reference front ()
 
AZ_FORCE_INLINE const_reference front () const
 
AZ_FORCE_INLINE reference back ()
 
AZ_FORCE_INLINE const_reference back () const
 
AZ_FORCE_INLINE void push_front (const_reference value)
 
AZ_FORCE_INLINE void pop_front ()
 
AZ_FORCE_INLINE void push_back (const_reference value)
 
AZ_FORCE_INLINE void pop_back ()
 
AZ_INLINE iterator insert (iterator insertPos, const_reference value)
 
template<class InputIterator >
AZ_FORCE_INLINE void insert (iterator insertPos, InputIterator first, InputIterator last)
 
iterator erase (const_reference value)
 
iterator erase (const_iterator toErase)
 
AZ_FORCE_INLINE iterator erase (const_iterator first, const_iterator last)
 
void clear ()
 
void swap (this_type &rhs)
 
void splice (iterator splicePos, this_type &rhs)
 
void splice (iterator splicePos, this_type &rhs, iterator first)
 
void splice (iterator splicePos, this_type &rhs, iterator first, iterator last)
 
void remove (const_reference value)
 
template<class Predicate >
void remove_if (Predicate pred)
 
void unique ()
 
template<class BinaryPredicate >
void unique (BinaryPredicate compare)
 
AZ_FORCE_INLINE void merge (this_type &rhs)
 
template<class Compare >
void merge (this_type &rhs, Compare compare)
 
AZ_FORCE_INLINE void sort ()
 
template<class Compare >
void sort (Compare comp)
 
void reverse ()
 
bool validate () const
 
int validate_iterator (const const_iterator &iter) const
 
int validate_iterator (const iterator &iter) const
 
void leak_and_reset ()
 Reset the container without going to unhook any elements.
 

Protected Member Functions

node_ptr_type get_head ()
 

Protected Attributes

size_type m_numElements
 
aligned_storage< sizeof(node_type), alignment_of< node_type >::value >::type m_root
 

Detailed Description

template<class T, class Hook>
class AZStd::intrusive_list< T, Hook >

Intrusive list is a AZStd extension container.

It uses the intrusive_list_node contained in the provided user type T. You have 2 choices you can make your T type to either inherit from intrusive_list_node or just have intrusive_list_node as a public member. Based on which option you prefer you should use the appropriate hook type. Hook parameter should be list_base_hook (if you inherit the intrusive_list_node) or list_member_hook if you have it as a public member. Intrusive list never allocate any memory, destroy or create any objects. Just used the provided nodes to store it's information. Generally speaking intrusive containers are better for the cache. You can see examples of all that AZStdExamples.

Member Data Documentation

◆ m_root

template<class T , class Hook >
aligned_storage<sizeof(node_type),alignment_of<node_type>::value>::type AZStd::intrusive_list< T, Hook >::m_root
protected

OK we face different problems when we implement intrusive list. We choose to create fake node_type as a root node! Why ? There are 2 general ways to solve this issue:

  1. Store the head and tail pointer here and store pointer to the list in the iterator. This makes iterator 2 size, plus operators – and ++ include an if. This is the case because we need end iterator (which will be NULL). And we can't move it.
  2. We can store the base class in the iterator, and every time we need the value we compute the hook offset and recast the pointer. all of this is fine, but we need to have a "simple" way to debug our containers" in a easy way. So at this stage we consider the wasting a memory for a fake root node as the best solution, while we can debug the container. This can change internally at any moment if needed, no interface change will occur.
The documentation for this class was generated from the following file: