home *** CD-ROM | disk | FTP | other *** search
/ Geek Gadgets 1 / ADE-1.bin / ade-dist / libg++-2.7.1-bin.lha / lib / g++-include / deque.h < prev    next >
C/C++ Source or Header  |  1996-10-12  |  20KB  |  682 lines
  1. /*
  2.  *
  3.  * Copyright (c) 1994
  4.  * Hewlett-Packard Company
  5.  *
  6.  * Permission to use, copy, modify, distribute and sell this software
  7.  * and its documentation for any purpose is hereby granted without fee,
  8.  * provided that the above copyright notice appear in all copies and
  9.  * that both that copyright notice and this permission notice appear
  10.  * in supporting documentation.  Hewlett-Packard Company makes no
  11.  * representations about the suitability of this software for any
  12.  * purpose.  It is provided "as is" without express or implied warranty.
  13.  *
  14.  */
  15.  
  16. #ifndef DEQUE_H
  17. #define DEQUE_H
  18.  
  19. #include <function.h>
  20. #include <algobase.h>
  21. #include <iterator.h>
  22. #ifndef __GNUG__
  23. #include <bool.h>
  24. #endif
  25.  
  26. #ifndef Allocator
  27. #define Allocator allocator
  28. #include <defalloc.h>
  29. #endif
  30.  
  31. #ifndef deque 
  32. #define deque deque
  33. #endif
  34.  
  35. template <class T> 
  36. class deque {
  37. public:
  38.     class iterator;
  39.     class const_iterator;
  40.     friend class iterator;
  41.     friend class const_iterator;
  42. public:
  43.     typedef T value_type;
  44.     typedef Allocator<T> data_allocator_type;
  45.     typedef Allocator<T>::pointer pointer;
  46.     typedef Allocator<T>::reference reference;
  47.     typedef Allocator<T>::const_reference const_reference;
  48.     typedef Allocator<T>::size_type size_type;
  49.     typedef Allocator<T>::difference_type difference_type;
  50.     typedef Allocator<pointer> map_allocator_type;   
  51. protected:
  52.     static data_allocator_type data_allocator;
  53. #ifdef __GNUG__
  54.     //    static  // Too bad -- I don't like this hack very much...
  55.     static size_type buffer_size() {
  56.     return data_allocator.init_page_size();
  57.     }
  58. #define __dq_buffer_size buffer_size()
  59. #else
  60.     static size_type buffer_size;
  61. #define __dq_buffer_size buffer_size
  62. #endif
  63.     static map_allocator_type map_allocator;
  64.     typedef Allocator<pointer>::pointer map_pointer;
  65. public:
  66.     class iterator : public random_access_iterator<T, difference_type> {
  67.     friend class deque<T>;
  68.     friend class const_iterator;
  69.     protected:
  70.     pointer current;
  71.     pointer first;
  72.     pointer last;
  73.     map_pointer node;
  74.     iterator(pointer x, map_pointer y) 
  75.         : current(x), first(*y), last(*y + __dq_buffer_size), node(y) {}
  76.     public:
  77.     iterator() : current(0), first(0), last(0), node(0) {}
  78.     reference operator*() const { return *current; }
  79.     difference_type operator-(const iterator& x) const {
  80.         return node == x.node 
  81.         ? current - x.current 
  82.         : difference_type(__dq_buffer_size * (node - x.node - 1) +
  83.                   (current - first) + (x.last - x.current));
  84.     }
  85.     iterator& operator++() {
  86.         if (++current == last) {
  87.         first = *(++node);
  88.         current = first;
  89.         last = first + __dq_buffer_size;
  90.         }
  91.         return *this; 
  92.     }
  93.     iterator operator++(int)  {
  94.         iterator tmp = *this;
  95.         ++*this;
  96.         return tmp;
  97.     }
  98.     iterator& operator--() {
  99.         if (current == first) {
  100.         first = *(--node);
  101.         last = first + __dq_buffer_size;
  102.         current = last;
  103.         }
  104.         --current;
  105.         return *this;
  106.     }
  107.     iterator operator--(int) {
  108.         iterator tmp = *this;
  109.         --*this;
  110.         return tmp;
  111.     }
  112.     iterator& operator+=(difference_type n) {
  113.         difference_type offset = n + (current - first);
  114.         difference_type num_node_to_jump = offset >= 0
  115.         ? offset / __dq_buffer_size
  116.         : -((-offset + __dq_buffer_size - 1) / __dq_buffer_size);
  117.         if (num_node_to_jump == 0)
  118.         current += n;
  119.         else {
  120.         node = node + num_node_to_jump;
  121.         first = *node;
  122.         last = first + __dq_buffer_size;
  123.         current = first + (offset - num_node_to_jump * __dq_buffer_size);
  124.         }
  125.         return *this;
  126.     }
  127.     iterator& operator-=(difference_type n) { return *this += -n; }
  128.     iterator operator+(difference_type n) const {
  129.         iterator tmp = *this;
  130.         return tmp += n;
  131.     }
  132.     iterator operator-(difference_type n) const {
  133.         iterator tmp = *this;
  134.         return tmp -= n;
  135.     }
  136.     reference operator[](difference_type n) { return *(*this + n); }
  137.     bool operator==(const iterator& x) const {      
  138.         return current == x.current || 
  139.         ((current == first || x.current == x.first) && 
  140.          *this - x == 0);
  141.     }
  142.     bool operator<(const iterator& x) const {
  143.         return (node == x.node) ? (current < x.current) : (node < x.node);
  144.     }
  145.     };
  146.     class const_iterator : public random_access_iterator<T, difference_type> {
  147.     friend class deque<T>;
  148.     protected:
  149.     pointer current;
  150.     pointer first;
  151.     pointer last;
  152.     map_pointer node;
  153.     const_iterator(pointer x, map_pointer y) 
  154.         : current(x), first(*y), last(*y + __dq_buffer_size), node(y) {}
  155.     public:
  156.     const_iterator() : current(0), first(0), last(0), node(0) {}
  157.     const_iterator(const iterator& x) 
  158.         : current(x.current), first(x.first), last(x.last), node(x.node) {}     
  159.     const_reference operator*() const { return *current; }
  160.     difference_type operator-(const const_iterator& x) const {
  161.         return node == x.node 
  162.         ? current - x.current 
  163.         : difference_type(__dq_buffer_size * (node - x.node - 1) +
  164.                   (current - first) + (x.last - x.current));
  165.     }
  166.     const_iterator& operator++() {
  167.         if (++current == last) {
  168.         first = *(++node);
  169.         current = first;
  170.         last = first + __dq_buffer_size;
  171.         }
  172.         return *this; 
  173.     }
  174.     const_iterator operator++(int)  {
  175.         const_iterator tmp = *this;
  176.         ++*this;
  177.         return tmp;
  178.     }
  179.     const_iterator& operator--() {
  180.         if (current == first) {
  181.         first = *(--node);
  182.         last = first + __dq_buffer_size;
  183.         current = last;
  184.         }
  185.         --current;
  186.         return *this;
  187.     }
  188.     const_iterator operator--(int) {
  189.         const_iterator tmp = *this;
  190.         --*this;
  191.         return tmp;
  192.     }
  193.     const_iterator& operator+=(difference_type n) {
  194.         difference_type offset = n + (current - first);
  195.         difference_type num_node_to_jump = offset >= 0
  196.         ? offset / __dq_buffer_size
  197.         : -((-offset + __dq_buffer_size - 1) / __dq_buffer_size);
  198.         if (num_node_to_jump == 0)
  199.         current += n;
  200.         else {
  201.         node = node + num_node_to_jump;
  202.         first = *node;
  203.         last = first + __dq_buffer_size;
  204.         current = first + (offset - num_node_to_jump * __dq_buffer_size);
  205.         }
  206.         return *this;
  207.     }
  208.     const_iterator& operator-=(difference_type n) { return *this += -n; }
  209.     const_iterator operator+(difference_type n) const {
  210.         const_iterator tmp = *this;
  211.         return tmp += n;
  212.     }
  213.     const_iterator operator-(difference_type n) const {
  214.         const_iterator tmp = *this;
  215.         return tmp -= n;
  216.     }
  217.     const_reference operator[](difference_type n) { 
  218.         return *(*this + n); 
  219.     }
  220.     bool operator==(const const_iterator& x) const {      
  221.         return current == x.current || 
  222.         ((current == first || x.current == x.first) && 
  223.          *this - x == 0);
  224.     }
  225.     bool operator<(const const_iterator& x) const {
  226.         return (node == x.node) ? (current < x.current) : (node < x.node);
  227.     }
  228.     };
  229.     typedef reverse_iterator<const_iterator, value_type, const_reference, 
  230.                              difference_type>  const_reverse_iterator;
  231.     typedef reverse_iterator<iterator, value_type, reference, difference_type>
  232.         reverse_iterator; 
  233. protected:    
  234.     iterator start;
  235.     iterator finish;
  236.     size_type length;
  237.     map_pointer map;
  238.     size_type map_size;
  239.  
  240.     void allocate_at_begin();
  241.     void allocate_at_end();
  242.     void deallocate_at_begin();
  243.     void deallocate_at_end();
  244.  
  245. public:
  246.     deque() : start(), finish(), length(0), map(0), map_size(0) {
  247. #ifndef __GNUG__
  248.     __dq_buffer_size = data_allocator.init_page_size();
  249. #endif
  250.     }
  251.     iterator begin() { return start; }
  252.     const_iterator begin() const { return start; }
  253.     iterator end() { return finish; }
  254.     const_iterator end() const { return finish; }
  255.     reverse_iterator rbegin() { return reverse_iterator(end()); }
  256.     const_reverse_iterator rbegin() const { 
  257.         return const_reverse_iterator(end()); 
  258.     }
  259.     reverse_iterator rend() { return reverse_iterator(begin()); }
  260.     const_reverse_iterator rend() const { 
  261.         return const_reverse_iterator(begin()); 
  262.     } 
  263.     bool empty() const { return length == 0; }
  264.     size_type size() const { return length; }
  265.     size_type max_size() const { return data_allocator.max_size(); }
  266.     reference operator[](size_type n) { return *(begin() + n); }
  267.     const_reference operator[](size_type n) const { return *(begin() + n); }
  268.     reference front() { return *begin(); }
  269.     const_reference front() const { return *begin(); }
  270.     reference back() { return *(end() - 1); }
  271.     const_reference back() const { return *(end() - 1); }
  272.     void push_front(const T& x) {
  273.     if (empty() || begin().current == begin().first)
  274.         allocate_at_begin();
  275.     --start.current;
  276.     construct(start.current, x);
  277.     ++length;
  278.     if (end().current == end().last) allocate_at_end();
  279.     }
  280.     void push_back(const T& x) {
  281.     if (empty()) allocate_at_end();
  282.     construct(finish.current, x);
  283.     ++finish.current;
  284.     ++length;
  285.     if (end().current == end().last) allocate_at_end();
  286.     }
  287.     void pop_front() {
  288.     destroy(start.current);
  289.     ++start.current;
  290.     --length; 
  291.     if (empty() || begin().current == begin().last)
  292.         deallocate_at_begin();
  293.     }
  294.     void pop_back() {
  295.     if (end().current == end().first) deallocate_at_end();
  296.     --finish.current;
  297.     destroy(finish.current);
  298.     --length; 
  299.     if (empty()) deallocate_at_end();
  300.     }
  301.     void swap(deque<T>& x) {
  302.     ::swap(start, x.start);
  303.     ::swap(finish, x.finish);
  304.     ::swap(length, x.length);
  305.     ::swap(map, x.map);
  306.     ::swap(map_size, x.map_size);
  307.     }
  308. #ifdef __GNUG__
  309.     iterator insert(iterator position, const T& x) {
  310.     return insert(deque_iterator<T>(position), x);
  311.     }
  312.     deque_iterator<T> insert(deque_iterator<T> position, const T& x);
  313.     void insert(iterator position, size_type n, const T& x) {
  314.     insert(deque_iterator<T>(position), n, x);
  315.     }
  316.     void insert(deque_iterator<T>(position), size_type n, const T& x);
  317. //  template <class Iterator> void insert(iterator position,
  318. //                                        Iterator first, Iterator last);
  319.     void insert(iterator position, const T* first, const T* last) {
  320.     insert(deque_iterator<T>(position), first, last);
  321.     }
  322.     void insert(deque_iterator<T> position, const T* first, const T* last);
  323.     void erase(iterator position) {
  324.     erase(deque_iterator<T>(position));
  325.     }
  326.     void erase(deque_iterator<T> position);
  327.     void erase(iterator first, iterator last) {
  328.     erase(deque_iterator<T>(first), deque_iterator<T>(last));
  329.     }
  330.     void erase(deque_iterator<T> first, deque_iterator<T> last);    
  331. #else
  332.     iterator insert(iterator position, const T& x);
  333.     void insert(iterator position, size_type n, const T& x);
  334. //  template <class Iterator> void insert(iterator position,
  335. //                                        Iterator first, Iterator last);
  336.     void insert(iterator position, const T* first, const T* last);
  337.     void erase(iterator position);
  338.     void erase(iterator first, iterator last);
  339. #endif    
  340.     deque(size_type n, const T& value = T())
  341.     : start(), finish(), length(0), map(0), map_size(0) {
  342. #ifndef __GNUG__
  343.     __dq_buffer_size = data_allocator.init_page_size();  
  344. #endif
  345.     insert(begin(), n, value);
  346.     }
  347. //  template <class Iterator> deque(Iterator first, Iterator last);
  348.     deque(const T* first, const T* last)
  349.     : start(), finish(), length(0), map(0), map_size(0) {
  350. #ifndef __GNUG__
  351.     __dq_buffer_size = data_allocator.init_page_size();  
  352. #endif
  353.     copy(first, last, back_inserter(*this));
  354.     }
  355.     deque(const deque<T>& x)
  356.     : start(), finish(), length(0), map(0), map_size(0) {
  357. #ifndef __GNUG__
  358.     __dq_buffer_size = data_allocator.init_page_size();  
  359. #endif
  360.     copy(x.begin(), x.end(), back_inserter(*this));
  361.     }
  362.     deque<T>& operator=(const deque<T>& x) {
  363.     if (this != &x)
  364.         if (size() >= x.size()) 
  365.         erase(copy(x.begin(), x.end(), begin()), end());
  366.         else 
  367.         copy(x.begin() + size(), x.end(),
  368.              inserter(*this, copy(x.begin(), x.begin() + size(),
  369.                       begin())));
  370.     return *this;
  371.     }
  372.     ~deque();
  373. #ifdef __GNUG__
  374.     friend T* value_type(const iterator&) {
  375.     return (T*)(0);
  376.     }
  377. #endif
  378. };
  379.  
  380. #ifdef __GNUG__
  381. template <class T>
  382. struct deque_iterator: deque<T>::iterator {
  383.     deque_iterator(deque<T>::iterator i) : deque<T>::iterator(i) {}
  384. };
  385.  
  386. template <class T>
  387. inline T* value_type(const deque_iterator<T>&) {
  388.     return (T*)(0);
  389. }
  390. #else
  391. template <class T>
  392. deque<T>::data_allocator_type deque<T>::data_allocator;
  393.  
  394. template <class T>
  395. deque<T>::map_allocator_type deque<T>::map_allocator;
  396.  
  397. template <class T>
  398. deque<T>::size_type deque<T>::__dq_buffer_size = 0; 
  399. // should be data_allocator.init_page_size(); // Borland bug
  400. #endif
  401.  
  402. template <class T>
  403. bool operator==(const deque<T>& x, const deque<T>& y) {
  404.     return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
  405. }
  406.  
  407. template <class T>
  408. bool operator<(const deque<T>& x, const deque<T>& y) {
  409.     return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
  410. }
  411.  
  412. template <class T>
  413. deque<T>::~deque() { while (!empty()) pop_front(); }     
  414.  
  415. template <class T>
  416. void deque<T>::allocate_at_begin() {
  417.     pointer p = data_allocator.allocate(__dq_buffer_size);
  418.     if (!empty()) {
  419.     if (start.node == map) {
  420.         difference_type i = finish.node - start.node;
  421.         map_size = (i + 1) * 2;
  422. #ifdef __GNU_G__
  423.         map_pointer tmp = map_allocator_type::allocate(map_size);
  424.         copy(start.node, finish.node + 1, tmp + map_size / 4 + 1);
  425.         map_allocator_type::deallocate(map);
  426. #else
  427.         map_pointer tmp = map_allocator.allocate(map_size);
  428.         copy(start.node, finish.node + 1, tmp + map_size / 4 + 1);
  429.         map_allocator.deallocate(map);
  430. #endif
  431.         map = tmp;
  432.         map[map_size / 4] = p;
  433.         start = iterator(p + __dq_buffer_size, map + map_size / 4);
  434.         finish = iterator(finish.current, map + map_size / 4 + i + 1);
  435.     } else {
  436. #ifdef __GNUG__
  437.     map_size = map_allocator_type::init_page_size();
  438.     map = map_allocator_type::allocate(map_size);
  439. #else
  440.         *--start.node = p;
  441.         start = iterator(p + __dq_buffer_size, start.node);
  442. #endif
  443.     }
  444.     } else {
  445. #ifdef __GNUG__
  446.     map_size = map_allocator_type::init_page_size();
  447.     map = map_allocator_type::allocate(map_size);
  448. #else
  449.     map_size = map_allocator.init_page_size();
  450.     map = map_allocator.allocate(map_size);
  451. #endif
  452.     map[map_size / 2] = p;
  453.     start = iterator(p + __dq_buffer_size / 2 + 1, map + map_size / 2);
  454.     finish = start;
  455.     }
  456. }
  457.  
  458. template <class T>
  459. void deque<T>::allocate_at_end() {
  460.     pointer p = data_allocator.allocate(__dq_buffer_size);
  461.     if (!empty()) {
  462.     if (finish.node == map + map_size - 1) {
  463.         difference_type i = finish.node - start.node;
  464.          map_size = (i + 1) * 2;
  465. #ifdef __GNUG__
  466.         map_pointer tmp = map_allocator_type::allocate(map_size);
  467.         copy(start.node, finish.node + 1, tmp + map_size / 4);
  468.         map_allocator_type::deallocate(map);
  469. #else
  470.         map_pointer tmp = map_allocator.allocate(map_size);
  471.         copy(start.node, finish.node + 1, tmp + map_size / 4);
  472.         map_allocator.deallocate(map);
  473. #endif
  474.         map = tmp;
  475.          map[map_size / 4 + i + 1] = p;
  476.         start = iterator(start.current, map + map_size / 4);
  477.         finish = iterator(p, map + map_size / 4 + i + 1);
  478.     } else {
  479.         *++finish.node = p;
  480.         finish = iterator(p, finish.node);
  481.     }
  482.     } else {
  483. #ifdef __GNUG__
  484.     map_size = map_allocator_type::init_page_size();
  485.     map = map_allocator_type::allocate(map_size);
  486. #else
  487.     map_size = map_allocator.init_page_size();
  488.     map = map_allocator.allocate(map_size);
  489. #endif
  490.     map[map_size / 2] = p;
  491.     start = iterator(p + __dq_buffer_size / 2, map + map_size / 2);
  492.     finish = start;
  493.     }
  494. }
  495.  
  496. template <class T>
  497. void deque<T>::deallocate_at_begin() {
  498.     data_allocator.deallocate(*start.node++);
  499.     if (empty()) {
  500.     if (finish.current == finish.first) 
  501.         data_allocator.deallocate(*start.node);
  502.     start = iterator();
  503.     finish = start;
  504. #ifdef __GNUG__
  505.     map_allocator.deallocate(map);
  506. #else
  507.     map_allocator.deallocate(map);
  508. #endif
  509.     } else
  510.     start = iterator(*start.node, start.node);
  511. }
  512.  
  513. template <class T>
  514. void deque<T>::deallocate_at_end() {
  515.     data_allocator.deallocate(*finish.node--);
  516.     if (empty()) {
  517.     start = iterator();
  518.     finish = start;
  519. #ifdef __GNUG__
  520.     map_allocator.deallocate(map);
  521. #else
  522.     map_allocator.deallocate(map);
  523. #endif
  524.     } else
  525.     finish = iterator(*finish.node + __dq_buffer_size, finish.node);
  526. }
  527.  
  528. template <class T>
  529. #ifdef __GNUG__
  530. deque_iterator<T>
  531. deque<T>::insert(deque_iterator<T> posn, const T& x) {
  532.     iterator position = posn;
  533. #else
  534. deque<T>::iterator deque<T>::insert(iterator position, const T& x) {
  535. #endif
  536.     if (position == begin()) {
  537.     push_front(x);
  538.     return begin();
  539.     } else if (position == end()) {
  540.     push_back(x);
  541.     return end() - 1;
  542.     } else {
  543.     difference_type index = position - begin();
  544.     if (index < length) {
  545.         push_front(*begin());
  546.         copy(begin() + 2, begin() + index + 1, begin() + 1); 
  547.     } else {
  548.         push_back(*(end() - 1));
  549.         copy_backward(begin() + index, end() - 2, end() - 1); 
  550.         }
  551.     *(begin() + index) = x;
  552.     return begin() + index;
  553.     }
  554. }
  555.  
  556. template <class T>
  557. #ifdef __GNUG__
  558. void deque<T>::insert(deque_iterator<T> posn,
  559.               size_t n, // BAD HACK
  560.               const T& x) {
  561.     iterator position = posn;
  562. #else
  563. void deque<T>::insert(iterator position, size_type n, const T& x) {
  564. #endif
  565.     difference_type index = position - begin();
  566.     difference_type remainder = length - index;
  567.     if (remainder > index) {
  568.     if (n > index) {
  569.         difference_type m = n - index;
  570.         while (m-- > 0) push_front(x);
  571.         difference_type i = index;
  572.         while (i--) push_front(*(begin() + n - 1));
  573.         fill(begin() + n, begin() + n + index, x);
  574.     } else {
  575.         difference_type i = n;
  576.         while (i--) push_front(*(begin() + n - 1));
  577.         copy(begin() + n + n, begin() + n + index, begin() + n);
  578.         fill(begin() + index, begin() + n + index, x);
  579.     }
  580.     } else {
  581.     difference_type orig_len = index + remainder;
  582.     if (n > remainder) {
  583.         difference_type m = n - remainder;
  584.         while (m-- > 0) push_back(x);
  585.         difference_type i = 0;
  586.         while (i < remainder) push_back(*(begin() + index + i++));
  587.         fill(begin() + index, begin() + orig_len, x);
  588.     } else {
  589.         difference_type i = 0;
  590.         while (i < n) push_back(*(begin() + orig_len - n + i++));
  591.         copy_backward(begin() + index, begin() + orig_len - n, 
  592.               begin() + orig_len);
  593.         fill(begin() + index, begin() + index + n, x);
  594.     }
  595.     }
  596. }
  597.  
  598. template <class T>
  599. void deque<T>::insert
  600. #ifdef __GNUG__
  601. (deque_iterator<T> posn, const T* first, const T* last)
  602. {
  603.     iterator position = posn;
  604. #else
  605. (iterator position, const T* first, const T* last)
  606. {
  607. #endif
  608.     difference_type index = position - begin();
  609.     difference_type remainder = length - index;
  610.     size_type n = 0;
  611.     distance(first, last, n);
  612.     if (remainder > index) {
  613.     if (n > index) {
  614.         const T* m = last - index;
  615.         while (m != first) push_front(*--m);
  616.         difference_type i = index;
  617.         while (i--) push_front(*(begin() + n - 1));
  618.         copy(last - index, last, begin() + n);
  619.     } else {
  620.         difference_type i = n;
  621.         while (i--) push_front(*(begin() + n - 1));
  622.         copy(begin() + n + n, begin() + n + index, begin() + n);
  623.         copy(first, last, begin() + index);
  624.     }
  625.     } else {
  626.     difference_type orig_len = index + remainder;
  627.     if (n > remainder) {
  628.         const T* m = first + remainder;
  629.         while (m != last) push_back(*m++);
  630.         difference_type i = 0;
  631.         while (i < remainder) push_back(*(begin() + index + i++));
  632.         copy(first, first + remainder, begin() + index);
  633.     } else {
  634.         difference_type i = 0;
  635.         while (i < n) push_back(*(begin() + orig_len - n + i++));
  636.         copy_backward(begin() + index, begin() + orig_len - n, 
  637.               begin() + orig_len);
  638.         copy(first, last, begin() + index);
  639.     }
  640.     }
  641. }
  642.  
  643. template <class T>
  644. #ifdef __GNUG__
  645. void deque<T>::erase(deque_iterator<T> posn) {
  646.     iterator position = posn;
  647. #else
  648. void deque<T>::erase(iterator position) {
  649. #endif
  650.     if (end() - position > position - begin()) {
  651.     copy_backward(begin(), position, position + 1);
  652.     pop_front();
  653.     } else {
  654.     copy(position + 1, end(), position);
  655.     pop_back();
  656.     }
  657. }
  658.     
  659. template <class T>
  660. #ifdef __GNUG__
  661. void deque<T>::erase(deque_iterator<T> fi, deque_iterator<T> la) {
  662.     iterator first = fi;
  663.     iterator last = la;
  664.     difference_type n = last - first;
  665. #else
  666. void deque<T>::erase(iterator first, iterator last) {
  667.      difference_type n = last - first;
  668. #endif
  669.     if (end() - last > first - begin()) {
  670.     copy_backward(begin(), first, last);
  671.     while(n-- > 0) pop_front();
  672.     } else   {
  673.     copy(last, end(), first);
  674.     while(n-- > 0) pop_back();
  675.     }
  676. }
  677.  
  678. #undef Allocator
  679. #undef deque
  680.  
  681. #endif
  682.