.\" ident @(#)list.3 .\" Standard Template Library .\" $$RW_INSERT_HEADER "slyrs.man" .TH list 3C++ "02 Apr 1998" "Rogue Wave Software" "-" .ce2 Standard C++ Library Copyright 1998, Rogue Wave Software, Inc. .SH NAME \f2list\fP \ - A sequence that supports bidirectional iterators. .SH SYNOPSIS .br #include .br template > .br class list; .SH DESCRIPTION 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 \f2T\fP must include the following (where \f2T\fP is the type, \f2t\fP is a \f2value\fP of \f2T\fP and \f2u\fP is a \f2const\fP \f2value\fP of \f2T\fP): .HP 20 Copy constructors \f2T(t)\fP and \f2T(u)\fP .HP 0 .HP 13 Destructor \f2t.~T()\fP .HP 0 .HP 13 Address of \f2&t\fP and \f2&u\fP yielding \f2T*\fP and \f2const T*\fP respectively .HP 0 .HP 13 Assignment \f2t = a\fP where \f2a\fP is a (possibly \f2const\fP) value of \f2T\fP .HP 0 .SH INTERFACE .br template > .br class list { .br .br public: .br .br // typedefs .br .RE .RS 2 class iterator; .br class const_iterator; .br typedef typename .RE .RS 10 Allocator::reference reference; .RE .RS 2 typedef typename .RE .RS 10 Allocator::const_reference const_reference; .RE .RS 2 typedef typename .RE .RS 10 Allocator::size_type size_type; .RE .RS 2 typedef typename .RE .RS 10 Allocator::difference_type difference_type; .RE .RS 2 typedef T value_type; .br typedef Allocator allocator_type; .RE .RS 0 .RE .RS 2 typedef typename std::reverse_iterator .RE .RS 24 reverse_iterator; .RE .RS 2 typedef typename std::reverse_iterator .RE .RS 24 const_reverse_iterator; .RE .RS 0 .br // Construct/Copy/Destroy .br .RE .RS 2 explicit list (const Allocator& = Allocator()); .br explicit list (size_type); .br list (size_type, const T&, const Allocator& = .RE .RS 8 Allocator()) .RE .RS 2 template .br list (InputIterator, InputIterator, .RE .RS 8 const Allocator& = Allocator()); .RE .RS 2 list(const list& x); .RE .RS 3 ~list(); .RE .RS 2 list& operator= (const list&); .br template .RE .RS 3 void assign (InputIterator, InputIterator); .RE .RS 2 void assign (size_type n, const T&); .RE .RS 0 .RE .RS 2 allocator_type get allocator () const; .RE .RS 0 .br // Iterators .br .RE .RS 2 iterator begin (); .br const_iterator begin () const; .br iterator end (); .br const_iterator end () const; .br reverse_iterator rbegin (); .br const_reverse_iterator rbegin () const; .br reverse_iterator rend (); .br const_reverse_iterator rend () const; .RE .RS 0 .br // Capacity .br .RE .RS 2 bool empty () const; .br size_type size () const; .br size_type max_size () const; .br void resize (size_type); .br void resize (size_type, T); .RE .RS 0 .br // Element Access .br .RE .RS 2 reference front (); .br const_reference front () const; .br reference back (); .br const_reference back () const; .RE .RS 0 .br // Modifiers .br .RE .RS 2 void push_front (const T&); .br void pop_front (); .br void push_back (const T&); .br void pop_back (); .RE .RS 0 .RE .RS 2 iterator insert (iterator, const T&); .br void insert (iterator, size_type, const T&); .br template .RE .RS 3 void insert (iterator, InputIterator, InputIterator); .RE .RS 0 .RE .RS 2 iterator erase (iterator); .br iterator erase (iterator, iterator); .RE .RS 0 .RE .RS 2 void swap (list&); .br void clear (); .RE .RS 0 .br // Special mutative operations on list .br .RE .RS 2 void splice (iterator, list&); .br void splice (iterator, list&, iterator); .br void splice (iterator, list&, iterator, .RE .RS 15 iterator); .RE .RS 0 .RE .RS 2 void remove (const T&); .br template .RE .RS 3 void remove_if (Predicate); .RE .RS 0 .RE .RS 2 void unique (); .br template .RE .RS 3 void unique (BinaryPredicate); .RE .RS 0 .RE .RS 2 void merge (list&); .br template .RE .RS 3 void merge (list&, Compare); .RE .RS 0 .RE .RS 2 void sort (); .br template .RE .RS 3 void sort (Compare); .RE .RS 0 .RE .RS 2 void reverse(); .RE .RS 0 }; .br .br .br .br // Non-member List Operators .br .br template .br bool operator== (const list&, .RE .RS 17 const list&); .RE .RS 0 .br template .br bool operator!= (const list&, .RE .RS 17 const list&); .RE .RS 0 .br template .br bool operator< (const list&, .RE .RS 16 const list&); .RE .RS 0 .br template .br bool operator> (const list&, .RE .RS 16 const list&); .RE .RS 0 .br template .br bool operator<= (const list&, .RE .RS 16 const list&); .RE .RS 0 .br template .br bool operator>= (const list&, .RE .RS 16 const list&); .RE .RS 0 .br // Specialized Algorithms .br .br template .br void swap (list&, list&); .SH CONSTRUCTORS .br explicit list(const Allocator& alloc = Allocator()); .RE .RS 3 Creates a list of zero elements. The list uses the allocator \f2alloc\fP for all storage management. .RE .br explicit list(size_type n); .RE .RS 3 Creates a list of length \f2n\fP, containing \f2n\fP copies of the default value for type \f2T\fP. \f2T\fP must have a default constructor. The list uses the allocator Allocator() for all storage management. .RE .br list(size_type n, const T& value, .RE .RS 5 const Allocator& alloc = Allocator()); .RE .RS 3 Creates a list of length \f2n\fP, containing \f2n\fP copies of \f2value\fP. The list uses the allocator \f2alloc\fP for all storage management. .RE .RE .RS 0 template .br list(InputIterator first, InputIterator last, .RE .RS 5 const Allocator& alloc = Allocator()); .RE .RS 3 Creates a list of length \f2last - first\fP, filled with all values obtained by dereferencing the \f2InputIterators\fP on the range\f2 [first, last)\fP. The list uses the allocator \f2alloc\fP for all storage management. .RE .RE .RS 0 list(const list& x); .RE .RS 3 Creates a copy of \f2x\fP. .RE .SH DESTRUCTORS .br ~list(); .RE .RS 3 Releases any allocated memory for this list. .RE .SH ASSIGNMENT OPERATORS .br list& .br operator=(const list& x) .RE .RS 3 Erases all elements in self, then inserts into self a copy of each element in \f2x\fP. Returns a reference to \f2*this\fP. .RE .SH ALLOCATORS .br allocator_type .br get_allocator() const; .RE .RS 3 Returns a copy of the allocator used by self for storage management. .RE .SH ITERATORS .br iterator .br begin(); .RE .RS 3 Returns a bidirectional iterator that points to the first element. .RE .br const_iterator .br begin() const; .RE .RS 3 Returns a constant bidirectional iterator that points to the first element. .RE .br iterator .br end(); .RE .RS 3 Returns a bidirectional iterator that points to the past-the-end value. .RE .br const_iterator .br end() const; .RE .RS 3 Returns a constant bidirectional iterator that points to the past-the-end value. .RE .br reverse_iterator .br rbegin(); .RE .RS 3 Returns a bidirectional iterator that points to the past-the-end value. .RE .br const_reverse_iterator .br rbegin() const; .RE .RS 3 Returns a constant bidirectional iterator that points to the past-the-end value. .RE .br reverse_iterator .br rend(); .RE .RS 3 Returns a bidirectional iterator that points to the first element. .RE .br const_reverse_iterator .br rend() const; .RE .RS 3 Returns a constant bidirectional iterator that points to the first element. .RE .SH MEMBER FUNCTIONS .br template .br void .br assign(InputIterator first, InputIterator last); .RE .RS 3 Erases all elements contained in self, then inserts new elements from the range \f2[first, last)\fP. .RE .br void .br assign(size_type n, const T& t); .RE .RS 3 Erases all elements contained in self, then inserts \f2n\fP instances of the \f2value\fP of \f2t.\fP .RE .br reference .br back(); .RE .RS 3 Returns a \f2reference\fP to the last element. .RE .br const_reference .br back() const; .RE .RS 3 Returns a constant reference to the last element. .RE .br void .br clear(); .RE .RS 3 Erases all elements from the list. .RE .br bool .br empty() const; .RE .RS 3 Returns \f2true\fP if the \f2size\fP is zero. .RE .br iterator .br erase(iterator position); .RE .RS 3 Removes the element pointed to by \f2position\fP. Returns an iterator pointing to the element following the deleted element, or \f2end()\fP if the deleted item was the last one in this list. .RE .br iterator .br erase(iterator first, iterator last); .RE .RS 3 Removes the elements in the range (\f2first, last\fP). Returns an iterator pointing to the element following the element following the last deleted element, or \f2end()\fP if there were no elements after the deleted range. .RE .br reference .br front(); .RE .RS 3 Returns a reference to the first element. .RE .br const_reference .br front() const; .RE .RS 3 Returns a constant reference to the first element. .RE .br iterator .br insert(iterator position, const T& x); .RE .RS 3 Inserts \f2x\fP before \f2position\fP. Returns an iterator that points to the inserted \f2x\fP. .RE .br void .br insert(iterator position, size_type n, const T& x); .RE .RS 3 Inserts \f2n\fP copies of \f2x\fP before \f2position\fP. .RE .br template .br void .br insert(iterator position, InputIterator first, .RE .RS 7 InputIterator last); .RE .RS 3 Inserts copies of the elements in the range \f2[first, last)\fP before \f2position\fP. .RE .RE .RS 0 size_type .br max_size() const; .RE .RS 3 Returns\f2 size()\fP of the largest possible list. .RE .br void .br merge(list& x); .RE .RS 3 Merges a sorted \f2x\fP with a sorted self using \f2operator<\fP. For equal elements in the two lists, elements from self always precede the elements from \f2x\fP. The \f2merge\fP function leaves \f2x\fP empty. .RE .br template .br void .br merge(list& x, Compare comp); .RE .RS 3 Merges a sorted \f2x\fP with sorted self using a compare function object, \f2comp\fP. For identical elements in the two lists, elements from self always precede the elements from \f2x\fP. The \f2merge\fP function leaves \f2x\fP empty. .RE .br void .br pop_back(); .RE .RS 3 Removes the last element. .RE .br void .br pop_front(); .RE .RS 3 Removes the first element. .RE .br void .br push_back(const T& x); .RE .RS 3 Appends a copy of \f2x\fP to the end of the list. .RE .br void .br push_front(const T& x); .RE .RS 3 Appends a copy of \f2x\fP to the front of the list. .RE .br void .br remove(const T& value); .br template .br void .br remove_if(Predicate pred); .RE .RS 3 Removes all elements in the list referenced by the list iterator \f2i\fP for which \f2*i == value \fPor\f2 pred(*i) == true\fP, whichever is applicable. This is a stable operation. The relative order of list items that are not removed is preserved. .RE .br void .br resize(size_type sz); .RE .RS 3 Alters the size of self. If the new size ( \f2sz\fP ) is greater than the current size, \f2sz\fP-\f2size() \fPcopies of the default value of type\f2 T \fPare inserted at the end of the list. If the new size is smaller than the current capacity, then the list is truncated by erasing \f2size()-sz\fP elements off the end. Otherwise, no action is taken. Type \f2T\fP must have a default constructor. .RE .br void .br resize(size_type sz, T c); .RE .RS 3 Alters the size of self. If the new size ( \f2sz\fP ) is greater than the current size, \f2sz\fP-\f2size() c\fP'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 \f2size()-sz\fP elements off the end. Otherwise, no action is taken. .RE .br void .br reverse(); .RE .RS 3 Reverses the order of the elements. .RE .br size_type .br size() const; .RE .RS 3 Returns the number of elements. .RE .br void .br sort(); .RE .RS 3 Sorts self according to the \f2operator<\fP. \f2sort\fP maintains the relative order of equal elements. .RE .br template .br void .br sort(Compare comp); .RE .RS 3 Sorts self according to a comparison function object, \f2comp\fP. This is also a stable sort. .RE .br void .br splice(iterator position, list& x); .RE .RS 3 Inserts \f2x \fPbefore \f2position\fP, leaving \f2x \fPempty. .RE .br void .br splice(iterator position, list& x, .RE .RS 7 iterator i); .RE .RS 3 Moves the elements pointed to by iterator \f2i\fP in \f2x\fP to self, inserting it before \f2position\fP. The element is removed from \f2x\fP. .RE .RE .RS 0 void .br splice(iterator position, list& x, .RE .RS 7 iterator first, iterator last); .RE .RS 3 Moves the elements in the range \f2[first, last)\fP in \f2x\fP to self, inserting them before \f2position\fP. The elements in the range \f2[first, last)\fP are removed from \f2x\fP. .RE .RE .RS 0 void .br swap(list & x); .RE .RS 3 Exchanges self with \f2x\fP. .RE .br void .br unique(); .RE .RS 3 Erases copies of consecutive repeated elements leaving the first occurrence. .RE .br template .br void .br unique(BinaryPredicate binary_pred); .RE .RS 3 Erases consecutive elements matching a \f2true\fP condition of the \f2binary_pred\fP. The first occurrence is not removed. .RE .SH NON-MEMBER OPERATORS .br template .br bool operator==(const list& x, .RE .RS 16 const list& y); .RE .RS 3 Returns \f2true\fP if \f2x\fP is the same as \f2y\fP. .RE .RE .RS 0 template .br bool operator!=(const list& x, .RE .RS 16 const list& y); .RE .RS 3 Returns !\f2(x==y)\fP. .RE .RE .RS 0 template .br bool operator<(const list& x, .RE .RS 15 const list& y); .RE .RS 3 Returns \f2true\fP if the sequence defined by the elements contained in \f2x\fP is lexicographically less than the sequence defined by the elements contained in \f2y\fP. .RE .RE .RS 0 template .br bool operator>(const list& x, .RE .RS 15 const list& y); .RE .RS 3 Returns \f2y < x\fP. .RE .RE .RS 0 template .br bool operator<=(const list& x, .RE .RS 15 const list& y); .RE .RS 3 Returns !\f2(y < x)\fP. .RE .RE .RS 0 template .br bool operator>=(const list& x, .RE .RS 15 const list& y); .RE .RS 3 Returns !\f2(x < y)\fP. .RE .SH SPECIALIZED ALGORITHMS .RE .RS 0 template .br void swap(list& a, list& b); .RE .RS 3 Swaps the contents of \f2a\fP and \f2b\fP. .RE .SH EXAMPLE .br // .br // list.cpp .br // .RE .RS 1 #include .br #include .br #include .RE .RS 0 using namespace std; .RE .RS 1 // Print out a list of strings .RE .RS 0 ostream& operator<<(ostream& out, const list& l) .RE .RS 1 { .RE .RS 0 .RE .RS 2 copy(l.begin(), l.end(), .RE .RS 7 ostream_iterator(cout," ")); .RE .RS 2 return out; .RE .RS 1 } .RE .RS 0 int main(void) .RE .RS 1 { .RE .RS 0 .RE .RS 3 // create a list of critters .RE .RS 2 list critters; .br int i; .RE .RS 0 .RE .RS 3 // insert several critters .RE .RS 2 critters.insert(critters.begin(),"antelope"); .br critters.insert(critters.begin(),"bear"); .br critters.insert(critters.begin(),"cat"); .RE .RS 0 .RE .RS 3 // print out the list .RE .RS 2 cout << critters << endl; .RE .RS 3 .br // Change cat to cougar .br *find(critters.begin(),critters.end(),"cat") = "cougar"; .RE .RS 2 cout << critters << endl; .RE .RS 0 .RE .RS 3 // put a zebra at the beginning .br // an ocelot ahead of antelope .br // and a rat at the end .RE .RS 2 critters.push_front("zebra"); .br critters.insert(find(critters.begin(),critters.end(), .RE .RS 19 "antelope"),"ocelot"); .RE .RS 2 critters.push_back("rat"); .br cout << critters << endl; .RE .RS 0 .RE .RS 3 // sort the list (Use list's sort function since the .br // generic algorithm requires a random access iterator .br // and list only provides bidirectional) .RE .RS 2 critters.sort(); .br cout << critters << endl; .RE .RS 0 .RE .RS 3 // now let's erase half of the critters .RE .RS 2 int half = critters.size() >> 1; .br for(i = 0; i < half; ++i) { .RE .RS 4 critters.erase(critters.begin()); .RE .RS 3 } .RE .RS 2 cout << critters << endl; .br return 0; .RE .RS 1 } .RE .RS 0 .br .br .br .RE .RS 0 Program Output .br .br cat bear antelope .br cougar bear antelope .br zebra cougar bear ocelot antelope rat .br antelope bear cougar ocelot rat zebra .br ocelot rat zebra .SH 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 that takes two templatized iterators: .br template .br list (InputIterator, InputIterator, .RE .RS 5 const Allocator& = Allocator()); .RE list also has an \f2insert\fP 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: .RE .RS 0 int intarray[10]; .br list first_list(intarray,intarray + 10); .br list second_list(first_list.begin(),first_list.end()); But not this way: .br list long_list(first_list.begin(),first_list.end()); since the \f2long_list\fP and \f2first_list\fP are not the same type. Additionally, list includes a \f2merge \fPfunction of this type. .br template void merge (list&, .RE .RS 1 Compare); .RE 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 \f2operator< \fPas the default. Thus, if your compiler does not support member function templates, all list merges use \f2operator<\fP. Also, many compilers do not support default template arguments. If your compiler is one of these, you always need to supply the \f2Allocator\fP template argument. For instance, you have to write: \f2list >\fP instead of: \f2list\fP If your compiler does not support namespaces, then you do not need the using declaration for \f2std\fP. .SH SEE ALSO allocator, Containers, Iterators