Class intrusive_slist
Synopsis
#include <include/EASTL/bonus/intrusive_slist.h>
template <typename T = intrusive_slist_node>
class intrusive_slist : public intrusive_slist_base
Description
Mentioned in
- Best Practices / Consider slist instead of list.
- Best Practices / Avoid redundant end() and size() in loops.
- Best Practices / Cache list size if you want list::size() to be O(1).
- Best Practices / Know your container efficiencies.
- FAQ / EASTL coverage of std STL
- FAQ / Debug.2 How do I view containers if the visualizer/tooltip support is not present?
- Modules / Module List
- Modules / Module Behaviour
Inheritance
Ancestors: intrusive_slist_base
Methods
| intrusive_slist | Creates an empty list. | |
| before_begin overload | Returns iterator to position before begin. O(1). | |
| before_begin overload | Returns iterator to previous position. O(1). | |
| begin overload | Returns an iterator pointing to the first element in the list. O(1). | |
| begin overload | Returns a const_iterator pointing to the first element in the list. O(1). | |
| cbefore_begin | Returns iterator to previous position. O(1). | |
| cbegin | Returns a const_iterator pointing to the first element in the list. O(1). | |
| cend | Returns a const_iterator pointing one-after the last element in the list. O(1). | |
| contains | Returns true if the given element is in the list; O(n). Equivalent to (locate(x) != end()). | |
| end overload | Returns an iterator pointing one-after the last element in the list. O(1). | |
| end overload | Returns a const_iterator pointing one-after the last element in the list. O(1). | |
| erase overload | Erases the element pointed to by the iterator. O(n) | |
| erase overload | Erases elements within the iterator range [first, last). O(n). | |
| erase_after overload | Erases the element after the element pointed to by the iterator. O(1) | |
| erase_after overload | Erases elements within the iterator range [before_first, last). O(1). | |
| front overload | Returns a reference to the first element. The list must be empty. | |
| front overload | Returns a const reference to the first element. The list must be empty. | |
| insert | Inserts an element before the element pointed to by the iterator. O(n) | |
| insert_after | Inserts an element after the element pointed to by the iterator. O(1) | |
| locate overload | 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) | |
| locate overload | 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) | |
| pop_front | Removes an element from the back of the list; O(n). The element must be present, but is not deallocated. | |
| previous overload | Returns iterator to previous position. O(n). | |
| push_front | 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. | |
| splice overload | Moves the given element into this list before the element pointed to by position; O(n) | |
| splice overload | Moves the contents of a list into this list before the element pointed to by position; O(n) | |
| splice overload | Moves the given element pointed to i within the list x into the current list before the element pointed to by position; O(n). | |
| splice overload | Moves the range of elements [first, last) from list x into the current list before the element pointed to by position; O(n) | |
| splice_after overload | Moves the given element into this list after the element pointed to by position; O(1) | |
| splice_after overload | Moves the contents of a list into this list after the element pointed to by position; O(n) | |
| splice_after overload | Moves the element after xPrevious to be after position | |
| splice_after overload | Moves the elements in the range of [before_first+1, before_last+1) to be after position. O(1). | |
| swap | Swaps the contents of two intrusive lists; O(1). | |
| validate | ||
| validate_iterator |
Source
Lines 102-187 in include/EASTL/bonus/intrusive_slist.h.
template <typename T = intrusive_slist_node>
class intrusive_slist : public intrusive_slist_base
{
public:
typedef intrusive_slist<T> this_type;
typedef intrusive_slist_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 IntrusiveSListIterator<T, T*, T&> iterator;
typedef IntrusiveSListIterator<T, const T*, const T&> const_iterator;
public:
intrusive_slist(); ///< Creates an empty list.
//intrusive_slist(const this_type& x); ///< Creates an empty list; ignores the argument. To consider: Is this a useful function?
//this_type& operator=(const this_type& x); ///< Clears the list; ignores the argument. To consider: Is this a useful function?
iterator begin(); ///< Returns an iterator pointing to the first element in the list. O(1).
const_iterator begin() const; ///< Returns a const_iterator pointing to the first element in the list. O(1).
const_iterator cbegin() const; ///< Returns a const_iterator pointing to the first element in the list. O(1).
iterator end(); ///< Returns an iterator pointing one-after the last element in the list. O(1).
const_iterator end() const; ///< Returns a const_iterator pointing one-after the last element in the list. O(1).
const_iterator cend() const; ///< Returns a const_iterator pointing one-after the last element in the list. O(1).
iterator before_begin(); ///< Returns iterator to position before begin. O(1).
const_iterator before_begin() const; ///< Returns iterator to previous position. O(1).
const_iterator cbefore_begin() const; ///< Returns iterator to previous position. O(1).
iterator previous(const_iterator position); ///< Returns iterator to previous position. O(n).
const_iterator previous(const_iterator position) const; ///< Returns iterator to previous position. O(n).
reference front(); ///< Returns a reference to the first element. The list must be empty.
const_reference front() const; ///< Returns a const reference to the first element. The list must be empty.
void push_front(value_type& value); ///< 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 pop_front(); ///< Removes an element from the back of the list; O(n). The element must be present, but is not deallocated.
bool contains(const value_type& value) const; ///< Returns true if the given element is in the list; O(n). Equivalent to (locate(x) != end()).
iterator locate(value_type& value); ///< 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& value) 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(iterator position, value_type& value); ///< Inserts an element before the element pointed to by the iterator. O(n)
iterator insert_after(iterator position, value_type& value); ///< Inserts an element after the element pointed to by the iterator. O(1)
iterator erase(iterator position); ///< Erases the element pointed to by the iterator. O(n)
iterator erase_after(iterator position); ///< Erases the element after the element pointed to by the iterator. O(1)
iterator erase(iterator first, iterator last); ///< Erases elements within the iterator range [first, last). O(n).
iterator erase_after(iterator before_first, iterator last); ///< Erases elements within the iterator range [before_first, last). O(1).
void swap(this_type& x); ///< Swaps the contents of two intrusive lists; O(1).
void splice(iterator position, value_type& value); ///< Moves the given element into this list before the element pointed to by position; O(n).
///< Required: x must be in some list or have first/next pointers that point it itself.
void splice(iterator position, this_type& x); ///< Moves the contents of a list into this list before the element pointed to by position; O(n).
///< Required: &x != this (same as std::list).
void splice(iterator position, this_type& x, iterator xPosition); ///< Moves the given element pointed to i within the list x into the current list before
///< the element pointed to by position; O(n).
void splice(iterator position, this_type& x, iterator first, iterator last); ///< Moves the range of elements [first, last) from list x into the current list before
///< the element pointed to by position; O(n).
///< Required: position must not be in [first, last). (same as std::list).
void splice_after(iterator position, value_type& value); ///< Moves the given element into this list after the element pointed to by position; O(1).
///< Required: x must be in some list or have first/next pointers that point it itself.
void splice_after(iterator position, this_type& x); ///< Moves the contents of a list into this list after the element pointed to by position; O(n).
///< Required: &x != this (same as std::list).
void splice_after(iterator position, this_type& x, iterator xPrevious); ///< Moves the element after xPrevious to be after position. O(1).
///< Required: &x != this (same as std::list).
void splice_after(iterator position, this_type& x, iterator before_first, iterator before_last); ///< Moves the elements in the range of [before_first+1, before_last+1) to be after position. O(1).
bool validate() const;
int validate_iterator(const_iterator i) const;
}; // intrusive_slist