re PR libstdc++/49561 ([C++0x] std::list::size complexity)

2011-10-04  Paolo Carlini  <paolo.carlini@oracle.com>

	PR libstdc++/49561
	* include/bits/stl_list.h (_List_base<>::_List_impl::_M_size):
	Add in C++0x mode.
	(_List_base<>::_List_impl, _List_base<>::_M_get_node,
	_List_base<>::_M_put_node, _List_base<>::_List_base(_List_base&&),
	list<>::size, list<>::swap, list<>::splice): Use it.
	(operator==(const list<>&, const list<>&)): Rewrite in C++0x mode.
	* include/bits/list.tcc (list<>::erase): Likewise.
	(list<>::merge): Adjust in C++0x mode.
	* testsuite/23_containers/list/requirements/dr438/assign_neg.cc:
	Adjust dg-error line number.
	* testsuite/23_containers/list/requirements/dr438/insert_neg.cc:
	Likewise.
	* testsuite/23_containers/list/requirements/dr438/
	constructor_1_neg.cc: Likewise.
	* testsuite/23_containers/list/requirements/dr438/
	constructor_2_neg.cc: Likewise.

From-SVN: r179528

7 files changed, 119 insertions, 34 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 2c17169..88d1d1b 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,5 +1,25 @@
 2011-10-04  Paolo Carlini  <paolo.carlini@oracle.com>
 
+	PR libstdc++/49561
+	* include/bits/stl_list.h (_List_base<>::_List_impl::_M_size):
+	Add in C++0x mode.
+	(_List_base<>::_List_impl, _List_base<>::_M_get_node,
+	_List_base<>::_M_put_node, _List_base<>::_List_base(_List_base&&),
+	list<>::size, list<>::swap, list<>::splice): Use it.
+	(operator==(const list<>&, const list<>&)): Rewrite in C++0x mode.
+	* include/bits/list.tcc (list<>::erase): Likewise.
+	(list<>::merge): Adjust in C++0x mode.
+	* testsuite/23_containers/list/requirements/dr438/assign_neg.cc:
+	Adjust dg-error line number.
+	* testsuite/23_containers/list/requirements/dr438/insert_neg.cc:
+	Likewise.
+	* testsuite/23_containers/list/requirements/dr438/
+	constructor_1_neg.cc: Likewise.
+	* testsuite/23_containers/list/requirements/dr438/
+	constructor_2_neg.cc: Likewise.
+
+2011-10-04  Paolo Carlini  <paolo.carlini@oracle.com>
+
 	* testsuite/20_util/bind/48698.cc (g): Fix return type, avoid -Wall
 	warning.
 
diff --git a/libstdc++-v3/include/bits/list.tcc b/libstdc++-v3/include/bits/list.tcc
index 01c1bc6..55156bb 100644
--- a/libstdc++-v3/include/bits/list.tcc
+++ b/libstdc++-v3/include/bits/list.tcc
@@ -67,8 +67,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
     _M_clear()
     {
       typedef _List_node<_Tp>  _Node;
-      _Node* __cur = static_cast<_Node*>(this->_M_impl._M_node._M_next);
-      while (__cur != &this->_M_impl._M_node)
+      _Node* __cur = static_cast<_Node*>(_M_impl._M_node._M_next);
+      while (__cur != &_M_impl._M_node)
 	{
 	  _Node* __tmp = __cur;
 	  __cur = static_cast<_Node*>(__cur->_M_next);
@@ -139,14 +139,14 @@ _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)
-        erase(__i, end());
-      else                          // __i == end()
-	_M_default_append(__new_size - __len);
+      if (__new_size > size())
+	_M_default_append(__new_size - size());
+      else if (__new_size < size())
+	{
+	  iterator __i = begin();
+	  std::advance(__i, __new_size);
+	  erase(__i, end());
+	}
     }
 
   template<typename _Tp, typename _Alloc>
@@ -154,14 +154,14 @@ _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)
-        erase(__i, end());
-      else                          // __i == end()
-        insert(end(), __new_size - __len, __x);
+      if (__new_size > size())
+	insert(end(), __new_size - size(), __x);
+      else if (__new_size < size())
+	{
+	  iterator __i = begin();
+	  std::advance(__i, __new_size);
+	  erase(__i, end());
+	}
     }
 #else
   template<typename _Tp, typename _Alloc>
@@ -312,6 +312,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	      ++__first1;
 	  if (__first2 != __last2)
 	    _M_transfer(__last1, __first2, __last2);
+
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+	  this->_M_impl._M_size += __x.size();
+	  __x._M_impl._M_size = 0;
+#endif
 	}
     }
 
@@ -346,6 +351,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 		++__first1;
 	    if (__first2 != __last2)
 	      _M_transfer(__last1, __first2, __last2);
+
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+	    this->_M_impl._M_size += __x.size();
+	    __x._M_impl._M_size = 0;
+#endif
 	  }
       }
 
diff --git a/libstdc++-v3/include/bits/stl_list.h b/libstdc++-v3/include/bits/stl_list.h
index 91e39f3..56ee2fb 100644
--- a/libstdc++-v3/include/bits/stl_list.h
+++ b/libstdc++-v3/include/bits/stl_list.h
@@ -306,22 +306,32 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;
 
-      struct _List_impl 
+      struct _List_impl
       : public _Node_alloc_type
       {
 	__detail::_List_node_base _M_node;
 
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+	size_t                    _M_size;
+#endif
+
 	_List_impl()
 	: _Node_alloc_type(), _M_node()
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+	, _M_size(0)
+#endif
 	{ }
 
 	_List_impl(const _Node_alloc_type& __a)
 	: _Node_alloc_type(__a), _M_node()
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+	, _M_size(0)
+#endif
 	{ }
 
 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 	_List_impl(_Node_alloc_type&& __a)
-	: _Node_alloc_type(std::move(__a)), _M_node()
+	: _Node_alloc_type(std::move(__a)), _M_node(), _M_size(0)
 	{ }
 #endif
       };
@@ -330,22 +340,33 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       _List_node<_Tp>*
       _M_get_node()
-      { return _M_impl._Node_alloc_type::allocate(1); }
-      
+      {
+	_List_node<_Tp>* __tmp = _M_impl._Node_alloc_type::allocate(1);
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+	++_M_impl._M_size;
+#endif	
+	return __tmp;
+      }
+
       void
       _M_put_node(_List_node<_Tp>* __p)
-      { _M_impl._Node_alloc_type::deallocate(__p, 1); }
+      {
+	_M_impl._Node_alloc_type::deallocate(__p, 1);
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+	--_M_impl._M_size;
+#endif
+      }
       
   public:
       typedef _Alloc allocator_type;
 
       _Node_alloc_type&
       _M_get_Node_allocator() _GLIBCXX_NOEXCEPT
-      { return *static_cast<_Node_alloc_type*>(&this->_M_impl); }
+      { return *static_cast<_Node_alloc_type*>(&_M_impl); }
 
       const _Node_alloc_type&
       _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT
-      { return *static_cast<const _Node_alloc_type*>(&this->_M_impl); }
+      { return *static_cast<const _Node_alloc_type*>(&_M_impl); }
 
       _Tp_alloc_type
       _M_get_Tp_allocator() const _GLIBCXX_NOEXCEPT
@@ -368,8 +389,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       : _M_impl(std::move(__x._M_get_Node_allocator()))
       {
 	_M_init();
-	__detail::_List_node_base::swap(this->_M_impl._M_node, 
-					__x._M_impl._M_node);	
+	__detail::_List_node_base::swap(_M_impl._M_node, __x._M_impl._M_node);
+	std::swap(_M_impl._M_size, __x._M_impl._M_size);
       }
 #endif
 
@@ -851,7 +872,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       /**  Returns the number of elements in the %list.  */
       size_type
       size() const _GLIBCXX_NOEXCEPT
-      { return std::distance(begin(), end()); }
+      {
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+	return this->_M_impl._M_size;
+#else
+	return std::distance(begin(), end());
+#endif
+      }
 
       /**  Returns the size() of the largest possible %list.  */
       size_type
@@ -1186,6 +1213,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       {
 	__detail::_List_node_base::swap(this->_M_impl._M_node, 
 					__x._M_impl._M_node);
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+	std::swap(this->_M_impl._M_size, __x._M_impl._M_size);
+#endif
 
 	// _GLIBCXX_RESOLVE_LIB_DEFECTS
 	// 431. Swapping containers with unequal allocators.
@@ -1230,6 +1260,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	    _M_check_equal_allocators(__x);
 
 	    this->_M_transfer(__position, __x.begin(), __x.end());
+
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+	    this->_M_impl._M_size += __x.size();
+	    __x._M_impl._M_size = 0;
+#endif
 	  }
       }
 
@@ -1261,7 +1296,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	  return;
 
 	if (this != &__x)
-	  _M_check_equal_allocators(__x);
+	  {
+	    _M_check_equal_allocators(__x);
+
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+	    ++this->_M_impl._M_size;
+	    --__x._M_impl._M_size;
+#endif
+	  }
 
 	this->_M_transfer(__position, __i, __j);
       }
@@ -1296,7 +1338,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	if (__first != __last)
 	  {
 	    if (this != &__x)
-	      _M_check_equal_allocators(__x);
+	      {
+		_M_check_equal_allocators(__x);
+
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+		const size_type __size = std::distance(__first, __last);
+		this->_M_impl._M_size += __size;
+		__x._M_impl._M_size -= __size;
+#endif
+	      }
 
 	    this->_M_transfer(__position, __first, __last);
 	  }
@@ -1571,6 +1621,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
     inline bool
     operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
     {
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+      return (__x.size() == __y.size()
+	      && std::equal(__x.begin(), __x.end(), __y.begin()));
+#else
       typedef typename list<_Tp, _Alloc>::const_iterator const_iterator;
       const_iterator __end1 = __x.end();
       const_iterator __end2 = __y.end();
@@ -1583,6 +1637,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	  ++__i2;
 	}
       return __i1 == __end1 && __i2 == __end2;
+#endif
     }
 
   /**
diff --git a/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/assign_neg.cc b/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/assign_neg.cc
index f53082d..974821f 100644
--- a/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/assign_neg.cc
+++ b/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/assign_neg.cc
@@ -18,7 +18,7 @@
 // <http://www.gnu.org/licenses/>.
 
 // { dg-do compile }
-// { dg-error "no matching" "" { target *-*-* } 1499 }
+// { dg-error "no matching" "" { target *-*-* } 1549 }
 
 #include <list>
 
diff --git a/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/constructor_1_neg.cc b/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/constructor_1_neg.cc
index f0af971..6683e78 100644
--- a/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/constructor_1_neg.cc
+++ b/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/constructor_1_neg.cc
@@ -18,7 +18,7 @@
 // <http://www.gnu.org/licenses/>.
 
 // { dg-do compile }
-// { dg-error "no matching" "" { target *-*-* } 1455 }
+// { dg-error "no matching" "" { target *-*-* } 1505 }
 
 #include <list>
 
diff --git a/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/constructor_2_neg.cc b/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/constructor_2_neg.cc
index 168d592..f3e7009 100644
--- a/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/constructor_2_neg.cc
+++ b/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/constructor_2_neg.cc
@@ -18,7 +18,7 @@
 // <http://www.gnu.org/licenses/>.
 
 // { dg-do compile }
-// { dg-error "no matching" "" { target *-*-* } 1455 }
+// { dg-error "no matching" "" { target *-*-* } 1505 }
 
 #include <list>
 #include <utility>
diff --git a/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/insert_neg.cc b/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/insert_neg.cc
index 32bfd53..7e19c42 100644
--- a/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/insert_neg.cc
+++ b/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/insert_neg.cc
@@ -18,7 +18,7 @@
 // <http://www.gnu.org/licenses/>.
 
 // { dg-do compile }
-// { dg-error "no matching" "" { target *-*-* } 1455 }
+// { dg-error "no matching" "" { target *-*-* } 1505 }
 
 #include <list>