diff options
Diffstat (limited to 'contrib/libstdc++/include/bits/stl_deque.h')
| -rw-r--r-- | contrib/libstdc++/include/bits/stl_deque.h | 531 |
1 files changed, 319 insertions, 212 deletions
diff --git a/contrib/libstdc++/include/bits/stl_deque.h b/contrib/libstdc++/include/bits/stl_deque.h index 54dadf2..9da0bb7 100644 --- a/contrib/libstdc++/include/bits/stl_deque.h +++ b/contrib/libstdc++/include/bits/stl_deque.h @@ -1,6 +1,7 @@ // Deque implementation -*- C++ -*- -// Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc. +// 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 @@ -15,7 +16,7 @@ // 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307, +// 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 @@ -65,8 +66,8 @@ #include <bits/stl_iterator_base_types.h> #include <bits/stl_iterator_base_funcs.h> -namespace _GLIBCXX_STD -{ +_GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD) + /** * @if maint * @brief This function controls the size of memory nodes. @@ -87,10 +88,11 @@ namespace _GLIBCXX_STD /** * @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. + * 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. @@ -105,14 +107,14 @@ namespace _GLIBCXX_STD 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; + 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; @@ -219,9 +221,9 @@ namespace _GLIBCXX_STD { 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. + * 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 @@ -320,6 +322,17 @@ namespace _GLIBCXX_STD // According to the resolution of DR179 not only the various comparison // operators but also operator- must accept mixed iterator/const_iterator // parameters. + template<typename _Tp, typename _Ref, typename _Ptr> + 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); + } + template<typename _Tp, typename _RefL, typename _PtrL, typename _RefR, typename _PtrR> inline typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type @@ -337,6 +350,11 @@ namespace _GLIBCXX_STD operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Ref, _Ptr>& __x) { return __x + __n; } + template<typename _Tp> + 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 @@ -357,17 +375,17 @@ namespace _GLIBCXX_STD allocator_type get_allocator() const - { return *static_cast<const _Alloc*>(&this->_M_impl); } + { return allocator_type(_M_get_Tp_allocator()); } - typedef _Deque_iterator<_Tp,_Tp&,_Tp*> iterator; - typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*> const_iterator; + 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_impl(__a) { _M_initialize_map(__num_elements); } _Deque_base(const allocator_type& __a) - : _M_impl(__a) + : _M_impl(__a) { } ~_Deque_base(); @@ -376,29 +394,47 @@ namespace _GLIBCXX_STD //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 _Alloc { + : public _Tp_alloc_type + { _Tp** _M_map; size_t _M_map_size; iterator _M_start; iterator _M_finish; - _Deque_impl(const _Alloc& __a) - : _Alloc(__a), _M_map(0), _M_map_size(0), _M_start(), _M_finish() + _Deque_impl(const _Tp_alloc_type& __a) + : _Tp_alloc_type(__a), _M_map(0), _M_map_size(0), + _M_start(), _M_finish() { } }; - typedef typename _Alloc::template rebind<_Tp*>::other _Map_alloc_type; - _Map_alloc_type _M_get_map_allocator() const - { return _Map_alloc_type(this->get_allocator()); } + _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<const _Tp_alloc_type*>(&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._Alloc::allocate(__deque_buf_size(sizeof(_Tp))); } + { + return _M_impl._Tp_alloc_type::allocate(__deque_buf_size(sizeof(_Tp))); + } void _M_deallocate_node(_Tp* __p) - { _M_impl._Alloc::deallocate(__p, __deque_buf_size(sizeof(_Tp))); } + { + _M_impl._Tp_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp))); + } _Tp** _M_allocate_map(size_t __n) @@ -418,14 +454,16 @@ namespace _GLIBCXX_STD }; template<typename _Tp, typename _Alloc> - _Deque_base<_Tp,_Alloc>::~_Deque_base() - { - if (this->_M_impl._M_map) + _Deque_base<_Tp, _Alloc>:: + ~_Deque_base() { - _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); + 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); + } } - } /** * @if maint @@ -439,12 +477,14 @@ namespace _GLIBCXX_STD */ template<typename _Tp, typename _Alloc> void - _Deque_base<_Tp,_Alloc>::_M_initialize_map(size_t __num_elements) + _Deque_base<_Tp, _Alloc>:: + _M_initialize_map(size_t __num_elements) { - size_t __num_nodes = __num_elements / __deque_buf_size(sizeof(_Tp)) + 1; + 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, - __num_nodes + 2); + 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 @@ -452,7 +492,8 @@ namespace _GLIBCXX_STD // 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** __nstart = (this->_M_impl._M_map + + (this->_M_impl._M_map_size - __num_nodes) / 2); _Tp** __nfinish = __nstart + __num_nodes; try @@ -468,13 +509,15 @@ namespace _GLIBCXX_STD 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)); + this->_M_impl._M_finish._M_cur = (this->_M_impl._M_finish._M_first + + __num_elements + % __deque_buf_size(sizeof(_Tp))); } template<typename _Tp, typename _Alloc> void - _Deque_base<_Tp,_Alloc>::_M_create_nodes(_Tp** __nstart, _Tp** __nfinish) + _Deque_base<_Tp, _Alloc>:: + _M_create_nodes(_Tp** __nstart, _Tp** __nfinish) { _Tp** __cur; try @@ -491,7 +534,8 @@ namespace _GLIBCXX_STD template<typename _Tp, typename _Alloc> void - _Deque_base<_Tp,_Alloc>::_M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish) + _Deque_base<_Tp, _Alloc>:: + _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish) { for (_Tp** __n = __nstart; __n < __nfinish; ++__n) _M_deallocate_node(*__n); @@ -521,28 +565,27 @@ namespace _GLIBCXX_STD * - 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. + * 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".) * - * **** As I write this, the nodes are /not/ allocated using the high-speed - * memory pool. There are 20 hours left in the year; perhaps I can fix - * this before 2002. + * 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". + * 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: @@ -554,16 +597,17 @@ namespace _GLIBCXX_STD * - 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 <N elements (where N is - * the node buffer size) must have one node, a deque with N through (2N-1) - * elements must have two nodes, etc. - * - 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. + * - Start and Finish are always nonsingular iterators. NOTE: this + * means that an empty deque must have one node, a deque with <N + * elements (where N is the node buffer size) must have one node, a + * deque with N through (2N-1) elements must have two nodes, etc. + * - 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). @@ -581,27 +625,30 @@ namespace _GLIBCXX_STD * and we can use other standard algorithms as well. * @endif */ - template<typename _Tp, typename _Alloc = allocator<_Tp> > + template<typename _Tp, typename _Alloc = std::allocator<_Tp> > 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 _Alloc::pointer pointer; - typedef typename _Alloc::const_pointer const_pointer; - typedef typename _Alloc::reference reference; - typedef typename _Alloc::const_reference const_reference; - typedef typename _Base::iterator iterator; - typedef typename _Base::const_iterator const_iterator; - typedef std::reverse_iterator<const_iterator> const_reverse_iterator; - typedef std::reverse_iterator<iterator> reverse_iterator; + 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_iterator> const_reverse_iterator; + typedef std::reverse_iterator<iterator> reverse_iterator; typedef size_t size_type; typedef ptrdiff_t difference_type; - typedef typename _Base::allocator_type allocator_type; + typedef _Alloc allocator_type; protected: typedef pointer* _Map_pointer; @@ -617,6 +664,7 @@ namespace _GLIBCXX_STD 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. @@ -642,24 +690,13 @@ namespace _GLIBCXX_STD * * This constructor fills the %deque with @a n copies of @a value. */ - deque(size_type __n, const value_type& __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 Create a %deque with default elements. - * @param n The number of elements to initially create. - * - * This constructor fills the %deque with @a n copies of a - * default-constructed element. - */ - explicit - deque(size_type __n) - : _Base(allocator_type(), __n) - { _M_fill_initialize(value_type()); } - - /** * @brief %Deque copy constructor. * @param x A %deque of identical element and allocator types. * @@ -667,8 +704,10 @@ namespace _GLIBCXX_STD * by @a x. */ deque(const deque& __x) - : _Base(__x.get_allocator(), __x.size()) - { std::uninitialized_copy(__x.begin(), __x.end(), this->_M_impl._M_start); } + : _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. @@ -690,7 +729,7 @@ namespace _GLIBCXX_STD : _Base(__a) { // Check whether it's an integral type. If so, it's not an iterator. - typedef typename _Is_integer<_InputIterator>::_Integral _Integral; + typedef typename std::__is_integer<_InputIterator>::__type _Integral; _M_initialize_dispatch(__first, __last, _Integral()); } @@ -700,7 +739,7 @@ namespace _GLIBCXX_STD * way. Managing the pointer is the user's responsibilty. */ ~deque() - { std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish); } + { _M_destroy_data(begin(), end(), _M_get_Tp_allocator()); } /** * @brief %Deque assignment operator. @@ -717,10 +756,10 @@ namespace _GLIBCXX_STD * @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. + * 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) @@ -742,7 +781,7 @@ namespace _GLIBCXX_STD void assign(_InputIterator __first, _InputIterator __last) { - typedef typename _Is_integer<_InputIterator>::_Integral _Integral; + typedef typename std::__is_integer<_InputIterator>::__type _Integral; _M_assign_dispatch(__first, __last, _Integral()); } @@ -769,50 +808,54 @@ namespace _GLIBCXX_STD { 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. + * 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. + * 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. + * 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. + * 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. + * 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); } + 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. + * 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 @@ -827,43 +870,32 @@ namespace _GLIBCXX_STD /** Returns the size() of the largest possible %deque. */ size_type max_size() const - { return size_type(-1); } + { 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. + * 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, const value_type& __x) + resize(size_type __new_size, value_type __x = value_type()) { const size_type __len = size(); if (__new_size < __len) - erase(this->_M_impl._M_start + __new_size, this->_M_impl._M_finish); + _M_erase_at_end(this->_M_impl._M_start + difference_type(__new_size)); else insert(this->_M_impl._M_finish, __new_size - __len, __x); } /** - * @brief Resizes the %deque to the specified number of elements. - * @param new_size Number of elements the %deque should contain. - * - * 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 default-constructed. - */ - void - resize(size_type new_size) - { resize(new_size, value_type()); } - - /** - * Returns true if the %deque is empty. (Thus begin() would equal end().) + * Returns true if the %deque is empty. (Thus begin() would + * equal end().) */ bool empty() const @@ -871,26 +903,30 @@ namespace _GLIBCXX_STD // 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. + * @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().) + * 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. + * @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().) + * 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 @@ -908,21 +944,26 @@ namespace _GLIBCXX_STD public: /** * @brief Provides access to the data contained in the %deque. - * @param n The index of the element for which data should be accessed. + * @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. + * 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]; } + { + _M_range_check(__n); + return (*this)[__n]; + } /** * @brief Provides access to the data contained in the %deque. - * @param n The index of the element for which data should be accessed. + * @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. * @@ -938,12 +979,12 @@ namespace _GLIBCXX_STD } /** - * Returns a read/write reference to the data at the first element of the - * %deque. + * Returns a read/write reference to the data at the first + * element of the %deque. */ reference front() - { return *this->_M_impl._M_start; } + { return *begin(); } /** * Returns a read-only (constant) reference to the data at the first @@ -951,7 +992,7 @@ namespace _GLIBCXX_STD */ const_reference front() const - { return *this->_M_impl._M_start; } + { return *begin(); } /** * Returns a read/write reference to the data at the last element of the @@ -960,7 +1001,7 @@ namespace _GLIBCXX_STD reference back() { - iterator __tmp = this->_M_impl._M_finish; + iterator __tmp = end(); --__tmp; return *__tmp; } @@ -972,7 +1013,7 @@ namespace _GLIBCXX_STD const_reference back() const { - const_iterator __tmp = this->_M_impl._M_finish; + const_iterator __tmp = end(); --__tmp; return *__tmp; } @@ -982,16 +1023,17 @@ namespace _GLIBCXX_STD * @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. + * 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) { - std::_Construct(this->_M_impl._M_start._M_cur - 1, __x); + this->_M_impl.construct(this->_M_impl._M_start._M_cur - 1, __x); --this->_M_impl._M_start._M_cur; } else @@ -1002,16 +1044,18 @@ namespace _GLIBCXX_STD * @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. + * 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) + if (this->_M_impl._M_finish._M_cur + != this->_M_impl._M_finish._M_last - 1) { - std::_Construct(this->_M_impl._M_finish._M_cur, __x); + this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __x); ++this->_M_impl._M_finish._M_cur; } else @@ -1029,9 +1073,10 @@ namespace _GLIBCXX_STD void pop_front() { - if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_last - 1) + if (this->_M_impl._M_start._M_cur + != this->_M_impl._M_start._M_last - 1) { - std::_Destroy(this->_M_impl._M_start._M_cur); + this->_M_impl.destroy(this->_M_impl._M_start._M_cur); ++this->_M_impl._M_start._M_cur; } else @@ -1049,10 +1094,11 @@ namespace _GLIBCXX_STD void pop_back() { - if (this->_M_impl._M_finish._M_cur != this->_M_impl._M_finish._M_first) + if (this->_M_impl._M_finish._M_cur + != this->_M_impl._M_finish._M_first) { --this->_M_impl._M_finish._M_cur; - std::_Destroy(this->_M_impl._M_finish._M_cur); + this->_M_impl.destroy(this->_M_impl._M_finish._M_cur); } else _M_pop_back_aux(); @@ -1068,7 +1114,7 @@ namespace _GLIBCXX_STD * specified location. */ iterator - insert(iterator position, const value_type& __x); + insert(iterator __position, const value_type& __x); /** * @brief Inserts a number of copies of given data into the %deque. @@ -1089,9 +1135,9 @@ namespace _GLIBCXX_STD * @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." + * 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<typename _InputIterator> void @@ -1099,7 +1145,7 @@ namespace _GLIBCXX_STD _InputIterator __last) { // Check whether it's an integral type. If so, it's not an iterator. - typedef typename _Is_integer<_InputIterator>::_Integral _Integral; + typedef typename std::__is_integer<_InputIterator>::__type _Integral; _M_insert_dispatch(__position, __first, __last, _Integral()); } @@ -1154,6 +1200,11 @@ namespace _GLIBCXX_STD 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()); } /** @@ -1162,7 +1213,9 @@ namespace _GLIBCXX_STD * pointed-to memory is not touched in any way. Managing the pointer is * the user's responsibilty. */ - void clear(); + void + clear() + { _M_erase_at_end(begin()); } protected: // Internal constructor functions follow. @@ -1182,8 +1235,8 @@ namespace _GLIBCXX_STD _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, __false_type) { - typedef typename iterator_traits<_InputIterator>::iterator_category - _IterCategory; + typedef typename std::iterator_traits<_InputIterator>:: + iterator_category _IterCategory; _M_range_initialize(__first, __last, _IterCategory()); } @@ -1204,13 +1257,13 @@ namespace _GLIBCXX_STD template<typename _InputIterator> void _M_range_initialize(_InputIterator __first, _InputIterator __last, - input_iterator_tag); + std::input_iterator_tag); // called by the second initialize_dispatch above template<typename _ForwardIterator> void _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last, - forward_iterator_tag); + std::forward_iterator_tag); //@} /** @@ -1218,8 +1271,8 @@ namespace _GLIBCXX_STD * @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. + * @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). @@ -1246,8 +1299,8 @@ namespace _GLIBCXX_STD _M_assign_dispatch(_InputIterator __first, _InputIterator __last, __false_type) { - typedef typename iterator_traits<_InputIterator>::iterator_category - _IterCategory; + typedef typename std::iterator_traits<_InputIterator>:: + iterator_category _IterCategory; _M_assign_aux(__first, __last, _IterCategory()); } @@ -1255,13 +1308,13 @@ namespace _GLIBCXX_STD template<typename _InputIterator> void _M_assign_aux(_InputIterator __first, _InputIterator __last, - input_iterator_tag); + std::input_iterator_tag); // called by the second assign_dispatch above template<typename _ForwardIterator> void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, - forward_iterator_tag) + std::forward_iterator_tag) { const size_type __len = std::distance(__first, __last); if (__len > size()) @@ -1272,11 +1325,11 @@ namespace _GLIBCXX_STD insert(end(), __mid, __last); } else - erase(std::copy(__first, __last, begin()), end()); + _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. + // 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) { @@ -1287,7 +1340,7 @@ namespace _GLIBCXX_STD } else { - erase(begin() + __n, end()); + _M_erase_at_end(begin() + difference_type(__n)); std::fill(begin(), end(), __val); } } @@ -1299,8 +1352,11 @@ namespace _GLIBCXX_STD * @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(); //@} @@ -1324,8 +1380,8 @@ namespace _GLIBCXX_STD _InputIterator __first, _InputIterator __last, __false_type) { - typedef typename iterator_traits<_InputIterator>::iterator_category - _IterCategory; + typedef typename std::iterator_traits<_InputIterator>:: + iterator_category _IterCategory; _M_range_insert_aux(__pos, __first, __last, _IterCategory()); } @@ -1333,13 +1389,13 @@ namespace _GLIBCXX_STD template<typename _InputIterator> void _M_range_insert_aux(iterator __pos, _InputIterator __first, - _InputIterator __last, input_iterator_tag); + _InputIterator __last, std::input_iterator_tag); // called by the second insert_dispatch above template<typename _ForwardIterator> void _M_range_insert_aux(iterator __pos, _ForwardIterator __first, - _ForwardIterator __last, forward_iterator_tag); + _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, @@ -1362,6 +1418,55 @@ namespace _GLIBCXX_STD _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<typename _Alloc1> + 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<value_type>::__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 @@ -1402,13 +1507,13 @@ namespace _GLIBCXX_STD * @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.) + * 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) + _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)) @@ -1416,9 +1521,10 @@ namespace _GLIBCXX_STD } void - _M_reserve_map_at_front (size_type __nodes_to_add = 1) + _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)) + 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); } @@ -1460,8 +1566,8 @@ namespace _GLIBCXX_STD inline bool operator<(const deque<_Tp, _Alloc>& __x, const deque<_Tp, _Alloc>& __y) - { return lexicographical_compare(__x.begin(), __x.end(), - __y.begin(), __y.end()); } + { return std::lexicographical_compare(__x.begin(), __x.end(), + __y.begin(), __y.end()); } /// Based on operator== template<typename _Tp, typename _Alloc> @@ -1496,6 +1602,7 @@ namespace _GLIBCXX_STD inline void swap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>& __y) { __x.swap(__y); } -} // namespace std + +_GLIBCXX_END_NESTED_NAMESPACE #endif /* _DEQUE_H */ |
