.\" ident @(#)deque.3 .\" Standard Template Library .\" $$RW_INSERT_HEADER "slyrs.man" .TH deque 3C++ "02 Apr 1998" "Rogue Wave Software" "-" .ce2 Standard C++ Library Copyright 1998, Rogue Wave Software, Inc. .SH NAME \f2deque\fP \ - A sequence that supports random access iterators and efficient insertion/deletion at both beginning and end. .SH SYNOPSIS .br #include .br .br template > .br class deque; .SH DESCRIPTION deque is a type of sequence that supports random access iterators. It supports constant time insert and erase operations at the beginning or the end of the container. Insertion and erase in the middle take linear time. Storage management is handled by the \f2Allocator\fP template parameter. Any type used for the template parameter \f2T\fP must include the following (where \f2T\fP is the \f2type\fP, \f2t\fP is a \f2value\fP of \f2T\fP and\f2 u\fP is a \f2const\fP \f2value\fP of \f2T\fP): .HP 21 \f2Copy constructors T(t)\fP and \f2T(u)\fP .HP 0 .HP 13 \f2Destructor t.~T()\fP .HP 0 .HP 13 \f2Address of &t\fP and \f2&u\fP yielding \f2T*\fP and \f2const T*\fP respectively .HP 0 .HP 13 \f2Assignment t = a\fP where \f2a\fP is a (possibly \f2const\fP) value of \f2T\fP .HP 0 .SH INTERFACE .br template > .br class deque { .br .br public: .br .RE .RS 1 // Types .RE .RS 0 .RE .RS 2 class iterator; .br class const_iterator; .RE .RS 0 .RE .RS 2 typedef T value_type; .br typedef Allocator allocator_type; .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 typename .RE .RS 10 std::reverse_iterator reverse_iterator; .RE .RS 2 typedef typename .RE .RS 10 std::reverse_iterator .RE .RS 32 const_reverse_iterator; .RE .RS 0 .RE .RS 1 // Construct/Copy/Destroy .RE .RS 0 .RE .RS 2 explicit deque (const Allocator& = Allocator()); .br explicit deque (size_type); .br deque (size_type, const T& value, .RE .RS 9 const Allocator& = Allocator ()); .RE .RS 2 deque (const deque&); .br template .RE .RS 3 deque (InputIterator, InputIterator, .RE .RS 10 const Allocator& = Allocator ()); .RE .RS 3 ~deque (); .RE .RS 2 deque& operator= .RE .RS 23 (const deque&); .RE .RS 2 template .RE .RS 3 void assign (InputIterator, InputIterator); .RE .RS 2 void assign (size_type, const T&); .br allocator_type get allocator () const; .RE .RS 0 .RE .RS 1 // Iterators .RE .RS 0 .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 size_type size () const; .br size_type max_size () const; .br void resize (size_type); .br void resize (size_type, T); .br bool empty () const; .RE .RS 0 .br // Element access .br .RE .RS 2 reference operator[] (size_type); .br const_reference operator[] (size_type) const; .br reference at (size_type); .br const_reference at (size_type) const; .br reference front (); .br const_reference front () const; .br reference back (); .br const_reference back () const; .RE .RS 0 .RE .RS 1 // Modifiers .RE .RS 0 .RE .RS 2 void push_front (const T&); .br void push_back (const T&); .br 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 void pop_front (); .br void pop_back (); .RE .RS 0 .RE .RS 2 iterator erase (iterator); .br iterator erase (iterator, iterator); .br void swap (deque&); .br void clear(); .RE .RS 0 }; .br .RE .RS 1 // Non-member Operators .RE .RS 0 .br template .br bool operator== (const deque&, .RE .RS 17 const deque&); .RE .RS 0 .br template .br bool operator!= (const deque&, .RE .RS 17 const deque&); .RE .RS 0 .br .br template .br bool operator< (const deque&, .RE .RS 16 const deque&); .RE .RS 0 .br template .br bool operator> (const deque&, .RE .RS 16 const deque&); .RE .RS 0 .br template .br bool operator<= (const deque&, .RE .RS 16 const deque&); .RE .RS 0 .br template .br bool operator>= (const deque&, .RE .RS 16 const deque&); .RE .RS 0 .br .br // Specialized Algorithms .br .br template .br voice swap (deque&, deque&); .SH CONSTRUCTORS .br explicit .br deque(const Allocator& alloc = Allocator()); .RE .RS 3 The default constructor. Creates a deque of zero elements. The deque uses the allocator \f2alloc\fP for all storage management. .RE .br explicit .br deque(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 deque uses the allocator Allocator() for all storage management. .RE .br deque(size_type n, const T& value, .RE .RS 6 const Allocator& alloc = Allocator()); .RE .RS 3 Creates a list of length \f2n\fP, containing \f2n\fP copies of \f2value\fP. The deque uses the allocator \f2alloc\fP for all storage management. .RE .RE .RS 0 deque(const deque& x); .RE .RS 3 Creates a copy of \f2x\fP. .RE .br template .br deque(InputIterator first, InputIterator last, .RE .RS 6 const Allocator& alloc = Allocator()); .RE .RS 3 Creates a deque of length \f2last - first\fP, filled with all values obtained by dereferencing the \f2InputIterators\fP on the range \f2[first, last)\fP. The deque uses the allocator \f2alloc\fP for all storage management. .RE .SH DESTRUCTORS .RE .RS 0 ~deque(); .RE .RS 3 Releases any allocated memory for self. .RE .SH ALLOCATORS .br allocator .br allocator_type get_allocator() const; .RE .RS 3 Returns a copy of the allocator used by self for storage management. .RE .SH ITERATORS .br iterator begin(); .RE .RS 3 Returns a random access iterator that points to the first element. .RE .br const_iterator begin() const; .RE .RS 3 Returns a constant random access iterator that points to the first element. .RE .br iterator end(); .RE .RS 3 Returns a random access iterator that points to the past-the-end value. .RE .br const_iterator end() const; .RE .RS 3 Returns a constant random access iterator that points to the past-the-end value. .RE .br reverse_iterator rbegin(); .RE .RS 3 Returns a random access \f2reverse_iterator\fP that points to the past-the-end value. .RE .br const_reverse_iterator rbegin() const; .RE .RS 3 Returns a constant random access reverse iterator that points to the past-the-end value. .RE .br reverse_iterator rend(); .RE .RS 3 Returns a random access \f2reverse_iterator\fP that points to the first element. .RE .br const_reverse_iterator rend() const; .RE .RS 3 Returns a constant random access reverse iterator that points to the first element. .RE .SH ASSIGNMENT OPERATORS .br deque& .br operator=(const deque& 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 self. .RE .SH REFERENCE OPERATORS .br reference operator[](size_type n); .RE .RS 3 Returns a \f2reference\fP to element \f2n\fP of self. The result can be used as an lvalue. The index \f2n\fP must be between \f20\fP and the \f2size() - 1\fP.. .RE .br const_reference operator[](size_type n) const; .RE .RS 3 Returns a constant reference to element \f2n\fP of self. The index \f2n\fP must be between \f20\fP and the \f2size() - 1\fP. .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 value of \f2t.\fP .RE .br reference .br at(size_type n); .RE .RS 3 Returns a reference to element \f2n\fP of self. The result can be used as an lvalue. The index \f2n\fP must be between \f20\fP and the\f2 size() - 1\fP. .RE .br const_reference .br at(size_type) const; .RE .RS 3 Returns a constant reference to element \f2n\fP of self. The index \f2n\fP must be between \f20\fP and the \f2size() - 1\fP. .RE .br reference .br back(); .RE .RS 3 Returns a reference 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 self. .RE .br bool .br empty() const; .RE .RS 3 Returns \f2true\fP if the size of self is zero. .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 erase(iterator first, iterator last); .RE .RS 3 Deletes the elements in the range (\f2first, last\fP). Returns an iterator pointing to the element following the last deleted element, or \f2end()\fP if there were no elements after the deleted range. .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 there were no elements after the deleted range. .RE .br iterator .br insert(iterator position, const T& x); .RE .RS 3 Inserts \f2x\fP before \f2position\fP. The return value 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 \fPbefore \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 \f2size()\fP of the largest possible deque. .RE .br void .br pop_back(); .RE .RS 3 Removes the last element. Note that this function does not return the element. .RE .br void .br pop_front(); .RE .RS 3 Removes the first element. Note that this function does not return the element. .RE .br void .br push_back(const T& x); .RE .RS 3 Appends a copy of \f2x\fP to the end. .RE .br void .br push_front(const T& x); .RE .RS 3 Inserts a copy of \f2x\fP at the front. .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, then \f2sz-size()\fP copies of the default value of type \f2T\fP are inserted at the end of the deque. If the new size is smaller than the current capacity, then the deque 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, then \f2sz-size()\fP \f2c\fP's are inserted at the end of the deque. If the new size is smaller than the current capacity, then the deque is truncated by erasing \f2size()-sz\fP elements off the end. Otherwise, no action is taken. .RE .br size_type .br size() const; .RE .RS 3 Returns the number of elements. .RE .br void .br swap(deque& x); .RE .RS 3 Exchanges self with \f2x\fP. .RE .SH NON-MEMBER FUNCTIONS .br template .br bool operator==(const deque& x, .RE .RS 16 const deque& y); .RE .RS 3 Equality operator. Returns \f2true\fP if \f2x\fP is the same as \f2y\fP. .RE .RE .RS 0 template .br bool operator!=(const deque& x, .RE .RS 16 const deque& y); .RE .RS 3 Returns \f2true\fP if \f2x\fP is not the same as \f2y\fP. .RE .RE .RS 0 template .br bool operator<(const deque& x, .RE .RS 15 const deque& y); .RE .RS 3 Returns \f2true\fP if the elements contained in \f2x\fP are lexicographically less than the elements contained in \f2y\fP. .RE .RE .RS 0 template .br bool operator>(const deque& x, .RE .RS 15 const deque& y); .RE .RS 3 Returns \f2true\fP if the elements contained in \f2x\fP are lexicographically greater than the elements contained in \f2y\fP. .RE .RE .RS 0 template .br bool operator<=(const deque& x, .RE .RS 15 const deque& y); .RE .RS 3 Returns \f2true\fP if the elements contained in \f2x\fP are lexicographically less than or equal to the elements contained in \f2y\fP. .RE .RE .RS 0 template .br bool operator>=(const deque& x, .RE .RS 15 const deque& y); .RE .RS 3 Returns \f2true\fP if the elements contained in \f2x\fP are lexicographically greater than or equal to the elements contained in \f2y\fP. .RE .RE .RS 0 template .br bool operator<(const deque& x, .RE .RS 15 const deque& y); .RE .RS 3 Returns \f2true\fP if the elements contained in \f2x\fP are lexicographically less than the elements contained in \f2y\fP. .RE .SH SPECIALIZED ALGORITHMS .RE .RS 0 template .br void swap(deque& a, deque& b); .RE .RS 3 Swaps the contents of \f2a\fP and \f2b\fP. .RE .SH EXAMPLE .br // .br // deque.cpp .br // .RE .RS 1 #include .br #include .br #include .RE .RS 0 using namespace std; .br .br deque deck_of_cards; .br deque current_hand; .br .br void initialize_cards(deque& cards) { .RE .RS 2 cards.push_front("aceofspades"); .br cards.push_front("kingofspades"); .br cards.push_front("queenofspades"); .br cards.push_front("jackofspades"); .br cards.push_front("tenofspades"); .RE .RS 3 // etc. .RE .RS 1 } .RE .RS 0 .br template .br void print_current_hand(It start, It2 end) .RE .RS 1 { .RE .RS 2 while (start < end) .br cout << *start++ << endl; .RE .RS 1 } .RE .RS 0 .br .br template .br void deal_cards(It, It2 end) { .RE .RS 2 for (int i=0;i<5;i++) { .RE .RS 4 current_hand.insert(current_hand.begin(),*end); .br deck_of_cards.erase(end++); .RE .RS 3 } .RE .RS 1 } .RE .RS 0 .br void play_poker() { .RE .RS 2 initialize_cards(deck_of_cards); .br deal_cards(current_hand.begin(),deck_of_cards.begin()); .RE .RS 1 } .RE .RS 0 .br int main() .RE .RS 1 { .RE .RS 2 play_poker(); .br print_current_hand(current_hand.begin(),current_hand.end()); .br return 0; .RE .RS 1 } .br .RE .RS 0 Program Output .RE .RS 0 .br aceofspades .br kingofspades .br queenofspades .br jackofspades .br tenofspades .SH WARNINGS Member function templates are used in all containers in by the Standard Template Library. An example of this is the constructor for deque, which takes two templatized iterators: .br template .br deque (InputIterator, InputIterator); deque 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 deque in the following two ways: .br int intarray[10]; .br deque first_deque(intarray, intarray + 10); .br deque second_deque(first_deque.begin(), .RE .RS 23 first_deque.end()); .RE But not this way: .RS 0 deque long_deque(first_deque.begin(), .RE .RS 33 first_deque.end()); .RE since the\f2 long_deque\fP and \f2first_deque\fP are not the same type. Additionally, 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: \f2deque >\fP instead of: \f2deque\fP If your compiler does not support namespaces, then you do not need the using declaration for \f2std\fP.