Class slist

Synopsis

#include <include/EASTL/slist.h>

template <typename T, typename Allocator = EASTLAllocatorType >
class slist : public SListBase<T, Allocator>

Description

slist

This is the equivalent of C++11's forward_list.

– size() is O(n) – Note that as of this writing, list::size() is an O(n) operation when EASTL_SLIST_SIZE_CACHE is disabled. That is, getting the size of the list is not a fast operation, as it requires traversing the list and counting the nodes. We could make list::size() be fast by having a member mSize variable. There are reasons for having such functionality and reasons for not having such functionality. We currently choose to not have a member mSize variable as it would add four bytes to the class, add a tiny amount of processing to functions such as insert and erase, and would only serve to improve the size function, but no others. The alternative argument is that the C++ standard states that std::list should be an O(1) operation (i.e. have a member size variable), most C++ standard library list implementations do so, the size is but an integer which is quick to update, and many users expect to have a fast size function. The EASTL_SLIST_SIZE_CACHE option changes this. To consider: Make size caching an optional template parameter.

Pool allocation If you want to make a custom memory pool for a list container, your pool needs to contain items of type slist::node_type. So if you have a memory pool that has a constructor that takes the size of pool items and the count of pool items, you would do this (assuming that MemoryPool implements the Allocator interface): typedef slist<Widget, MemoryPool> WidgetList; // Delare your WidgetList type. MemoryPool myPool(sizeof(WidgetList::node_type), 100); // Make a pool of 100 Widget nodes. WidgetList myList(&myPool); // Create a list that uses the pool.

Mentioned in

Inheritance

Ancestors: SListBase

Methods

slist overloadslist functions
assign overload
before_begin overload
begin overload
cbefore_begin
cbegin
cend
clear
DoAllocateNode
DoAssign overload
DoAssignValues
DoCreateNode overload
DoEraseAfter overload
DoFreeNode
DoInsertAfter overload
DoInsertValueAfter overload
DoInsertValuesAfter
DoSwap
emplace_after
emplace_front
empty
end overload
erase overload
erase_after overload
front overload
insert overload
insert_after overloadReturns an iterator pointing to the last inserted element, or position if insertion count is zero.
internalAllocator overload
internalNode overload
operator= overload
pop_front
previous overload
push_front overload

Mentioned in

remove
remove_if
reset_lose_memory
resize overload
reverse
size
sort 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.
splice overloadsplice splices to before position, like with the list container
splice_after overloadThe following splice_after funcions are deprecated, as they don't allow for recognizing the allocator, cannot maintain the source mSize, and are not in the C++11 Standard definition of std::forward_list (which is the equivalent of this class).
splice_after overloadThis function is deprecated
swap
validateNot yet implemented: void merge(this_type& x); void merge(this_type&& x); template <class Compare> void merge(this_type& x, Compare compare); template <class Compare> void merge(this_type&& x, Compare compare); If these get implemented then make sure to override them in fixed_slist.
validate_iterator

Source

Lines 239-438 in include/EASTL/slist.h. 

template <typename T, typename Allocator = EASTLAllocatorType >
class slist : public SListBase<T, Allocator>
{
    typedef SListBase<T, Allocator>              base_type;
    typedef slist<T, Allocator>                  this_type;
public:
    typedef T                                    value_type;
    typedef value_type*                          pointer;
    typedef const value_type*                    const_pointer;
    typedef value_type&                          reference;
    typedef const value_type&                    const_reference;
    typedef SListIterator<T, T*, T&>             iterator;
    typedef SListIterator<T, const T*, const T&> const_iterator;
    typedef typename base_type::size_type        size_type;
    typedef typename base_type::difference_type  difference_type;
    typedef typename base_type::allocator_type   allocator_type;
    typedef typename base_type::node_type        node_type;
    typedef typename base_type::base_node_type   base_node_type;
    using base_type::mNodeAllocator;
    using base_type::DoEraseAfter;
    using base_type::DoAllocateNode;
    using base_type::DoFreeNode;
    #if EASTL_SLIST_SIZE_CACHE
        using base_type::mSize;
    #endif
    using base_type::internalNode;
    using base_type::internalAllocator;
public:
    slist();
    slist(const allocator_type& allocator);
    explicit slist(size_type n, const allocator_type& allocator = EASTL_SLIST_DEFAULT_ALLOCATOR);
    slist(size_type n, const value_type& value, const allocator_type& allocator = EASTL_SLIST_DEFAULT_ALLOCATOR);
    slist(const this_type& x);
    slist(std::initializer_list<value_type> ilist, const allocator_type& allocator = EASTL_SLIST_DEFAULT_ALLOCATOR);
    slist(this_type&& x);
    slist(this_type&& x, const allocator_type& allocator);
    template <typename InputIterator>
    slist(InputIterator first, InputIterator last); // allocator arg removed because VC7.1 fails on the default arg. To do: Make a second version of this function without a default arg.
    this_type& operator=(const this_type& x);
    this_type& operator=(std::initializer_list<value_type>);
    this_type& operator=(this_type&& x);
    void swap(this_type& x);
    void assign(size_type n, const value_type& value);
    void assign(std::initializer_list<value_type> ilist);
    template <typename InputIterator>
    void assign(InputIterator first, InputIterator last);
    iterator       begin() EA_NOEXCEPT;
    const_iterator begin() const EA_NOEXCEPT;
    const_iterator cbegin() const EA_NOEXCEPT;
    iterator       end() EA_NOEXCEPT;
    const_iterator end() const EA_NOEXCEPT;
    const_iterator cend() const EA_NOEXCEPT;
    iterator       before_begin() EA_NOEXCEPT;
    const_iterator before_begin() const EA_NOEXCEPT;
    const_iterator cbefore_begin() const EA_NOEXCEPT;
    iterator        previous(const_iterator position);
    const_iterator  previous(const_iterator position) const;
    reference       front();
    const_reference front() const;
    template <class... Args>
    void emplace_front(Args&&... args);
    void      push_front(const value_type& value);
    reference push_front();
    void      push_front(value_type&& value);
    void      pop_front();
    bool      empty() const EA_NOEXCEPT;
    size_type size() const EA_NOEXCEPT;
    void resize(size_type n, const value_type& value);
    void resize(size_type n);
    iterator insert(const_iterator position);
    iterator insert(const_iterator position, const value_type& value);
    void     insert(const_iterator position, size_type n, const value_type& value);
    template <typename InputIterator>
    void insert(const_iterator position, InputIterator first, InputIterator last);
    // Returns an iterator pointing to the last inserted element, or position if insertion count is zero.
    iterator insert_after(const_iterator position);
    iterator insert_after(const_iterator position, const value_type& value);
    iterator insert_after(const_iterator position, size_type n, const value_type& value);
    iterator insert_after(const_iterator position, std::initializer_list<value_type> ilist);
    iterator insert_after(const_iterator position, value_type&& value);
    template <class... Args>
    iterator emplace_after(const_iterator position, Args&&... args);
    template <typename InputIterator>
    iterator insert_after(const_iterator position, InputIterator first, InputIterator last);
    iterator erase(const_iterator position);
    iterator erase(const_iterator first, const_iterator last);
    iterator erase_after(const_iterator position);
    iterator erase_after(const_iterator before_first, const_iterator last);
    void clear() EA_NOEXCEPT;
    void reset_lose_memory() EA_NOEXCEPT;    // This is a unilateral reset to an initially empty state. No destructors are called, no deallocation occurs.
    void remove(const value_type& value);
    template <typename Predicate>
    void remove_if(Predicate predicate);
    void reverse() EA_NOEXCEPT;
    // splice splices to before position, like with the list container. However, in order to do so 
    // it must walk the list from beginning to position, which is an O(n) operation that can thus 
    // be slow. It's recommended that the splice_after functions be used whenever possible as they are O(1).
    void splice(const_iterator position, this_type& x);
    void splice(const_iterator position, this_type& x, const_iterator i);
    void splice(const_iterator position, this_type& x, const_iterator first, const_iterator last);
    void splice(const_iterator position, this_type&& x);
    void splice(const_iterator position, this_type&& x, const_iterator i);
    void splice(const_iterator position, this_type&& x, const_iterator first, const_iterator last);
    void splice_after(const_iterator position, this_type& x);
    void splice_after(const_iterator position, this_type& x, const_iterator i);
    void splice_after(const_iterator position, this_type& x, const_iterator first, const_iterator last);
    void splice_after(const_iterator position, this_type&& x);
    void splice_after(const_iterator position, this_type&& x, const_iterator i);
    void splice_after(const_iterator position, this_type&& x, const_iterator first, const_iterator last);
    // The following splice_after funcions are deprecated, as they don't allow for recognizing 
    // the allocator, cannot maintain the source mSize, and are not in the C++11 Standard definition 
    // of std::forward_list (which is the equivalent of this class).
    void splice_after(const_iterator position, const_iterator before_first, const_iterator before_last);  // before_first and before_last come from a source container.
    void splice_after(const_iterator position, const_iterator previous);                                  // previous comes from a source container.
    // 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 sort();
    template <class Compare>
    void sort(Compare compare);
    // Not yet implemented:
    // void merge(this_type& x);
    // void merge(this_type&& x);
    // template <class Compare>
    // void merge(this_type& x, Compare compare);
    // template <class Compare>
    // void merge(this_type&& x, Compare compare);
    // If these get implemented then make sure to override them in fixed_slist.
    bool validate() const;
    int  validate_iterator(const_iterator i) const;
protected:
    node_type* DoCreateNode();
    template<typename... Args>
    node_type* DoCreateNode(Args&&... args);
    template <typename Integer>
    void DoAssign(Integer n, Integer value, true_type);
    template <typename InputIterator>
    void DoAssign(InputIterator first, InputIterator last, false_type);
    void DoAssignValues(size_type n, const value_type& value);
    template <typename InputIterator>
    node_type* DoInsertAfter(SListNodeBase* pNode, InputIterator first, InputIterator last);
    template <typename Integer>
    node_type* DoInsertAfter(SListNodeBase* pNode, Integer n, Integer value, true_type);
    template <typename InputIterator>
    node_type* DoInsertAfter(SListNodeBase* pNode, InputIterator first, InputIterator last, false_type);
    node_type* DoInsertValueAfter(SListNodeBase* pNode);
    node_type* DoInsertValuesAfter(SListNodeBase* pNode, size_type n, const value_type& value);
    template<typename... Args>
    node_type* DoInsertValueAfter(SListNodeBase* pNode, Args&&... args);
    void DoSwap(this_type& x);
}; // class slist




Add Discussion as Guest

Log in