From 8e72571637a1f148628617d7eaa3b45809af247d Mon Sep 17 00:00:00 2001 From: Jonathan Wakely Date: Tue, 19 May 2015 23:24:50 +0100 Subject: [PATCH] stl_list.h (_M_resize_pos(size_type&)): Declare. * 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. From-SVN: r223416 --- libstdc++-v3/ChangeLog | 8 +++ libstdc++-v3/include/bits/list.tcc | 81 ++++++++++++++++++++-------- 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 0cdd178d9ee..6c5964af75a 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,11 @@ +2015-05-19 Jonathan Wakely + + * 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 * 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 a9c8a550b4a..c5d2ab4e9d1 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 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 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 @@ -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 @@ -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 3401e5b4d25..a26859ec7fa 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(); -- 2.30.2