This fixes some missed optimizations I should have made when adding
the new std::__cxx11::list, making use of the O(1) list::size() when
it saves work.
In the equality comparisons two lists can't be equal if their sizes
differ.
When resizing a list we don't need to walk the list to find whether
we're growing or shrinking, and when shrinking by less than 50% it is
faster to find the first element to erase by moving backwards from the
end rather than starting at the beginning.
Tested powerpc64-linux.
I plan to commit this to trunk and the gcc-5-branch.
commit 9d6539fec972296694c30b073dd068cfbcdae8a5
Author: Jonathan Wakely <jwak...@redhat.com>
Date: Tue May 19 13:28:16 2015 +0100
* 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.
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();
