diff options
Diffstat (limited to 'libstdc++-v3/include/bits/stl_vector.h')
-rw-r--r-- | libstdc++-v3/include/bits/stl_vector.h | 243 |
1 files changed, 141 insertions, 102 deletions
diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h index 9b6d258f6ca..eaafa223dbf 100644 --- a/libstdc++-v3/include/bits/stl_vector.h +++ b/libstdc++-v3/include/bits/stl_vector.h @@ -63,6 +63,8 @@ #include <initializer_list> #endif +#include <debug/assertions.h> + namespace std _GLIBCXX_VISIBILITY(default) { _GLIBCXX_BEGIN_NAMESPACE_CONTAINER @@ -72,7 +74,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER struct _Vector_base { typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template - rebind<_Tp>::other _Tp_alloc_type; + rebind<_Tp>::other _Tp_alloc_type; typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type>::pointer pointer; @@ -214,30 +216,30 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER class vector : protected _Vector_base<_Tp, _Alloc> { // Concept requirements. - typedef typename _Alloc::value_type _Alloc_value_type; + typedef typename _Alloc::value_type _Alloc_value_type; #if __cplusplus < 201103L __glibcxx_class_requires(_Tp, _SGIAssignableConcept) #endif __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept) - typedef _Vector_base<_Tp, _Alloc> _Base; - typedef typename _Base::_Tp_alloc_type _Tp_alloc_type; - typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Alloc_traits; + typedef _Vector_base<_Tp, _Alloc> _Base; + typedef typename _Base::_Tp_alloc_type _Tp_alloc_type; + typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Alloc_traits; public: - typedef _Tp value_type; - typedef typename _Base::pointer pointer; - typedef typename _Alloc_traits::const_pointer const_pointer; - typedef typename _Alloc_traits::reference reference; - typedef typename _Alloc_traits::const_reference const_reference; + typedef _Tp value_type; + typedef typename _Base::pointer pointer; + typedef typename _Alloc_traits::const_pointer const_pointer; + typedef typename _Alloc_traits::reference reference; + typedef typename _Alloc_traits::const_reference const_reference; typedef __gnu_cxx::__normal_iterator<pointer, vector> iterator; typedef __gnu_cxx::__normal_iterator<const_pointer, vector> 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 _Alloc allocator_type; + 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 _Alloc allocator_type; protected: using _Base::_M_allocate; @@ -319,8 +321,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER */ vector(const vector& __x) : _Base(__x.size(), - _Alloc_traits::_S_select_on_copy(__x._M_get_Tp_allocator())) - { this->_M_impl._M_finish = + _Alloc_traits::_S_select_on_copy(__x._M_get_Tp_allocator())) + { + this->_M_impl._M_finish = std::__uninitialized_copy_a(__x.begin(), __x.end(), this->_M_impl._M_start, _M_get_Tp_allocator()); @@ -340,7 +343,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER /// Copy constructor with alternative allocator vector(const vector& __x, const allocator_type& __a) : _Base(__x.size(), __a) - { this->_M_impl._M_finish = + { + this->_M_impl._M_finish = std::__uninitialized_copy_a(__x.begin(), __x.end(), this->_M_impl._M_start, _M_get_Tp_allocator()); @@ -400,16 +404,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER #if __cplusplus >= 201103L template<typename _InputIterator, typename = std::_RequireInputIter<_InputIterator>> - vector(_InputIterator __first, _InputIterator __last, + vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a = allocator_type()) : _Base(__a) - { _M_initialize_dispatch(__first, __last, __false_type()); } + { _M_initialize_dispatch(__first, __last, __false_type()); } #else template<typename _InputIterator> - vector(_InputIterator __first, _InputIterator __last, + vector(_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()); @@ -449,10 +453,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER vector& operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move()) { - constexpr bool __move_storage = - _Alloc_traits::_S_propagate_on_move_assign() - || _Alloc_traits::_S_always_equal(); - _M_move_assign(std::move(__x), __bool_constant<__move_storage>()); + constexpr bool __move_storage = + _Alloc_traits::_S_propagate_on_move_assign() + || _Alloc_traits::_S_always_equal(); + _M_move_assign(std::move(__x), __bool_constant<__move_storage>()); return *this; } @@ -470,7 +474,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER vector& operator=(initializer_list<value_type> __l) { - this->assign(__l.begin(), __l.end()); + this->_M_assign_aux(__l.begin(), __l.end(), + random_access_iterator_tag()); return *this; } #endif @@ -504,14 +509,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER #if __cplusplus >= 201103L template<typename _InputIterator, typename = std::_RequireInputIter<_InputIterator>> - void - assign(_InputIterator __first, _InputIterator __last) - { _M_assign_dispatch(__first, __last, __false_type()); } + void + assign(_InputIterator __first, _InputIterator __last) + { _M_assign_dispatch(__first, __last, __false_type()); } #else template<typename _InputIterator> - void - assign(_InputIterator __first, _InputIterator __last) - { + void + assign(_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_assign_dispatch(__first, __last, _Integral()); @@ -532,7 +537,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER */ void assign(initializer_list<value_type> __l) - { this->assign(__l.begin(), __l.end()); } + { + this->_M_assign_aux(__l.begin(), __l.end(), + random_access_iterator_tag()); + } #endif /// Get a copy of the memory allocation object. @@ -694,7 +702,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER resize(size_type __new_size, const value_type& __x) { if (__new_size > size()) - insert(end(), __new_size - size(), __x); + _M_fill_insert(end(), __new_size - size(), __x); else if (__new_size < size()) _M_erase_at_end(this->_M_impl._M_start + __new_size); } @@ -714,7 +722,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER resize(size_type __new_size, value_type __x = value_type()) { if (__new_size > size()) - insert(end(), __new_size - size(), __x); + _M_fill_insert(end(), __new_size - size(), __x); else if (__new_size < size()) _M_erase_at_end(this->_M_impl._M_start + __new_size); } @@ -778,7 +786,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER */ reference operator[](size_type __n) _GLIBCXX_NOEXCEPT - { return *(this->_M_impl._M_start + __n); } + { + __glibcxx_requires_subscript(__n); + return *(this->_M_impl._M_start + __n); + } /** * @brief Subscript access to the data contained in the %vector. @@ -793,7 +804,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER */ const_reference operator[](size_type __n) const _GLIBCXX_NOEXCEPT - { return *(this->_M_impl._M_start + __n); } + { + __glibcxx_requires_subscript(__n); + return *(this->_M_impl._M_start + __n); + } protected: /// Safety check used only from at(). @@ -850,7 +864,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER */ reference front() _GLIBCXX_NOEXCEPT - { return *begin(); } + { + __glibcxx_requires_nonempty(); + return *begin(); + } /** * Returns a read-only (constant) reference to the data at the first @@ -858,7 +875,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER */ const_reference front() const _GLIBCXX_NOEXCEPT - { return *begin(); } + { + __glibcxx_requires_nonempty(); + return *begin(); + } /** * Returns a read/write reference to the data at the last @@ -866,7 +886,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER */ reference back() _GLIBCXX_NOEXCEPT - { return *(end() - 1); } + { + __glibcxx_requires_nonempty(); + return *(end() - 1); + } /** * Returns a read-only (constant) reference to the data at the @@ -874,7 +897,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER */ const_reference back() const _GLIBCXX_NOEXCEPT - { return *(end() - 1); } + { + __glibcxx_requires_nonempty(); + return *(end() - 1); + } // _GLIBCXX_RESOLVE_LIB_DEFECTS // DR 464. Suggestion for new member functions in standard containers. @@ -916,7 +942,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) { _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, - __x); + __x); ++this->_M_impl._M_finish; } else @@ -933,8 +959,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { emplace_back(std::move(__x)); } template<typename... _Args> - void - emplace_back(_Args&&... __args); + void + emplace_back(_Args&&... __args); #endif /** @@ -949,6 +975,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER void pop_back() _GLIBCXX_NOEXCEPT { + __glibcxx_requires_nonempty(); --this->_M_impl._M_finish; _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish); } @@ -967,8 +994,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * std::list. */ template<typename... _Args> - iterator - emplace(const_iterator __position, _Args&&... __args); + iterator + emplace(const_iterator __position, _Args&&... __args); /** * @brief Inserts given value into %vector before specified iterator. @@ -1030,7 +1057,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER */ iterator insert(const_iterator __position, initializer_list<value_type> __l) - { return this->insert(__position, __l.begin(), __l.end()); } + { + auto __offset = __position - cbegin(); + _M_range_insert(begin() + __offset, __l.begin(), __l.end(), + std::random_access_iterator_tag()); + return begin() + __offset; + } #endif #if __cplusplus >= 201103L @@ -1092,10 +1124,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER */ template<typename _InputIterator, typename = std::_RequireInputIter<_InputIterator>> - iterator - insert(const_iterator __position, _InputIterator __first, + iterator + insert(const_iterator __position, _InputIterator __first, _InputIterator __last) - { + { difference_type __offset = __position - cbegin(); _M_insert_dispatch(begin() + __offset, __first, __last, __false_type()); @@ -1117,10 +1149,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * consider using std::list. */ template<typename _InputIterator> - void - insert(iterator __position, _InputIterator __first, + 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()); @@ -1194,9 +1226,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER void swap(vector& __x) _GLIBCXX_NOEXCEPT { +#if __cplusplus >= 201103L + __glibcxx_assert(_Alloc_traits::propagate_on_container_swap::value + || _M_get_Tp_allocator() == __x._M_get_Tp_allocator()); +#endif this->_M_impl._M_swap_data(__x._M_impl); _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(), - __x._M_get_Tp_allocator()); + __x._M_get_Tp_allocator()); } /** @@ -1215,10 +1251,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * obtain @a n bytes of memory, and then copies [first,last) into it. */ template<typename _ForwardIterator> - pointer - _M_allocate_and_copy(size_type __n, + pointer + _M_allocate_and_copy(size_type __n, _ForwardIterator __first, _ForwardIterator __last) - { + { pointer __result = this->_M_allocate(__n); __try { @@ -1241,9 +1277,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER // _GLIBCXX_RESOLVE_LIB_DEFECTS // 438. Ambiguity in the "do the right thing" clause template<typename _Integer> - void - _M_initialize_dispatch(_Integer __n, _Integer __value, __true_type) - { + void + _M_initialize_dispatch(_Integer __n, _Integer __value, __true_type) + { this->_M_impl._M_start = _M_allocate(static_cast<size_type>(__n)); this->_M_impl._M_end_of_storage = this->_M_impl._M_start + static_cast<size_type>(__n); @@ -1252,10 +1288,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER // Called by the range constructor to implement [23.1.1]/9 template<typename _InputIterator> - void - _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, + 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()); @@ -1263,10 +1299,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER // Called by the second initialize_dispatch above template<typename _InputIterator> - void - _M_range_initialize(_InputIterator __first, + void + _M_range_initialize(_InputIterator __first, _InputIterator __last, std::input_iterator_tag) - { + { for (; __first != __last; ++__first) #if __cplusplus >= 201103L emplace_back(*__first); @@ -1277,10 +1313,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER // Called by the second initialize_dispatch above template<typename _ForwardIterator> - void - _M_range_initialize(_ForwardIterator __first, + void + _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last, std::forward_iterator_tag) - { + { const size_type __n = std::distance(__first, __last); this->_M_impl._M_start = this->_M_allocate(__n); this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; @@ -1319,31 +1355,27 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER // _GLIBCXX_RESOLVE_LIB_DEFECTS // 438. Ambiguity in the "do the right thing" clause template<typename _Integer> - void - _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) - { _M_fill_assign(__n, __val); } + void + _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) + { _M_fill_assign(__n, __val); } // Called by the range assign to implement [23.1.1]/9 template<typename _InputIterator> - void - _M_assign_dispatch(_InputIterator __first, _InputIterator __last, + 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()); - } + { _M_assign_aux(__first, __last, std::__iterator_category(__first)); } // Called by the second assign_dispatch above template<typename _InputIterator> - void - _M_assign_aux(_InputIterator __first, _InputIterator __last, + void + _M_assign_aux(_InputIterator __first, _InputIterator __last, std::input_iterator_tag); // Called by the second assign_dispatch above template<typename _ForwardIterator> - void - _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, + void + _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, std::forward_iterator_tag); // Called by assign(n,t), and the range assign when it turns out @@ -1351,7 +1383,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER void _M_fill_assign(size_type __n, const value_type& __val); - // Internal insert functions follow. // Called by the range insert to implement [23.1.1]/9 @@ -1359,32 +1390,31 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER // _GLIBCXX_RESOLVE_LIB_DEFECTS // 438. Ambiguity in the "do the right thing" clause template<typename _Integer> - void - _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val, + void + _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val, __true_type) - { _M_fill_insert(__pos, __n, __val); } + { _M_fill_insert(__pos, __n, __val); } // Called by the range insert to implement [23.1.1]/9 template<typename _InputIterator> - void - _M_insert_dispatch(iterator __pos, _InputIterator __first, + void + _M_insert_dispatch(iterator __pos, _InputIterator __first, _InputIterator __last, __false_type) - { - typedef typename std::iterator_traits<_InputIterator>:: - iterator_category _IterCategory; - _M_range_insert(__pos, __first, __last, _IterCategory()); + { + _M_range_insert(__pos, __first, __last, + std::__iterator_category(__first)); } // Called by the second insert_dispatch above template<typename _InputIterator> - void - _M_range_insert(iterator __pos, _InputIterator __first, + void + _M_range_insert(iterator __pos, _InputIterator __first, _InputIterator __last, std::input_iterator_tag); // Called by the second insert_dispatch above template<typename _ForwardIterator> - void - _M_range_insert(iterator __pos, _ForwardIterator __first, + void + _M_range_insert(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 @@ -1407,12 +1437,21 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _M_insert_aux(iterator __position, const value_type& __x); #else template<typename... _Args> - void - _M_insert_aux(iterator __position, _Args&&... __args); + static void + _S_insert_aux_assign(iterator __pos, _Args&&... __args) + { *__pos = _Tp(std::forward<_Args>(__args)...); } + + static void + _S_insert_aux_assign(iterator __pos, _Tp&& __arg) + { *__pos = std::move(__arg); } + + template<typename... _Args> + void + _M_insert_aux(iterator __position, _Args&&... __args); template<typename... _Args> - void - _M_emplace_back_aux(_Args&&... __args); + void + _M_emplace_back_aux(_Args&&... __args); #endif // Called by the latter. |