diff options
Diffstat (limited to 'libstdc++-v3')
| -rw-r--r-- | libstdc++-v3/ChangeLog | 8 | ||||
| -rw-r--r-- | libstdc++-v3/include/bits/list.tcc | 81 | ||||
| -rw-r--r-- | libstdc++-v3/include/bits/stl_list.h | 9 |
3 files changed, 76 insertions, 22 deletions
diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 0cdd178..6c5964a 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,11 @@ +2015-05-19 Jonathan Wakely <jwakely@redhat.com> + + * include/bits/stl_list.h (_M_resize_pos(size_type&)): Declare. + (operator==(const list&, const list&)): If size() is O(1) compare + sizes before comparing each element. + * include/bits/list.tcc (list::_M_resize_pos(size_type&)): Define. + (list::resize): Use _M_resize_pos. + 2015-05-19 François Dumont <fdumont@gcc.gnu.org> * testsuite/23_containers/unordered_map/cons/66055.cc: Add constructor diff --git a/libstdc++-v3/include/bits/list.tcc b/libstdc++-v3/include/bits/list.tcc index a9c8a55..c5d2ab4 100644 --- a/libstdc++-v3/include/bits/list.tcc +++ b/libstdc++-v3/include/bits/list.tcc @@ -157,6 +157,52 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER return __ret; } + // Return a const_iterator indicating the position to start inserting or + // erasing elements (depending whether the list is growing or shrinking), + // and set __new_size to the number of new elements that must be appended. + // Equivalent to the following, but performed optimally: + // if (__new_size < size()) { + // __new_size = 0; + // return std::next(begin(), __new_size); + // } else { + // __newsize -= size(); + // return end(); + // } + template<typename _Tp, typename _Alloc> + typename list<_Tp, _Alloc>::const_iterator + list<_Tp, _Alloc>:: + _M_resize_pos(size_type& __new_size) const + { + const_iterator __i; +#if _GLIBCXX_USE_CXX11_ABI + const size_type __len = size(); + if (__new_size < __len) + { + if (__new_size <= __len / 2) + { + __i = begin(); + std::advance(__i, __new_size); + } + else + { + __i = end(); + ptrdiff_t __num_erase = __len - __new_size; + std::advance(__i, -__num_erase); + } + __new_size = 0; + return __i; + } + else + __i = end(); +#else + size_type __len = 0; + for (__i = begin(); __i != end() && __len < __new_size; ++__i, ++__len) + ; +#endif + __new_size -= __len; + return __i; + } + #if __cplusplus >= 201103L template<typename _Tp, typename _Alloc> void @@ -182,14 +228,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER list<_Tp, _Alloc>:: resize(size_type __new_size) { - iterator __i = begin(); - size_type __len = 0; - for (; __i != end() && __len < __new_size; ++__i, ++__len) - ; - if (__len == __new_size) + const_iterator __i = _M_resize_pos(__new_size); + if (__new_size) + _M_default_append(__new_size); + else erase(__i, end()); - else // __i == end() - _M_default_append(__new_size - __len); } template<typename _Tp, typename _Alloc> @@ -197,14 +240,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER list<_Tp, _Alloc>:: resize(size_type __new_size, const value_type& __x) { - iterator __i = begin(); - size_type __len = 0; - for (; __i != end() && __len < __new_size; ++__i, ++__len) - ; - if (__len == __new_size) + const_iterator __i = _M_resize_pos(__new_size); + if (__new_size) + insert(end(), __new_size, __x); + else erase(__i, end()); - else // __i == end() - insert(end(), __new_size - __len, __x); } #else template<typename _Tp, typename _Alloc> @@ -212,14 +252,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER list<_Tp, _Alloc>:: resize(size_type __new_size, value_type __x) { - iterator __i = begin(); - size_type __len = 0; - for (; __i != end() && __len < __new_size; ++__i, ++__len) - ; - if (__len == __new_size) - erase(__i, end()); - else // __i == end() - insert(end(), __new_size - __len, __x); + const_iterator __i = _M_resize_pos(__new_size); + if (__new_size) + insert(end(), __new_size, __x); + else + erase(__i._M_const_cast(), end()); } #endif diff --git a/libstdc++-v3/include/bits/stl_list.h b/libstdc++-v3/include/bits/stl_list.h index 3401e5b..a26859e 100644 --- a/libstdc++-v3/include/bits/stl_list.h +++ b/libstdc++-v3/include/bits/stl_list.h @@ -1789,6 +1789,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 _S_do_it(_M_get_Node_allocator(), __x._M_get_Node_allocator())) __builtin_abort(); } + + // Used to implement resize. + const_iterator + _M_resize_pos(size_type& __new_size) const; }; _GLIBCXX_END_NAMESPACE_CXX11 @@ -1806,6 +1810,11 @@ _GLIBCXX_END_NAMESPACE_CXX11 inline bool operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) { +#if _GLIBCXX_USE_CXX11_ABI + if (__x.size() != __y.size()) + return false; +#endif + typedef typename list<_Tp, _Alloc>::const_iterator const_iterator; const_iterator __end1 = __x.end(); const_iterator __end2 = __y.end(); |