| /* |
| * |
| * Copyright (c) 1994 |
| * Hewlett-Packard Company |
| * |
| * Permission to use, copy, modify, distribute and sell this software |
| * and its documentation for any purpose is hereby granted without fee, |
| * provided that the above copyright notice appear in all copies and |
| * that both that copyright notice and this permission notice appear |
| * in supporting documentation. Hewlett-Packard Company makes no |
| * representations about the suitability of this software for any |
| * purpose. It is provided "as is" without express or implied warranty. |
| * |
| * |
| * Copyright (c) 1997 |
| * Silicon Graphics Computer Systems, Inc. |
| * |
| * Permission to use, copy, modify, distribute and sell this software |
| * and its documentation for any purpose is hereby granted without fee, |
| * provided that the above copyright notice appear in all copies and |
| * that both that copyright notice and this permission notice appear |
| * in supporting documentation. Silicon Graphics makes no |
| * representations about the suitability of this software for any |
| * purpose. It is provided "as is" without express or implied warranty. |
| */ |
| |
| #ifndef __SGI_STL_DEQUE_H |
| #define __SGI_STL_DEQUE_H |
| |
| /* Class invariants: |
| * For any nonsingular iterator i: |
| * i.node is the address of an element in the map array. The |
| * contents of i.node is a pointer to the beginning of a node. |
| * i.first == *(i.node) |
| * i.last == i.first + node_size |
| * i.cur is a pointer in the range [i.first, i.last). NOTE: |
| * the implication of this is that i.cur is always a dereferenceable |
| * pointer, even if i is a past-the-end iterator. |
| * Start and Finish are always nonsingular iterators. NOTE: this means |
| * that an empty deque must have one node, and that a deque |
| * with N elements, where N is the buffer size, must have two nodes. |
| * For every node other than start.node and finish.node, every element |
| * in the node is an initialized object. If start.node == finish.node, |
| * then [start.cur, finish.cur) are initialized objects, and |
| * the elements outside that range are uninitialized storage. Otherwise, |
| * [start.cur, start.last) and [finish.first, finish.cur) are initialized |
| * objects, and [start.first, start.cur) and [finish.cur, finish.last) |
| * are uninitialized storage. |
| * [map, map + map_size) is a valid, non-empty range. |
| * [start.node, finish.node] is a valid range contained within |
| * [map, map + map_size). |
| * A pointer in the range [map, map + map_size) points to an allocated |
| * node if and only if the pointer is in the range [start.node, finish.node]. |
| */ |
| |
| |
| /* |
| * In previous versions of deque, node_size was fixed by the |
| * implementation. In this version, however, users can select |
| * the node size. Deque has three template parameters; the third, |
| * a number of type size_t, is the number of elements per node. |
| * If the third template parameter is 0 (which is the default), |
| * then deque will use a default node size. |
| * |
| * The only reason for using an alternate node size is if your application |
| * requires a different performance tradeoff than the default. If, |
| * for example, your program contains many deques each of which contains |
| * only a few elements, then you might want to save memory (possibly |
| * by sacrificing some speed) by using smaller nodes. |
| * |
| * Unfortunately, some compilers have trouble with non-type template |
| * parameters; stl_config.h defines __STL_NON_TYPE_TMPL_PARAM_BUG if |
| * that is the case. If your compiler is one of them, then you will |
| * not be able to use alternate node sizes; you will have to use the |
| * default value. |
| */ |
| |
| #include <stddef.h> |
| #include <algobase.h> |
| #include <alloc.h> |
| |
| // Note: this function is simply a kludge to work around several compilers' |
| // bugs in handling constant expressions. |
| inline size_t __deque_buf_size(size_t n, size_t sz) |
| { |
| return n != 0 ? n : (sz < 512 ? size_t(512 / sz) : size_t(1)); |
| } |
| |
| #ifndef __STL_NON_TYPE_TMPL_PARAM_BUG |
| template <class T, class Ref, size_t BufSiz> |
| struct __deque_iterator { |
| typedef __deque_iterator<T, T&, BufSiz> iterator; |
| typedef __deque_iterator<T, const T&, BufSiz> const_iterator; |
| static size_t buffer_size() {return __deque_buf_size(BufSiz, sizeof(T)); } |
| #else /* __STL_NON_TYPE_TMPL_PARAM_BUG */ |
| template <class T, class Ref> |
| struct __deque_iterator { |
| typedef __deque_iterator<T, T&> iterator; |
| typedef __deque_iterator<T, const T&> const_iterator; |
| static size_t buffer_size() {return __deque_buf_size(0, sizeof(T)); } |
| #endif |
| |
| typedef random_access_iterator_tag iterator_category; |
| typedef T value_type; |
| typedef value_type* pointer; |
| typedef value_type& reference; |
| typedef const value_type& const_reference; |
| typedef size_t size_type; |
| typedef ptrdiff_t difference_type; |
| typedef pointer* map_pointer; |
| |
| typedef __deque_iterator self; |
| |
| pointer cur; |
| pointer first; |
| pointer last; |
| map_pointer node; |
| |
| __deque_iterator(pointer x, map_pointer y) |
| : cur(x), first(*y), last(*y + buffer_size()), node(y) {} |
| __deque_iterator() : cur(0), first(0), last(0), node(0) {} |
| __deque_iterator(const iterator& x) |
| : cur(x.cur), first(x.first), last(x.last), node(x.node) {} |
| |
| Ref operator*() const { return *cur; } |
| |
| difference_type operator-(const self& x) const { |
| return buffer_size() * (node - x.node - 1) + |
| (cur - first) + (x.last - x.cur); |
| } |
| |
| self& operator++() { |
| ++cur; |
| if (cur == last) { |
| set_node(node + 1); |
| cur = first; |
| } |
| return *this; |
| } |
| self operator++(int) { |
| self tmp = *this; |
| ++*this; |
| return tmp; |
| } |
| |
| self& operator--() { |
| if (cur == first) { |
| set_node(node - 1); |
| cur = last; |
| } |
| --cur; |
| return *this; |
| } |
| self operator--(int) { |
| self tmp = *this; |
| --*this; |
| return tmp; |
| } |
| |
| self& operator+=(difference_type n) { |
| difference_type offset = n + (cur - first); |
| if (offset >= 0 && offset < buffer_size()) |
| cur += n; |
| else { |
| difference_type node_offset = |
| offset > 0 ? offset / buffer_size() |
| : -difference_type((-offset - 1) / buffer_size()) - 1; |
| set_node(node + node_offset); |
| cur = first + (offset - node_offset * buffer_size()); |
| } |
| return *this; |
| } |
| |
| self operator+(difference_type n) const { |
| self tmp = *this; |
| return tmp += n; |
| } |
| |
| self& operator-=(difference_type n) { return *this += -n; } |
| |
| self operator-(difference_type n) const { |
| self tmp = *this; |
| return tmp -= n; |
| } |
| |
| Ref operator[](difference_type n) const { return *(*this + n); } |
| |
| bool operator==(const self& x) const { return cur == x.cur; } |
| bool operator!=(const self& x) const { return !(*this == x); } |
| bool operator<(const self& x) const { |
| return (node == x.node) ? (cur < x.cur) : (node < x.node); |
| } |
| |
| void set_node(map_pointer new_node) { |
| node = new_node; |
| first = *new_node; |
| last = first + buffer_size(); |
| } |
| }; |
| |
| #ifndef __STL_NON_TYPE_TMPL_PARAM_BUG |
| |
| template <class T, class Ref, size_t BufSiz> |
| inline random_access_iterator_tag |
| iterator_category(const __deque_iterator<T, Ref, BufSiz>&) { |
| return random_access_iterator_tag(); |
| } |
| |
| template <class T, class Ref, size_t BufSiz> |
| inline T* value_type(const __deque_iterator<T, Ref, BufSiz>&) { return 0; } |
| |
| template <class T, class Ref, size_t BufSiz> |
| inline ptrdiff_t* distance_type(const __deque_iterator<T, Ref, BufSiz>&) { |
| return 0; |
| } |
| |
| #else /* __STL_NON_TYPE_TMPL_PARAM_BUG */ |
| |
| template <class T, class Ref> |
| inline random_access_iterator_tag |
| iterator_category(const __deque_iterator<T, Ref>&) { |
| return random_access_iterator_tag(); |
| } |
| |
| template <class T, class Ref> |
| inline T* value_type(const __deque_iterator<T, Ref>&) { return 0; } |
| |
| template <class T, class Ref> |
| inline ptrdiff_t* distance_type(const __deque_iterator<T, Ref>&) { |
| return 0; |
| } |
| |
| #endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */ |
| |
| |
| // See __deque_buf_size(). The only reason that the default value is 0 |
| // is as a workaround for bugs in the way that some compilers handle |
| // constant expressions. |
| template <class T, class Alloc = alloc, size_t BufSiz = 0> |
| class deque { |
| public: // Basic types |
| typedef T value_type; |
| typedef value_type* pointer; |
| typedef value_type& reference; |
| typedef const value_type& const_reference; |
| typedef size_t size_type; |
| typedef ptrdiff_t difference_type; |
| |
| public: // Iterators |
| #ifndef __STL_NON_TYPE_TMPL_PARAM_BUG |
| typedef __deque_iterator<value_type, reference, BufSiz> iterator; |
| typedef __deque_iterator<value_type, const_reference, BufSiz> const_iterator; |
| #else /* __STL_NON_TYPE_TMPL_PARAM_BUG */ |
| typedef __deque_iterator<value_type, reference> iterator; |
| typedef __deque_iterator<value_type, const_reference> const_iterator; |
| #endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */ |
| 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; |
| |
| protected: // Internal typedefs |
| typedef pointer* map_pointer; |
| typedef simple_alloc<value_type, Alloc> data_allocator; |
| typedef simple_alloc<pointer, Alloc> map_allocator; |
| |
| static size_type buffer_size() { |
| return __deque_buf_size(BufSiz, sizeof(value_type)); |
| } |
| static size_type initial_map_size() { return 8; } |
| |
| protected: // Data members |
| iterator start; |
| iterator finish; |
| |
| map_pointer map; |
| size_type map_size; |
| |
| public: // Basic accessors |
| iterator begin() { return start; } |
| iterator end() { return finish; } |
| const_iterator begin() const { return start; } |
| const_iterator end() const { return finish; } |
| |
| reverse_iterator rbegin() { return reverse_iterator(finish); } |
| reverse_iterator rend() { return reverse_iterator(start); } |
| const_reverse_iterator rbegin() const { |
| return const_reverse_iterator(finish); |
| } |
| const_reverse_iterator rend() const { |
| return const_reverse_iterator(start); |
| } |
| |
| reference operator[](size_type n) { return start[n]; } |
| const_reference operator[](size_type n) const { return start[n]; } |
| |
| reference front() { return *start; } |
| reference back() { |
| iterator tmp = finish; |
| --tmp; |
| return *tmp; |
| } |
| const_reference front() const { return *start; } |
| const_reference back() const { |
| const_iterator tmp = finish; |
| --tmp; |
| return *tmp; |
| } |
| |
| size_type size() const { return finish - start;; } |
| size_type max_size() const { return size_type(-1); } |
| bool empty() const { return finish == start; } |
| |
| public: // Constructor, destructor. |
| deque() |
| : start(), finish(), map(0), map_size(0) |
| { |
| create_map_and_nodes(0); |
| } |
| |
| deque(const deque& x) |
| : start(), finish(), map(0), map_size(0) |
| { |
| create_map_and_nodes(x.size()); |
| # ifdef __STL_USE_EXCEPTIONS |
| try { |
| # endif /* __STL_USE_EXCEPTIONS */ |
| uninitialized_copy(x.begin(), x.end(), start); |
| # ifdef __STL_USE_EXCEPTIONS |
| } |
| catch(...) { |
| destroy_map_and_nodes(); |
| throw; |
| } |
| # endif /* __STL_USE_EXCEPTIONS */ |
| } |
| |
| deque(size_type n, const value_type& value) |
| : start(), finish(), map(0), map_size(0) { |
| fill_initialize(n, value); |
| } |
| |
| deque(int n, const value_type& value) |
| : start(), finish(), map(0), map_size(0) { |
| fill_initialize(n, value); |
| } |
| |
| deque(long n, const value_type& value) |
| : start(), finish(), map(0), map_size(0) { |
| fill_initialize(n, value); |
| } |
| |
| explicit deque(size_type n) |
| : start(), finish(), map(0), map_size(0) { |
| fill_initialize(n, value_type()); |
| } |
| |
| #ifdef __STL_MEMBER_TEMPLATES |
| |
| template <class InputIterator> |
| deque(InputIterator first, InputIterator last) |
| : start(), finish(), map(0), map_size(0) |
| { |
| range_initialize(first, last, iterator_category(first)); |
| } |
| |
| #else /* __STL_MEMBER_TEMPLATES */ |
| |
| deque(const value_type* first, const value_type* last) |
| : start(), finish(), map(0), map_size(0) |
| { |
| create_map_and_nodes(last - first); |
| # ifdef __STL_USE_EXCEPTIONS |
| try { |
| # endif /* __STL_USE_EXCEPTIONS */ |
| uninitialized_copy(first, last, start); |
| # ifdef __STL_USE_EXCEPTIONS |
| } |
| catch(...) { |
| destroy_map_and_nodes(); |
| throw; |
| } |
| # endif /* __STL_USE_EXCEPTIONS */ |
| } |
| |
| deque(const_iterator first, const_iterator last) |
| : start(), finish(), map(0), map_size(0) |
| { |
| create_map_and_nodes(last - first); |
| # ifdef __STL_USE_EXCEPTIONS |
| try { |
| # endif /* __STL_USE_EXCEPTIONS */ |
| uninitialized_copy(first, last, start); |
| # ifdef __STL_USE_EXCEPTIONS |
| } |
| catch(...) { |
| destroy_map_and_nodes(); |
| throw; |
| } |
| # endif /* __STL_USE_EXCEPTIONS */ |
| } |
| |
| #endif /* __STL_MEMBER_TEMPLATES */ |
| |
| ~deque() { |
| destroy(start, finish); |
| destroy_map_and_nodes(); |
| } |
| |
| deque& operator= (const deque& x) { |
| const size_type len = size(); |
| if (&x != this) { |
| if (len >= x.size()) |
| erase(copy(x.begin(), x.end(), start), finish); |
| else { |
| const_iterator mid = x.begin() + len; |
| copy(x.begin(), mid, start); |
| insert(finish, mid, x.end()); |
| } |
| } |
| return *this; |
| } |
| |
| void swap(deque& x) { |
| ::swap(start, x.start); |
| ::swap(finish, x.finish); |
| ::swap(map, x.map); |
| ::swap(map_size, x.map_size); |
| } |
| |
| public: // push_* and pop_* |
| |
| void push_back(const value_type& t) { |
| if (finish.cur != finish.last - 1) { |
| construct(finish.cur, t); |
| ++finish.cur; |
| } |
| else |
| push_back_aux(t); |
| } |
| |
| void push_front(const value_type& t) { |
| if (start.cur != start.first) { |
| construct(start.cur - 1, t); |
| --start.cur; |
| } |
| else |
| push_front_aux(t); |
| } |
| |
| void pop_back() { |
| if (finish.cur != finish.first) { |
| --finish.cur; |
| destroy(finish.cur); |
| } |
| else |
| pop_back_aux(); |
| } |
| |
| void pop_front() { |
| if (start.cur != start.last - 1) { |
| destroy(start.cur); |
| ++start.cur; |
| } |
| else |
| pop_front_aux(); |
| } |
| |
| public: // Insert |
| |
| iterator insert(iterator position, const value_type& x) { |
| if (position.cur == start.cur) { |
| push_front(x); |
| return start; |
| } |
| else if (position.cur == finish.cur) { |
| push_back(x); |
| iterator tmp = finish; |
| --tmp; |
| return tmp; |
| } |
| else { |
| return insert_aux(position, x); |
| } |
| } |
| |
| iterator insert(iterator position) { return insert(position, value_type()); } |
| |
| void insert(iterator pos, size_type n, const value_type& x); |
| |
| void insert(iterator pos, int n, const value_type& x) { |
| insert(pos, (size_type) n, x); |
| } |
| void insert(iterator pos, long n, const value_type& x) { |
| insert(pos, (size_type) n, x); |
| } |
| |
| #ifdef __STL_MEMBER_TEMPLATES |
| |
| template <class InputIterator> |
| void insert(iterator pos, InputIterator first, InputIterator last) { |
| insert(pos, first, last, iterator_category(first)); |
| } |
| |
| #else /* __STL_MEMBER_TEMPLATES */ |
| |
| void insert(iterator pos, const value_type* first, const value_type* last); |
| void insert(iterator pos, const_iterator first, const_iterator last); |
| |
| #endif /* __STL_MEMBER_TEMPLATES */ |
| |
| void resize(size_type new_size, const value_type& x) { |
| const size_type len = size(); |
| if (new_size < len) |
| erase(start + new_size, finish); |
| else |
| insert(finish, new_size - len, x); |
| } |
| |
| void resize(size_type new_size) { resize(new_size, value_type()); } |
| |
| public: // Erase |
| void erase(iterator pos) { |
| iterator next = pos; |
| ++next; |
| if (pos - start < size() / 2) { |
| copy_backward(start, pos, next); |
| pop_front(); |
| } |
| else { |
| copy(next, finish, pos); |
| pop_back(); |
| } |
| } |
| |
| void erase(iterator first, iterator last); |
| void clear(); |
| |
| protected: // Internal construction/destruction |
| |
| void create_map_and_nodes(size_type num_elements); |
| void destroy_map_and_nodes(); |
| void fill_initialize(size_type n, const value_type& value); |
| |
| #ifdef __STL_MEMBER_TEMPLATES |
| |
| template <class InputIterator> |
| void range_initialize(InputIterator first, InputIterator last, |
| input_iterator_tag); |
| |
| template <class ForwardIterator> |
| void range_initialize(ForwardIterator first, ForwardIterator last, |
| forward_iterator_tag); |
| |
| template <class BidirectionalIterator> |
| void range_initialize(BidirectionalIterator first, |
| BidirectionalIterator last, |
| bidirectional_iterator_tag) { |
| range_initialize(first, last, forward_iterator_tag()); |
| } |
| |
| template <class RandomAccessIterator> |
| void range_initialize(RandomAccessIterator first, RandomAccessIterator last, |
| random_access_iterator_tag) { |
| range_initialize(first, last, forward_iterator_tag()); |
| } |
| |
| #endif /* __STL_MEMBER_TEMPLATES */ |
| |
| protected: // Internal push_* and pop_* |
| |
| void push_back_aux(const value_type& t); |
| void push_front_aux(const value_type& t); |
| void pop_back_aux(); |
| void pop_front_aux(); |
| |
| protected: // Internal insert functions |
| |
| #ifdef __STL_MEMBER_TEMPLATES |
| |
| template <class InputIterator> |
| void insert(iterator pos, InputIterator first, InputIterator last, |
| input_iterator_tag); |
| |
| template <class ForwardIterator> |
| void insert(iterator pos, ForwardIterator first, ForwardIterator last, |
| forward_iterator_tag); |
| |
| template <class BidirectionalIterator> |
| void insert(iterator pos, |
| BidirectionalIterator first, BidirectionalIterator last, |
| bidirectional_iterator_tag) { |
| insert(pos, first, last, forward_iterator_tag()); |
| } |
| |
| template <class RandomAccessIterator> |
| void insert(iterator pos, |
| RandomAccessIterator first, RandomAccessIterator last, |
| random_access_iterator_tag) { |
| insert(pos, first, last, forward_iterator_tag()); |
| } |
| #endif /* __STL_MEMBER_TEMPLATES */ |
| |
| iterator insert_aux(iterator pos, const value_type& x); |
| void insert_aux(iterator pos, size_type n, const value_type& x); |
| |
| #ifdef __STL_MEMBER_TEMPLATES |
| |
| template <class ForwardIterator> |
| void insert_aux(iterator pos, ForwardIterator first, ForwardIterator last, |
| size_type n); |
| |
| #else /* __STL_MEMBER_TEMPLATES */ |
| |
| 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); |
| |
| #endif /* __STL_MEMBER_TEMPLATES */ |
| |
| iterator reserve_elements_at_front(size_type n) { |
| size_type vacancies = start.cur - start.first; |
| if (n > vacancies) |
| new_elements_at_front(n - vacancies); |
| return start - n; |
| } |
| |
| iterator reserve_elements_at_back(size_type n) { |
| size_type vacancies = (finish.last - finish.cur) - 1; |
| if (n > vacancies) |
| new_elements_at_back(n - vacancies); |
| return finish + 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); |
| |
| protected: // Allocation of map and nodes |
| |
| // Makes sure the map has space for new nodes. Does not actually |
| // add the nodes. Can invalidate map pointers. (And consequently, |
| // deque iterators.) |
| |
| void reserve_map_at_back (size_type nodes_to_add = 1) { |
| if (nodes_to_add + 1 > map_size - (finish.node - map)) |
| reallocate_map(nodes_to_add, false); |
| } |
| |
| void reserve_map_at_front (size_type nodes_to_add = 1) { |
| if (nodes_to_add > start.node - map) |
| reallocate_map(nodes_to_add, true); |
| } |
| |
| void reallocate_map(size_type nodes_to_add, bool add_at_front); |
| |
| pointer allocate_node() { return data_allocator::allocate(buffer_size()); } |
| void deallocate_node(pointer n) { |
| data_allocator::deallocate(n, buffer_size()); |
| } |
| |
| #ifdef __STL_NON_TYPE_TMPL_PARAM_BUG |
| public: |
| bool operator==(const deque<T, Alloc, 0>& x) const { |
| return size() == x.size() && equal(begin(), end(), x.begin()); |
| } |
| bool operator!=(const deque<T, Alloc, 0>& x) const { |
| return size() != x.size() || !equal(begin(), end(), x.begin()); |
| } |
| bool operator<(const deque<T, Alloc, 0>& x) const { |
| return lexicographical_compare(begin(), end(), x.begin(), x.end()); |
| } |
| #endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */ |
| }; |
| |
| // Non-inline member functions |
| |
| template <class T, class Alloc, size_t BufSize> |
| void deque<T, Alloc, BufSize>::insert(iterator pos, |
| size_type n, const value_type& x) { |
| if (pos.cur == start.cur) { |
| iterator new_start = reserve_elements_at_front(n); |
| uninitialized_fill(new_start, start, x); |
| start = new_start; |
| } |
| else if (pos.cur == finish.cur) { |
| iterator new_finish = reserve_elements_at_back(n); |
| uninitialized_fill(finish, new_finish, x); |
| finish = new_finish; |
| } |
| else |
| insert_aux(pos, n, x); |
| } |
| |
| #ifndef __STL_MEMBER_TEMPLATES |
| |
| template <class T, class Alloc, size_t BufSize> |
| void deque<T, Alloc, BufSize>::insert(iterator pos, |
| const value_type* first, |
| const value_type* last) { |
| size_type n = last - first; |
| if (pos.cur == start.cur) { |
| iterator new_start = reserve_elements_at_front(n); |
| # ifdef __STL_USE_EXCEPTIONS |
| try { |
| # endif |
| uninitialized_copy(first, last, new_start); |
| start = new_start; |
| # ifdef __STL_USE_EXCEPTIONS |
| } |
| catch(...) { |
| destroy_nodes_at_front(new_start); |
| throw; |
| } |
| # endif |
| } |
| else if (pos.cur == finish.cur) { |
| iterator new_finish = reserve_elements_at_back(n); |
| # ifdef __STL_USE_EXCEPTIONS |
| try { |
| # endif |
| uninitialized_copy(first, last, finish); |
| finish = new_finish; |
| # ifdef __STL_USE_EXCEPTIONS |
| } |
| catch(...) { |
| destroy_nodes_at_back(new_finish); |
| throw; |
| } |
| # endif |
| } |
| else |
| insert_aux(pos, first, last, n); |
| } |
| |
| template <class T, class Alloc, size_t BufSize> |
| void deque<T, Alloc, BufSize>::insert(iterator pos, |
| const_iterator first, |
| const_iterator last) |
| { |
| size_type n = last - first; |
| if (pos.cur == start.cur) { |
| iterator new_start = reserve_elements_at_front(n); |
| # ifdef __STL_USE_EXCEPTIONS |
| try { |
| # endif |
| uninitialized_copy(first, last, new_start); |
| start = new_start; |
| # ifdef __STL_USE_EXCEPTIONS |
| } |
| catch(...) { |
| destroy_nodes_at_front(new_start); |
| throw; |
| } |
| # endif |
| } |
| else if (pos.cur == finish.cur) { |
| iterator new_finish = reserve_elements_at_back(n); |
| # ifdef __STL_USE_EXCEPTIONS |
| try { |
| # endif |
| uninitialized_copy(first, last, finish); |
| finish = new_finish; |
| # ifdef __STL_USE_EXCEPTIONS |
| } |
| catch(...) { |
| destroy_nodes_at_back(new_finish); |
| throw; |
| } |
| # endif |
| } |
| else |
| insert_aux(pos, first, last, n); |
| } |
| |
| #endif /* __STL_MEMBER_TEMPLATES */ |
| |
| template <class T, class Alloc, size_t BufSize> |
| void deque<T, Alloc, BufSize>::erase(iterator first, iterator last) { |
| if (first == start && last == finish) |
| clear(); |
| else { |
| difference_type n = last - first; |
| difference_type elems_before = first - start; |
| if (elems_before < (size() - n) / 2) { |
| copy_backward(start, first, last); |
| iterator new_start = start + n; |
| destroy(start, new_start); |
| for (map_pointer cur = start.node; cur < new_start.node; ++cur) |
| data_allocator::deallocate(*cur, buffer_size()); |
| start = new_start; |
| } |
| else { |
| copy(last, finish, first); |
| iterator new_finish = finish - n; |
| destroy(new_finish, finish); |
| for (map_pointer cur = new_finish.node + 1; cur <= finish.node; ++cur) |
| data_allocator::deallocate(*cur, buffer_size()); |
| finish = new_finish; |
| } |
| } |
| } |
| |
| template <class T, class Alloc, size_t BufSize> |
| void deque<T, Alloc, BufSize>::clear() { |
| for (map_pointer node = start.node + 1; node < finish.node; ++node) { |
| destroy(*node, *node + buffer_size()); |
| data_allocator::deallocate(*node, buffer_size()); |
| } |
| |
| if (start.node != finish.node) { |
| destroy(start.cur, start.last); |
| destroy(finish.first, finish.cur); |
| data_allocator::deallocate(finish.first, buffer_size()); |
| } |
| else |
| destroy(start.cur, finish.cur); |
| |
| finish = start; |
| } |
| |
| template <class T, class Alloc, size_t BufSize> |
| void deque<T, Alloc, BufSize>::create_map_and_nodes(size_type num_elements) { |
| size_type num_nodes = num_elements / buffer_size() + 1; |
| |
| map_size = max(initial_map_size(), num_nodes + 2); |
| map = map_allocator::allocate(map_size); |
| |
| map_pointer nstart = map + (map_size - num_nodes) / 2; |
| map_pointer nfinish = nstart + num_nodes - 1; |
| |
| map_pointer cur; |
| # ifdef __STL_USE_EXCEPTIONS |
| try { |
| # endif /* __STL_USE_EXCEPTIONS */ |
| for (cur = nstart; cur <= nfinish; ++cur) |
| *cur = allocate_node(); |
| # ifdef __STL_USE_EXCEPTIONS |
| } |
| catch(...) { |
| for (map_pointer n = nstart; n < cur; ++n) |
| deallocate_node(*n); |
| map_allocator::deallocate(map, map_size); |
| throw; |
| } |
| # endif /* __STL_USE_EXCEPTIONS */ |
| |
| start.set_node(nstart); |
| finish.set_node(nfinish); |
| start.cur = start.first; |
| finish.cur = finish.first + num_elements % buffer_size(); |
| } |
| |
| // This is only used as a cleanup function in catch clauses. |
| template <class T, class Alloc, size_t BufSize> |
| void deque<T, Alloc, BufSize>::destroy_map_and_nodes() { |
| for (map_pointer cur = start.node; cur <= finish.node; ++cur) |
| deallocate_node(*cur); |
| map_allocator::deallocate(map, map_size); |
| } |
| |
| |
| template <class T, class Alloc, size_t BufSize> |
| void deque<T, Alloc, BufSize>::fill_initialize(size_type n, |
| const value_type& value) { |
| create_map_and_nodes(n); |
| map_pointer cur; |
| # ifdef __STL_USE_EXCEPTIONS |
| try { |
| # endif /* __STL_USE_EXCEPTIONS */ |
| for (cur = start.node; cur < finish.node; ++cur) |
| uninitialized_fill(*cur, *cur + buffer_size(), value); |
| uninitialized_fill(finish.first, finish.cur, value); |
| # ifdef __STL_USE_EXCEPTIONS |
| } |
| catch(...) { |
| for (map_pointer n = start.node; n < cur; ++n) |
| destroy(*cur, *cur + buffer_size()); |
| destroy_map_and_nodes(); |
| throw; |
| } |
| # endif /* __STL_USE_EXCEPTIONS */ |
| } |
| |
| #ifdef __STL_MEMBER_TEMPLATES |
| |
| template <class T, class Alloc, size_t BufSize> |
| template <class InputIterator> |
| void deque<T, Alloc, BufSize>::range_initialize(InputIterator first, |
| InputIterator last, |
| input_iterator_tag) { |
| create_map_and_nodes(0); |
| for ( ; first != last; ++first) |
| push_back(*first); |
| } |
| |
| template <class T, class Alloc, size_t BufSize> |
| template <class ForwardIterator> |
| void deque<T, Alloc, BufSize>::range_initialize(ForwardIterator first, |
| ForwardIterator last, |
| forward_iterator_tag) { |
| size_type n = 0; |
| distance(first, last, n); |
| create_map_and_nodes(n); |
| # ifdef __STL_USE_EXCEPTIONS |
| try { |
| # endif /* __STL_USE_EXCEPTIONS */ |
| uninitialized_copy(first, last, start); |
| # ifdef __STL_USE_EXCEPTIONS |
| } |
| catch(...) { |
| destroy_map_and_nodes(); |
| throw; |
| } |
| # endif /* __STL_USE_EXCEPTIONS */ |
| } |
| |
| #endif /* __STL_MEMBER_TEMPLATES */ |
| |
| // Called only if finish.cur == finish.last - 1. |
| template <class T, class Alloc, size_t BufSize> |
| void deque<T, Alloc, BufSize>::push_back_aux(const value_type& t) { |
| value_type t_copy = t; |
| reserve_map_at_back(); |
| *(finish.node + 1) = allocate_node(); |
| # ifdef __STL_USE_EXCEPTIONS |
| try { |
| # endif /* __STL_USE_EXCEPTIONS */ |
| construct(finish.cur, t_copy); |
| finish.set_node(finish.node + 1); |
| finish.cur = finish.first; |
| # ifdef __STL_USE_EXCEPTIONS |
| } |
| catch(...) { |
| deallocate_node(*(finish.node + 1)); |
| throw; |
| } |
| # endif /* __STL_USE_EXCEPTIONS */ |
| } |
| |
| // Called only if start.cur == start.first. |
| template <class T, class Alloc, size_t BufSize> |
| void deque<T, Alloc, BufSize>::push_front_aux(const value_type& t) { |
| value_type t_copy = t; |
| reserve_map_at_front(); |
| *(start.node - 1) = allocate_node(); |
| # ifdef __STL_USE_EXCEPTIONS |
| try { |
| # endif /* __STL_USE_EXCEPTIONS */ |
| start.set_node(start.node - 1); |
| start.cur = start.last - 1; |
| construct(start.cur, t_copy); |
| # ifdef __STL_USE_EXCEPTIONS |
| } |
| catch(...) { |
| start.set_node(start.node + 1); |
| start.cur = start.first; |
| deallocate_node(*(start.node - 1)); |
| throw; |
| } |
| # endif /* __STL_USE_EXCEPTIONS */ |
| } |
| |
| // Called only if finish.cur == finish.first. |
| template <class T, class Alloc, size_t BufSize> |
| void deque<T, Alloc, BufSize>:: pop_back_aux() { |
| deallocate_node(finish.first); |
| finish.set_node(finish.node - 1); |
| finish.cur = finish.last - 1; |
| destroy(finish.cur); |
| } |
| |
| // Called only if start.cur == start.last - 1. Note that if the deque |
| // has at least one element (a necessary precondition for this member |
| // function), and if start.cur == start.last, then the deque must have |
| // at least two nodes. |
| template <class T, class Alloc, size_t BufSize> |
| void deque<T, Alloc, BufSize>::pop_front_aux() { |
| destroy(start.cur); |
| deallocate_node(start.first); |
| start.set_node(start.node + 1); |
| start.cur = start.first; |
| } |
| |
| #ifdef __STL_MEMBER_TEMPLATES |
| |
| template <class T, class Alloc, size_t BufSize> |
| template <class InputIterator> |
| void deque<T, Alloc, BufSize>::insert(iterator pos, |
| InputIterator first, InputIterator last, |
| input_iterator_tag) { |
| copy(first, last, inserter(*this, pos)); |
| } |
| |
| template <class T, class Alloc, size_t BufSize> |
| template <class ForwardIterator> |
| void deque<T, Alloc, BufSize>::insert(iterator pos, |
| ForwardIterator first, |
| ForwardIterator last, |
| forward_iterator_tag) { |
| size_type n = 0; |
| distance(first, last, n); |
| if (pos.cur == start.cur) { |
| iterator new_start = reserve_elements_at_front(n); |
| # ifdef __STL_USE_EXCEPTIONS |
| try { |
| # endif |
| uninitialized_copy(first, last, new_start); |
| start = new_start; |
| # ifdef __STL_USE_EXCEPTIONS |
| } |
| catch(...) { |
| destroy_nodes_at_front(new_start); |
| throw; |
| } |
| # endif |
| } |
| else if (pos.cur == finish.cur) { |
| iterator new_finish = reserve_elements_at_back(n); |
| # ifdef __STL_USE_EXCEPTIONS |
| try { |
| # endif |
| uninitialized_copy(first, last, finish); |
| finish = new_finish; |
| # ifdef __STL_USE_EXCEPTIONS |
| } |
| catch(...) { |
| destroy_nodes_at_back(new_finish); |
| throw; |
| } |
| # endif |
| } |
| else |
| insert_aux(pos, first, last, n); |
| } |
| |
| #endif /* __STL_MEMBER_TEMPLATES */ |
| |
| 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) { |
| difference_type index = pos - start; |
| value_type x_copy = x; |
| if (index < size() / 2) { |
| push_front(front()); |
| iterator front1 = start; |
| ++front1; |
| iterator front2 = front1; |
| ++front2; |
| pos = start + index; |
| iterator pos1 = pos; |
| ++pos1; |
| copy(front2, pos1, front1); |
| } |
| else { |
| push_back(back()); |
| iterator back1 = finish; |
| --back1; |
| iterator back2 = back1; |
| --back2; |
| pos = start + index; |
| copy_backward(pos, back2, back1); |
| } |
| *pos = x_copy; |
| return pos; |
| } |
| |
| template <class T, class Alloc, size_t BufSize> |
| void deque<T, Alloc, BufSize>::insert_aux(iterator pos, |
| size_type n, const value_type& x) { |
| const difference_type elems_before = pos - start; |
| size_type length = size(); |
| value_type x_copy = x; |
| if (elems_before < length / 2) { |
| iterator new_start = reserve_elements_at_front(n); |
| iterator old_start = start; |
| pos = start + elems_before; |
| # ifdef __STL_USE_EXCEPTIONS |
| try { |
| # endif /* __STL_USE_EXCEPTIONS */ |
| if (elems_before >= n) { |
| iterator start_n = start + n; |
| uninitialized_copy(start, start_n, new_start); |
| start = new_start; |
| copy(start_n, pos, old_start); |
| fill(pos - n, pos, x_copy); |
| } |
| else { |
| __uninitialized_copy_fill(start, pos, new_start, start, x_copy); |
| start = new_start; |
| fill(old_start, pos, x_copy); |
| } |
| # ifdef __STL_USE_EXCEPTIONS |
| } |
| catch(...) { |
| destroy_nodes_at_front(new_start); |
| throw; |
| } |
| # endif /* __STL_USE_EXCEPTIONS */ |
| } |
| else { |
| iterator new_finish = reserve_elements_at_back(n); |
| iterator old_finish = finish; |
| const difference_type elems_after = length - elems_before; |
| pos = finish - elems_after; |
| # ifdef __STL_USE_EXCEPTIONS |
| try { |
| # endif /* __STL_USE_EXCEPTIONS */ |
| if (elems_after > n) { |
| iterator finish_n = finish - n; |
| uninitialized_copy(finish_n, finish, finish); |
| finish = new_finish; |
| copy_backward(pos, finish_n, old_finish); |
| fill(pos, pos + n, x_copy); |
| } |
| else { |
| __uninitialized_fill_copy(finish, pos + n, x_copy, pos, finish); |
| finish = new_finish; |
| fill(pos, old_finish, x_copy); |
| } |
| # ifdef __STL_USE_EXCEPTIONS |
| } |
| catch(...) { |
| destroy_nodes_at_back(new_finish); |
| throw; |
| } |
| # endif /* __STL_USE_EXCEPTIONS */ |
| } |
| } |
| |
| #ifdef __STL_MEMBER_TEMPLATES |
| |
| template <class T, class Alloc, size_t BufSize> |
| template <class ForwardIterator> |
| void deque<T, Alloc, BufSize>::insert_aux(iterator pos, |
| ForwardIterator first, |
| ForwardIterator last, |
| size_type n) |
| { |
| const difference_type elems_before = pos - start; |
| size_type length = size(); |
| if (elems_before < length / 2) { |
| iterator new_start = reserve_elements_at_front(n); |
| iterator old_start = start; |
| pos = start + elems_before; |
| # ifdef __STL_USE_EXCEPTIONS |
| try { |
| # endif /* __STL_USE_EXCEPTIONS */ |
| if (elems_before >= n) { |
| iterator start_n = start + n; |
| uninitialized_copy(start, start_n, new_start); |
| start = new_start; |
| copy(start_n, pos, old_start); |
| copy(first, last, pos - n); |
| } |
| else { |
| ForwardIterator mid = first; |
| advance(mid, n - elems_before); |
| __uninitialized_copy_copy(start, pos, first, mid, new_start); |
| start = new_start; |
| copy(mid, last, old_start); |
| } |
| # ifdef __STL_USE_EXCEPTIONS |
| } |
| catch(...) { |
| destroy_nodes_at_front(new_start); |
| throw; |
| } |
| # endif /* __STL_USE_EXCEPTIONS */ |
| } |
| else { |
| iterator new_finish = reserve_elements_at_back(n); |
| iterator old_finish = finish; |
| const difference_type elems_after = length - elems_before; |
| pos = finish - elems_after; |
| # ifdef __STL_USE_EXCEPTIONS |
| try { |
| # endif /* __STL_USE_EXCEPTIONS */ |
| if (elems_after > n) { |
| iterator finish_n = finish - n; |
| uninitialized_copy(finish_n, finish, finish); |
| finish = new_finish; |
| copy_backward(pos, finish_n, old_finish); |
| copy(first, last, pos); |
| } |
| else { |
| ForwardIterator mid = first; |
| advance(mid, elems_after); |
| __uninitialized_copy_copy(mid, last, pos, finish, finish); |
| finish = new_finish; |
| copy(first, mid, pos); |
| } |
| # ifdef __STL_USE_EXCEPTIONS |
| } |
| catch(...) { |
| destroy_nodes_at_back(new_finish); |
| throw; |
| } |
| # endif /* __STL_USE_EXCEPTIONS */ |
| } |
| } |
| |
| #else /* __STL_MEMBER_TEMPLATES */ |
| |
| 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) |
| { |
| const difference_type elems_before = pos - start; |
| size_type length = size(); |
| if (elems_before < length / 2) { |
| iterator new_start = reserve_elements_at_front(n); |
| iterator old_start = start; |
| pos = start + elems_before; |
| # ifdef __STL_USE_EXCEPTIONS |
| try { |
| # endif /* __STL_USE_EXCEPTIONS */ |
| if (elems_before >= n) { |
| iterator start_n = start + n; |
| uninitialized_copy(start, start_n, new_start); |
| start = new_start; |
| copy(start_n, pos, old_start); |
| copy(first, last, pos - n); |
| } |
| else { |
| const value_type* mid = first + (n - elems_before); |
| __uninitialized_copy_copy(start, pos, first, mid, new_start); |
| start = new_start; |
| copy(mid, last, old_start); |
| } |
| # ifdef __STL_USE_EXCEPTIONS |
| } |
| catch(...) { |
| destroy_nodes_at_front(new_start); |
| throw; |
| } |
| # endif /* __STL_USE_EXCEPTIONS */ |
| } |
| else { |
| iterator new_finish = reserve_elements_at_back(n); |
| iterator old_finish = finish; |
| const difference_type elems_after = length - elems_before; |
| pos = finish - elems_after; |
| # ifdef __STL_USE_EXCEPTIONS |
| try { |
| # endif /* __STL_USE_EXCEPTIONS */ |
| if (elems_after > n) { |
| iterator finish_n = finish - n; |
| uninitialized_copy(finish_n, finish, finish); |
| finish = new_finish; |
| copy_backward(pos, finish_n, old_finish); |
| copy(first, last, pos); |
| } |
| else { |
| const value_type* mid = first + elems_after; |
| __uninitialized_copy_copy(mid, last, pos, finish, finish); |
| finish = new_finish; |
| copy(first, mid, pos); |
| } |
| # ifdef __STL_USE_EXCEPTIONS |
| } |
| catch(...) { |
| destroy_nodes_at_back(new_finish); |
| throw; |
| } |
| # endif /* __STL_USE_EXCEPTIONS */ |
| } |
| } |
| |
| 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) |
| { |
| const difference_type elems_before = pos - start; |
| size_type length = size(); |
| if (elems_before < length / 2) { |
| iterator new_start = reserve_elements_at_front(n); |
| iterator old_start = start; |
| pos = start + elems_before; |
| # ifdef __STL_USE_EXCEPTIONS |
| try { |
| # endif /* __STL_USE_EXCEPTIONS */ |
| if (elems_before >= n) { |
| iterator start_n = start + n; |
| uninitialized_copy(start, start_n, new_start); |
| start = new_start; |
| copy(start_n, pos, old_start); |
| copy(first, last, pos - n); |
| } |
| else { |
| const_iterator mid = first + (n - elems_before); |
| __uninitialized_copy_copy(start, pos, first, mid, new_start); |
| start = new_start; |
| copy(mid, last, old_start); |
| } |
| # ifdef __STL_USE_EXCEPTIONS |
| } |
| catch(...) { |
| destroy_nodes_at_front(new_start); |
| throw; |
| } |
| # endif /* __STL_USE_EXCEPTIONS */ |
| } |
| else { |
| iterator new_finish = reserve_elements_at_back(n); |
| iterator old_finish = finish; |
| const difference_type elems_after = length - elems_before; |
| pos = finish - elems_after; |
| # ifdef __STL_USE_EXCEPTIONS |
| try { |
| # endif /* __STL_USE_EXCEPTIONS */ |
| if (elems_after > n) { |
| iterator finish_n = finish - n; |
| uninitialized_copy(finish_n, finish, finish); |
| finish = new_finish; |
| copy_backward(pos, finish_n, old_finish); |
| copy(first, last, pos); |
| } |
| else { |
| const_iterator mid = first + elems_after; |
| __uninitialized_copy_copy(mid, last, pos, finish, finish); |
| finish = new_finish; |
| copy(first, mid, pos); |
| } |
| # ifdef __STL_USE_EXCEPTIONS |
| } |
| catch(...) { |
| destroy_nodes_at_back(new_finish); |
| throw; |
| } |
| # endif /* __STL_USE_EXCEPTIONS */ |
| } |
| } |
| |
| #endif /* __STL_MEMBER_TEMPLATES */ |
| |
| template <class T, class Alloc, size_t BufSize> |
| void deque<T, Alloc, BufSize>::new_elements_at_front(size_type new_elements) { |
| size_type new_nodes = (new_elements + buffer_size() - 1) / buffer_size(); |
| reserve_map_at_front(new_nodes); |
| size_type i; |
| # ifdef __STL_USE_EXCEPTIONS |
| try { |
| # endif /* __STL_USE_EXCEPTIONS */ |
| for (i = 1; i <= new_nodes; ++i) |
| *(start.node - i) = allocate_node(); |
| # ifdef __STL_USE_EXCEPTIONS |
| } |
| catch(...) { |
| for (size_type j = 1; j < i; ++j) |
| deallocate_node(*(start.node - j)); |
| throw; |
| } |
| # endif /* __STL_USE_EXCEPTIONS */ |
| } |
| |
| template <class T, class Alloc, size_t BufSize> |
| void deque<T, Alloc, BufSize>::new_elements_at_back(size_type new_elements) { |
| size_type new_nodes = (new_elements + buffer_size() - 1) / buffer_size(); |
| reserve_map_at_back(new_nodes); |
| size_type i; |
| # ifdef __STL_USE_EXCEPTIONS |
| try { |
| # endif /* __STL_USE_EXCEPTIONS */ |
| for (i = 1; i <= new_nodes; ++i) |
| *(finish.node + i) = allocate_node(); |
| # ifdef __STL_USE_EXCEPTIONS |
| } |
| catch(...) { |
| for (size_type j = 1; j < i; ++j) |
| deallocate_node(*(finish.node + j)); |
| throw; |
| } |
| # endif /* __STL_USE_EXCEPTIONS */ |
| } |
| |
| template <class T, class Alloc, size_t BufSize> |
| void deque<T, Alloc, BufSize>::destroy_nodes_at_front(iterator before_start) { |
| for (map_pointer n = before_start.node; n < start.node; ++n) |
| deallocate_node(*n); |
| } |
| |
| template <class T, class Alloc, size_t BufSize> |
| void deque<T, Alloc, BufSize>::destroy_nodes_at_back(iterator after_finish) { |
| for (map_pointer n = after_finish.node; n > finish.node; --n) |
| deallocate_node(*n); |
| } |
| |
| template <class T, class Alloc, size_t BufSize> |
| void deque<T, Alloc, BufSize>::reallocate_map(size_type nodes_to_add, |
| bool add_at_front) { |
| size_type old_num_nodes = finish.node - start.node + 1; |
| size_type new_num_nodes = old_num_nodes + nodes_to_add; |
| |
| map_pointer new_nstart; |
| if (map_size > 2 * new_num_nodes) { |
| new_nstart = map + (map_size - new_num_nodes) / 2 |
| + (add_at_front ? nodes_to_add : 0); |
| if (new_nstart < start.node) |
| copy(start.node, finish.node + 1, new_nstart); |
| else |
| copy_backward(start.node, finish.node + 1, new_nstart + old_num_nodes); |
| } |
| else { |
| size_type new_map_size = map_size + max(map_size, nodes_to_add) + 2; |
| |
| map_pointer new_map = map_allocator::allocate(new_map_size); |
| new_nstart = new_map + (new_map_size - new_num_nodes) / 2 |
| + (add_at_front ? nodes_to_add : 0); |
| copy(start.node, finish.node + 1, new_nstart); |
| map_allocator::deallocate(map, map_size); |
| |
| map = new_map; |
| map_size = new_map_size; |
| } |
| |
| start.set_node(new_nstart); |
| finish.set_node(new_nstart + old_num_nodes - 1); |
| } |
| |
| |
| // Nonmember functions. |
| |
| #ifndef __STL_NON_TYPE_TMPL_PARAM_BUG |
| |
| template <class T, class Alloc, size_t BufSiz> |
| bool operator==(const deque<T, Alloc, BufSiz>& x, |
| const deque<T, Alloc, BufSiz>& y) { |
| return x.size() == y.size() && equal(x.begin(), x.end(), y.begin()); |
| } |
| |
| template <class T, class Alloc, size_t BufSiz> |
| bool operator<(const deque<T, Alloc, BufSiz>& x, |
| const deque<T, Alloc, BufSiz>& y) { |
| return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); |
| } |
| |
| #endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */ |
| |
| |
| #endif /* __SGI_STL_DEQUE_H */ |
| |