diff options
Diffstat (limited to 'contrib/libstdc++/include/bits/stl_bvector.h')
| -rw-r--r-- | contrib/libstdc++/include/bits/stl_bvector.h | 829 |
1 files changed, 482 insertions, 347 deletions
diff --git a/contrib/libstdc++/include/bits/stl_bvector.h b/contrib/libstdc++/include/bits/stl_bvector.h index afae738..9dc2656 100644 --- a/contrib/libstdc++/include/bits/stl_bvector.h +++ b/contrib/libstdc++/include/bits/stl_bvector.h @@ -1,6 +1,7 @@ // vector<bool> specialization -*- 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 @@ -61,8 +62,8 @@ #ifndef _BVECTOR_H #define _BVECTOR_H 1 -namespace _GLIBCXX_STD -{ +_GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD) + typedef unsigned long _Bit_type; enum { _S_word_bit = int(CHAR_BIT * sizeof(_Bit_type)) }; @@ -76,7 +77,8 @@ namespace _GLIBCXX_STD _Bit_reference() : _M_p(0), _M_mask(0) { } - operator bool() const { return !!(*_M_p & _M_mask); } + operator bool() const + { return !!(*_M_p & _M_mask); } _Bit_reference& operator=(bool __x) @@ -101,10 +103,12 @@ namespace _GLIBCXX_STD { return !bool(*this) && bool(__x); } void - flip() { *_M_p ^= _M_mask; } + flip() + { *_M_p ^= _M_mask; } }; - struct _Bit_iterator_base : public iterator<random_access_iterator_tag, bool> + struct _Bit_iterator_base + : public std::iterator<std::random_access_iterator_tag, bool> { _Bit_type * _M_p; unsigned int _M_offset; @@ -115,7 +119,7 @@ namespace _GLIBCXX_STD void _M_bump_up() { - if (_M_offset++ == _S_word_bit - 1) + if (_M_offset++ == int(_S_word_bit) - 1) { _M_offset = 0; ++_M_p; @@ -127,7 +131,7 @@ namespace _GLIBCXX_STD { if (_M_offset-- == 0) { - _M_offset = _S_word_bit - 1; + _M_offset = int(_S_word_bit) - 1; --_M_p; } } @@ -136,15 +140,14 @@ namespace _GLIBCXX_STD _M_incr(ptrdiff_t __i) { difference_type __n = __i + _M_offset; - _M_p += __n / _S_word_bit; - __n = __n % _S_word_bit; + _M_p += __n / int(_S_word_bit); + __n = __n % int(_S_word_bit); if (__n < 0) { - _M_offset = static_cast<unsigned int>(__n + _S_word_bit); + __n += int(_S_word_bit); --_M_p; } - else - _M_offset = static_cast<unsigned int>(__n); + _M_offset = static_cast<unsigned int>(__n); } bool @@ -178,7 +181,8 @@ namespace _GLIBCXX_STD inline ptrdiff_t operator-(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) { - return _S_word_bit * (__x._M_p - __y._M_p) + __x._M_offset - __y._M_offset; + return (int(_S_word_bit) * (__x._M_p - __y._M_p) + + __x._M_offset - __y._M_offset); } struct _Bit_iterator : public _Bit_iterator_base @@ -188,11 +192,13 @@ namespace _GLIBCXX_STD typedef _Bit_iterator iterator; _Bit_iterator() : _Bit_iterator_base(0, 0) { } + _Bit_iterator(_Bit_type * __x, unsigned int __y) : _Bit_iterator_base(__x, __y) { } reference - operator*() const { return reference(_M_p, 1UL << _M_offset); } + operator*() const + { return reference(_M_p, 1UL << _M_offset); } iterator& operator++() @@ -253,13 +259,13 @@ namespace _GLIBCXX_STD } reference - operator[](difference_type __i) + operator[](difference_type __i) const { return *(*this + __i); } }; inline _Bit_iterator - operator+(ptrdiff_t __n, const _Bit_iterator& __x) { return __x + __n; } - + operator+(ptrdiff_t __n, const _Bit_iterator& __x) + { return __x + __n; } struct _Bit_const_iterator : public _Bit_iterator_base { @@ -269,8 +275,10 @@ namespace _GLIBCXX_STD typedef _Bit_const_iterator const_iterator; _Bit_const_iterator() : _Bit_iterator_base(0, 0) { } + _Bit_const_iterator(_Bit_type * __x, unsigned int __y) : _Bit_iterator_base(__x, __y) { } + _Bit_const_iterator(const _Bit_iterator& __x) : _Bit_iterator_base(__x._M_p, __x._M_offset) { } @@ -323,7 +331,8 @@ namespace _GLIBCXX_STD } const_iterator - operator+(difference_type __i) const { + operator+(difference_type __i) const + { const_iterator __tmp = *this; return __tmp += __i; } @@ -336,7 +345,7 @@ namespace _GLIBCXX_STD } const_reference - operator[](difference_type __i) + operator[](difference_type __i) const { return *(*this + __i); } }; @@ -344,13 +353,34 @@ namespace _GLIBCXX_STD operator+(ptrdiff_t __n, const _Bit_const_iterator& __x) { return __x + __n; } + inline void + __fill_bvector(_Bit_iterator __first, _Bit_iterator __last, bool __x) + { + for (; __first != __last; ++__first) + *__first = __x; + } + + inline void + fill(_Bit_iterator __first, _Bit_iterator __last, const bool& __x) + { + if (__first._M_p != __last._M_p) + { + std::fill(__first._M_p + 1, __last._M_p, __x ? ~0 : 0); + __fill_bvector(__first, _Bit_iterator(__first._M_p + 1, 0), __x); + __fill_bvector(_Bit_iterator(__last._M_p, 0), __last, __x); + } + else + __fill_bvector(__first, __last, __x); + } + template<class _Alloc> - class _Bvector_base + struct _Bvector_base { typedef typename _Alloc::template rebind<_Bit_type>::other _Bit_alloc_type; - struct _Bvector_impl : public _Bit_alloc_type + struct _Bvector_impl + : public _Bit_alloc_type { _Bit_iterator _M_start; _Bit_iterator _M_finish; @@ -363,36 +393,47 @@ namespace _GLIBCXX_STD public: typedef _Alloc allocator_type; + _Bit_alloc_type& + _M_get_Bit_allocator() + { return *static_cast<_Bit_alloc_type*>(&this->_M_impl); } + + const _Bit_alloc_type& + _M_get_Bit_allocator() const + { return *static_cast<const _Bit_alloc_type*>(&this->_M_impl); } + allocator_type get_allocator() const - { return *static_cast<const _Bit_alloc_type*>(&this->_M_impl); } + { return allocator_type(_M_get_Bit_allocator()); } _Bvector_base(const allocator_type& __a) : _M_impl(__a) { } - ~_Bvector_base() { this->_M_deallocate(); } + ~_Bvector_base() + { this->_M_deallocate(); } protected: _Bvector_impl _M_impl; _Bit_type* _M_allocate(size_t __n) - { return _M_impl.allocate((__n + _S_word_bit - 1) / _S_word_bit); } + { return _M_impl.allocate((__n + int(_S_word_bit) - 1) + / int(_S_word_bit)); } void _M_deallocate() { if (_M_impl._M_start._M_p) _M_impl.deallocate(_M_impl._M_start._M_p, - _M_impl._M_end_of_storage - _M_impl._M_start._M_p); + _M_impl._M_end_of_storage - _M_impl._M_start._M_p); } }; -} // namespace std + +_GLIBCXX_END_NESTED_NAMESPACE // Declare a partial specialization of vector<T, Alloc>. #include <bits/stl_vector.h> -namespace _GLIBCXX_STD -{ +_GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD) + /** * @brief A specialization of vector for booleans which offers fixed time * access to individual elements in any order. @@ -412,345 +453,223 @@ namespace _GLIBCXX_STD * also provided as with C-style arrays. */ template<typename _Alloc> - class vector<bool, _Alloc> : public _Bvector_base<_Alloc> + class vector<bool, _Alloc> : protected _Bvector_base<_Alloc> { - public: - typedef bool value_type; - typedef size_t size_type; - typedef ptrdiff_t difference_type; - typedef _Bit_reference reference; - typedef bool const_reference; - typedef _Bit_reference* pointer; - typedef const bool* const_pointer; + typedef _Bvector_base<_Alloc> _Base; - typedef _Bit_iterator iterator; - typedef _Bit_const_iterator const_iterator; - - typedef std::reverse_iterator<const_iterator> const_reverse_iterator; - typedef std::reverse_iterator<iterator> reverse_iterator; - - typedef typename _Bvector_base<_Alloc>::allocator_type allocator_type; + public: + typedef bool value_type; + typedef size_t size_type; + typedef ptrdiff_t difference_type; + typedef _Bit_reference reference; + typedef bool const_reference; + typedef _Bit_reference* pointer; + typedef const bool* const_pointer; + typedef _Bit_iterator iterator; + typedef _Bit_const_iterator const_iterator; + typedef std::reverse_iterator<const_iterator> const_reverse_iterator; + typedef std::reverse_iterator<iterator> reverse_iterator; + typedef _Alloc allocator_type; allocator_type get_allocator() const - { return _Bvector_base<_Alloc>::get_allocator(); } + { return _Base::get_allocator(); } protected: - using _Bvector_base<_Alloc>::_M_allocate; - using _Bvector_base<_Alloc>::_M_deallocate; + using _Base::_M_allocate; + using _Base::_M_deallocate; + using _Base::_M_get_Bit_allocator; - protected: - void _M_initialize(size_type __n) + public: + explicit + vector(const allocator_type& __a = allocator_type()) + : _Base(__a) { } + + explicit + vector(size_type __n, const bool& __value = bool(), + const allocator_type& __a = allocator_type()) + : _Base(__a) { - _Bit_type* __q = this->_M_allocate(__n); - this->_M_impl._M_end_of_storage = __q - + (__n + _S_word_bit - 1) / _S_word_bit; - this->_M_impl._M_start = iterator(__q, 0); - this->_M_impl._M_finish = this->_M_impl._M_start + difference_type(__n); + _M_initialize(__n); + std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_of_storage, + __value ? ~0 : 0); } - void _M_insert_aux(iterator __position, bool __x) + vector(const vector& __x) + : _Base(__x._M_get_Bit_allocator()) { - if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage) - { - std::copy_backward(__position, this->_M_impl._M_finish, - this->_M_impl._M_finish + 1); - *__position = __x; - ++this->_M_impl._M_finish; - } - else - { - const size_type __len = size() ? 2 * size() - : static_cast<size_type>(_S_word_bit); - _Bit_type * __q = this->_M_allocate(__len); - iterator __i = std::copy(begin(), __position, iterator(__q, 0)); - *__i++ = __x; - this->_M_impl._M_finish = std::copy(__position, end(), __i); - this->_M_deallocate(); - this->_M_impl._M_end_of_storage = __q + (__len + _S_word_bit - 1) - / _S_word_bit; - this->_M_impl._M_start = iterator(__q, 0); - } + _M_initialize(__x.size()); + _M_copy_aligned(__x.begin(), __x.end(), this->_M_impl._M_start); } template<class _InputIterator> - void _M_initialize_range(_InputIterator __first, _InputIterator __last, - input_iterator_tag) - { - this->_M_impl._M_start = iterator(); - this->_M_impl._M_finish = iterator(); - this->_M_impl._M_end_of_storage = 0; - for ( ; __first != __last; ++__first) - push_back(*__first); - } + vector(_InputIterator __first, _InputIterator __last, + const allocator_type& __a = allocator_type()) + : _Base(__a) + { + typedef typename std::__is_integer<_InputIterator>::__type _Integral; + _M_initialize_dispatch(__first, __last, _Integral()); + } - template<class _ForwardIterator> - void _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last, - forward_iterator_tag) - { - const size_type __n = std::distance(__first, __last); - _M_initialize(__n); - std::copy(__first, __last, this->_M_impl._M_start); - } + ~vector() { } - template<class _InputIterator> - void _M_insert_range(iterator __pos, _InputIterator __first, - _InputIterator __last, input_iterator_tag) + vector& + operator=(const vector& __x) { - for ( ; __first != __last; ++__first) + if (&__x == this) + return *this; + if (__x.size() > capacity()) { - __pos = insert(__pos, *__first); - ++__pos; + this->_M_deallocate(); + _M_initialize(__x.size()); } + this->_M_impl._M_finish = _M_copy_aligned(__x.begin(), __x.end(), + begin()); + return *this; } - template<class _ForwardIterator> - void _M_insert_range(iterator __position, _ForwardIterator __first, - _ForwardIterator __last, forward_iterator_tag) - { - if (__first != __last) - { - size_type __n = std::distance(__first, __last); - if (capacity() - size() >= __n) - { - std::copy_backward(__position, end(), - this->_M_impl._M_finish + difference_type(__n)); - std::copy(__first, __last, __position); - this->_M_impl._M_finish += difference_type(__n); - } - else - { - const size_type __len = size() + std::max(size(), __n); - _Bit_type * __q = this->_M_allocate(__len); - iterator __i = std::copy(begin(), __position, iterator(__q, 0)); - __i = std::copy(__first, __last, __i); - this->_M_impl._M_finish = std::copy(__position, end(), __i); - this->_M_deallocate(); - this->_M_impl._M_end_of_storage = __q + (__len + _S_word_bit - 1) - / _S_word_bit; - this->_M_impl._M_start = iterator(__q, 0); - } - } - } + // 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 + assign(size_type __n, const bool& __x) + { _M_fill_assign(__n, __x); } - public: - iterator begin() + template<class _InputIterator> + void + assign(_InputIterator __first, _InputIterator __last) + { + typedef typename std::__is_integer<_InputIterator>::__type _Integral; + _M_assign_dispatch(__first, __last, _Integral()); + } + + iterator + begin() { return this->_M_impl._M_start; } - const_iterator begin() const + const_iterator + begin() const { return this->_M_impl._M_start; } - iterator end() + iterator + end() { return this->_M_impl._M_finish; } - const_iterator end() const + const_iterator + end() const { return this->_M_impl._M_finish; } - reverse_iterator rbegin() + reverse_iterator + rbegin() { return reverse_iterator(end()); } - const_reverse_iterator rbegin() const + const_reverse_iterator + rbegin() const { return const_reverse_iterator(end()); } - reverse_iterator rend() + reverse_iterator + rend() { return reverse_iterator(begin()); } - const_reverse_iterator rend() const + const_reverse_iterator + rend() const { return const_reverse_iterator(begin()); } - size_type size() const + size_type + size() const { return size_type(end() - begin()); } - size_type max_size() const - { return size_type(-1); } - - size_type capacity() const - { return size_type(const_iterator(this->_M_impl._M_end_of_storage, 0) - - begin()); } - bool empty() const - { return begin() == end(); } - - reference operator[](size_type __n) - { return *(begin() + difference_type(__n)); } - - const_reference operator[](size_type __n) const - { return *(begin() + difference_type(__n)); } - - void _M_range_check(size_type __n) const - { - if (__n >= this->size()) - __throw_out_of_range(__N("vector<bool>::_M_range_check")); - } - - 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]; } - - explicit vector(const allocator_type& __a = allocator_type()) - : _Bvector_base<_Alloc>(__a) { } - - vector(size_type __n, bool __value, - const allocator_type& __a = allocator_type()) - : _Bvector_base<_Alloc>(__a) - { - _M_initialize(__n); - std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_of_storage, - __value ? ~0 : 0); - } - - explicit vector(size_type __n) - : _Bvector_base<_Alloc>(allocator_type()) + size_type + max_size() const { - _M_initialize(__n); - std::fill(this->_M_impl._M_start._M_p, - this->_M_impl._M_end_of_storage, 0); - } - - vector(const vector& __x) : _Bvector_base<_Alloc>(__x.get_allocator()) - { - _M_initialize(__x.size()); - std::copy(__x.begin(), __x.end(), this->_M_impl._M_start); + const size_type __asize = _M_get_Bit_allocator().max_size(); + return (__asize <= size_type(-1) / int(_S_word_bit) ? + __asize * int(_S_word_bit) : size_type(-1)); } - // Check whether it's an integral type. If so, it's not an iterator. - template<class _Integer> - void _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) - { - _M_initialize(__n); - std::fill(this->_M_impl._M_start._M_p, - this->_M_impl._M_end_of_storage, __x ? ~0 : 0); - } - - template<class _InputIterator> - void - _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, - __false_type) - { _M_initialize_range(__first, __last, - std::__iterator_category(__first)); } - - template<class _InputIterator> - vector(_InputIterator __first, _InputIterator __last, - const allocator_type& __a = allocator_type()) - : _Bvector_base<_Alloc>(__a) - { - typedef typename _Is_integer<_InputIterator>::_Integral _Integral; - _M_initialize_dispatch(__first, __last, _Integral()); - } + size_type + capacity() const + { return size_type(const_iterator(this->_M_impl._M_end_of_storage, 0) + - begin()); } - ~vector() { } + bool + empty() const + { return begin() == end(); } - vector& operator=(const vector& __x) + reference + operator[](size_type __n) { - if (&__x == this) - return *this; - if (__x.size() > capacity()) - { - this->_M_deallocate(); - _M_initialize(__x.size()); - } - std::copy(__x.begin(), __x.end(), begin()); - this->_M_impl._M_finish = begin() + difference_type(__x.size()); - return *this; + return *iterator(this->_M_impl._M_start._M_p + + __n / int(_S_word_bit), __n % int(_S_word_bit)); } - // 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_t __n, bool __x) + const_reference + operator[](size_type __n) const { - if (__n > size()) - { - std::fill(this->_M_impl._M_start._M_p, - this->_M_impl._M_end_of_storage, __x ? ~0 : 0); - insert(end(), __n - size(), __x); - } - else - { - erase(begin() + __n, end()); - std::fill(this->_M_impl._M_start._M_p, - this->_M_impl._M_end_of_storage, __x ? ~0 : 0); - } + return *const_iterator(this->_M_impl._M_start._M_p + + __n / int(_S_word_bit), __n % int(_S_word_bit)); } - void assign(size_t __n, bool __x) - { _M_fill_assign(__n, __x); } - - template<class _InputIterator> - void assign(_InputIterator __first, _InputIterator __last) + protected: + void + _M_range_check(size_type __n) const { - typedef typename _Is_integer<_InputIterator>::_Integral _Integral; - _M_assign_dispatch(__first, __last, _Integral()); + if (__n >= this->size()) + __throw_out_of_range(__N("vector<bool>::_M_range_check")); } - template<class _Integer> - void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) - { _M_fill_assign((size_t) __n, (bool) __val); } - - template<class _InputIterator> - void _M_assign_dispatch(_InputIterator __first, _InputIterator __last, - __false_type) - { _M_assign_aux(__first, __last, std::__iterator_category(__first)); } - - template<class _InputIterator> - void _M_assign_aux(_InputIterator __first, _InputIterator __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); - } + public: + reference + at(size_type __n) + { _M_range_check(__n); return (*this)[__n]; } - template<class _ForwardIterator> - void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, - forward_iterator_tag) - { - const size_type __len = std::distance(__first, __last); - if (__len < size()) - erase(std::copy(__first, __last, begin()), end()); - else - { - _ForwardIterator __mid = __first; - std::advance(__mid, size()); - std::copy(__first, __mid, begin()); - insert(end(), __mid, __last); - } - } + const_reference + at(size_type __n) const + { _M_range_check(__n); return (*this)[__n]; } - void reserve(size_type __n) + void + reserve(size_type __n) { if (__n > this->max_size()) __throw_length_error(__N("vector::reserve")); if (this->capacity() < __n) { _Bit_type* __q = this->_M_allocate(__n); - this->_M_impl._M_finish = std::copy(begin(), end(), - iterator(__q, 0)); + this->_M_impl._M_finish = _M_copy_aligned(begin(), end(), + iterator(__q, 0)); this->_M_deallocate(); this->_M_impl._M_start = iterator(__q, 0); - this->_M_impl._M_end_of_storage = __q + (__n + _S_word_bit - 1) / _S_word_bit; + this->_M_impl._M_end_of_storage = (__q + (__n + int(_S_word_bit) - 1) + / int(_S_word_bit)); } } - reference front() + reference + front() { return *begin(); } - const_reference front() const + const_reference + front() const { return *begin(); } - reference back() + reference + back() { return *(end() - 1); } - const_reference back() const + const_reference + back() const { return *(end() - 1); } - void push_back(bool __x) + // _GLIBCXX_RESOLVE_LIB_DEFECTS + // DR 464. Suggestion for new member functions in standard containers. + // N.B. DR 464 says nothing about vector<bool> but we need something + // here due to the way we are implementing DR 464 in the debug-mode + // vector class. + void + data() { } + + void + push_back(bool __x) { if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage) *this->_M_impl._M_finish++ = __x; @@ -758,23 +677,31 @@ template<typename _Alloc> _M_insert_aux(end(), __x); } - void swap(vector<bool, _Alloc>& __x) + void + swap(vector<bool, _Alloc>& __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_end_of_storage, __x._M_impl._M_end_of_storage); + + // _GLIBCXX_RESOLVE_LIB_DEFECTS + // 431. Swapping containers with unequal allocators. + std::__alloc_swap<typename _Base::_Bit_alloc_type>:: + _S_do_it(_M_get_Bit_allocator(), __x._M_get_Bit_allocator()); } // [23.2.5]/1, third-to-last entry in synopsis listing - static void swap(reference __x, reference __y) + static void + swap(reference __x, reference __y) { bool __tmp = __x; __x = __y; __y = __tmp; } - iterator insert(iterator __position, bool __x = bool()) + iterator + insert(iterator __position, const bool& __x = bool()) { const difference_type __n = __position - begin(); if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage @@ -785,29 +712,195 @@ template<typename _Alloc> return begin() + __n; } - // Check whether it's an integral type. If so, it's not an iterator. + template<class _InputIterator> + void + insert(iterator __position, + _InputIterator __first, _InputIterator __last) + { + typedef typename std::__is_integer<_InputIterator>::__type _Integral; + _M_insert_dispatch(__position, __first, __last, _Integral()); + } + void + insert(iterator __position, size_type __n, const bool& __x) + { _M_fill_insert(__position, __n, __x); } + + void + pop_back() + { --this->_M_impl._M_finish; } + + iterator + erase(iterator __position) + { + if (__position + 1 != end()) + std::copy(__position + 1, end(), __position); + --this->_M_impl._M_finish; + return __position; + } + + iterator + erase(iterator __first, iterator __last) + { + _M_erase_at_end(std::copy(__last, end(), __first)); + return __first; + } + + void + resize(size_type __new_size, bool __x = bool()) + { + if (__new_size < size()) + _M_erase_at_end(begin() + difference_type(__new_size)); + else + insert(end(), __new_size - size(), __x); + } + + void + flip() + { + for (_Bit_type * __p = this->_M_impl._M_start._M_p; + __p != this->_M_impl._M_end_of_storage; ++__p) + *__p = ~*__p; + } + + void + clear() + { _M_erase_at_end(begin()); } + + + protected: + // Precondition: __first._M_offset == 0 && __result._M_offset == 0. + iterator + _M_copy_aligned(const_iterator __first, const_iterator __last, + iterator __result) + { + _Bit_type* __q = std::copy(__first._M_p, __last._M_p, __result._M_p); + return std::copy(const_iterator(__last._M_p, 0), __last, + iterator(__q, 0)); + } + + void + _M_initialize(size_type __n) + { + _Bit_type* __q = this->_M_allocate(__n); + this->_M_impl._M_end_of_storage = (__q + + ((__n + int(_S_word_bit) - 1) + / int(_S_word_bit))); + this->_M_impl._M_start = iterator(__q, 0); + this->_M_impl._M_finish = this->_M_impl._M_start + difference_type(__n); + } + + // Check whether it's an integral type. If so, it's not an iterator. template<class _Integer> - void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, - __true_type) - { _M_fill_insert(__pos, __n, __x); } + void + _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) + { + _M_initialize(__n); + std::fill(this->_M_impl._M_start._M_p, + this->_M_impl._M_end_of_storage, __x ? ~0 : 0); + } template<class _InputIterator> - void _M_insert_dispatch(iterator __pos, - _InputIterator __first, _InputIterator __last, - __false_type) - { _M_insert_range(__pos, __first, __last, - std::__iterator_category(__first)); } + void + _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, + __false_type) + { _M_initialize_range(__first, __last, + std::__iterator_category(__first)); } template<class _InputIterator> - void insert(iterator __position, - _InputIterator __first, _InputIterator __last) + void + _M_initialize_range(_InputIterator __first, _InputIterator __last, + std::input_iterator_tag) + { + for (; __first != __last; ++__first) + push_back(*__first); + } + + template<class _ForwardIterator> + void + _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last, + std::forward_iterator_tag) + { + const size_type __n = std::distance(__first, __last); + _M_initialize(__n); + std::copy(__first, __last, this->_M_impl._M_start); + } + + template<class _Integer> + void + _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) + { _M_fill_assign((size_t) __n, (bool) __val); } + + template<class _InputIterator> + void + _M_assign_dispatch(_InputIterator __first, _InputIterator __last, + __false_type) + { _M_assign_aux(__first, __last, std::__iterator_category(__first)); } + + void + _M_fill_assign(size_t __n, bool __x) { - typedef typename _Is_integer<_InputIterator>::_Integral _Integral; - _M_insert_dispatch(__position, __first, __last, _Integral()); + if (__n > size()) + { + std::fill(this->_M_impl._M_start._M_p, + this->_M_impl._M_end_of_storage, __x ? ~0 : 0); + insert(end(), __n - size(), __x); + } + else + { + _M_erase_at_end(begin() + __n); + std::fill(this->_M_impl._M_start._M_p, + this->_M_impl._M_end_of_storage, __x ? ~0 : 0); + } } - void _M_fill_insert(iterator __position, size_type __n, bool __x) + template<class _InputIterator> + void + _M_assign_aux(_InputIterator __first, _InputIterator __last, + std::input_iterator_tag) + { + iterator __cur = begin(); + for (; __first != __last && __cur != end(); ++__cur, ++__first) + *__cur = *__first; + if (__first == __last) + _M_erase_at_end(__cur); + else + insert(end(), __first, __last); + } + + template<class _ForwardIterator> + void + _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, + std::forward_iterator_tag) + { + const size_type __len = std::distance(__first, __last); + if (__len < size()) + _M_erase_at_end(std::copy(__first, __last, begin())); + else + { + _ForwardIterator __mid = __first; + std::advance(__mid, size()); + std::copy(__first, __mid, begin()); + insert(end(), __mid, __last); + } + } + + // Check whether it's an integral type. If so, it's not an iterator. + template<class _Integer> + void + _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, + __true_type) + { _M_fill_insert(__pos, __n, __x); } + + template<class _InputIterator> + void + _M_insert_dispatch(iterator __pos, + _InputIterator __first, _InputIterator __last, + __false_type) + { _M_insert_range(__pos, __first, __last, + std::__iterator_category(__first)); } + + void + _M_fill_insert(iterator __position, size_type __n, bool __x) { if (__n == 0) return; @@ -822,55 +915,97 @@ template<typename _Alloc> { const size_type __len = size() + std::max(size(), __n); _Bit_type * __q = this->_M_allocate(__len); - iterator __i = std::copy(begin(), __position, iterator(__q, 0)); - std::fill_n(__i, __n, __x); + iterator __i = _M_copy_aligned(begin(), __position, + iterator(__q, 0)); + std::fill(__i, __i + difference_type(__n), __x); this->_M_impl._M_finish = std::copy(__position, end(), __i + difference_type(__n)); this->_M_deallocate(); - this->_M_impl._M_end_of_storage = __q + (__len + _S_word_bit - 1) - / _S_word_bit; + this->_M_impl._M_end_of_storage = (__q + ((__len + + int(_S_word_bit) - 1) + / int(_S_word_bit))); this->_M_impl._M_start = iterator(__q, 0); } } - void insert(iterator __position, size_type __n, bool __x) - { _M_fill_insert(__position, __n, __x); } - - void pop_back() - { --this->_M_impl._M_finish; } - - iterator erase(iterator __position) - { - if (__position + 1 != end()) - std::copy(__position + 1, end(), __position); - --this->_M_impl._M_finish; - return __position; - } + template<class _InputIterator> + void + _M_insert_range(iterator __pos, _InputIterator __first, + _InputIterator __last, std::input_iterator_tag) + { + for (; __first != __last; ++__first) + { + __pos = insert(__pos, *__first); + ++__pos; + } + } - iterator erase(iterator __first, iterator __last) - { - this->_M_impl._M_finish = std::copy(__last, end(), __first); - return __first; - } + template<class _ForwardIterator> + void + _M_insert_range(iterator __position, _ForwardIterator __first, + _ForwardIterator __last, std::forward_iterator_tag) + { + if (__first != __last) + { + size_type __n = std::distance(__first, __last); + if (capacity() - size() >= __n) + { + std::copy_backward(__position, end(), + this->_M_impl._M_finish + + difference_type(__n)); + std::copy(__first, __last, __position); + this->_M_impl._M_finish += difference_type(__n); + } + else + { + const size_type __len = size() + std::max(size(), __n); + _Bit_type * __q = this->_M_allocate(__len); + iterator __i = _M_copy_aligned(begin(), __position, + iterator(__q, 0)); + __i = std::copy(__first, __last, __i); + this->_M_impl._M_finish = std::copy(__position, end(), __i); + this->_M_deallocate(); + this->_M_impl._M_end_of_storage = (__q + + ((__len + + int(_S_word_bit) - 1) + / int(_S_word_bit))); + this->_M_impl._M_start = iterator(__q, 0); + } + } + } - void resize(size_type __new_size, bool __x = bool()) + void + _M_insert_aux(iterator __position, bool __x) { - if (__new_size < size()) - erase(begin() + difference_type(__new_size), end()); + if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage) + { + std::copy_backward(__position, this->_M_impl._M_finish, + this->_M_impl._M_finish + 1); + *__position = __x; + ++this->_M_impl._M_finish; + } else - insert(end(), __new_size - size(), __x); - } - - void flip() - { - for (_Bit_type * __p = this->_M_impl._M_start._M_p; - __p != this->_M_impl._M_end_of_storage; ++__p) - *__p = ~*__p; + { + const size_type __len = size() ? 2 * size() + : static_cast<size_type>(_S_word_bit); + _Bit_type * __q = this->_M_allocate(__len); + iterator __i = _M_copy_aligned(begin(), __position, + iterator(__q, 0)); + *__i++ = __x; + this->_M_impl._M_finish = std::copy(__position, end(), __i); + this->_M_deallocate(); + this->_M_impl._M_end_of_storage = (__q + ((__len + + int(_S_word_bit) - 1) + / int(_S_word_bit))); + this->_M_impl._M_start = iterator(__q, 0); + } } - void clear() - { erase(begin(), end()); } + void + _M_erase_at_end(iterator __pos) + { this->_M_impl._M_finish = __pos; } }; -} // namespace std + +_GLIBCXX_END_NESTED_NAMESPACE #endif |
