aboutsummaryrefslogtreecommitdiff
path: root/libstdc++-v3
diff options
context:
space:
mode:
Diffstat (limited to 'libstdc++-v3')
-rw-r--r--libstdc++-v3/ChangeLog8
-rw-r--r--libstdc++-v3/include/bits/list.tcc81
-rw-r--r--libstdc++-v3/include/bits/stl_list.h9
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();