Library: Containers
Does not inherit
A sequence that supports bidirectional iterators
#include <list>
namespace std {
template <class T, class Allocator = allocator<T> >
class list;
}
list is a type of sequence that supports bidirectional iterators. A list 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 members. Here 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 |
namespace std {
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 typename
Allocator::pointer pointer;
typedef typename
Allocator::const_pointer const_pointer;
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, 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();
};
// Nonmember 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 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 start, InputIterator finish,
const Allocator& alloc = Allocator());
Creates a list of length finish - start, filled with all values obtained by dereferencing the InputIterators on the range [start, finish). The list uses the allocator alloc for all storage management.
list(const list<T, Allocator>& x);
Creates a copy of x.
~list();
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 start, InputIterator finish);
If InputIterator is an integral type, the function calls assign(size_type(start), value_type (finish)). Otherwise, the function replaces elements in *this with copies of those in the range [start, finish). The function invalidates all iterators and references to elements in *this.
void assign(size_type n, const T& t);
Replaces elements in *this with n copies of t. The function invalidates all iterators and references to elements in *this.
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 start, iterator finish);
Removes the elements in the range [start, finish). 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 start,
InputIterator finish);
Inserts copies of the elements in the range [start, finish) 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, 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 start, iterator finish);
Moves the elements in the range [start, finish) in x to self, inserting them before position. The elements in the range [start, finish) 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);
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).
template <class T, class Allocator> void swap(list<T, Allocator>& a, list<T, Allocator>& b);
Swaps the contents of a and b.
//
// list.cpp
//
#include <algorithm> // for find
#include <list> // for list
#include <string> // for string
#include <iostream> // for cout, endl
// Print out a list of strings.
inline std::ostream&
operator<< (std::ostream &out,
const std::list<std::string,
std::allocator<std::string> > &l)
{
typedef std::ostream_iterator<std::string, char,
std::char_traits<char> >
ositer;
std::copy (l.begin (), l.end (), ositer (out," "));
return out;
}
int main ()
{
typedef std::list<std::string,
std::allocator<std::string> > List;
// Create a list of critters.
List critters;
// Insert several critters.
critters.insert (critters.begin (), "antelope");
critters.insert (critters.begin (), "bear");
critters.insert (critters.begin (), "cat");
// Print out the list.
std::cout << critters << std::endl;
// Change cat to cougar.
*std::find (critters.begin (),critters.end (), "cat")
= "cougar";
std::cout << critters << std::endl;
// Put a zebra at the beginning, an ocelot ahead of
// antelope, and a rat at the end.
critters.push_front ("zebra");
critters.insert (std::find (critters.begin (),
critters.end (),
"antelope"), "ocelot");
critters.push_back ("rat");
std::cout << critters << std::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 ();
std::cout << critters << std::endl;
// Now let's erase half of the critters.
List::size_type half = critters.size () / 2;
for (List::size_type i = 0; i != half; ++i)
critters.erase (critters.begin ());
std::cout << critters << std::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
Member function templates are used in all of the containers included in the Standard Template Library. For example, the constructor for list 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());
You cannot construct a list 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<.
allocator, Containers, Iterators
ISO/IEC 14882:1998 -- International Standard for Information Systems -- Programming Language C++, Section 23.2.2