Lecture Notes for SE 598, Data Structures and Algorithms

21 June 2000, STL Dequeues

1. behavior

   1. overall, dequeue behavior and vector behavior are alike

      1. vectors have some operators that dequeues don't

      2. dequeues have some operators that vectors don't

2. a dequeue is a template class

   1. with template <class T, class Allocator = allocator>

   2. for example

      1. deque<customer> waiters;

3. dequeue constructors

   1. the default constructor - deque<T> tdeq;

   2. the size and value constructor - deque<T> tdeq(n, v);

   3. the copy constructor - deque<customer> line2(line1);

   4. the segment-copy constructor

      1. template<class InputIterator>
         deque(InputIterator start, InputIterator end)
         

4. reading and writing values

   1. the array accessor - index values from 0 through n - 1

5. growing and shrinking dequeues

   1. the size() member function

      1. the reserve() and capacity() member functions don't apply to dequeues.

   2. the d.push_back(v) and d.pop_back() member functions

   3. the d.push_front(v) and d.pop_front() member functions

      1. the first (leftmost) index value is always 0

      2. push_front(v) and pop_front() do not apply to vectors

6. deque relation operators

   1. dequeue relational operators apply to the contents of the dequeues

   2. the deque member operators == and !=

   3. the dequeue member operator < is defined as: d1 < d2 is true if and only if

      1. d1.size() <= d2.size() and

      2. there exists a k such that 0 <= k <= d1.size() and

      3. d1[0..k-1] = d2[0..k-1] and

      4. either k == d1.size() or d1[k] < d2[k]

      5. this is known as lexicographic order

7. iterators

   1. type types deque<T>::iterator and deque<T>::const_iterator

      1. deque iterators are random iterators

   2. member functions d.begin() and d.end()

   3. the reverse iterators - they work backwards from regular iterators

      1. the types deque<T>::reverse_iterator and deque<T>::const_reverse_iterator

         1. the sense of prefix and postfix ++ is reversed for reverse iterators

            1. "move to the next" means "move one to the left"

         2. if defined, the sense of + n and += n is also reversed for reverse iterators

            1. "move n to the left" instead of "move n to the right"

         3. similarly for prefix and postfix --, and - n and -= n if defined.

            1. "move to the right"; "move n to the right"

      2. the member functions d.rbegin() and d.rend()

         1. for a dequeue d,

            1. *d.begin() == *(d.rend() - 1) is always true, assuming d.size() > 0

            2. *(d.end() - 1) == *d.rbegin() is always true, assuming d.size() > 0

      3. the iterator and reverse iterator types are different and incompatible - this can be an annoying source of usually trivial errors

         1. for example, d.begin() == (d.rend - 1) is incorrect: it does not type check

      4. reverse iterators are a pain to deal with manually, but they are useful with generic algorithms

         1. compare sort(v.begin(),v.end()) to sort(v.rbegin(), v.rend())

This page last modified on 19 June 2000.