Class intrusive_list

Synopsis

#include <include/EASTL/intrusive_list.h>

template <typename T = intrusive_list_node>
class intrusive_list : public intrusive_list_base

Description

intrusive_list

Example usage: struct IntNode : public eastl::intrusive_list_node { int mX; IntNode(int x) : mX(x) { } };

IntNode nodeA(0); IntNode nodeB(1);

intrusive_list<IntNode> intList; intList.push_back(nodeA); intList.push_back(nodeB); intList.remove(nodeA);

Mentioned in

Inheritance

Ancestors: intrusive_list_base

Methods

intrusive_list overloadCreates an empty list.
intrusive_list overloadCreates an empty list; ignores the argument.
back overloadReturns a reference to the last element. The list must be non-empty.
back overloadReturns a const reference to the last element. The list must be non-empty.
begin overloadReturns an iterator pointing to the first element in the list.
begin overloadReturns a const_iterator pointing to the first element in the list.
cbeginReturns a const_iterator pointing to the first element in the list.
cendReturns a const_iterator pointing one-after the last element in the list.
containsReturns true if the given element is in the list; O(n). Equivalent to (locate(x) != end()).
crbeginReturns a const_reverse_iterator pointing at the end of the list (start of the reverse sequence).
crendReturns a const_reverse_iterator pointing at the start of the list (end of the reverse sequence).
end overloadReturns an iterator pointing one-after the last element in the list.
end overloadReturns a const_iterator pointing one-after the last element in the list.
erase overloadErases the element pointed to by the iterator. O(1)
erase overloadErases elements within the iterator range [pos, last). O(1)
front overloadReturns a reference to the first element. The list must be non-empty.
front overloadReturns a const reference to the first element. The list must be non-empty.
insertInserts an element before the element pointed to by the iterator. O(1)
locate overloadConverts a reference to an object in the list back to an iterator, or returns end() if it is not part of the list. O(n)
locate overloadConverts a const reference to an object in the list back to a const iterator, or returns end() if it is not part of the list. O(n)
merge overloadSorting functionality This is independent of the global sort algorithms, as lists are linked nodes and can be sorted more efficiently by moving nodes around in ways that global sort algorithms aren't privy to.
operator=Clears the list; ignores the argument.
push_backAdds an element to the back of the list; O(1). The element is not copied. The element must not be in any other list.
push_frontAdds an element to the front of the list; O(1). The element is not copied. The element must not be in any other list.
rbegin overloadReturns a reverse_iterator pointing at the end of the list (start of the reverse sequence).
rbegin overloadReturns a const_reverse_iterator pointing at the end of the list (start of the reverse sequence).
removeErases an element from a list; O(1). Note that this is static so you don't need to know which list the element, although it must be in some list.
rend overloadReturns a reverse_iterator pointing at the start of the list (end of the reverse sequence).
rend overloadReturns a const_reverse_iterator pointing at the start of the list (end of the reverse sequence).
sort overload
splice overloadMoves the given element into this list before the element pointed to by pos; O(1)
splice overloadMoves the contents of a list into this list before the element pointed to by pos; O(1)
splice overloadMoves the given element pointed to i within the list x into the current list before the element pointed to by pos; O(1).
splice overloadMoves the range of elements [first, last) from list x into the current list before the element pointed to by pos; O(1)
swapSwaps the contents of two intrusive lists; O(1).
unique overload
validate_iteratorbool validate() const; // Inherited from parent.

Source

Lines 207-314 in include/EASTL/intrusive_list.h.

template <typename T = intrusive_list_node>
class intrusive_list : public intrusive_list_base
{
public:
    typedef intrusive_list<T>                               this_type;
    typedef intrusive_list_base                             base_type;
    typedef T                                               node_type;
    typedef T                                               value_type;
    typedef typename base_type::size_type                   size_type;
    typedef typename base_type::difference_type             difference_type;
    typedef T&                                              reference;
    typedef const T&                                        const_reference;
    typedef T*                                              pointer;
    typedef const T*                                        const_pointer;
    typedef intrusive_list_iterator<T, T*, T&>              iterator;
    typedef intrusive_list_iterator<T, const T*, const T&>  const_iterator;
    typedef eastl::reverse_iterator<iterator>               reverse_iterator;
    typedef eastl::reverse_iterator<const_iterator>         const_reverse_iterator;
public:
    intrusive_list();                                ///< Creates an empty list.
    intrusive_list(const this_type& x);              ///< Creates an empty list; ignores the argument.
  //intrusive_list(std::initializer_list<value_type> ilist); To consider: Is this feasible, given how initializer_list works by creating a temporary array? Even if it is feasible, is it a good idea?
    this_type&  operator=(const this_type& x);       ///< Clears the list; ignores the argument.
    void        swap(this_type&);                    ///< Swaps the contents of two intrusive lists; O(1).
    iterator                begin() EA_NOEXCEPT;                 ///< Returns an iterator pointing to the first element in the list.
    const_iterator          begin() const EA_NOEXCEPT;           ///< Returns a const_iterator pointing to the first element in the list.
    const_iterator          cbegin() const EA_NOEXCEPT;          ///< Returns a const_iterator pointing to the first element in the list.
    iterator                end() EA_NOEXCEPT;                   ///< Returns an iterator pointing one-after the last element in the list.
    const_iterator          end() const EA_NOEXCEPT;             ///< Returns a const_iterator pointing one-after the last element in the list.
    const_iterator          cend() const EA_NOEXCEPT;            ///< Returns a const_iterator pointing one-after the last element in the list.
    reverse_iterator        rbegin() EA_NOEXCEPT;                ///< Returns a reverse_iterator pointing at the end of the list (start of the reverse sequence).
    const_reverse_iterator  rbegin() const EA_NOEXCEPT;          ///< Returns a const_reverse_iterator pointing at the end of the list (start of the reverse sequence).
    const_reverse_iterator  crbegin() const EA_NOEXCEPT;         ///< Returns a const_reverse_iterator pointing at the end of the list (start of the reverse sequence).
    reverse_iterator        rend() EA_NOEXCEPT;                  ///< Returns a reverse_iterator pointing at the start of the list (end of the reverse sequence).
    const_reverse_iterator  rend() const EA_NOEXCEPT;            ///< Returns a const_reverse_iterator pointing at the start of the list (end of the reverse sequence).
    const_reverse_iterator  crend() const EA_NOEXCEPT;           ///< Returns a const_reverse_iterator pointing at the start of the list (end of the reverse sequence).

    reference               front();                 ///< Returns a reference to the first element. The list must be non-empty.
    const_reference         front() const;           ///< Returns a const reference to the first element. The list must be non-empty.
    reference               back();                  ///< Returns a reference to the last element. The list must be non-empty.
    const_reference         back() const;            ///< Returns a const reference to the last element. The list must be non-empty.
    void        push_front(value_type& x);             ///< Adds an element to the front of the list; O(1). The element is not copied. The element must not be in any other list.
    void        push_back(value_type& x);              ///< Adds an element to the back of the list; O(1). The element is not copied. The element must not be in any other list.
    bool        contains(const value_type& x) const;   ///< Returns true if the given element is in the list; O(n). Equivalent to (locate(x) != end()).
    iterator        locate(value_type& x);             ///< Converts a reference to an object in the list back to an iterator, or returns end() if it is not part of the list. O(n)
    const_iterator  locate(const value_type& x) const; ///< Converts a const reference to an object in the list back to a const iterator, or returns end() if it is not part of the list. O(n)
    iterator    insert(const_iterator pos, value_type& x);   ///< Inserts an element before the element pointed to by the iterator. O(1)
    iterator    erase(const_iterator pos);                   ///< Erases the element pointed to by the iterator. O(1)
    iterator    erase(const_iterator pos, const_iterator last);    ///< Erases elements within the iterator range [pos, last). O(1)
    reverse_iterator erase(const_reverse_iterator pos);
    reverse_iterator erase(const_reverse_iterator pos, const_reverse_iterator last);
    static void remove(value_type& value);                    ///< Erases an element from a list; O(1). Note that this is static so you don't need to know which list the element, although it must be in some list.
    void               splice(const_iterator pos, value_type& x);
            ///< Moves the given element into this list before the element pointed to by pos; O(1).
            ///< Required: x must be in some list or have first/next pointers that point it itself.
    void               splice(const_iterator pos, intrusive_list& x);
            ///< Moves the contents of a list into this list before the element pointed to by pos; O(1).
            ///< Required: &x != this (same as std::list).
    void               splice(const_iterator pos, intrusive_list& x, const_iterator i);
            ///< Moves the given element pointed to i within the list x into the current list before
            ///< the element pointed to by pos; O(1).
    void               splice(const_iterator pos, intrusive_list& x, const_iterator first, const_iterator last);
            ///< Moves the range of elements [first, last) from list x into the current list before
            ///< the element pointed to by pos; O(1).
            ///< Required: pos must not be in [first, last). (same as std::list).
public:
    // Sorting functionality
    // This is independent of the global sort algorithms, as lists are 
    // linked nodes and can be sorted more efficiently by moving nodes
    // around in ways that global sort algorithms aren't privy to.
    void merge(this_type& x);
    template <typename Compare>
    void merge(this_type& x, Compare compare);
    void unique();
    template <typename BinaryPredicate>
    void unique(BinaryPredicate);
    void sort();
    template<typename Compare>
    void sort(Compare compare);
public:
    // bool validate() const; // Inherited from parent.
    int     validate_iterator(const_iterator i) const;
}; // intrusive_list





Add Discussion as Guest

Log in