Main Page   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members  

deque Class Template Reference

#include <stl_deque.h>

Collaboration diagram for deque:

Collaboration graph
[legend]
List of all members.

Public Types

typedef T value_type
typedef value_type * pointer
typedef const value_type * const_pointer
typedef value_type & reference
typedef const value_type & const_reference
typedef size_t size_type
typedef ptrdiff_t difference_type
typedef __deque_iterator<
T, T &, T *, BufSiz > 		iterator
typedef __deque_iterator<
T, const T &, const T &,
BufSiz > 		const_iterator
typedef reverse_iterator<
const_iterator, value_type,
const_reference, difference_type > 		const_reverse_iterator
typedef reverse_iterator<
iterator, value_type, reference,
difference_type > 		reverse_iterator

Public Methods

iterator begin ()
iterator end ()
const_iterator begin () const
const_iterator end () const
reverse_iterator rbegin ()
reverse_iterator rend ()
const_reverse_iterator rbegin () const
const_reverse_iterator rend () const
reference operator[] (size_type n)
const_reference operator[] (size_type n) const
reference front ()
reference back ()
const_reference front () const
const_reference back () const
size_type size () const
size_type max_size () const
bool empty () const
 deque ()
 deque (const deque &x)
 deque (size_type n, const value_type &value)
 deque (int n, const value_type &value)
 deque (long n, const value_type &value)
 deque (size_type n)
 deque (const value_type *first, const value_type *last)
 deque (const_iterator first, const_iterator last)
 ~deque ()
deque & operator= (const deque &x)
void swap (deque &x)
void push_back (const value_type &t)
void push_front (const value_type &t)
void pop_back ()
void pop_front ()
iterator insert (iterator position, const value_type &x)
iterator insert (iterator position)
void insert (iterator pos, size_type n, const value_type &x)
void insert (iterator pos, int n, const value_type &x)
void insert (iterator pos, long n, const value_type &x)
void insert (iterator pos, const value_type *first, const value_type *last)
void insert (iterator pos, const_iterator first, const_iterator last)
void resize (size_type new_size, const value_type &x)
void resize (size_type new_size)
iterator erase (iterator pos)
iterator erase (iterator first, iterator last)
void clear ()

Protected Types

typedef pointer * map_pointer
typedef simple_alloc< value_type,
Alloc > 		data_allocator
typedef simple_alloc< pointer,
Alloc > 		map_allocator

Protected Methods

void create_map_and_nodes (size_type num_elements)
void destroy_map_and_nodes ()
void fill_initialize (size_type n, const value_type &value)
void push_back_aux (const value_type &t)
void push_front_aux (const value_type &t)
void pop_back_aux ()
void pop_front_aux ()
iterator insert_aux (iterator pos, const value_type &x)
void insert_aux (iterator pos, size_type n, const value_type &x)
void insert_aux (iterator pos, const value_type *first, const value_type *last, size_type n)
void insert_aux (iterator pos, const_iterator first, const_iterator last, size_type n)
iterator reserve_elements_at_front (size_type n)
iterator reserve_elements_at_back (size_type n)
void new_elements_at_front (size_type new_elements)
void new_elements_at_back (size_type new_elements)
void destroy_nodes_at_front (iterator before_start)
void destroy_nodes_at_back (iterator after_finish)
void reserve_map_at_back (size_type nodes_to_add=1)
void reserve_map_at_front (size_type nodes_to_add=1)
void reallocate_map (size_type nodes_to_add, bool add_at_front)
pointer allocate_node ()
void deallocate_node (pointer n)

Static Protected Methods

size_type buffer_size ()
size_type initial_map_size ()

Protected Attributes

iterator start
iterator finish
map_pointer map
size_type map_size

template<class T, class Alloc = alloc, size_t BufSiz = 0>
class deque< T, Alloc, BufSiz >

Member Typedef Documentation

template<class T, class Alloc = alloc, size_t BufSiz = 0>
typedef __deque_iterator<T, const T&, const T&, BufSiz> deque::const_iterator
 

Definition at line 257 of file stl_deque.h.

template<class T, class Alloc = alloc, size_t BufSiz = 0>
typedef const value_type* deque::const_pointer
 

Definition at line 248 of file stl_deque.h.

template<class T, class Alloc = alloc, size_t BufSiz = 0>
typedef const value_type& deque::const_reference
 

Definition at line 250 of file stl_deque.h.

template<class T, class Alloc = alloc, size_t BufSiz = 0>
typedef reverse_iterator<const_iterator, value_type, const_reference, difference_type> deque::const_reverse_iterator
 

Definition at line 269 of file stl_deque.h.

template<class T, class Alloc = alloc, size_t BufSiz = 0>
typedef simple_alloc<value_type, Alloc> deque::data_allocator [protected]
 

Definition at line 276 of file stl_deque.h.

template<class T, class Alloc = alloc, size_t BufSiz = 0>
typedef ptrdiff_t deque::difference_type
 

Definition at line 252 of file stl_deque.h.

template<class T, class Alloc = alloc, size_t BufSiz = 0>
typedef __deque_iterator<T, T&, T*, BufSiz> deque::iterator
 

Definition at line 256 of file stl_deque.h.

template<class T, class Alloc = alloc, size_t BufSiz = 0>
typedef simple_alloc<pointer, Alloc> deque::map_allocator [protected]
 

Definition at line 277 of file stl_deque.h.

template<class T, class Alloc = alloc, size_t BufSiz = 0>
typedef pointer* deque::map_pointer [protected]
 

Definition at line 275 of file stl_deque.h.

Referenced by clear, and fill_initialize.

template<class T, class Alloc = alloc, size_t BufSiz = 0>
typedef value_type* deque::pointer
 

Definition at line 247 of file stl_deque.h.

template<class T, class Alloc = alloc, size_t BufSiz = 0>
typedef value_type& deque::reference
 

Definition at line 249 of file stl_deque.h.

template<class T, class Alloc = alloc, size_t BufSiz = 0>
typedef reverse_iterator<iterator, value_type, reference, difference_type> deque::reverse_iterator
 

Definition at line 271 of file stl_deque.h.

template<class T, class Alloc = alloc, size_t BufSiz = 0>
typedef size_t deque::size_type
 

Definition at line 251 of file stl_deque.h.

Referenced by destroy_nodes_at_front, and new_elements_at_back.

template<class T, class Alloc = alloc, size_t BufSiz = 0>
typedef T deque::value_type
 

Definition at line 246 of file stl_deque.h.

Constructor & Destructor Documentation

template<class T, class Alloc = alloc, size_t BufSiz = 0>
deque< T, Alloc, BufSiz >::deque (    )  [inline]
 

Definition at line 329 of file stl_deque.h. 

00333                          { return finish - start;; }

template<class T, class Alloc = alloc, size_t BufSiz = 0>
deque< T, Alloc, BufSiz >::deque (  const deque< T, Alloc, BufSiz > &    x )  [inline]
 

Definition at line 335 of file stl_deque.h. 

00335                      { return finish == start; }
00336 
00337 public:                         // Constructor, destructor.
00338   deque()
00339     : start(), finish(), map(0), map_size(0)
00340   {
00341     create_map_and_nodes(0);
00342   }
00343

template<class T, class Alloc = alloc, size_t BufSiz = 0>
deque< T, Alloc, BufSiz >::deque (  size_type    n,
const value_type &    value
)  [inline]
 

Definition at line 345 of file stl_deque.h.

References __STL_TRY, and uninitialized_copy. 

00345     : start(), finish(), map(0), map_size(0)
00346   {
00347     create_map_and_nodes(x.size());
00348     __STL_TRY {
00349       uninitialized_copy(x.begin(), x.end(), start);

template<class T, class Alloc = alloc, size_t BufSiz = 0>
deque< T, Alloc, BufSiz >::deque (  int    n,
const value_type &    value
)  [inline]
 

Definition at line 351 of file stl_deque.h. 

00355     : start(), finish(), map(0), map_size(0)

template<class T, class Alloc = alloc, size_t BufSiz = 0>
deque< T, Alloc, BufSiz >::deque (  long    n,
const value_type &    value
)  [inline]
 

Definition at line 357 of file stl_deque.h. 

00361     : start(), finish(), map(0), map_size(0)

template<class T, class Alloc = alloc, size_t BufSiz = 0>
deque< T, Alloc, BufSiz >::deque (  size_type    n )  [inline, explicit]
 

Definition at line 363 of file stl_deque.h. 

00367     : start(), finish(), map(0), map_size(0)

template<class T, class Alloc = alloc, size_t BufSiz = 0>
deque< T, Alloc, BufSiz >::deque (  const value_type *    first,
const value_type *    last
)  [inline]
 

Definition at line 380 of file stl_deque.h.

References __deque_iterator::iterator_category. 

00382     : start(), finish(), map(0), map_size(0)
00383   {
00384     range_initialize(first, last, iterator_category(first));
00385   }
00386 
00387 #else /* __STL_MEMBER_TEMPLATES */
00388

template<class T, class Alloc = alloc, size_t BufSiz = 0>
deque< T, Alloc, BufSiz >::deque (  const_iterator    first,
const_iterator    last
)  [inline]
 

Definition at line 390 of file stl_deque.h.

References __STL_TRY, __STL_UNWIND, and uninitialized_copy. 

00390     : start(), finish(), map(0), map_size(0)
00391   {
00392     create_map_and_nodes(last - first);
00393     __STL_TRY {
00394       uninitialized_copy(first, last, start);
00395     }
00396     __STL_UNWIND(destroy_map_and_nodes());
00397   }
00398

template<class T, class Alloc = alloc, size_t BufSiz = 0>
deque< T, Alloc, BufSiz >::~deque (    )  [inline]
 

Definition at line 402 of file stl_deque.h.

References __STL_TRY. 

00403               {
00404       uninitialized_copy(first, last, start);
00405     }

Member Function Documentation

template<class T, class Alloc = alloc, size_t BufSiz = 0>
pointer deque< T, Alloc, BufSiz >::allocate_node (    )  [inline, protected]
 

Definition at line 635 of file stl_deque.h. 

00637 {

template<class T, class Alloc = alloc, size_t BufSiz = 0>
const_reference deque< T, Alloc, BufSiz >::back (    )  const [inline]
 

Definition at line 318 of file stl_deque.h. 

00320                     { return *start; }
00321   reference back() {
00322     iterator tmp = finish;

template<class T, class Alloc = alloc, size_t BufSiz = 0>
reference deque< T, Alloc, BufSiz >::back (    )  [inline]
 

Definition at line 312 of file stl_deque.h. 

00315                                     { return start[difference_type(n)]; }
00316   const_reference operator[](size_type n) const {

template<class T, class Alloc = alloc, size_t BufSiz = 0>
const_iterator deque< T, Alloc, BufSiz >::begin (    )  const [inline]
 

Definition at line 294 of file stl_deque.h. 

00300 :                         // Basic accessors

template<class T, class Alloc = alloc, size_t BufSiz = 0>
iterator deque< T, Alloc, BufSiz >::begin (    )  [inline]
 

Definition at line 292 of file stl_deque.h.

Referenced by insert, operator<, and swap. 

00293 :                      // Data members

template<class T, class Alloc = alloc, size_t BufSiz = 0>
size_type deque< T, Alloc, BufSiz >::buffer_size (    )  [inline, static, protected]
 

Definition at line 279 of file stl_deque.h.

Referenced by create_map_and_nodes. 

00283          :                      // Internal typedefs

template<class T, class Alloc, size_t BufSize>
void deque< T, Alloc, BufSize >::clear (    ) 
 

Definition at line 759 of file stl_deque.h.

References map_pointer. 

00768                                      {
00769   for (map_pointer node = start.node + 1; node < finish.node; ++node) {
00770     destroy(*node, *node + buffer_size());
00771     data_allocator::deallocate(*node, buffer_size());
00772   }
00773 
00774   if (start.node != finish.node) {

template<class T, class Alloc, size_t BufSize>
void deque< T, Alloc, BufSize >::create_map_and_nodes (  size_type    num_elements )  [protected]
 

Definition at line 777 of file stl_deque.h.

References buffer_size. 

00786                                                                           {
00787   size_type num_nodes = num_elements / buffer_size() + 1;
00788 
00789   map_size = max(initial_map_size(), num_nodes + 2);
00790   map = map_allocator::allocate(map_size);
00791 
00792   map_pointer nstart = map + (map_size - num_nodes) / 2;
00793   map_pointer nfinish = nstart + num_nodes - 1;
00794     
00795   map_pointer cur;
00796   __STL_TRY {
00797     for (cur = nstart; cur <= nfinish; ++cur)
00798       *cur = allocate_node();
00799   }
00800 #     ifdef  __STL_USE_EXCEPTIONS 
00801   catch(...) {
00802     for (map_pointer n = nstart; n < cur; ++n)
00803       deallocate_node(*n);
00804     map_allocator::deallocate(map, map_size);

template<class T, class Alloc = alloc, size_t BufSiz = 0>
void deque< T, Alloc, BufSiz >::deallocate_node (  pointer    n )  [inline, protected]
 

Definition at line 636 of file stl_deque.h.

References __deque_iterator< T, T &, T *, BufSiz >::node.

Referenced by destroy_nodes_at_front, fill_initialize, and new_elements_at_back. 

00637                                                          {
00638     if (nodes_to_add > start.node - map)

template<class T, class Alloc, size_t BufSize>
void deque< T, Alloc, BufSize >::destroy_map_and_nodes (    )  [protected]
 

Definition at line 808 of file stl_deque.h.

template<class T, class Alloc, size_t BufSize>
void deque< T, Alloc, BufSize >::destroy_nodes_at_back (  iterator    after_finish )  [protected]
 

Definition at line 1250 of file stl_deque.h. 

01253                                                                            {

template<class T, class Alloc, size_t BufSize>
void deque< T, Alloc, BufSize >::destroy_nodes_at_front (  iterator    before_start )  [protected]
 

Definition at line 1244 of file stl_deque.h.

References deallocate_node, __deque_iterator< T, T &, T *, BufSiz >::node, and size_type. 

01244              {
01245     for (size_type j = 1; j < i; ++j)
01246       deallocate_node(*(finish.node + j));      
01247     throw;

template<class T, class Alloc = alloc, size_t BufSiz = 0>
bool deque< T, Alloc, BufSiz >::empty (    )  const [inline]
 

Definition at line 326 of file stl_deque.h. 

00326 { return *start; }

template<class T, class Alloc = alloc, size_t BufSiz = 0>
const_iterator deque< T, Alloc, BufSiz >::end (    )  const [inline]
 

Definition at line 295 of file stl_deque.h. 

00300 :                         // Basic accessors

template<class T, class Alloc = alloc, size_t BufSiz = 0>
iterator deque< T, Alloc, BufSiz >::end (    )  [inline]
 

Definition at line 293 of file stl_deque.h.

Referenced by insert, operator<, and swap. 

00293 :                      // Data members

template<class T, class Alloc, size_t BufSize>
deque< T, Alloc, BufSize >::iterator deque< T, Alloc, BufSize >::erase (  iterator    first,
iterator    last
) 
 

Definition at line 730 of file stl_deque.h. 

00739                                                              {
00740   if (first == start && last == finish) {
00741     clear();
00742     return finish;
00743   }
00744   else {
00745     difference_type n = last - first;
00746     difference_type elems_before = first - start;
00747     if (elems_before < (size() - n) / 2) {
00748       copy_backward(start, first, last);
00749       iterator new_start = start + n;
00750       destroy(start, new_start);
00751       for (map_pointer cur = start.node; cur < new_start.node; ++cur)
00752         data_allocator::deallocate(*cur, buffer_size());
00753       start = new_start;
00754     }
00755     else {
00756       copy(last, finish, first);

template<class T, class Alloc = alloc, size_t BufSiz = 0>
iterator deque< T, Alloc, BufSiz >::erase (  iterator    pos )  [inline]
 

Definition at line 520 of file stl_deque.h. 

00526                                   { resize(new_size, value_type()); }
00527 
00528 public:                         // Erase
00529   iterator erase(iterator pos) {
00530     iterator next = pos;
00531     ++next;
00532     difference_type index = pos - start;
00533     if (index < (size() >> 1)) {

template<class T, class Alloc, size_t BufSize>
void deque< T, Alloc, BufSize >::fill_initialize (  size_type    n,
const value_type &    value
)  [protected]
 

Definition at line 816 of file stl_deque.h.

References deallocate_node, map_pointer, map_size, and __deque_iterator< T, T &, T *, BufSiz >::node. 

00817                                                      {
00818   for (map_pointer cur = start.node; cur <= finish.node; ++cur)
00819     deallocate_node(*cur);
00820   map_allocator::deallocate(map, map_size);
00821 }
00822   
00823 
00824 template <class T, class Alloc, size_t BufSize>
00825 void deque<T, Alloc, BufSize>::fill_initialize(size_type n,
00826                                                const value_type& value) {
00827   create_map_and_nodes(n);
00828   map_pointer cur;
00829   __STL_TRY {
00830     for (cur = start.node; cur < finish.node; ++cur)
00831       uninitialized_fill(*cur, *cur + buffer_size(), value);
00832     uninitialized_fill(finish.first, finish.cur, value);
00833   }

template<class T, class Alloc = alloc, size_t BufSiz = 0>
const_reference deque< T, Alloc, BufSiz >::front (    )  const [inline]
 

Definition at line 317 of file stl_deque.h. 

00320 { return *start; }

template<class T, class Alloc = alloc, size_t BufSiz = 0>
reference deque< T, Alloc, BufSiz >::front (    )  [inline]
 

Definition at line 311 of file stl_deque.h. 

00311 {

template<class T, class Alloc = alloc, size_t BufSiz = 0>
size_type deque< T, Alloc, BufSiz >::initial_map_size (    )  [inline, static, protected]
 

Definition at line 282 of file stl_deque.h. 

00283 :                      // Internal typedefs

template<class T, class Alloc, size_t BufSize>
void deque< T, Alloc, BufSize >::insert (  iterator    pos,
const_iterator    first,
const_iterator    last
) 
 

Definition at line 701 of file stl_deque.h. 

00713 {
00714   size_type n = last - first;
00715   if (pos.cur == start.cur) {
00716     iterator new_start = reserve_elements_at_front(n);
00717     __STL_TRY {
00718       uninitialized_copy(first, last, new_start);
00719       start = new_start;
00720     }
00721     __STL_UNWIND(destroy_nodes_at_front(new_start));
00722   }
00723   else if (pos.cur == finish.cur) {
00724     iterator new_finish = reserve_elements_at_back(n);

template<class T, class Alloc, size_t BufSize>
void deque< T, Alloc, BufSize >::insert (  iterator    pos,
const value_type *    first,
const value_type *    last
) 
 

Definition at line 676 of file stl_deque.h. 

00687                                                               {
00688   size_type n = last - first;
00689   if (pos.cur == start.cur) {
00690     iterator new_start = reserve_elements_at_front(n);
00691     __STL_TRY {
00692       uninitialized_copy(first, last, new_start);
00693       start = new_start;
00694     }
00695     __STL_UNWIND(destroy_nodes_at_front(new_start));
00696   }
00697   else if (pos.cur == finish.cur) {
00698     iterator new_finish = reserve_elements_at_back(n);

template<class T, class Alloc = alloc, size_t BufSiz = 0>
void deque< T, Alloc, BufSiz >::insert (  iterator    pos,
long    n,
const value_type &    x
)  [inline]
 

Definition at line 491 of file stl_deque.h. 

00493                                      { return insert(position, value_type()); }

template<class T, class Alloc = alloc, size_t BufSiz = 0>
void deque< T, Alloc, BufSiz >::insert (  iterator    pos,
int    n,
const value_type &    x
)  [inline]
 

Definition at line 488 of file stl_deque.h. 

00488          {
00489       return insert_aux(position, x);
00490     }

template<class T, class Alloc, size_t BufSize>
void deque< T, Alloc, BufSize >::insert (  iterator    pos,
size_type    n,
const value_type &    x
) 
 

Definition at line 657 of file stl_deque.h.

References begin, end, and lexicographical_compare. 

00657                                                     {
00658     return lexicographical_compare(begin(), end(), x.begin(), x.end());
00659   }
00660 #endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */
00661 };
00662 
00663 // Non-inline member functions
00664 
00665 template <class T, class Alloc, size_t BufSize>
00666 void deque<T, Alloc, BufSize>::insert(iterator pos,
00667                                       size_type n, const value_type& x) {
00668   if (pos.cur == start.cur) {
00669     iterator new_start = reserve_elements_at_front(n);
00670     uninitialized_fill(new_start, start, x);
00671     start = new_start;

template<class T, class Alloc = alloc, size_t BufSiz = 0>
iterator deque< T, Alloc, BufSiz >::insert (  iterator    position )  [inline]
 

Definition at line 484 of file stl_deque.h. 

00488 {

template<class T, class Alloc = alloc, size_t BufSiz = 0>
iterator deque< T, Alloc, BufSiz >::insert (  iterator    position,
const value_type &    x
)  [inline]
 

Definition at line 468 of file stl_deque.h. 

00475       :                         // Insert
00476 
00477   iterator insert(iterator position, const value_type& x) {
00478     if (position.cur == start.cur) {
00479       push_front(x);
00480       return start;
00481     }
00482     else if (position.cur == finish.cur) {

template<class T, class Alloc, size_t BufSize>
void deque< T, Alloc, BufSize >::insert_aux (  iterator    pos,
const_iterator    first,
const_iterator    last,
size_type    n
)  [protected]
 

Definition at line 1153 of file stl_deque.h. 

01166 {
01167   const difference_type elems_before = pos - start;
01168   size_type length = size();
01169   if (elems_before < length / 2) {
01170     iterator new_start = reserve_elements_at_front(n);
01171     iterator old_start = start;
01172     pos = start + elems_before;
01173     __STL_TRY {
01174       if (elems_before >= n) {
01175         iterator start_n = start + n;
01176         uninitialized_copy(start, start_n, new_start);
01177         start = new_start;
01178         copy(start_n, pos, old_start);
01179         copy(first, last, pos - difference_type(n));
01180       }
01181       else {
01182         const_iterator mid = first + (n - elems_before);
01183         __uninitialized_copy_copy(start, pos, first, mid, new_start);
01184         start = new_start;
01185         copy(mid, last, old_start);
01186       }
01187     }
01188     __STL_UNWIND(destroy_nodes_at_front(new_start));
01189   }
01190   else {
01191     iterator new_finish = reserve_elements_at_back(n);
01192     iterator old_finish = finish;
01193     const difference_type elems_after = length - elems_before;
01194     pos = finish - elems_after;
01195     __STL_TRY {
01196       if (elems_after > n) {
01197         iterator finish_n = finish - difference_type(n);
01198         uninitialized_copy(finish_n, finish, finish);
01199         finish = new_finish;
01200         copy_backward(pos, finish_n, old_finish);
01201         copy(first, last, pos);
01202       }
01203       else {

template<class T, class Alloc, size_t BufSize>
void deque< T, Alloc, BufSize >::insert_aux (  iterator    pos,
const value_type *    first,
const value_type *    last,
size_type    n
)  [protected]
 

Definition at line 1100 of file stl_deque.h. 

01113 {
01114   const difference_type elems_before = pos - start;
01115   size_type length = size();
01116   if (elems_before < length / 2) {
01117     iterator new_start = reserve_elements_at_front(n);
01118     iterator old_start = start;
01119     pos = start + elems_before;
01120     __STL_TRY {
01121       if (elems_before >= difference_type(n)) {
01122         iterator start_n = start + difference_type(n);
01123         uninitialized_copy(start, start_n, new_start);
01124         start = new_start;
01125         copy(start_n, pos, old_start);
01126         copy(first, last, pos - difference_type(n));
01127       }
01128       else {
01129         const value_type* mid = first + (difference_type(n) - elems_before);
01130         __uninitialized_copy_copy(start, pos, first, mid, new_start);
01131         start = new_start;
01132         copy(mid, last, old_start);
01133       }
01134     }
01135     __STL_UNWIND(destroy_nodes_at_front(new_start));
01136   }
01137   else {
01138     iterator new_finish = reserve_elements_at_back(n);
01139     iterator old_finish = finish;
01140     const difference_type elems_after = difference_type(length) - elems_before;
01141     pos = finish - elems_after;
01142     __STL_TRY {
01143       if (elems_after > difference_type(n)) {
01144         iterator finish_n = finish - difference_type(n);
01145         uninitialized_copy(finish_n, finish, finish);
01146         finish = new_finish;
01147         copy_backward(pos, finish_n, old_finish);
01148         copy(first, last, pos);
01149       }
01150       else {

template<class T, class Alloc, size_t BufSize>
void deque< T, Alloc, BufSize >::insert_aux (  iterator    pos,
size_type    n,
const value_type &    x
)  [protected]
 

Definition at line 989 of file stl_deque.h. 

00999                                                                             {
01000   const difference_type elems_before = pos - start;
01001   size_type length = size();
01002   value_type x_copy = x;
01003   if (elems_before < length / 2) {
01004     iterator new_start = reserve_elements_at_front(n);
01005     iterator old_start = start;
01006     pos = start + elems_before;
01007     __STL_TRY {
01008       if (elems_before >= difference_type(n)) {
01009         iterator start_n = start + difference_type(n);
01010         uninitialized_copy(start, start_n, new_start);
01011         start = new_start;
01012         copy(start_n, pos, old_start);
01013         fill(pos - difference_type(n), pos, x_copy);
01014       }
01015       else {
01016         __uninitialized_copy_fill(start, pos, new_start, start, x_copy);
01017         start = new_start;
01018         fill(old_start, pos, x_copy);
01019       }
01020     }
01021     __STL_UNWIND(destroy_nodes_at_front(new_start));
01022   }
01023   else {
01024     iterator new_finish = reserve_elements_at_back(n);
01025     iterator old_finish = finish;
01026     const difference_type elems_after = difference_type(length) - elems_before;
01027     pos = finish - elems_after;
01028     __STL_TRY {
01029       if (elems_after > difference_type(n)) {
01030         iterator finish_n = finish - difference_type(n);
01031         uninitialized_copy(finish_n, finish, finish);
01032         finish = new_finish;
01033         copy_backward(pos, finish_n, old_finish);
01034         fill(pos, pos + difference_type(n), x_copy);
01035       }
01036       else {
01037         __uninitialized_fill_copy(finish, pos + difference_type(n),

template<class T, class Alloc, size_t BufSize>
deque< T, Alloc, BufSize >::iterator deque< T, Alloc, BufSize >::insert_aux (  iterator    pos,
const value_type &    x
)  [protected]
 

Definition at line 961 of file stl_deque.h. 

00970                                                                       {
00971   difference_type index = pos - start;
00972   value_type x_copy = x;
00973   if (index < size() / 2) {
00974     push_front(front());
00975     iterator front1 = start;
00976     ++front1;
00977     iterator front2 = front1;
00978     ++front2;
00979     pos = start + index;
00980     iterator pos1 = pos;
00981     ++pos1;
00982     copy(front2, pos1, front1);
00983   }
00984   else {
00985     push_back(back());
00986     iterator back1 = finish;

template<class T, class Alloc = alloc, size_t BufSiz = 0>
size_type deque< T, Alloc, BufSiz >::max_size (    )  const [inline]
 

Definition at line 325 of file stl_deque.h. 

00326 { return *start; }

template<class T, class Alloc, size_t BufSize>
void deque< T, Alloc, BufSize >::new_elements_at_back (  size_type    new_elements )  [protected]
 

Definition at line 1226 of file stl_deque.h.

References deallocate_node, __deque_iterator< T, T &, T *, BufSiz >::node, and size_type. 

01226              {
01227     for (size_type j = 1; j < i; ++j)
01228       deallocate_node(*(start.node - j));      
01229     throw;
01230   }
01231 #       endif /* __STL_USE_EXCEPTIONS */
01232 }
01233 
01234 template <class T, class Alloc, size_t BufSize>
01235 void deque<T, Alloc, BufSize>::new_elements_at_back(size_type new_elements) {
01236   size_type new_nodes = (new_elements + buffer_size() - 1) / buffer_size();
01237   reserve_map_at_back(new_nodes);
01238   size_type i;
01239   __STL_TRY {
01240     for (i = 1; i <= new_nodes; ++i)
01241       *(finish.node + i) = allocate_node();

template<class T, class Alloc, size_t BufSize>
void deque< T, Alloc, BufSize >::new_elements_at_front (  size_type    new_elements )  [protected]
 

Definition at line 1208 of file stl_deque.h. 

01217                                                                            {
01218   size_type new_nodes = (new_elements + buffer_size() - 1) / buffer_size();
01219   reserve_map_at_front(new_nodes);
01220   size_type i;
01221   __STL_TRY {
01222     for (i = 1; i <= new_nodes; ++i)
01223       *(start.node - i) = allocate_node();

template<class T, class Alloc = alloc, size_t BufSiz = 0>
deque& deque< T, Alloc, BufSiz >::operator= (  const deque< T, Alloc, BufSiz > &    x )  [inline]
 

Definition at line 407 of file stl_deque.h. 

00411            {
00412     destroy(start, finish);
00413     destroy_map_and_nodes();
00414   }
00415 
00416   deque& operator= (const deque& x) {
00417     const size_type len = size();
00418     if (&x != this) {
00419       if (len >= x.size())

template<class T, class Alloc = alloc, size_t BufSiz = 0>
const_reference deque< T, Alloc, BufSiz >::operator[] (  size_type    n )  const [inline]
 

Definition at line 307 of file stl_deque.h. 

00307                           { return reverse_iterator(start); }
00308   const_reverse_iterator rbegin() const {
00309     return const_reverse_iterator(finish);

template<class T, class Alloc = alloc, size_t BufSiz = 0>
reference deque< T, Alloc, BufSiz >::operator[] (  size_type    n )  [inline]
 

Definition at line 306 of file stl_deque.h. 

00306 { return reverse_iterator(finish); }

template<class T, class Alloc = alloc, size_t BufSiz = 0>
void deque< T, Alloc, BufSiz >::pop_back (    )  [inline]
 

Definition at line 448 of file stl_deque.h.

References construct, __deque_iterator< T, T &, T *, BufSiz >::cur, and __deque_iterator< T, T &, T *, BufSiz >::first. 

00448                                        {
00449     if (start.cur != start.first) {
00450       construct(start.cur - 1, t);
00451       --start.cur;
00452     }
00453     else
00454       push_front_aux(t);
00455   }

template<class T, class Alloc, size_t BufSize>
void deque< T, Alloc, BufSize >::pop_back_aux (    )  [protected]
 

Definition at line 900 of file stl_deque.h.

template<class T, class Alloc = alloc, size_t BufSiz = 0>
void deque< T, Alloc, BufSiz >::pop_front (    )  [inline]
 

Definition at line 457 of file stl_deque.h.

References __deque_iterator< T, T &, T *, BufSiz >::cur, destroy, and __deque_iterator< T, T &, T *, BufSiz >::first. 

00457                   {
00458     if (finish.cur != finish.first) {
00459       --finish.cur;
00460       destroy(finish.cur);
00461     }
00462     else
00463       pop_back_aux();
00464   }

template<class T, class Alloc, size_t BufSize>
void deque< T, Alloc, BufSize >::pop_front_aux (    )  [protected]
 

Definition at line 912 of file stl_deque.h.

template<class T, class Alloc = alloc, size_t BufSiz = 0>
void deque< T, Alloc, BufSiz >::push_back (  const value_type &    t )  [inline]
 

Definition at line 430 of file stl_deque.h.

References finish, map, map_size, start, and swap. 

00430                       {
00431     __STD::swap(start, x.start);
00432     __STD::swap(finish, x.finish);
00433     __STD::swap(map, x.map);
00434     __STD::swap(map_size, x.map_size);
00435   }
00436 
00437 public:                         // push_* and pop_*

template<class T, class Alloc, size_t BufSize>
void deque< T, Alloc, BufSize >::push_back_aux (  const value_type &    t )  [protected]
 

Definition at line 865 of file stl_deque.h. 

00874                                                                 {
00875   value_type t_copy = t;

template<class T, class Alloc = alloc, size_t BufSiz = 0>
void deque< T, Alloc, BufSiz >::push_front (  const value_type &    t )  [inline]
 

Definition at line 439 of file stl_deque.h.

References construct, __deque_iterator< T, T &, T *, BufSiz >::cur, and __deque_iterator< T, T &, T *, BufSiz >::last. 

00439                                       {
00440     if (finish.cur != finish.last - 1) {
00441       construct(finish.cur, t);
00442       ++finish.cur;
00443     }
00444     else
00445       push_back_aux(t);
00446   }

template<class T, class Alloc, size_t BufSize>
void deque< T, Alloc, BufSize >::push_front_aux (  const value_type &    t )  [protected]
 

Definition at line 879 of file stl_deque.h. 

00888                                                                  {
00889   value_type t_copy = t;
00890   reserve_map_at_front();
00891   *(start.node - 1) = allocate_node();
00892   __STL_TRY {
00893     start.set_node(start.node - 1);
00894     start.cur = start.last - 1;
00895     construct(start.cur, t_copy);
00896   }

template<class T, class Alloc = alloc, size_t BufSiz = 0>
const_reverse_iterator deque< T, Alloc, BufSiz >::rbegin (    )  const [inline]
 

Definition at line 299 of file stl_deque.h. 

00300       :                         // Basic accessors
00301   iterator begin() { return start; }

template<class T, class Alloc = alloc, size_t BufSiz = 0>
reverse_iterator deque< T, Alloc, BufSiz >::rbegin (    )  [inline]
 

Definition at line 297 of file stl_deque.h. 

00300 :                         // Basic accessors

template<class T, class Alloc, size_t BufSize>
void deque< T, Alloc, BufSize >::reallocate_map (  size_type    nodes_to_add,
bool    add_at_front
)  [protected]
 

Definition at line 1256 of file stl_deque.h. 

01259                                                                           {
01260   for (map_pointer n = after_finish.node; n > finish.node; --n)
01261     deallocate_node(*n);
01262 }
01263 
01264 template <class T, class Alloc, size_t BufSize>
01265 void deque<T, Alloc, BufSize>::reallocate_map(size_type nodes_to_add,
01266                                               bool add_at_front) {
01267   size_type old_num_nodes = finish.node - start.node + 1;
01268   size_type new_num_nodes = old_num_nodes + nodes_to_add;
01269 
01270   map_pointer new_nstart;
01271   if (map_size > 2 * new_num_nodes) {
01272     new_nstart = map + (map_size - new_num_nodes) / 2 
01273                      + (add_at_front ? nodes_to_add : 0);
01274     if (new_nstart < start.node)
01275       copy(start.node, finish.node + 1, new_nstart);
01276     else
01277       copy_backward(start.node, finish.node + 1, new_nstart + old_num_nodes);
01278   }
01279   else {
01280     size_type new_map_size = map_size + max(map_size, nodes_to_add) + 2;
01281 
01282     map_pointer new_map = map_allocator::allocate(new_map_size);
01283     new_nstart = new_map + (new_map_size - new_num_nodes) / 2
01284                          + (add_at_front ? nodes_to_add : 0);
01285     copy(start.node, finish.node + 1, new_nstart);

template<class T, class Alloc = alloc, size_t BufSiz = 0>
const_reverse_iterator deque< T, Alloc, BufSiz >::rend (    )  const [inline]
 

Definition at line 302 of file stl_deque.h. 

00302                  { return finish; }
00303   const_iterator begin() const { return start; }
00304   const_iterator end() const { return finish; }

template<class T, class Alloc = alloc, size_t BufSiz = 0>
reverse_iterator deque< T, Alloc, BufSiz >::rend (    )  [inline]
 

Definition at line 298 of file stl_deque.h. 

00300 :                         // Basic accessors

template<class T, class Alloc = alloc, size_t BufSiz = 0>
iterator deque< T, Alloc, BufSiz >::reserve_elements_at_back (  size_type    n )  [inline, protected]
 

Definition at line 604 of file stl_deque.h.

References __deque_iterator< T, T &, T *, BufSiz >::cur, __deque_iterator::difference_type, and __deque_iterator< T, T &, T *, BufSiz >::first. 

00606                                                   {
00607     size_type vacancies = start.cur - start.first;
00608     if (n > vacancies) 
00609       new_elements_at_front(n - vacancies);

template<class T, class Alloc = alloc, size_t BufSiz = 0>
iterator deque< T, Alloc, BufSiz >::reserve_elements_at_front (  size_type    n )  [inline, protected]
 

Definition at line 597 of file stl_deque.h. 

00606                                                   {

template<class T, class Alloc = alloc, size_t BufSiz = 0>
void deque< T, Alloc, BufSiz >::reserve_map_at_back (  size_type    nodes_to_add = 1 )  [inline, protected]
 

Definition at line 623 of file stl_deque.h. 

00626          :                      // Allocation of map and nodes

template<class T, class Alloc = alloc, size_t BufSiz = 0>
void deque< T, Alloc, BufSiz >::reserve_map_at_front (  size_type    nodes_to_add = 1 )  [inline, protected]
 

Definition at line 628 of file stl_deque.h.

References __deque_iterator< T, T &, T *, BufSiz >::node. 

00632                                                         {

template<class T, class Alloc = alloc, size_t BufSiz = 0>
void deque< T, Alloc, BufSiz >::resize (  size_type    new_size )  [inline]
 

Definition at line 517 of file stl_deque.h. 

00518 {

template<class T, class Alloc = alloc, size_t BufSiz = 0>
void deque< T, Alloc, BufSiz >::resize (  size_type    new_size,
const value_type &    x
)  [inline]
 

Definition at line 509 of file stl_deque.h. 

00518                                                        {

template<class T, class Alloc = alloc, size_t BufSiz = 0>
size_type deque< T, Alloc, BufSiz >::size (    )  const [inline]
 

Definition at line 324 of file stl_deque.h.

Referenced by operator<. 

00326 { return *start; }

template<class T, class Alloc = alloc, size_t BufSiz = 0>
void deque< T, Alloc, BufSiz >::swap (  deque< T, Alloc, BufSiz > &    x )  [inline]
 

Definition at line 421 of file stl_deque.h.

References begin, copy, __deque_iterator::difference_type, and end. 

00421            {
00422         const_iterator mid = x.begin() + difference_type(len);
00423         copy(x.begin(), mid, start);
00424         insert(finish, mid, x.end());
00425       }
00426     }

Member Data Documentation

template<class T, class Alloc = alloc, size_t BufSiz = 0>
iterator deque::finish [protected]
 

Definition at line 286 of file stl_deque.h.

Referenced by push_back.

template<class T, class Alloc = alloc, size_t BufSiz = 0>
map_pointer deque::map [protected]
 

Definition at line 288 of file stl_deque.h.

Referenced by push_back.

template<class T, class Alloc = alloc, size_t BufSiz = 0>
size_type deque::map_size [protected]
 

Definition at line 289 of file stl_deque.h.

Referenced by fill_initialize, and push_back.

template<class T, class Alloc = alloc, size_t BufSiz = 0>
iterator deque::start [protected]
 

Definition at line 285 of file stl_deque.h.

Referenced by push_back.

The documentation for this class was generated from the following file:
logo OpenMask

Documentation generated on Thu May 2 15:03:27 2002

Generated with doxygen 1.2.12 by Dimitri van Heesch ,   1997-2001