list

Container

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

A sequence that supports bidirectional iterators

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()

#include <list>

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

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 provide the following (where T is the type, t is a value of T and u is a const value of T):

  Default constructor   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

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

public:

// typedefs

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

   typename reverse_iterator;
   typename const_reverse_iterator;

// Construct/Copy/Destroy

   explicit list (const Allocator& = Allocator());
   explicit list (size_type, const Allocator& = Allocator());
   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);
   template <class Size, class T>
    void assign (Size n);
   template <class Size, class T>
    void assign (Size 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);
   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>&);

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

Creates a list of zero elements. The list will use the allocator alloc for all storage management.

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

Creates a list of length n, containing n copies of the default value for type T. Requires that T have a default constructor. The list will use the allocator alloc 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 will use 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 will use the allocator alloc for all storage management.

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

Copy constructor. Creates a copy of x.

~list();

The destructor. Releases any allocated memory for this list.

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.

allocator_type 
get_allocator() const;

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

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.

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

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

template <class Size, class T>
void 
assign(Size n);

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

template <class Size, class T>
void 
assign(Size 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);

Inserts a copy of the default value for type T before position. Returns an iterator that points to the inserted value. Requires that type T have a default constructor.

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 will 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 same elements in the two lists, elements from self will 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 referred 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. Requires that type T 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 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.

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

Equality operator. 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);

Inequality operator. 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).

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

Efficiently swaps the contents of a and b.

//
// list.cpp
//
 #include <list>
 #include <string>
 #include <iostream.h>
 // 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;
 }

Output : 
cat bear antelope
cougar bear antelope
zebra cougar bear ocelot antelope rat
antelope bear cougar ocelot rat zebra
ocelot  rat zebra

Member function templates are used in all containers provided by the Standard Template Library. An example of this feature is the constructor for list<T, Allocator> that takes two templated 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, we provide substitute functions that 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 provides 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, we were unable to provide a substitute function in addition to the merge that uses the operator< as the default. Thus, if your compiler does not support member function templates, all list mergers will use operator<.

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

list<int, allocator<int> >

instead of:

list<int>

allocator, Containers, Iterators

©Copyright 1996, Rogue Wave Software, Inc.