list(3C++) - list(3C++)
Standard C++ Library Copyright 1998, Rogue Wave Software, Inc.
NAMElist
- A sequence that supports bidirectional iterators.
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 han‐
dled 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_iteratorbegin() const;
Returns a constant bidirectional iterator that points to the first element.
iteratorend();
Returns a bidirectional iterator that points to the past-the-end value.
const_iteratorend() const;
Returns a constant bidirectional iterator that points to the past-the-end
value.
reverse_iteratorrbegin();
Returns a bidirectional iterator that points to the past-the-end value.
const_reverse_iteratorrbegin() const;
Returns a constant bidirectional iterator that points to the past-the-end
value.
reverse_iteratorrend();
Returns a bidirectional iterator that points to the first element.
const_reverse_iteratorrend() 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).
voidassign(size_type n, const T& t);
Erases all elements contained in self, then inserts n instances of the
value of t.
referenceback();
Returns a reference to the last element.
const_referenceback() const;
Returns a constant reference to the last element.
voidclear();
Erases all elements from the list.
boolempty() const;
Returns true if the size is zero.
iteratorerase(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.
iteratorerase(iterator first, iterator last);
Removes the elements in the range (first, last). Returns an iterator point‐
ing to the element following the element following the last deleted ele‐
ment, or end() if there were no elements after the deleted range.
referencefront();
Returns a reference to the first element.
const_referencefront() const;
Returns a constant reference to the first element.
iteratorinsert(iterator position, const T& x);
Inserts x before position. Returns an iterator that points to the inserted
x.
voidinsert(iterator position, size_type n, const T& x);
Inserts n copies of x before position.
template <class InputIterator>
voidinsert(iterator position, InputIterator first,
InputIterator last);
Inserts copies of the elements in the range [first, last) before position.
size_typemax_size() const;
Returns size() of the largest possible list.
voidmerge(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>
voidmerge(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.
voidpop_back();
Removes the last element.
voidpop_front();
Removes the first element.
voidpush_back(const T& x);
Appends a copy of x to the end of the list.
voidpush_front(const T& x);
Appends a copy of x to the front of the list.
voidremove(const T& value);
template <class Predicate>
voidremove_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.
voidresize(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.
voidresize(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.
voidreverse();
Reverses the order of the elements.
size_typesize() const;
Returns the number of elements.
voidsort();
Sorts self according to the operator<. sort maintains the relative order of
equal elements.
template <class Compare>
voidsort(Compare comp);
Sorts self according to a comparison function object, comp. This is also a
stable sort.
voidsplice(iterator position, list<T, Allocator>& x);
Inserts x before position, leaving x empty.
voidsplice(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.
voidsplice(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.
voidswap(list <T, Allocator>& x);
Exchanges self with x.
voidunique();
Erases copies of consecutive repeated elements leaving the first occur‐
rence.
template <class BinaryPredicate>
voidunique(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 lex‐
icographically 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 ALGORITHMStemplate <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 Outputcat bear antelopecougar bear antelopezebra cougar bear ocelot antelope ratantelope bear cougar ocelot rat zebraocelot rat zebraWARNINGS
Member function templates are used in all containers included in the
Standard Template Library. An example of this feature is the construc‐
tor 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 itera‐
tor as arguments. For compilers that do not support this feature, substitute
functions allow you to use an iterator obtained from the same type of con‐
tainer 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 inmerging 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 com‐
piler is one of these, you always need to supply the Allocator template argu‐
ment. 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
Rogue Wave Software 02 Apr 1998 list(3C++)