X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=libstdc%2B%2B-v3%2Finclude%2Fbits%2Fstl_deque.h;h=03cda6956ca2ad4a6d2d246f94eb4f08204d254e;hb=1f9c69a9a395b4c1b2869e3736ee4558bb174306;hp=8e7f1305bfd988fc1638f66dab08eaa7fe8a6ded;hpb=30a20a1ee0168656d375ea2333e14b46937bdc6a;p=platform%2Fupstream%2Fgcc.git diff --git a/libstdc++-v3/include/bits/stl_deque.h b/libstdc++-v3/include/bits/stl_deque.h index 8e7f130..03cda69 100644 --- a/libstdc++-v3/include/bits/stl_deque.h +++ b/libstdc++-v3/include/bits/stl_deque.h @@ -1,3 +1,33 @@ +// Deque implementation -*- C++ -*- + +// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 +// Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 2, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING. If not, write to the Free +// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, +// USA. + +// As a special exception, you may use this file as part of a free software +// library without restriction. Specifically, if other files instantiate +// templates or use macros or inline functions from this file, or you compile +// this file and link it with other files to produce an executable, this +// file does not by itself cause the resulting executable to be covered by +// the GNU General Public License. This exception does not however +// invalidate any other reasons why the executable file might be covered by +// the GNU General Public License. + /* * * Copyright (c) 1994 @@ -24,1299 +54,1555 @@ * purpose. It is provided "as is" without express or implied warranty. */ -/* NOTE: This is an internal header file, included by other STL headers. - * You should not attempt to use it directly. +/** @file stl_deque.h + * This is an internal header file, included by other library headers. + * You should not attempt to use it directly. */ +#ifndef _DEQUE_H +#define _DEQUE_H 1 + #include #include #include -#ifndef __SGI_STL_INTERNAL_DEQUE_H -#define __SGI_STL_INTERNAL_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]. - */ +_GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD) + + /** + * @if maint + * @brief This function controls the size of memory nodes. + * @param size The size of an element. + * @return The number (not byte size) of elements per node. + * + * This function started off as a compiler kludge from SGI, but seems to + * be a useful wrapper around a repeated constant expression. The '512' is + * tuneable (and no other code needs to change), but no investigation has + * been done since inheriting the SGI code. + * @endif + */ + inline size_t + __deque_buf_size(size_t __size) + { return __size < 512 ? size_t(512 / __size) : size_t(1); } + + + /** + * @brief A deque::iterator. + * + * Quite a bit of intelligence here. Much of the functionality of + * deque is actually passed off to this class. A deque holds two + * of these internally, marking its valid range. Access to + * elements is done as offsets of either of those two, relying on + * operator overloading in this class. + * + * @if maint + * All the functions are op overloads except for _M_set_node. + * @endif + */ + template + struct _Deque_iterator + { + typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator; + typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator; + + static size_t _S_buffer_size() + { return __deque_buf_size(sizeof(_Tp)); } + + typedef std::random_access_iterator_tag iterator_category; + typedef _Tp value_type; + typedef _Ptr pointer; + typedef _Ref reference; + typedef size_t size_type; + typedef ptrdiff_t difference_type; + typedef _Tp** _Map_pointer; + typedef _Deque_iterator _Self; + + _Tp* _M_cur; + _Tp* _M_first; + _Tp* _M_last; + _Map_pointer _M_node; + + _Deque_iterator(_Tp* __x, _Map_pointer __y) + : _M_cur(__x), _M_first(*__y), + _M_last(*__y + _S_buffer_size()), _M_node(__y) {} + + _Deque_iterator() : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) {} + + _Deque_iterator(const iterator& __x) + : _M_cur(__x._M_cur), _M_first(__x._M_first), + _M_last(__x._M_last), _M_node(__x._M_node) {} + + reference + operator*() const + { return *_M_cur; } + + pointer + operator->() const + { return _M_cur; } + + _Self& + operator++() + { + ++_M_cur; + if (_M_cur == _M_last) + { + _M_set_node(_M_node + 1); + _M_cur = _M_first; + } + return *this; + } + _Self + operator++(int) + { + _Self __tmp = *this; + ++*this; + return __tmp; + } -/* - * In previous versions of deque, there was an extra template - * parameter so users could control the node size. This extension - * turns out to violate the C++ standard (it can be detected using - * template template parameters), and it has been removed. - */ + _Self& + operator--() + { + if (_M_cur == _M_first) + { + _M_set_node(_M_node - 1); + _M_cur = _M_last; + } + --_M_cur; + return *this; + } -namespace std -{ - -// 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 __size) { - return __size < 512 ? size_t(512 / __size) : size_t(1); -} - -template -struct _Deque_iterator { - typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator; - typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator; - static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); } - - typedef random_access_iterator_tag iterator_category; - typedef _Tp value_type; - typedef _Ptr pointer; - typedef _Ref reference; - typedef size_t size_type; - typedef ptrdiff_t difference_type; - typedef _Tp** _Map_pointer; - - typedef _Deque_iterator _Self; - - _Tp* _M_cur; - _Tp* _M_first; - _Tp* _M_last; - _Map_pointer _M_node; - - _Deque_iterator(_Tp* __x, _Map_pointer __y) - : _M_cur(__x), _M_first(*__y), - _M_last(*__y + _S_buffer_size()), _M_node(__y) {} - _Deque_iterator() : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) {} - _Deque_iterator(const iterator& __x) - : _M_cur(__x._M_cur), _M_first(__x._M_first), - _M_last(__x._M_last), _M_node(__x._M_node) {} - - reference operator*() const { return *_M_cur; } - pointer operator->() const { return _M_cur; } - - difference_type operator-(const _Self& __x) const { - return difference_type(_S_buffer_size()) * (_M_node - __x._M_node - 1) + - (_M_cur - _M_first) + (__x._M_last - __x._M_cur); - } - - _Self& operator++() { - ++_M_cur; - if (_M_cur == _M_last) { - _M_set_node(_M_node + 1); - _M_cur = _M_first; - } - return *this; - } - _Self operator++(int) { - _Self __tmp = *this; - ++*this; - return __tmp; - } - - _Self& operator--() { - if (_M_cur == _M_first) { - _M_set_node(_M_node - 1); - _M_cur = _M_last; - } - --_M_cur; - return *this; - } - _Self operator--(int) { - _Self __tmp = *this; - --*this; - return __tmp; - } - - _Self& operator+=(difference_type __n) - { - difference_type __offset = __n + (_M_cur - _M_first); - if (__offset >= 0 && __offset < difference_type(_S_buffer_size())) - _M_cur += __n; - else { - difference_type __node_offset = - __offset > 0 ? __offset / difference_type(_S_buffer_size()) - : -difference_type((-__offset - 1) / _S_buffer_size()) - 1; - _M_set_node(_M_node + __node_offset); - _M_cur = _M_first + - (__offset - __node_offset * difference_type(_S_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; - } - - reference operator[](difference_type __n) const { return *(*this + __n); } - - bool operator==(const _Self& __x) const { return _M_cur == __x._M_cur; } - bool operator!=(const _Self& __x) const { return !(*this == __x); } - bool operator<(const _Self& __x) const { - return (_M_node == __x._M_node) ? - (_M_cur < __x._M_cur) : (_M_node < __x._M_node); - } - bool operator>(const _Self& __x) const { return __x < *this; } - bool operator<=(const _Self& __x) const { return !(__x < *this); } - bool operator>=(const _Self& __x) const { return !(*this < __x); } - - void _M_set_node(_Map_pointer __new_node) { - _M_node = __new_node; - _M_first = *__new_node; - _M_last = _M_first + difference_type(_S_buffer_size()); - } -}; - -template -inline _Deque_iterator<_Tp, _Ref, _Ptr> -operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Ref, _Ptr>& __x) -{ - return __x + __n; -} - - -// Deque base class. It has two purposes. First, its constructor -// and destructor allocate (but don't initialize) storage. This makes -// exception safety easier. Second, the base class encapsulates all of -// the differences between SGI-style allocators and standard-conforming -// allocators. - -// Base class for ordinary allocators. -template -class _Deque_alloc_base { -public: - typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type; - allocator_type get_allocator() const { return _M_node_allocator; } - - _Deque_alloc_base(const allocator_type& __a) - : _M_node_allocator(__a), _M_map_allocator(__a), - _M_map(0), _M_map_size(0) - {} - -protected: - typedef typename _Alloc_traits<_Tp*, _Alloc>::allocator_type - _Map_allocator_type; - - allocator_type _M_node_allocator; - _Map_allocator_type _M_map_allocator; - - _Tp* _M_allocate_node() { - return _M_node_allocator.allocate(__deque_buf_size(sizeof(_Tp))); - } - void _M_deallocate_node(_Tp* __p) { - _M_node_allocator.deallocate(__p, __deque_buf_size(sizeof(_Tp))); - } - _Tp** _M_allocate_map(size_t __n) - { return _M_map_allocator.allocate(__n); } - void _M_deallocate_map(_Tp** __p, size_t __n) - { _M_map_allocator.deallocate(__p, __n); } - - _Tp** _M_map; - size_t _M_map_size; -}; - -// Specialization for instanceless allocators. -template -class _Deque_alloc_base<_Tp, _Alloc, true> -{ -public: - typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type; - allocator_type get_allocator() const { return allocator_type(); } - - _Deque_alloc_base(const allocator_type&) : _M_map(0), _M_map_size(0) {} - -protected: - typedef typename _Alloc_traits<_Tp, _Alloc>::_Alloc_type _Node_alloc_type; - typedef typename _Alloc_traits<_Tp*, _Alloc>::_Alloc_type _Map_alloc_type; - - _Tp* _M_allocate_node() { - return _Node_alloc_type::allocate(__deque_buf_size(sizeof(_Tp))); - } - void _M_deallocate_node(_Tp* __p) { - _Node_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp))); - } - _Tp** _M_allocate_map(size_t __n) - { return _Map_alloc_type::allocate(__n); } - void _M_deallocate_map(_Tp** __p, size_t __n) - { _Map_alloc_type::deallocate(__p, __n); } - - _Tp** _M_map; - size_t _M_map_size; -}; - -template -class _Deque_base - : public _Deque_alloc_base<_Tp,_Alloc, - _Alloc_traits<_Tp, _Alloc>::_S_instanceless> -{ -public: - typedef _Deque_alloc_base<_Tp,_Alloc, - _Alloc_traits<_Tp, _Alloc>::_S_instanceless> - _Base; - typedef typename _Base::allocator_type allocator_type; - typedef _Deque_iterator<_Tp,_Tp&,_Tp*> iterator; - typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*> const_iterator; - - _Deque_base(const allocator_type& __a, size_t __num_elements) - : _Base(__a), _M_start(), _M_finish() - { _M_initialize_map(__num_elements); } - _Deque_base(const allocator_type& __a) - : _Base(__a), _M_start(), _M_finish() {} - ~_Deque_base(); - -protected: - void _M_initialize_map(size_t); - void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish); - void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish); - enum { _S_initial_map_size = 8 }; - -protected: - iterator _M_start; - iterator _M_finish; -}; - -// Non-inline member functions from _Deque_base. - -template -_Deque_base<_Tp,_Alloc>::~_Deque_base() { - if (_M_map) { - _M_destroy_nodes(_M_start._M_node, _M_finish._M_node + 1); - _M_deallocate_map(_M_map, _M_map_size); - } -} - -template -void -_Deque_base<_Tp,_Alloc>::_M_initialize_map(size_t __num_elements) -{ - size_t __num_nodes = - __num_elements / __deque_buf_size(sizeof(_Tp)) + 1; - - _M_map_size = max((size_t) _S_initial_map_size, __num_nodes + 2); - _M_map = _M_allocate_map(_M_map_size); - - _Tp** __nstart = _M_map + (_M_map_size - __num_nodes) / 2; - _Tp** __nfinish = __nstart + __num_nodes; - - __STL_TRY { - _M_create_nodes(__nstart, __nfinish); - } - __STL_UNWIND((_M_deallocate_map(_M_map, _M_map_size), - _M_map = 0, _M_map_size = 0)); - _M_start._M_set_node(__nstart); - _M_finish._M_set_node(__nfinish - 1); - _M_start._M_cur = _M_start._M_first; - _M_finish._M_cur = _M_finish._M_first + - __num_elements % __deque_buf_size(sizeof(_Tp)); -} - -template -void _Deque_base<_Tp,_Alloc>::_M_create_nodes(_Tp** __nstart, _Tp** __nfinish) -{ - _Tp** __cur; - __STL_TRY { - for (__cur = __nstart; __cur < __nfinish; ++__cur) - *__cur = _M_allocate_node(); - } - __STL_UNWIND(_M_destroy_nodes(__nstart, __cur)); -} - -template -void -_Deque_base<_Tp,_Alloc>::_M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish) -{ - for (_Tp** __n = __nstart; __n < __nfinish; ++__n) - _M_deallocate_node(*__n); -} - -template > -class deque : protected _Deque_base<_Tp, _Alloc> { - - // concept requirements - glibcpp_class_requires(_Tp, SGIAssignableConcept); - - typedef _Deque_base<_Tp, _Alloc> _Base; -public: // Basic types - typedef _Tp 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 typename _Base::allocator_type allocator_type; - allocator_type get_allocator() const { return _Base::get_allocator(); } - -public: // Iterators - typedef typename _Base::iterator iterator; - typedef typename _Base::const_iterator const_iterator; - - typedef reverse_iterator const_reverse_iterator; - typedef reverse_iterator reverse_iterator; - -protected: // Internal typedefs - typedef pointer* _Map_pointer; - static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); } - -protected: - using _Base::_M_initialize_map; - using _Base::_M_create_nodes; - using _Base::_M_destroy_nodes; - using _Base::_M_allocate_node; - using _Base::_M_deallocate_node; - using _Base::_M_allocate_map; - using _Base::_M_deallocate_map; - - using _Base::_M_map; - using _Base::_M_map_size; - using _Base::_M_start; - using _Base::_M_finish; - -public: // Basic accessors - iterator begin() { return _M_start; } - iterator end() { return _M_finish; } - const_iterator begin() const { return _M_start; } - const_iterator end() const { return _M_finish; } - - reverse_iterator rbegin() { return reverse_iterator(_M_finish); } - reverse_iterator rend() { return reverse_iterator(_M_start); } - const_reverse_iterator rbegin() const - { return const_reverse_iterator(_M_finish); } - const_reverse_iterator rend() const - { return const_reverse_iterator(_M_start); } - - reference operator[](size_type __n) - { return _M_start[difference_type(__n)]; } - const_reference operator[](size_type __n) const - { return _M_start[difference_type(__n)]; } - - void _M_range_check(size_type __n) const { - if (__n >= this->size()) - __throw_range_error("deque"); - } - - reference at(size_type __n) - { _M_range_check(__n); return (*this)[__n]; } - const_reference at(size_type __n) const - { _M_range_check(__n); return (*this)[__n]; } - - reference front() { return *_M_start; } - reference back() { - iterator __tmp = _M_finish; - --__tmp; - return *__tmp; - } - const_reference front() const { return *_M_start; } - const_reference back() const { - const_iterator __tmp = _M_finish; - --__tmp; - return *__tmp; - } - - size_type size() const { return _M_finish - _M_start; } - size_type max_size() const { return size_type(-1); } - bool empty() const { return _M_finish == _M_start; } - -public: // Constructor, destructor. - explicit deque(const allocator_type& __a = allocator_type()) - : _Base(__a, 0) {} - deque(const deque& __x) : _Base(__x.get_allocator(), __x.size()) - { uninitialized_copy(__x.begin(), __x.end(), _M_start); } - deque(size_type __n, const value_type& __value, - const allocator_type& __a = allocator_type()) : _Base(__a, __n) - { _M_fill_initialize(__value); } - explicit deque(size_type __n) : _Base(allocator_type(), __n) - { _M_fill_initialize(value_type()); } - - // Check whether it's an integral type. If so, it's not an iterator. - template - deque(_InputIterator __first, _InputIterator __last, - const allocator_type& __a = allocator_type()) : _Base(__a) { - typedef typename _Is_integer<_InputIterator>::_Integral _Integral; - _M_initialize_dispatch(__first, __last, _Integral()); - } - - template - void _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) { - _M_initialize_map(__n); - _M_fill_initialize(__x); - } - - template - void _M_initialize_dispatch(_InputIter __first, _InputIter __last, - __false_type) { - _M_range_initialize(__first, __last, __iterator_category(__first)); - } - - ~deque() { destroy(_M_start, _M_finish); } - - deque& operator= (const deque& __x) { - const size_type __len = size(); - if (&__x != this) { - if (__len >= __x.size()) - erase(copy(__x.begin(), __x.end(), _M_start), _M_finish); - else { - const_iterator __mid = __x.begin() + difference_type(__len); - copy(__x.begin(), __mid, _M_start); - insert(_M_finish, __mid, __x.end()); + _Self + operator--(int) + { + _Self __tmp = *this; + --*this; + return __tmp; } - } - return *this; - } - - void swap(deque& __x) { - std::swap(_M_start, __x._M_start); - std::swap(_M_finish, __x._M_finish); - std::swap(_M_map, __x._M_map); - std::swap(_M_map_size, __x._M_map_size); - } - -public: - // assign(), a generalized assignment member function. Two - // versions: one that takes a count, and one that takes a range. - // The range version is a member template, so we dispatch on whether - // or not the type is an integer. - - void _M_fill_assign(size_type __n, const _Tp& __val) { - if (__n > size()) { - fill(begin(), end(), __val); - insert(end(), __n - size(), __val); - } - else { - erase(begin() + __n, end()); - fill(begin(), end(), __val); - } - } - - void assign(size_type __n, const _Tp& __val) { - _M_fill_assign(__n, __val); - } - - template - void assign(_InputIterator __first, _InputIterator __last) { - typedef typename _Is_integer<_InputIterator>::_Integral _Integral; - _M_assign_dispatch(__first, __last, _Integral()); - } - -private: // helper functions for assign() - - template - void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) - { _M_fill_assign((size_type) __n, (_Tp) __val); } - - template - void _M_assign_dispatch(_InputIterator __first, _InputIterator __last, - __false_type) { - _M_assign_aux(__first, __last, __iterator_category(__first)); - } - - template - void _M_assign_aux(_InputIterator __first, _InputIterator __last, - input_iterator_tag); - - template - void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, - forward_iterator_tag) { - size_type __len = 0; - distance(__first, __last, __len); - if (__len > size()) { - _ForwardIterator __mid = __first; - advance(__mid, size()); - copy(__first, __mid, begin()); - insert(end(), __mid, __last); - } - else - erase(copy(__first, __last, begin()), end()); - } - -public: // push_* and pop_* - - void push_back(const value_type& __t) { - if (_M_finish._M_cur != _M_finish._M_last - 1) { - construct(_M_finish._M_cur, __t); - ++_M_finish._M_cur; - } - else - _M_push_back_aux(__t); - } - - void push_back() { - if (_M_finish._M_cur != _M_finish._M_last - 1) { - construct(_M_finish._M_cur); - ++_M_finish._M_cur; - } - else - _M_push_back_aux(); - } - - void push_front(const value_type& __t) { - if (_M_start._M_cur != _M_start._M_first) { - construct(_M_start._M_cur - 1, __t); - --_M_start._M_cur; - } - else - _M_push_front_aux(__t); - } - - void push_front() { - if (_M_start._M_cur != _M_start._M_first) { - construct(_M_start._M_cur - 1); - --_M_start._M_cur; - } - else - _M_push_front_aux(); - } + _Self& + operator+=(difference_type __n) + { + const difference_type __offset = __n + (_M_cur - _M_first); + if (__offset >= 0 && __offset < difference_type(_S_buffer_size())) + _M_cur += __n; + else + { + const difference_type __node_offset = + __offset > 0 ? __offset / difference_type(_S_buffer_size()) + : -difference_type((-__offset - 1) + / _S_buffer_size()) - 1; + _M_set_node(_M_node + __node_offset); + _M_cur = _M_first + (__offset - __node_offset + * difference_type(_S_buffer_size())); + } + return *this; + } - void pop_back() { - if (_M_finish._M_cur != _M_finish._M_first) { - --_M_finish._M_cur; - destroy(_M_finish._M_cur); - } - else - _M_pop_back_aux(); - } - - void pop_front() { - if (_M_start._M_cur != _M_start._M_last - 1) { - destroy(_M_start._M_cur); - ++_M_start._M_cur; - } - else - _M_pop_front_aux(); - } + _Self + operator+(difference_type __n) const + { + _Self __tmp = *this; + return __tmp += __n; + } -public: // Insert + _Self& + operator-=(difference_type __n) + { return *this += -__n; } - iterator insert(iterator position, const value_type& __x) { - if (position._M_cur == _M_start._M_cur) { - push_front(__x); - return _M_start; - } - else if (position._M_cur == _M_finish._M_cur) { - push_back(__x); - iterator __tmp = _M_finish; - --__tmp; - return __tmp; - } - else { - return _M_insert_aux(position, __x); - } - } - - iterator insert(iterator __position) - { return insert(__position, value_type()); } - - void insert(iterator __pos, size_type __n, const value_type& __x) - { _M_fill_insert(__pos, __n, __x); } - - void _M_fill_insert(iterator __pos, size_type __n, const value_type& __x); - - // Check whether it's an integral type. If so, it's not an iterator. - template - void insert(iterator __pos, _InputIterator __first, _InputIterator __last) { - typedef typename _Is_integer<_InputIterator>::_Integral _Integral; - _M_insert_dispatch(__pos, __first, __last, _Integral()); - } - - template - void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, - __true_type) { - _M_fill_insert(__pos, (size_type) __n, (value_type) __x); - } - - template - void _M_insert_dispatch(iterator __pos, - _InputIterator __first, _InputIterator __last, - __false_type) { - insert(__pos, __first, __last, __iterator_category(__first)); - } - - void resize(size_type __new_size, const value_type& __x) { - const size_type __len = size(); - if (__new_size < __len) - erase(_M_start + __new_size, _M_finish); - else - insert(_M_finish, __new_size - __len, __x); - } - - void resize(size_type new_size) { resize(new_size, value_type()); } - -public: // Erase - iterator erase(iterator __pos) { - iterator __next = __pos; - ++__next; - size_type __index = __pos - _M_start; - if (__index < (size() >> 1)) { - copy_backward(_M_start, __pos, __next); - pop_front(); - } - else { - copy(__next, _M_finish, __pos); - pop_back(); - } - return _M_start + __index; - } - - iterator erase(iterator __first, iterator __last); - void clear(); - -protected: // Internal construction/destruction - - void _M_fill_initialize(const value_type& __value); - - template - void _M_range_initialize(_InputIterator __first, _InputIterator __last, - input_iterator_tag); - - template - void _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last, - forward_iterator_tag); - -protected: // Internal push_* and pop_* - - void _M_push_back_aux(const value_type&); - void _M_push_back_aux(); - void _M_push_front_aux(const value_type&); - void _M_push_front_aux(); - void _M_pop_back_aux(); - void _M_pop_front_aux(); - -protected: // Internal insert functions - - template - void insert(iterator __pos, _InputIterator __first, _InputIterator __last, - input_iterator_tag); - - template - void insert(iterator __pos, - _ForwardIterator __first, _ForwardIterator __last, - forward_iterator_tag); - - iterator _M_insert_aux(iterator __pos, const value_type& __x); - iterator _M_insert_aux(iterator __pos); - void _M_insert_aux(iterator __pos, size_type __n, const value_type& __x); - - template - void _M_insert_aux(iterator __pos, - _ForwardIterator __first, _ForwardIterator __last, - size_type __n); - - iterator _M_reserve_elements_at_front(size_type __n) { - size_type __vacancies = _M_start._M_cur - _M_start._M_first; - if (__n > __vacancies) - _M_new_elements_at_front(__n - __vacancies); - return _M_start - difference_type(__n); - } - - iterator _M_reserve_elements_at_back(size_type __n) { - size_type __vacancies = (_M_finish._M_last - _M_finish._M_cur) - 1; - if (__n > __vacancies) - _M_new_elements_at_back(__n - __vacancies); - return _M_finish + difference_type(__n); - } - - void _M_new_elements_at_front(size_type __new_elements); - void _M_new_elements_at_back(size_type __new_elements); - -protected: // Allocation of _M_map and nodes - - // Makes sure the _M_map has space for new nodes. Does not actually - // add the nodes. Can invalidate _M_map pointers. (And consequently, - // deque iterators.) - - void _M_reserve_map_at_back (size_type __nodes_to_add = 1) { - if (__nodes_to_add + 1 > _M_map_size - (_M_finish._M_node - _M_map)) - _M_reallocate_map(__nodes_to_add, false); - } - - void _M_reserve_map_at_front (size_type __nodes_to_add = 1) { - if (__nodes_to_add > size_type(_M_start._M_node - _M_map)) - _M_reallocate_map(__nodes_to_add, true); - } - - void _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front); -}; - -// Non-inline member functions - -template -template -void deque<_Tp, _Alloc> - ::_M_assign_aux(_InputIter __first, _InputIter __last, input_iterator_tag) -{ - iterator __cur = begin(); - for ( ; __first != __last && __cur != end(); ++__cur, ++__first) - *__cur = *__first; - if (__first == __last) - erase(__cur, end()); - else - insert(end(), __first, __last); -} - -template -void deque<_Tp, _Alloc>::_M_fill_insert(iterator __pos, - size_type __n, const value_type& __x) -{ - if (__pos._M_cur == _M_start._M_cur) { - iterator __new_start = _M_reserve_elements_at_front(__n); - __STL_TRY { - uninitialized_fill(__new_start, _M_start, __x); - _M_start = __new_start; - } - __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node)); - } - else if (__pos._M_cur == _M_finish._M_cur) { - iterator __new_finish = _M_reserve_elements_at_back(__n); - __STL_TRY { - uninitialized_fill(_M_finish, __new_finish, __x); - _M_finish = __new_finish; + _Self + operator-(difference_type __n) const + { + _Self __tmp = *this; + return __tmp -= __n; + } + + reference + operator[](difference_type __n) const + { return *(*this + __n); } + + /** @if maint + * Prepares to traverse new_node. Sets everything except + * _M_cur, which should therefore be set by the caller + * immediately afterwards, based on _M_first and _M_last. + * @endif + */ + void + _M_set_node(_Map_pointer __new_node) + { + _M_node = __new_node; + _M_first = *__new_node; + _M_last = _M_first + difference_type(_S_buffer_size()); + } + }; + + // Note: we also provide overloads whose operands are of the same type in + // order to avoid ambiguous overload resolution when std::rel_ops operators + // are in scope (for additional details, see libstdc++/3628) + template + inline bool + operator==(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, + const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) + { return __x._M_cur == __y._M_cur; } + + template + inline bool + operator==(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, + const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) + { return __x._M_cur == __y._M_cur; } + + template + inline bool + operator!=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, + const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) + { return !(__x == __y); } + + template + inline bool + operator!=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, + const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) + { return !(__x == __y); } + + template + inline bool + operator<(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, + const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) + { return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur) + : (__x._M_node < __y._M_node); } + + template + inline bool + operator<(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, + const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) + { return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur) + : (__x._M_node < __y._M_node); } + + template + inline bool + operator>(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, + const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) + { return __y < __x; } + + template + inline bool + operator>(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, + const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) + { return __y < __x; } + + template + inline bool + operator<=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, + const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) + { return !(__y < __x); } + + template + inline bool + operator<=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, + const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) + { return !(__y < __x); } + + template + inline bool + operator>=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, + const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) + { return !(__x < __y); } + + template + inline bool + operator>=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, + const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) + { return !(__x < __y); } + + // _GLIBCXX_RESOLVE_LIB_DEFECTS + // According to the resolution of DR179 not only the various comparison + // operators but also operator- must accept mixed iterator/const_iterator + // parameters. + template + inline typename _Deque_iterator<_Tp, _Ref, _Ptr>::difference_type + operator-(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, + const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) + { + return typename _Deque_iterator<_Tp, _Ref, _Ptr>::difference_type + (_Deque_iterator<_Tp, _Ref, _Ptr>::_S_buffer_size()) + * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first) + + (__y._M_last - __y._M_cur); } - __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1, - __new_finish._M_node + 1)); - } - else - _M_insert_aux(__pos, __n, __x); -} - -template -typename deque<_Tp,_Alloc>::iterator -deque<_Tp,_Alloc>::erase(iterator __first, iterator __last) -{ - if (__first == _M_start && __last == _M_finish) { - clear(); - return _M_finish; - } - else { - difference_type __n = __last - __first; - difference_type __elems_before = __first - _M_start; - if (static_cast(__elems_before) < (size() - __n) / 2) { - copy_backward(_M_start, __first, __last); - iterator __new_start = _M_start + __n; - destroy(_M_start, __new_start); - _M_destroy_nodes(__new_start._M_node, _M_start._M_node); - _M_start = __new_start; + + template + inline typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type + operator-(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, + const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) + { + return typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type + (_Deque_iterator<_Tp, _RefL, _PtrL>::_S_buffer_size()) + * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first) + + (__y._M_last - __y._M_cur); } - else { - copy(__last, _M_finish, __first); - iterator __new_finish = _M_finish - __n; - destroy(__new_finish, _M_finish); - _M_destroy_nodes(__new_finish._M_node + 1, _M_finish._M_node + 1); - _M_finish = __new_finish; + + template + inline _Deque_iterator<_Tp, _Ref, _Ptr> + operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Ref, _Ptr>& __x) + { return __x + __n; } + + template + void + fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first, + const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& __value); + + /** + * @if maint + * Deque base class. This class provides the unified face for %deque's + * allocation. This class's constructor and destructor allocate and + * deallocate (but do not initialize) storage. This makes %exception + * safety easier. + * + * Nothing in this class ever constructs or destroys an actual Tp element. + * (Deque handles that itself.) Only/All memory management is performed + * here. + * @endif + */ + template + class _Deque_base + { + public: + typedef _Alloc allocator_type; + + allocator_type + get_allocator() const + { return allocator_type(_M_get_Tp_allocator()); } + + typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator; + typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator; + + _Deque_base(const allocator_type& __a, size_t __num_elements) + : _M_impl(__a) + { _M_initialize_map(__num_elements); } + + _Deque_base(const allocator_type& __a) + : _M_impl(__a) + { } + + ~_Deque_base(); + + protected: + //This struct encapsulates the implementation of the std::deque + //standard container and at the same time makes use of the EBO + //for empty allocators. + typedef typename _Alloc::template rebind<_Tp*>::other _Map_alloc_type; + + typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type; + + struct _Deque_impl + : public _Tp_alloc_type + { + _Tp** _M_map; + size_t _M_map_size; + iterator _M_start; + iterator _M_finish; + + _Deque_impl(const _Tp_alloc_type& __a) + : _Tp_alloc_type(__a), _M_map(0), _M_map_size(0), + _M_start(), _M_finish() + { } + }; + + _Tp_alloc_type& + _M_get_Tp_allocator() + { return *static_cast<_Tp_alloc_type*>(&this->_M_impl); } + + const _Tp_alloc_type& + _M_get_Tp_allocator() const + { return *static_cast(&this->_M_impl); } + + _Map_alloc_type + _M_get_map_allocator() const + { return _Map_alloc_type(_M_get_Tp_allocator()); } + + _Tp* + _M_allocate_node() + { + return _M_impl._Tp_alloc_type::allocate(__deque_buf_size(sizeof(_Tp))); + } + + void + _M_deallocate_node(_Tp* __p) + { + _M_impl._Tp_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp))); + } + + _Tp** + _M_allocate_map(size_t __n) + { return _M_get_map_allocator().allocate(__n); } + + void + _M_deallocate_map(_Tp** __p, size_t __n) + { _M_get_map_allocator().deallocate(__p, __n); } + + protected: + void _M_initialize_map(size_t); + void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish); + void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish); + enum { _S_initial_map_size = 8 }; + + _Deque_impl _M_impl; + }; + + template + _Deque_base<_Tp, _Alloc>:: + ~_Deque_base() + { + if (this->_M_impl._M_map) + { + _M_destroy_nodes(this->_M_impl._M_start._M_node, + this->_M_impl._M_finish._M_node + 1); + _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size); + } } - return _M_start + __elems_before; - } -} - -template -void deque<_Tp,_Alloc>::clear() -{ - for (_Map_pointer __node = _M_start._M_node + 1; - __node < _M_finish._M_node; - ++__node) { - destroy(*__node, *__node + _S_buffer_size()); - _M_deallocate_node(*__node); - } - - if (_M_start._M_node != _M_finish._M_node) { - destroy(_M_start._M_cur, _M_start._M_last); - destroy(_M_finish._M_first, _M_finish._M_cur); - _M_deallocate_node(_M_finish._M_first); - } - else - destroy(_M_start._M_cur, _M_finish._M_cur); - - _M_finish = _M_start; -} - -// Precondition: _M_start and _M_finish have already been initialized, -// but none of the deque's elements have yet been constructed. -template -void deque<_Tp,_Alloc>::_M_fill_initialize(const value_type& __value) { - _Map_pointer __cur; - __STL_TRY { - for (__cur = _M_start._M_node; __cur < _M_finish._M_node; ++__cur) - uninitialized_fill(*__cur, *__cur + _S_buffer_size(), __value); - uninitialized_fill(_M_finish._M_first, _M_finish._M_cur, __value); - } - __STL_UNWIND(destroy(_M_start, iterator(*__cur, __cur))); -} - -template template -void deque<_Tp,_Alloc>::_M_range_initialize(_InputIterator __first, - _InputIterator __last, - input_iterator_tag) -{ - _M_initialize_map(0); - __STL_TRY { - for ( ; __first != __last; ++__first) - push_back(*__first); - } - __STL_UNWIND(clear()); -} - -template template -void deque<_Tp,_Alloc>::_M_range_initialize(_ForwardIterator __first, - _ForwardIterator __last, - forward_iterator_tag) -{ - size_type __n = 0; - distance(__first, __last, __n); - _M_initialize_map(__n); - - _Map_pointer __cur_node; - __STL_TRY { - for (__cur_node = _M_start._M_node; - __cur_node < _M_finish._M_node; - ++__cur_node) { - _ForwardIterator __mid = __first; - advance(__mid, _S_buffer_size()); - uninitialized_copy(__first, __mid, *__cur_node); - __first = __mid; + + /** + * @if maint + * @brief Layout storage. + * @param num_elements The count of T's for which to allocate space + * at first. + * @return Nothing. + * + * The initial underlying memory layout is a bit complicated... + * @endif + */ + template + void + _Deque_base<_Tp, _Alloc>:: + _M_initialize_map(size_t __num_elements) + { + const size_t __num_nodes = (__num_elements/ __deque_buf_size(sizeof(_Tp)) + + 1); + + this->_M_impl._M_map_size = std::max((size_t) _S_initial_map_size, + size_t(__num_nodes + 2)); + this->_M_impl._M_map = _M_allocate_map(this->_M_impl._M_map_size); + + // For "small" maps (needing less than _M_map_size nodes), allocation + // starts in the middle elements and grows outwards. So nstart may be + // the beginning of _M_map, but for small maps it may be as far in as + // _M_map+3. + + _Tp** __nstart = (this->_M_impl._M_map + + (this->_M_impl._M_map_size - __num_nodes) / 2); + _Tp** __nfinish = __nstart + __num_nodes; + + try + { _M_create_nodes(__nstart, __nfinish); } + catch(...) + { + _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size); + this->_M_impl._M_map = 0; + this->_M_impl._M_map_size = 0; + __throw_exception_again; + } + + this->_M_impl._M_start._M_set_node(__nstart); + this->_M_impl._M_finish._M_set_node(__nfinish - 1); + this->_M_impl._M_start._M_cur = _M_impl._M_start._M_first; + this->_M_impl._M_finish._M_cur = (this->_M_impl._M_finish._M_first + + __num_elements + % __deque_buf_size(sizeof(_Tp))); } - uninitialized_copy(__first, __last, _M_finish._M_first); - } - __STL_UNWIND(destroy(_M_start, iterator(*__cur_node, __cur_node))); -} - -// Called only if _M_finish._M_cur == _M_finish._M_last - 1. -template -void deque<_Tp,_Alloc>::_M_push_back_aux(const value_type& __t) -{ - value_type __t_copy = __t; - _M_reserve_map_at_back(); - *(_M_finish._M_node + 1) = _M_allocate_node(); - __STL_TRY { - construct(_M_finish._M_cur, __t_copy); - _M_finish._M_set_node(_M_finish._M_node + 1); - _M_finish._M_cur = _M_finish._M_first; - } - __STL_UNWIND(_M_deallocate_node(*(_M_finish._M_node + 1))); -} - -// Called only if _M_finish._M_cur == _M_finish._M_last - 1. -template -void deque<_Tp,_Alloc>::_M_push_back_aux() -{ - _M_reserve_map_at_back(); - *(_M_finish._M_node + 1) = _M_allocate_node(); - __STL_TRY { - construct(_M_finish._M_cur); - _M_finish._M_set_node(_M_finish._M_node + 1); - _M_finish._M_cur = _M_finish._M_first; - } - __STL_UNWIND(_M_deallocate_node(*(_M_finish._M_node + 1))); -} - -// Called only if _M_start._M_cur == _M_start._M_first. -template -void deque<_Tp,_Alloc>::_M_push_front_aux(const value_type& __t) -{ - value_type __t_copy = __t; - _M_reserve_map_at_front(); - *(_M_start._M_node - 1) = _M_allocate_node(); - __STL_TRY { - _M_start._M_set_node(_M_start._M_node - 1); - _M_start._M_cur = _M_start._M_last - 1; - construct(_M_start._M_cur, __t_copy); - } - __STL_UNWIND((++_M_start, _M_deallocate_node(*(_M_start._M_node - 1)))); -} - -// Called only if _M_start._M_cur == _M_start._M_first. -template -void deque<_Tp,_Alloc>::_M_push_front_aux() -{ - _M_reserve_map_at_front(); - *(_M_start._M_node - 1) = _M_allocate_node(); - __STL_TRY { - _M_start._M_set_node(_M_start._M_node - 1); - _M_start._M_cur = _M_start._M_last - 1; - construct(_M_start._M_cur); - } - __STL_UNWIND((++_M_start, _M_deallocate_node(*(_M_start._M_node - 1)))); -} - -// Called only if _M_finish._M_cur == _M_finish._M_first. -template -void deque<_Tp,_Alloc>::_M_pop_back_aux() -{ - _M_deallocate_node(_M_finish._M_first); - _M_finish._M_set_node(_M_finish._M_node - 1); - _M_finish._M_cur = _M_finish._M_last - 1; - destroy(_M_finish._M_cur); -} - -// Called only if _M_start._M_cur == _M_start._M_last - 1. Note that -// if the deque has at least one element (a precondition for this member -// function), and if _M_start._M_cur == _M_start._M_last, then the deque -// must have at least two nodes. -template -void deque<_Tp,_Alloc>::_M_pop_front_aux() -{ - destroy(_M_start._M_cur); - _M_deallocate_node(_M_start._M_first); - _M_start._M_set_node(_M_start._M_node + 1); - _M_start._M_cur = _M_start._M_first; -} - -template template -void deque<_Tp,_Alloc>::insert(iterator __pos, - _InputIterator __first, _InputIterator __last, - input_iterator_tag) -{ - copy(__first, __last, inserter(*this, __pos)); -} - -template template -void -deque<_Tp,_Alloc>::insert(iterator __pos, - _ForwardIterator __first, _ForwardIterator __last, - forward_iterator_tag) { - size_type __n = 0; - distance(__first, __last, __n); - if (__pos._M_cur == _M_start._M_cur) { - iterator __new_start = _M_reserve_elements_at_front(__n); - __STL_TRY { - uninitialized_copy(__first, __last, __new_start); - _M_start = __new_start; + + template + void + _Deque_base<_Tp, _Alloc>:: + _M_create_nodes(_Tp** __nstart, _Tp** __nfinish) + { + _Tp** __cur; + try + { + for (__cur = __nstart; __cur < __nfinish; ++__cur) + *__cur = this->_M_allocate_node(); + } + catch(...) + { + _M_destroy_nodes(__nstart, __cur); + __throw_exception_again; + } } - __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node)); - } - else if (__pos._M_cur == _M_finish._M_cur) { - iterator __new_finish = _M_reserve_elements_at_back(__n); - __STL_TRY { - uninitialized_copy(__first, __last, _M_finish); - _M_finish = __new_finish; + + template + void + _Deque_base<_Tp, _Alloc>:: + _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish) + { + for (_Tp** __n = __nstart; __n < __nfinish; ++__n) + _M_deallocate_node(*__n); } - __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1, - __new_finish._M_node + 1)); - } - else - _M_insert_aux(__pos, __first, __last, __n); -} - -template -typename deque<_Tp, _Alloc>::iterator -deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos, const value_type& __x) -{ - difference_type __index = __pos - _M_start; - value_type __x_copy = __x; - if (static_cast(__index) < size() / 2) { - push_front(front()); - iterator __front1 = _M_start; - ++__front1; - iterator __front2 = __front1; - ++__front2; - __pos = _M_start + __index; - iterator __pos1 = __pos; - ++__pos1; - copy(__front2, __pos1, __front1); - } - else { - push_back(back()); - iterator __back1 = _M_finish; - --__back1; - iterator __back2 = __back1; - --__back2; - __pos = _M_start + __index; - copy_backward(__pos, __back2, __back1); - } - *__pos = __x_copy; - return __pos; -} - -template -typename deque<_Tp,_Alloc>::iterator -deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos) -{ - difference_type __index = __pos - _M_start; - if (static_cast(__index) < size() / 2) { - push_front(front()); - iterator __front1 = _M_start; - ++__front1; - iterator __front2 = __front1; - ++__front2; - __pos = _M_start + __index; - iterator __pos1 = __pos; - ++__pos1; - copy(__front2, __pos1, __front1); - } - else { - push_back(back()); - iterator __back1 = _M_finish; - --__back1; - iterator __back2 = __back1; - --__back2; - __pos = _M_start + __index; - copy_backward(__pos, __back2, __back1); - } - *__pos = value_type(); - return __pos; -} - -template -void deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos, - size_type __n, - const value_type& __x) -{ - const difference_type __elems_before = __pos - _M_start; - size_type __length = this->size(); - value_type __x_copy = __x; - if (__elems_before < difference_type(__length / 2)) { - iterator __new_start = _M_reserve_elements_at_front(__n); - iterator __old_start = _M_start; - __pos = _M_start + __elems_before; - __STL_TRY { - if (__elems_before >= difference_type(__n)) { - iterator __start_n = _M_start + difference_type(__n); - uninitialized_copy(_M_start, __start_n, __new_start); - _M_start = __new_start; - copy(__start_n, __pos, __old_start); - fill(__pos - difference_type(__n), __pos, __x_copy); + + /** + * @brief A standard container using fixed-size memory allocation and + * constant-time manipulation of elements at either end. + * + * @ingroup Containers + * @ingroup Sequences + * + * Meets the requirements of a container, a + * reversible container, and a + * sequence, including the + * optional sequence requirements. + * + * In previous HP/SGI versions of deque, there was an extra template + * parameter so users could control the node size. This extension turned + * out to violate the C++ standard (it can be detected using template + * template parameters), and it was removed. + * + * @if maint + * Here's how a deque manages memory. Each deque has 4 members: + * + * - Tp** _M_map + * - size_t _M_map_size + * - iterator _M_start, _M_finish + * + * map_size is at least 8. %map is an array of map_size + * pointers-to-"nodes". (The name %map has nothing to do with the + * std::map class, and "nodes" should not be confused with + * std::list's usage of "node".) + * + * A "node" has no specific type name as such, but it is referred + * to as "node" in this file. It is a simple array-of-Tp. If Tp + * is very large, there will be one Tp element per node (i.e., an + * "array" of one). For non-huge Tp's, node size is inversely + * related to Tp size: the larger the Tp, the fewer Tp's will fit + * in a node. The goal here is to keep the total size of a node + * relatively small and constant over different Tp's, to improve + * allocator efficiency. + * + * Not every pointer in the %map array will point to a node. If + * the initial number of elements in the deque is small, the + * /middle/ %map pointers will be valid, and the ones at the edges + * will be unused. This same situation will arise as the %map + * grows: available %map pointers, if any, will be on the ends. As + * new nodes are created, only a subset of the %map's pointers need + * to be copied "outward". + * + * Class invariants: + * - For any nonsingular iterator i: + * - i.node points to a member of the %map array. (Yes, you read that + * correctly: i.node does not actually point to a node.) The member of + * the %map array is what actually points to the node. + * - i.first == *(i.node) (This points to the node (first Tp element).) + * - 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, a deque with > + class deque : protected _Deque_base<_Tp, _Alloc> + { + // concept requirements + typedef typename _Alloc::value_type _Alloc_value_type; + __glibcxx_class_requires(_Tp, _SGIAssignableConcept) + __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept) + + typedef _Deque_base<_Tp, _Alloc> _Base; + typedef typename _Base::_Tp_alloc_type _Tp_alloc_type; + + public: + typedef _Tp value_type; + typedef typename _Tp_alloc_type::pointer pointer; + typedef typename _Tp_alloc_type::const_pointer const_pointer; + typedef typename _Tp_alloc_type::reference reference; + typedef typename _Tp_alloc_type::const_reference const_reference; + typedef typename _Base::iterator iterator; + typedef typename _Base::const_iterator const_iterator; + typedef std::reverse_iterator const_reverse_iterator; + typedef std::reverse_iterator reverse_iterator; + typedef size_t size_type; + typedef ptrdiff_t difference_type; + typedef _Alloc allocator_type; + + protected: + typedef pointer* _Map_pointer; + + static size_t _S_buffer_size() + { return __deque_buf_size(sizeof(_Tp)); } + + // Functions controlling memory layout, and nothing else. + using _Base::_M_initialize_map; + using _Base::_M_create_nodes; + using _Base::_M_destroy_nodes; + using _Base::_M_allocate_node; + using _Base::_M_deallocate_node; + using _Base::_M_allocate_map; + using _Base::_M_deallocate_map; + using _Base::_M_get_Tp_allocator; + + /** @if maint + * A total of four data members accumulated down the heirarchy. + * May be accessed via _M_impl.* + * @endif + */ + using _Base::_M_impl; + + public: + // [23.2.1.1] construct/copy/destroy + // (assign() and get_allocator() are also listed in this section) + /** + * @brief Default constructor creates no elements. + */ + explicit + deque(const allocator_type& __a = allocator_type()) + : _Base(__a, 0) {} + + /** + * @brief Create a %deque with copies of an exemplar element. + * @param n The number of elements to initially create. + * @param value An element to copy. + * + * This constructor fills the %deque with @a n copies of @a value. + */ + explicit + deque(size_type __n, const value_type& __value = value_type(), + const allocator_type& __a = allocator_type()) + : _Base(__a, __n) + { _M_fill_initialize(__value); } + + /** + * @brief %Deque copy constructor. + * @param x A %deque of identical element and allocator types. + * + * The newly-created %deque uses a copy of the allocation object used + * by @a x. + */ + deque(const deque& __x) + : _Base(__x._M_get_Tp_allocator(), __x.size()) + { std::__uninitialized_copy_a(__x.begin(), __x.end(), + this->_M_impl._M_start, + _M_get_Tp_allocator()); } + + /** + * @brief Builds a %deque from a range. + * @param first An input iterator. + * @param last An input iterator. + * + * Create a %deque consisting of copies of the elements from [first, + * last). + * + * If the iterators are forward, bidirectional, or random-access, then + * this will call the elements' copy constructor N times (where N is + * distance(first,last)) and do no memory reallocation. But if only + * input iterators are used, then this will do at most 2N calls to the + * copy constructor, and logN memory reallocations. + */ + template + deque(_InputIterator __first, _InputIterator __last, + const allocator_type& __a = allocator_type()) + : _Base(__a) + { + // Check whether it's an integral type. If so, it's not an iterator. + typedef typename std::__is_integer<_InputIterator>::__type _Integral; + _M_initialize_dispatch(__first, __last, _Integral()); + } + + /** + * The dtor only erases the elements, and note that if the elements + * themselves are pointers, the pointed-to memory is not touched in any + * way. Managing the pointer is the user's responsibilty. + */ + ~deque() + { _M_destroy_data(begin(), end(), _M_get_Tp_allocator()); } + + /** + * @brief %Deque assignment operator. + * @param x A %deque of identical element and allocator types. + * + * All the elements of @a x are copied, but unlike the copy constructor, + * the allocator object is not copied. + */ + deque& + operator=(const deque& __x); + + /** + * @brief Assigns a given value to a %deque. + * @param n Number of elements to be assigned. + * @param val Value to be assigned. + * + * This function fills a %deque with @a n copies of the given + * value. Note that the assignment completely changes the + * %deque and that the resulting %deque's size is the same as + * the number of elements assigned. Old data may be lost. + */ + void + assign(size_type __n, const value_type& __val) + { _M_fill_assign(__n, __val); } + + /** + * @brief Assigns a range to a %deque. + * @param first An input iterator. + * @param last An input iterator. + * + * This function fills a %deque with copies of the elements in the + * range [first,last). + * + * Note that the assignment completely changes the %deque and that the + * resulting %deque's size is the same as the number of elements + * assigned. Old data may be lost. + */ + template + void + assign(_InputIterator __first, _InputIterator __last) + { + typedef typename std::__is_integer<_InputIterator>::__type _Integral; + _M_assign_dispatch(__first, __last, _Integral()); + } + + /// Get a copy of the memory allocation object. + allocator_type + get_allocator() const + { return _Base::get_allocator(); } + + // iterators + /** + * Returns a read/write iterator that points to the first element in the + * %deque. Iteration is done in ordinary element order. + */ + iterator + begin() + { return this->_M_impl._M_start; } + + /** + * Returns a read-only (constant) iterator that points to the first + * element in the %deque. Iteration is done in ordinary element order. + */ + const_iterator + begin() const + { return this->_M_impl._M_start; } + + /** + * Returns a read/write iterator that points one past the last + * element in the %deque. Iteration is done in ordinary + * element order. + */ + iterator + end() + { return this->_M_impl._M_finish; } + + /** + * Returns a read-only (constant) iterator that points one past + * the last element in the %deque. Iteration is done in + * ordinary element order. + */ + const_iterator + end() const + { return this->_M_impl._M_finish; } + + /** + * Returns a read/write reverse iterator that points to the + * last element in the %deque. Iteration is done in reverse + * element order. + */ + reverse_iterator + rbegin() + { return reverse_iterator(this->_M_impl._M_finish); } + + /** + * Returns a read-only (constant) reverse iterator that points + * to the last element in the %deque. Iteration is done in + * reverse element order. + */ + const_reverse_iterator + rbegin() const + { return const_reverse_iterator(this->_M_impl._M_finish); } + + /** + * Returns a read/write reverse iterator that points to one + * before the first element in the %deque. Iteration is done + * in reverse element order. + */ + reverse_iterator + rend() + { return reverse_iterator(this->_M_impl._M_start); } + + /** + * Returns a read-only (constant) reverse iterator that points + * to one before the first element in the %deque. Iteration is + * done in reverse element order. + */ + const_reverse_iterator + rend() const + { return const_reverse_iterator(this->_M_impl._M_start); } + + // [23.2.1.2] capacity + /** Returns the number of elements in the %deque. */ + size_type + size() const + { return this->_M_impl._M_finish - this->_M_impl._M_start; } + + /** Returns the size() of the largest possible %deque. */ + size_type + max_size() const + { return _M_get_Tp_allocator().max_size(); } + + /** + * @brief Resizes the %deque to the specified number of elements. + * @param new_size Number of elements the %deque should contain. + * @param x Data with which new elements should be populated. + * + * This function will %resize the %deque to the specified + * number of elements. If the number is smaller than the + * %deque's current size the %deque is truncated, otherwise the + * %deque is extended and new elements are populated with given + * data. + */ + void + resize(size_type __new_size, value_type __x = value_type()) + { + const size_type __len = size(); + if (__new_size < __len) + _M_erase_at_end(this->_M_impl._M_start + difference_type(__new_size)); + else + insert(this->_M_impl._M_finish, __new_size - __len, __x); } - else { - __uninitialized_copy_fill(_M_start, __pos, __new_start, - _M_start, __x_copy); - _M_start = __new_start; - fill(__old_start, __pos, __x_copy); + + /** + * Returns true if the %deque is empty. (Thus begin() would + * equal end().) + */ + bool + empty() const + { return this->_M_impl._M_finish == this->_M_impl._M_start; } + + // element access + /** + * @brief Subscript access to the data contained in the %deque. + * @param n The index of the element for which data should be + * accessed. + * @return Read/write reference to data. + * + * This operator allows for easy, array-style, data access. + * Note that data access with this operator is unchecked and + * out_of_range lookups are not defined. (For checked lookups + * see at().) + */ + reference + operator[](size_type __n) + { return this->_M_impl._M_start[difference_type(__n)]; } + + /** + * @brief Subscript access to the data contained in the %deque. + * @param n The index of the element for which data should be + * accessed. + * @return Read-only (constant) reference to data. + * + * This operator allows for easy, array-style, data access. + * Note that data access with this operator is unchecked and + * out_of_range lookups are not defined. (For checked lookups + * see at().) + */ + const_reference + operator[](size_type __n) const + { return this->_M_impl._M_start[difference_type(__n)]; } + + protected: + /// @if maint Safety check used only from at(). @endif + void + _M_range_check(size_type __n) const + { + if (__n >= this->size()) + __throw_out_of_range(__N("deque::_M_range_check")); } - } - __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node)); - } - else { - iterator __new_finish = _M_reserve_elements_at_back(__n); - iterator __old_finish = _M_finish; - const difference_type __elems_after = - difference_type(__length) - __elems_before; - __pos = _M_finish - __elems_after; - __STL_TRY { - if (__elems_after > difference_type(__n)) { - iterator __finish_n = _M_finish - difference_type(__n); - uninitialized_copy(__finish_n, _M_finish, _M_finish); - _M_finish = __new_finish; - copy_backward(__pos, __finish_n, __old_finish); - fill(__pos, __pos + difference_type(__n), __x_copy); + + public: + /** + * @brief Provides access to the data contained in the %deque. + * @param n The index of the element for which data should be + * accessed. + * @return Read/write reference to data. + * @throw std::out_of_range If @a n is an invalid index. + * + * This function provides for safer data access. The parameter + * is first checked that it is in the range of the deque. The + * function throws out_of_range if the check fails. + */ + reference + at(size_type __n) + { + _M_range_check(__n); + return (*this)[__n]; } - else { - __uninitialized_fill_copy(_M_finish, __pos + difference_type(__n), - __x_copy, __pos, _M_finish); - _M_finish = __new_finish; - fill(__pos, __old_finish, __x_copy); + + /** + * @brief Provides access to the data contained in the %deque. + * @param n The index of the element for which data should be + * accessed. + * @return Read-only (constant) reference to data. + * @throw std::out_of_range If @a n is an invalid index. + * + * This function provides for safer data access. The parameter is first + * checked that it is in the range of the deque. The function throws + * out_of_range if the check fails. + */ + const_reference + at(size_type __n) const + { + _M_range_check(__n); + return (*this)[__n]; } - } - __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1, - __new_finish._M_node + 1)); - } -} - -template template -void deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos, - _ForwardIterator __first, - _ForwardIterator __last, - size_type __n) -{ - const difference_type __elemsbefore = __pos - _M_start; - size_type __length = size(); - if (static_cast(__elemsbefore) < __length / 2) { - iterator __new_start = _M_reserve_elements_at_front(__n); - iterator __old_start = _M_start; - __pos = _M_start + __elemsbefore; - __STL_TRY { - if (__elemsbefore >= difference_type(__n)) { - iterator __start_n = _M_start + difference_type(__n); - uninitialized_copy(_M_start, __start_n, __new_start); - _M_start = __new_start; - copy(__start_n, __pos, __old_start); - copy(__first, __last, __pos - difference_type(__n)); + + /** + * Returns a read/write reference to the data at the first + * element of the %deque. + */ + reference + front() + { return *begin(); } + + /** + * Returns a read-only (constant) reference to the data at the first + * element of the %deque. + */ + const_reference + front() const + { return *begin(); } + + /** + * Returns a read/write reference to the data at the last element of the + * %deque. + */ + reference + back() + { + iterator __tmp = end(); + --__tmp; + return *__tmp; } - else { - _ForwardIterator __mid = __first; - advance(__mid, difference_type(__n) - __elemsbefore); - __uninitialized_copy_copy(_M_start, __pos, __first, __mid, - __new_start); - _M_start = __new_start; - copy(__mid, __last, __old_start); + + /** + * Returns a read-only (constant) reference to the data at the last + * element of the %deque. + */ + const_reference + back() const + { + const_iterator __tmp = end(); + --__tmp; + return *__tmp; } - } - __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node)); - } - else { - iterator __new_finish = _M_reserve_elements_at_back(__n); - iterator __old_finish = _M_finish; - const difference_type __elemsafter = - difference_type(__length) - __elemsbefore; - __pos = _M_finish - __elemsafter; - __STL_TRY { - if (__elemsafter > difference_type(__n)) { - iterator __finish_n = _M_finish - difference_type(__n); - uninitialized_copy(__finish_n, _M_finish, _M_finish); - _M_finish = __new_finish; - copy_backward(__pos, __finish_n, __old_finish); - copy(__first, __last, __pos); + + // [23.2.1.2] modifiers + /** + * @brief Add data to the front of the %deque. + * @param x Data to be added. + * + * This is a typical stack operation. The function creates an + * element at the front of the %deque and assigns the given + * data to it. Due to the nature of a %deque this operation + * can be done in constant time. + */ + void + push_front(const value_type& __x) + { + if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first) + { + this->_M_impl.construct(this->_M_impl._M_start._M_cur - 1, __x); + --this->_M_impl._M_start._M_cur; + } + else + _M_push_front_aux(__x); } - else { - _ForwardIterator __mid = __first; - advance(__mid, __elemsafter); - __uninitialized_copy_copy(__mid, __last, __pos, _M_finish, _M_finish); - _M_finish = __new_finish; - copy(__first, __mid, __pos); + + /** + * @brief Add data to the end of the %deque. + * @param x Data to be added. + * + * This is a typical stack operation. The function creates an + * element at the end of the %deque and assigns the given data + * to it. Due to the nature of a %deque this operation can be + * done in constant time. + */ + void + push_back(const value_type& __x) + { + if (this->_M_impl._M_finish._M_cur + != this->_M_impl._M_finish._M_last - 1) + { + this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __x); + ++this->_M_impl._M_finish._M_cur; + } + else + _M_push_back_aux(__x); } - } - __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1, - __new_finish._M_node + 1)); - } -} - -template -void deque<_Tp,_Alloc>::_M_new_elements_at_front(size_type __new_elems) -{ - size_type __new_nodes - = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size(); - _M_reserve_map_at_front(__new_nodes); - size_type __i; - __STL_TRY { - for (__i = 1; __i <= __new_nodes; ++__i) - *(_M_start._M_node - __i) = _M_allocate_node(); - } -# ifdef __STL_USE_EXCEPTIONS - catch(...) { - for (size_type __j = 1; __j < __i; ++__j) - _M_deallocate_node(*(_M_start._M_node - __j)); - throw; - } -# endif /* __STL_USE_EXCEPTIONS */ -} - -template -void deque<_Tp,_Alloc>::_M_new_elements_at_back(size_type __new_elems) -{ - size_type __new_nodes - = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size(); - _M_reserve_map_at_back(__new_nodes); - size_type __i; - __STL_TRY { - for (__i = 1; __i <= __new_nodes; ++__i) - *(_M_finish._M_node + __i) = _M_allocate_node(); - } -# ifdef __STL_USE_EXCEPTIONS - catch(...) { - for (size_type __j = 1; __j < __i; ++__j) - _M_deallocate_node(*(_M_finish._M_node + __j)); - throw; - } -# endif /* __STL_USE_EXCEPTIONS */ -} - -template -void deque<_Tp,_Alloc>::_M_reallocate_map(size_type __nodes_to_add, - bool __add_at_front) -{ - size_type __old_num_nodes = _M_finish._M_node - _M_start._M_node + 1; - size_type __new_num_nodes = __old_num_nodes + __nodes_to_add; - - _Map_pointer __new_nstart; - if (_M_map_size > 2 * __new_num_nodes) { - __new_nstart = _M_map + (_M_map_size - __new_num_nodes) / 2 - + (__add_at_front ? __nodes_to_add : 0); - if (__new_nstart < _M_start._M_node) - copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart); - else - copy_backward(_M_start._M_node, _M_finish._M_node + 1, - __new_nstart + __old_num_nodes); - } - else { - size_type __new_map_size = - _M_map_size + max(_M_map_size, __nodes_to_add) + 2; - - _Map_pointer __new_map = _M_allocate_map(__new_map_size); - __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2 - + (__add_at_front ? __nodes_to_add : 0); - copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart); - _M_deallocate_map(_M_map, _M_map_size); - - _M_map = __new_map; - _M_map_size = __new_map_size; - } - - _M_start._M_set_node(__new_nstart); - _M_finish._M_set_node(__new_nstart + __old_num_nodes - 1); -} - - -// Nonmember functions. - -template -inline bool operator==(const deque<_Tp, _Alloc>& __x, - const deque<_Tp, _Alloc>& __y) { - return __x.size() == __y.size() && - equal(__x.begin(), __x.end(), __y.begin()); -} - -template -inline bool operator<(const deque<_Tp, _Alloc>& __x, - const deque<_Tp, _Alloc>& __y) { - return lexicographical_compare(__x.begin(), __x.end(), - __y.begin(), __y.end()); -} - -template -inline bool operator!=(const deque<_Tp, _Alloc>& __x, - const deque<_Tp, _Alloc>& __y) { - return !(__x == __y); -} - -template -inline bool operator>(const deque<_Tp, _Alloc>& __x, - const deque<_Tp, _Alloc>& __y) { - return __y < __x; -} - -template -inline bool operator<=(const deque<_Tp, _Alloc>& __x, - const deque<_Tp, _Alloc>& __y) { - return !(__y < __x); -} -template -inline bool operator>=(const deque<_Tp, _Alloc>& __x, - const deque<_Tp, _Alloc>& __y) { - return !(__x < __y); -} - -template -inline void swap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>& __y) { - __x.swap(__y); -} - -} // namespace std - -#endif /* __SGI_STL_INTERNAL_DEQUE_H */ - -// Local Variables: -// mode:C++ -// End: + + /** + * @brief Removes first element. + * + * This is a typical stack operation. It shrinks the %deque by one. + * + * Note that no data is returned, and if the first element's data is + * needed, it should be retrieved before pop_front() is called. + */ + void + pop_front() + { + if (this->_M_impl._M_start._M_cur + != this->_M_impl._M_start._M_last - 1) + { + this->_M_impl.destroy(this->_M_impl._M_start._M_cur); + ++this->_M_impl._M_start._M_cur; + } + else + _M_pop_front_aux(); + } + + /** + * @brief Removes last element. + * + * This is a typical stack operation. It shrinks the %deque by one. + * + * Note that no data is returned, and if the last element's data is + * needed, it should be retrieved before pop_back() is called. + */ + void + pop_back() + { + if (this->_M_impl._M_finish._M_cur + != this->_M_impl._M_finish._M_first) + { + --this->_M_impl._M_finish._M_cur; + this->_M_impl.destroy(this->_M_impl._M_finish._M_cur); + } + else + _M_pop_back_aux(); + } + + /** + * @brief Inserts given value into %deque before specified iterator. + * @param position An iterator into the %deque. + * @param x Data to be inserted. + * @return An iterator that points to the inserted data. + * + * This function will insert a copy of the given value before the + * specified location. + */ + iterator + insert(iterator __position, const value_type& __x); + + /** + * @brief Inserts a number of copies of given data into the %deque. + * @param position An iterator into the %deque. + * @param n Number of elements to be inserted. + * @param x Data to be inserted. + * + * This function will insert a specified number of copies of the given + * data before the location specified by @a position. + */ + void + insert(iterator __position, size_type __n, const value_type& __x) + { _M_fill_insert(__position, __n, __x); } + + /** + * @brief Inserts a range into the %deque. + * @param position An iterator into the %deque. + * @param first An input iterator. + * @param last An input iterator. + * + * This function will insert copies of the data in the range + * [first,last) into the %deque before the location specified + * by @a pos. This is known as "range insert." + */ + template + void + insert(iterator __position, _InputIterator __first, + _InputIterator __last) + { + // Check whether it's an integral type. If so, it's not an iterator. + typedef typename std::__is_integer<_InputIterator>::__type _Integral; + _M_insert_dispatch(__position, __first, __last, _Integral()); + } + + /** + * @brief Remove element at given position. + * @param position Iterator pointing to element to be erased. + * @return An iterator pointing to the next element (or end()). + * + * This function will erase the element at the given position and thus + * shorten the %deque by one. + * + * The user is cautioned that + * this function only erases the element, and that if the element is + * itself a pointer, the pointed-to memory is not touched in any way. + * Managing the pointer is the user's responsibilty. + */ + iterator + erase(iterator __position); + + /** + * @brief Remove a range of elements. + * @param first Iterator pointing to the first element to be erased. + * @param last Iterator pointing to one past the last element to be + * erased. + * @return An iterator pointing to the element pointed to by @a last + * prior to erasing (or end()). + * + * This function will erase the elements in the range [first,last) and + * shorten the %deque accordingly. + * + * The user is cautioned that + * this function only erases the elements, and that if the elements + * themselves are pointers, the pointed-to memory is not touched in any + * way. Managing the pointer is the user's responsibilty. + */ + iterator + erase(iterator __first, iterator __last); + + /** + * @brief Swaps data with another %deque. + * @param x A %deque of the same element and allocator types. + * + * This exchanges the elements between two deques in constant time. + * (Four pointers, so it should be quite fast.) + * Note that the global std::swap() function is specialized such that + * std::swap(d1,d2) will feed to this function. + */ + void + swap(deque& __x) + { + std::swap(this->_M_impl._M_start, __x._M_impl._M_start); + std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish); + std::swap(this->_M_impl._M_map, __x._M_impl._M_map); + std::swap(this->_M_impl._M_map_size, __x._M_impl._M_map_size); + + // _GLIBCXX_RESOLVE_LIB_DEFECTS + // 431. Swapping containers with unequal allocators. + std::__alloc_swap<_Tp_alloc_type>::_S_do_it(_M_get_Tp_allocator(), + __x._M_get_Tp_allocator()); + } + + /** + * Erases all the elements. Note that this function only erases the + * elements, and that if the elements themselves are pointers, the + * pointed-to memory is not touched in any way. Managing the pointer is + * the user's responsibilty. + */ + void + clear() + { _M_erase_at_end(begin()); } + + protected: + // Internal constructor functions follow. + + // called by the range constructor to implement [23.1.1]/9 + template + void + _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) + { + _M_initialize_map(__n); + _M_fill_initialize(__x); + } + + // called by the range constructor to implement [23.1.1]/9 + template + void + _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, + __false_type) + { + typedef typename std::iterator_traits<_InputIterator>:: + iterator_category _IterCategory; + _M_range_initialize(__first, __last, _IterCategory()); + } + + // called by the second initialize_dispatch above + //@{ + /** + * @if maint + * @brief Fills the deque with whatever is in [first,last). + * @param first An input iterator. + * @param last An input iterator. + * @return Nothing. + * + * If the iterators are actually forward iterators (or better), then the + * memory layout can be done all at once. Else we move forward using + * push_back on each value from the iterator. + * @endif + */ + template + void + _M_range_initialize(_InputIterator __first, _InputIterator __last, + std::input_iterator_tag); + + // called by the second initialize_dispatch above + template + void + _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last, + std::forward_iterator_tag); + //@} + + /** + * @if maint + * @brief Fills the %deque with copies of value. + * @param value Initial value. + * @return Nothing. + * @pre _M_start and _M_finish have already been initialized, + * but none of the %deque's elements have yet been constructed. + * + * This function is called only when the user provides an explicit size + * (with or without an explicit exemplar value). + * @endif + */ + void + _M_fill_initialize(const value_type& __value); + + // Internal assign functions follow. The *_aux functions do the actual + // assignment work for the range versions. + + // called by the range assign to implement [23.1.1]/9 + template + void + _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) + { + _M_fill_assign(static_cast(__n), + static_cast(__val)); + } + + // called by the range assign to implement [23.1.1]/9 + template + void + _M_assign_dispatch(_InputIterator __first, _InputIterator __last, + __false_type) + { + typedef typename std::iterator_traits<_InputIterator>:: + iterator_category _IterCategory; + _M_assign_aux(__first, __last, _IterCategory()); + } + + // called by the second assign_dispatch above + template + void + _M_assign_aux(_InputIterator __first, _InputIterator __last, + std::input_iterator_tag); + + // called by the second assign_dispatch above + template + void + _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, + std::forward_iterator_tag) + { + const size_type __len = std::distance(__first, __last); + if (__len > size()) + { + _ForwardIterator __mid = __first; + std::advance(__mid, size()); + std::copy(__first, __mid, begin()); + insert(end(), __mid, __last); + } + else + _M_erase_at_end(std::copy(__first, __last, begin())); + } + + // Called by assign(n,t), and the range assign when it turns out + // to be the same thing. + void + _M_fill_assign(size_type __n, const value_type& __val) + { + if (__n > size()) + { + std::fill(begin(), end(), __val); + insert(end(), __n - size(), __val); + } + else + { + _M_erase_at_end(begin() + difference_type(__n)); + std::fill(begin(), end(), __val); + } + } + + //@{ + /** + * @if maint + * @brief Helper functions for push_* and pop_*. + * @endif + */ + void _M_push_back_aux(const value_type&); + + void _M_push_front_aux(const value_type&); + + void _M_pop_back_aux(); + + void _M_pop_front_aux(); + //@} + + // Internal insert functions follow. The *_aux functions do the actual + // insertion work when all shortcuts fail. + + // called by the range insert to implement [23.1.1]/9 + template + void + _M_insert_dispatch(iterator __pos, + _Integer __n, _Integer __x, __true_type) + { + _M_fill_insert(__pos, static_cast(__n), + static_cast(__x)); + } + + // called by the range insert to implement [23.1.1]/9 + template + void + _M_insert_dispatch(iterator __pos, + _InputIterator __first, _InputIterator __last, + __false_type) + { + typedef typename std::iterator_traits<_InputIterator>:: + iterator_category _IterCategory; + _M_range_insert_aux(__pos, __first, __last, _IterCategory()); + } + + // called by the second insert_dispatch above + template + void + _M_range_insert_aux(iterator __pos, _InputIterator __first, + _InputIterator __last, std::input_iterator_tag); + + // called by the second insert_dispatch above + template + void + _M_range_insert_aux(iterator __pos, _ForwardIterator __first, + _ForwardIterator __last, std::forward_iterator_tag); + + // Called by insert(p,n,x), and the range insert when it turns out to be + // the same thing. Can use fill functions in optimal situations, + // otherwise passes off to insert_aux(p,n,x). + void + _M_fill_insert(iterator __pos, size_type __n, const value_type& __x); + + // called by insert(p,x) + iterator + _M_insert_aux(iterator __pos, const value_type& __x); + + // called by insert(p,n,x) via fill_insert + void + _M_insert_aux(iterator __pos, size_type __n, const value_type& __x); + + // called by range_insert_aux for forward iterators + template + void + _M_insert_aux(iterator __pos, + _ForwardIterator __first, _ForwardIterator __last, + size_type __n); + + + // Internal erase functions follow. + + void + _M_destroy_data_aux(iterator __first, iterator __last); + + void + _M_destroy_data_dispatch(iterator, iterator, __true_type) { } + + void + _M_destroy_data_dispatch(iterator __first, iterator __last, __false_type) + { _M_destroy_data_aux(__first, __last); } + + // Called by ~deque(). + // NB: Doesn't deallocate the nodes. + template + void + _M_destroy_data(iterator __first, iterator __last, const _Alloc1&) + { _M_destroy_data_aux(__first, __last); } + + void + _M_destroy_data(iterator __first, iterator __last, + const std::allocator<_Tp>&) + { + typedef typename std::__is_scalar::__type + _Has_trivial_destructor; + _M_destroy_data_dispatch(__first, __last, _Has_trivial_destructor()); + } + + // Called by erase(q1, q2). + void + _M_erase_at_begin(iterator __pos) + { + _M_destroy_data(begin(), __pos, _M_get_Tp_allocator()); + _M_destroy_nodes(this->_M_impl._M_start._M_node, __pos._M_node); + this->_M_impl._M_start = __pos; + } + + // Called by erase(q1, q2), resize(), clear(), _M_assign_aux, + // _M_fill_assign, operator=. + void + _M_erase_at_end(iterator __pos) + { + _M_destroy_data(__pos, end(), _M_get_Tp_allocator()); + _M_destroy_nodes(__pos._M_node + 1, + this->_M_impl._M_finish._M_node + 1); + this->_M_impl._M_finish = __pos; + } + + //@{ + /** + * @if maint + * @brief Memory-handling helpers for the previous internal insert + * functions. + * @endif + */ + iterator + _M_reserve_elements_at_front(size_type __n) + { + const size_type __vacancies = this->_M_impl._M_start._M_cur + - this->_M_impl._M_start._M_first; + if (__n > __vacancies) + _M_new_elements_at_front(__n - __vacancies); + return this->_M_impl._M_start - difference_type(__n); + } + + iterator + _M_reserve_elements_at_back(size_type __n) + { + const size_type __vacancies = (this->_M_impl._M_finish._M_last + - this->_M_impl._M_finish._M_cur) - 1; + if (__n > __vacancies) + _M_new_elements_at_back(__n - __vacancies); + return this->_M_impl._M_finish + difference_type(__n); + } + + void + _M_new_elements_at_front(size_type __new_elements); + + void + _M_new_elements_at_back(size_type __new_elements); + //@} + + + //@{ + /** + * @if maint + * @brief Memory-handling helpers for the major %map. + * + * Makes sure the _M_map has space for new nodes. Does not + * actually add the nodes. Can invalidate _M_map pointers. + * (And consequently, %deque iterators.) + * @endif + */ + void + _M_reserve_map_at_back(size_type __nodes_to_add = 1) + { + if (__nodes_to_add + 1 > this->_M_impl._M_map_size + - (this->_M_impl._M_finish._M_node - this->_M_impl._M_map)) + _M_reallocate_map(__nodes_to_add, false); + } + + void + _M_reserve_map_at_front(size_type __nodes_to_add = 1) + { + if (__nodes_to_add > size_type(this->_M_impl._M_start._M_node + - this->_M_impl._M_map)) + _M_reallocate_map(__nodes_to_add, true); + } + + void + _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front); + //@} + }; + + + /** + * @brief Deque equality comparison. + * @param x A %deque. + * @param y A %deque of the same type as @a x. + * @return True iff the size and elements of the deques are equal. + * + * This is an equivalence relation. It is linear in the size of the + * deques. Deques are considered equivalent if their sizes are equal, + * and if corresponding elements compare equal. + */ + template + inline bool + operator==(const deque<_Tp, _Alloc>& __x, + const deque<_Tp, _Alloc>& __y) + { return __x.size() == __y.size() + && std::equal(__x.begin(), __x.end(), __y.begin()); } + + /** + * @brief Deque ordering relation. + * @param x A %deque. + * @param y A %deque of the same type as @a x. + * @return True iff @a x is lexicographically less than @a y. + * + * This is a total ordering relation. It is linear in the size of the + * deques. The elements must be comparable with @c <. + * + * See std::lexicographical_compare() for how the determination is made. + */ + template + inline bool + operator<(const deque<_Tp, _Alloc>& __x, + const deque<_Tp, _Alloc>& __y) + { return lexicographical_compare(__x.begin(), __x.end(), + __y.begin(), __y.end()); } + + /// Based on operator== + template + inline bool + operator!=(const deque<_Tp, _Alloc>& __x, + const deque<_Tp, _Alloc>& __y) + { return !(__x == __y); } + + /// Based on operator< + template + inline bool + operator>(const deque<_Tp, _Alloc>& __x, + const deque<_Tp, _Alloc>& __y) + { return __y < __x; } + + /// Based on operator< + template + inline bool + operator<=(const deque<_Tp, _Alloc>& __x, + const deque<_Tp, _Alloc>& __y) + { return !(__y < __x); } + + /// Based on operator< + template + inline bool + operator>=(const deque<_Tp, _Alloc>& __x, + const deque<_Tp, _Alloc>& __y) + { return !(__x < __y); } + + /// See std::deque::swap(). + template + inline void + swap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>& __y) + { __x.swap(__y); } + +_GLIBCXX_END_NESTED_NAMESPACE + +#endif /* _DEQUE_H */