List

list

Sequence

list is a kind of sequence (See Sequences.) that supports bidirectional iterators and allows constant time insert and erase operations anywhere within the sequence, with storage management handled automatically. Unlike vectors and deques, fast random access to list elements is not supported, but many algorithms only need sequential access anyway. See Reversible Container.

template 
class Allocator = allocator> class list {
public:
// typedefs:
    typedef iterator
    typedef const_iterator
    typedef Allocator::pointer pointer
    typedef Allocator::reference reference
    typedef Allocator::const_reference const_reference
    typedef size_type
    typedef difference_type
    typedef T value_type
    typedef reverse_iterator
    typedef const_reverse_iterator;

// allocation/deallocation:
    list()
    list(size_type n, const T& value = T())
    template 
    list(InputIterator first, InputIterator last)
    list(const list& x)
    ~list()
    list& operator=(const list& x)
    void swap(list& x);

// accessors:
    iterator begin()
    const_iterator begin() const
    iterator end()
    const_iterator end() const
    reverse_iterator rbegin()
    const_reverse_iterator rbegin();
    reverse_iterator rend();
    const_reverse_iterator rend();
    bool empty() const;
    size_type size() const;
    size_type max_size() const;
    reference front();
    const_reference front() const;
    reference back();
    const_reference back() const;

// insert/erase:
    void push_front(const T& x);
    void push_back(const T& x);
    iterator insert(iterator position, const T& x = T());
    void insert(iterator position, size_type n, const T& x);
    template 
    void insert(iterator position, InputIterator first, InputIterator last);
    void pop_front();
    void pop_back();
    void erase(iterator position);
    void erase(iterator first, iterator last);

// special mutative operations on list:
    void splice(iterator position, list& x);
    void splice(iterator position, list& x, iterator i);
    void splice(iterator position, list& x,
                iterator first, iterator last);
    void remove(const T& value);
    template  void remove_if(Predicate pred);
    void unique();
    template  void unique(BinaryPredicate binary_pred);
    void merge(list& x);
    template  void merge(list& x, Compare comp);
    void reverse();
    void sort();
    template  void sort(Compare comp);
};

template 
bool operator==(const list& x, const list& y);

template 
bool operator<(const list& x, const list& y);

iterator

Typedef on list

iterator is a bidirectional iterator referring to T. The exact type is implementation dependent and determined by Allocator.

const_iterator

Typedef on list

const_iterator is a constant bidirectional iterator referring to const T. The exact type is implementation dependent and determined by Allocator. It is guaranteed that there is a constructor for const_iterator out of iterator.

size_type

Typedef on list

size_type is an unsigned integral type. The exact type is implementation dependent and determined by Allocator.

difference_type

Typedef on list

difference_type is a signed integral type. The exact type is implementation dependent and determined by Allocator.

insert (iterator position, const T& x = T());	Method on list
insert (iterator position, size_type n, const T& x);	Method on list
insert (iterator position, InputIterator first, InputIterator last);	Method on list

insert does not affect the validity of iterators and references. Insertion of a single element into a list takes constant time and exactly one call to the copy constructor of T. Insertion of multiple elements into a list is linear in the number of elements inserted, and the number of calls to the copy constructor of T is exactly equal to the number of elements inserted.

erase (iterator position);	Method on list
erase (iterator first, iterator last);	Method on list

erase invalidates only the iterators and references to the erased elements. Erasing a single element is a constant time operation with a single call to the destructor of T. Erasing a range in a list is linear time in the size of the range and the number of calls to the destructor of type T is exactly equal to the size of the range.

Since lists allow fast insertion and erasing from the middle of a list, certain operations are provided specifically for them:

list provides three splice operations that destructively move elements from one list to another:

void splice (iterator position, list& x)

Method on list

inserts the contents of x before position and x becomes empty. It takes constant time. The result is undefined if &x == this.

void splice (iterator position, list& x, iterator i)

Method on list

void splice (iterator position, list& x, iterator first, iterator last)

Method on list

inserts elements in the range [first, last) before position and removes the elements from x. It takes constant time if &x == this; otherwise, it takes linear time. [first, last) is a valid range in x. The result is undefined if position is an iterator in the range [first, last).

remove (const T& value);

Method on list

remove erases all the elements in the list referred by the list iterator i for which the following conditions hold: *i == value, pred(*i) == true. remove is stable, that is, the relative order of the elements that are not removed is the same as their relative order in the original list. Exactly size() applications of the corresponding predicate are done.

unique

Method on list

unique erases all but the first element from every consecutive group of equal elements in the list. Exactly size() - 1 applications of the corresponding binary predicate are done.

merge (list& x);	Method on list
merge (list& x, Compare comp);	Method on list

merge merges the argument list into the list (both are assumed to be sorted). The merge is stable, that is, for equal elements in the two lists, the elements from the list always precede the elements from the argument list. x is empty after the merge. At most size() + x.size() - 1 comparisons are done.

reverse

Method on list

reverse reverses the order of the elements in the list. It is linear time.

sort	Method on list

sort sorts the list according to the operator< or a compare function object. `size().