## list

    Container

- Summary
- Data Type and Member Function Indexes
- Synopsis
- Description
- Interface
- Constructors
- Destructors
- Assignment Operators
- Allocators
- Iterators
- Member Functions
- Non-member Operators
- Specialized Algorithms
- Example
- Warnings
- See Also

### Summary

A sequence that supports bidirectional iterators.

### Data Type and Member Function Indexes
(exclusive of constructors and destructors)

Member Functions
assign() back() begin() clear() empty() end() erase() front() get_allocator() insert() | max_size() merge() operator!=() operator>() operator>=() operator<() operator<=() operator=() operator==() pop_back() | pop_front() push_back() push_front() rbegin() remove() remove_if() rend() resize() reverse() size() | sort() splice() swap() unique()

### Synopsis

    #include <list>
    template <class T, class Allocator = allocator<T> >
    class list;

### Description

list<T,Allocator> is a type of sequence that supports bidirectional iterators. A list<T,Allocator> allows constant time insert and erase operations anywhere within the sequence, with storage management handled automatically. Constant time random access is not supported.

Any type used for the template parameter `T` must include the following (where `T` is the type, `t` is a `value` of `T` and `u` is a `const` `value` of `T`):

Copy constructors | `T(t)` and `T(u)`
Destructor | `t.~T()`
Address of | `&t` and `&u` yielding `T*` and `const T*` respectively
Assignment | `t = a` where `a` is a (possibly `const`) value of `T`

### Interface

    template <class T, class Allocator = allocator<T> >
     class list {

    public:

    // typedefs

       class iterator;
       class const_iterator;
       typedef typename
               Allocator::reference        reference;
       typedef typename
               Allocator::const_reference  const_reference;
       typedef typename
               Allocator::size_type        size_type;
       typedef typename
               Allocator::difference_type  difference_type;
       typedef T value_type;
       typedef Allocator allocator_type;

       typedef typename std::reverse_iterator<iterator>
                             reverse_iterator;
       typedef typename std::reverse_iterator<const_iterator>
                             const_reverse_iterator;

    // Construct/Copy/Destroy

       explicit list (const Allocator& = Allocator());
       explicit list (size_type);
       list (size_type, const T&, const Allocator& =
             Allocator())
       template <class InputIterator>
       list (InputIterator, InputIterator,
             const Allocator& = Allocator());
       list(const list<T, Allocator>& x);
       ~list();
       list<T,Allocator>& operator= (const list<T,Allocator>&);
       template <class InputIterator>
        void assign (InputIterator, InputIterator);
       void assign (size_type n, const T&);

       allocator_type get allocator () const;

    // Iterators

       iterator begin ();
       const_iterator begin () const;
       iterator end ();
       const_iterator end () const;
       reverse_iterator rbegin ();
       const_reverse_iterator rbegin () const;
       reverse_iterator rend ();
       const_reverse_iterator rend () const;

    // Capacity

       bool empty () const;
       size_type size () const;
       size_type max_size () const;
       void resize (size_type);
       void resize (size_type, T);

    // Element Access

       reference front ();
       const_reference front () const;
       reference back ();
       const_reference back () const;

    // Modifiers

       void push_front (const T&);
       void pop_front ();
       void push_back (const T&);
       void pop_back ();

       iterator insert (iterator, const T&);
       void insert (iterator, size_type, const T&);
       template <class InputIterator>
        void insert (iterator, InputIterator, InputIterator);

       iterator erase (iterator);
       iterator erase (iterator, iterator);

       void swap (list<T, Allocator>&);
       void clear ();

    // Special mutative operations on list

       void splice (iterator, list<T, Allocator>&);
       void splice (iterator, list<T, Allocator>&, iterator);
       void splice (iterator, list<T, Allocator>&, iterator,
                    iterator);

       void remove (const T&);
       template <class Predicate>
        void remove_if (Predicate);

       void unique ();
       template <class BinaryPredicate>
        void unique (BinaryPredicate);

       void merge (list<T, Allocator>&);
       template <class Compare>
        void merge (list<T, Allocator>&, Compare);

       void sort ();
       template <class Compare>
        void sort (Compare);

       void reverse();
    };

    // Non-member List Operators

    template <class T, class Allocator>
     bool operator== (const list<T, Allocator>&,
                      const list<T, Allocator>&);

    template <class T, class Allocator>
     bool operator!= (const list<T, Allocator>&,
                      const list<T, Allocator>&);

    template <class T, class Allocator>
     bool operator< (const list<T, Allocator>&,
                     const list<T, Allocator>&);

    template <class T, class Allocator>
     bool operator> (const list<T, Allocator>&,
                     const list<T, Allocator>&);

    template <class T, class Allocator>
     bool operator<= (const list<T, Allocator>&,
                     const list<T, Allocator>&);

    template <class T, class Allocator>
     bool operator>= (const list<T, Allocator>&,
                     const list<T, Allocator>&);

    // Specialized Algorithms

    template <class T, class Allocator>
    void swap (list<T,Allocator>&, list<T, Allocator>&);

### Constructors

    explicit list(const Allocator& alloc = Allocator());

Creates a list of zero elements. The list uses the allocator `alloc` for all storage management.

    explicit list(size_type n);

Creates a list of length `n`, containing `n` copies of the default value for type `T`. `T` must have a default constructor. The list uses the allocator Allocator() for all storage management.

    list(size_type n, const T& value,
          const Allocator& alloc = Allocator());

Creates a list of length `n`, containing `n` copies of `value`. The list uses the allocator `alloc` for all storage management.

    template <class InputIterator>
    list(InputIterator first, InputIterator last,
          const Allocator& alloc = Allocator());

Creates a list of length `last - first`, filled with all values obtained by dereferencing the `InputIterators` on the range `[first, last)`. The list uses the allocator `alloc` for all storage management.

    list(const list<T, Allocator>& x);

Creates a copy of `x`.

### Destructors

    ~list();

Releases any allocated memory for this list.

### Assignment Operators

    list<T, Allocator>&
    operator=(const list<T, Allocator>& x)

Erases all elements in self, then inserts into self a copy of each element in `x`. Returns a reference to `*this`.

### Allocators

    allocator_type
    get_allocator() const;

Returns a copy of the allocator used by self for storage management.

### Iterators

    iterator
    begin();

Returns a bidirectional iterator that points to the first element.

    const_iterator
    begin() const;

Returns a constant bidirectional iterator that points to the first element.

    iterator
    end();

Returns a bidirectional iterator that points to the past-the-end value.

    const_iterator
    end() const;

Returns a constant bidirectional iterator that points to the past-the-end value.

    reverse_iterator
    rbegin();

Returns a bidirectional iterator that points to the past-the-end value.

    const_reverse_iterator
    rbegin() const;

Returns a constant bidirectional iterator that points to the past-the-end value.

    reverse_iterator
    rend();

Returns a bidirectional iterator that points to the first element.

    const_reverse_iterator
    rend() const;

Returns a constant bidirectional iterator that points to the first element.

### Member Functions

    template <class InputIterator>
    void
    assign(InputIterator first, InputIterator last);

Erases all elements contained in self, then inserts new elements from the range `[first, last)`.

    void
    assign(size_type n, const T& t);

Erases all elements contained in self, then inserts `n` instances of the `value` of `t.`

    reference
    back();

Returns a `reference` to the last element.

    const_reference
    back() const;

Returns a constant reference to the last element.

    void
    clear();

Erases all elements from the list.

    bool
    empty() const;

Returns `true` if the `size` is zero.

    iterator
    erase(iterator position);

Removes the element pointed to by `position`. Returns an iterator pointing to the element following the deleted element, or `end()` if the deleted item was the last one in this list.

    iterator
    erase(iterator first, iterator last);

Removes the elements in the range (`first, last`). Returns an iterator pointing to the element following the element following the last deleted element, or `end()` if there were no elements after the deleted range.

    reference
    front();

Returns a reference to the first element.

    const_reference
    front() const;

Returns a constant reference to the first element.

    iterator
    insert(iterator position, const T& x);

Inserts `x` before `position`. Returns an iterator that points to the inserted `x`.

    void
    insert(iterator position, size_type n, const T& x);

Inserts `n` copies of `x` before `position`.

    template <class InputIterator>
    void
    insert(iterator position, InputIterator first,
            InputIterator last);

Inserts copies of the elements in the range `[first, last)` before `position`.

    size_type
    max_size() const;

Returns `size()` of the largest possible list.

    void
    merge(list<T, Allocator>& x);

Merges a sorted `x` with a sorted self using `operator<`. For equal elements in the two lists, elements from self always precede the elements from `x`. The `merge` function leaves `x` empty.

    template <class Compare>
    void
    merge(list<T, Allocator>& x, Compare comp);

Merges a sorted `x` with sorted self using a compare function object, `comp`. For identical elements in the two lists, elements from self always precede the elements from `x`. The `merge` function leaves `x` empty.

    void
    pop_back();

Removes the last element.

    void
    pop_front();

Removes the first element.

    void
    push_back(const T& x);

Appends a copy of `x` to the end of the list.

    void
    push_front(const T& x);

Appends a copy of `x` to the front of the list.

    void
    remove(const T& value);
    template <class Predicate>
    void
    remove_if(Predicate pred);

Removes all elements in the list referenced by the list iterator `i` for which `*i == value` or `pred(*i) == true`, whichever is applicable. This is a stable operation. The relative order of list items that are not removed is preserved.

    void
    resize(size_type sz);

Alters the size of self. If the new size ( `sz` ) is greater than the current size, `sz`-`size()` copies of the default value of type `T` are inserted at the end of the list. If the new size is smaller than the current capacity, then the list is truncated by erasing `size()-sz` elements off the end. Otherwise, no action is taken. Type `T` must have a default constructor.

    void
    resize(size_type sz, T c);

Alters the size of self. If the new size ( `sz` ) is greater than the current size, `sz`-`size() c`'s are inserted at the end of the list. If the new size is smaller than the current capacity, then the list is truncated by erasing `size()-sz` elements off the end. Otherwise, no action is taken.

    void
    reverse();

Reverses the order of the elements.

    size_type
    size() const;

Returns the number of elements.

    void
    sort();

Sorts self according to the `operator<`. `sort` maintains the relative order of equal elements.

    template <class Compare>
    void
    sort(Compare comp);

Sorts self according to a comparison function object, `comp`. This is also a stable sort.

    void
    splice(iterator position, list<T, Allocator>& x);

Inserts `x` before `position`, leaving `x` empty.

    void
    splice(iterator position, list<T, Allocator>& x,
            iterator i);

Moves the elements pointed to by iterator `i` in `x` to self, inserting it before `position`. The element is removed from `x`.

    void
    splice(iterator position, list<T, Allocator >& x,
            iterator first, iterator last);

Moves the elements in the range `[first, last)` in `x` to self, inserting them before `position`. The elements in the range `[first, last)` are removed from `x`.

    void
    swap(list <T, Allocator>& x);

Exchanges self with `x`.

    void
    unique();

Erases copies of consecutive repeated elements leaving the first occurrence.

    template <class BinaryPredicate>
    void
    unique(BinaryPredicate binary_pred);

Erases consecutive elements matching a `true` condition of the `binary_pred`. The first occurrence is not removed.

### Non-member Operators

    template <class T, class Allocator>
    bool operator==(const list<T, Allocator>& x,
                     const list<T, Allocator>& y);

Returns `true` if `x` is the same as `y`.

    template <class T, class Allocator>
    bool operator!=(const list<T, Allocator>& x,
                     const list<T, Allocator>& y);

Returns !`(x==y)`.

    template <class T, class Allocator>
    bool operator<(const list<T, Allocator>& x,
                    const list<T,Allocator>& y);

Returns `true` if the sequence defined by the elements contained in `x` is lexicographically less than the sequence defined by the elements contained in `y`.

    template <class T, class Allocator>
    bool operator>(const list<T, Allocator>& x,
                    const list<T,Allocator>& y);

Returns `y < x`.

    template <class T, class Allocator>
    bool operator<=(const list<T, Allocator>& x,
                    const list<T,Allocator>& y);

Returns !`(y < x)`.

    template <class T, class Allocator>
    bool operator>=(const list<T, Allocator>& x,
                    const list<T,Allocator>& y);

Returns !`(x < y)`.

### Specialized Algorithms

    template <class T, class Allocator>
    void swap(list<T, Allocator>& a, list<T, Allocator>& b);

Swaps the contents of `a` and `b`.

### Example

    //
    // list.cpp
    //
     #include <list>
     #include <string>
     #include <iostream>
     using namespace std;
     // Print out a list of strings
     ostream& operator<<(ostream& out, const list<string>& l)
     {

       copy(l.begin(), l.end(),
            ostream_iterator<string,char>(cout," "));
       return out;
     }
     int main(void)
     {

       // create a list of critters
       list<string> critters;
       int i;

       // insert several critters
       critters.insert(critters.begin(),"antelope");
       critters.insert(critters.begin(),"bear");
       critters.insert(critters.begin(),"cat");

       // print out the list
       cout << critters << endl;

       // Change cat to cougar
       *find(critters.begin(),critters.end(),"cat") = "cougar";
       cout << critters << endl;

       // put a zebra at the beginning
       // an ocelot ahead of antelope
       // and a rat at the end
       critters.push_front("zebra");
       critters.insert(find(critters.begin(),critters.end(),
                       "antelope"),"ocelot");
       critters.push_back("rat");
       cout << critters << endl;

       // sort the list (Use list's sort function since the
       // generic algorithm requires a random access iterator
       // and list only provides bidirectional)
       critters.sort();
       cout << critters << endl;

       // now let's erase half of the critters
       int half = critters.size() >> 1;
       for(i = 0; i < half; ++i) {
         critters.erase(critters.begin());
       }
       cout << critters << endl;
       return 0;
     }

Program Output

    cat bear antelope
    cougar bear antelope
    zebra cougar bear ocelot antelope rat
    antelope bear cougar ocelot rat zebra
    ocelot rat zebra

### Warnings

Member function templates are used in all containers included in the Standard Template Library. An example of this feature is the constructor for list<T, Allocator> that takes two templatized iterators:

    template <class InputIterator>
    list (InputIterator, InputIterator,
          const Allocator& = Allocator());

list also has an `insert` function of this type. These functions, when not restricted by compiler limitations, allow you to use any type of input iterator as arguments. For compilers that do not support this feature, substitute functions allow you to use an iterator obtained from the same type of container as the one you are constructing (or calling a member function on), or you can use a pointer to the type of element you have in the container.

For example, if your compiler does not support member function templates, you can construct a list in the following two ways:

    int intarray[10];
    list<int> first_list(intarray,intarray + 10);
    list<int> second_list(first_list.begin(),first_list.end());

But not this way:

    list<long> long_list(first_list.begin(),first_list.end());

since the `long_list` and `first_list` are not the same type.

Additionally, list includes a `merge` function of this type.

    template <class Compare> void merge (list<T, Allocator>&,
      Compare);

This function allows you to specify a compare function object to be used in merging two lists. In this case, a substitute function is not included with the merge that uses the `operator<` as the default. Thus, if your compiler does not support member function templates, all list merges use `operator<`.

Also, many compilers do not support default template arguments. If your compiler is one of these, you always need to supply the `Allocator` template argument. For instance, you have to write:

`list<int, allocator<int> >`

instead of:

`list<int>`

If your compiler does not support namespaces, then you do not need the using declaration for `std`.

### See Also

allocator, Containers, Iterators

Copyright (c) 1998, Rogue Wave Software, Inc.
Send mail to report errors or comment on the documentation.
OEM Release, June 1998