[v3] Add missing forward_list<>::splice_after and merge overloads fix splice_after taking a range
Paolo Carlini
paolo.carlini@oracle.com
Wed Apr 11 10:36:00 GMT 2012
Hi,
> Hi,
>
> Nico noticed in private email that we weren't implementing LWG 1310,
> thus I proceede to add the required overloads, pretty trivial work
> (suited for 4.7.1 too).
>
> But then, when I got to the testcases I noticed that really almost
> nothing worked as expected for the splice_after overload taking a
> range: memory leaks easily noticeable for existing testcases too; also
> showing up as "disappearing" elements of the destination forward_list;
> in some cases the end of the range improperly handled (thus, as ,
> last], instead of last), as must always be). Hey, we had a complexity
> much lower than the expected O(distance(first, last)) per C++11 ;)
> Thus I'm fixing this rather serious issue too. Have a look, tomorrow I
> mean to commit to mainline.
>
> Tested x86_64-linux, normal and debug (and a lot of valgrind too).
I'm going with something a bit more invasive, cleaning up a bit the _M_*
helpers.
Francois, can you please review the debug-mode checks for cases like:
std::forward_list<int> fl1(1), fl2(1);
fl1.splice_after(fl1.before_begin(), fl2, fl2.before_begin(),
fl2.begin());
?
I don't think we should error out. We don't for things like:
std::list<int> fl1(1), fl2(1);
fl1.splice(fl1.begin(), fl2, fl2.begin(), fl2.begin());
ie, the source is in both cases just an empty range, not an invalid range.
Thanks,
Paolo.
/////////////////////
-------------- next part --------------
2012-04-11 Paolo Carlini <paolo.carlini@oracle.com>
* include/bits/forward_list.h (splice_after(const_iterator,
forward_list&), splice_after(const_iterator, forward_list&,
consst_iterator), splice_after(const_iterator, forward_list&,
const_iterator, const_iterator), merge(forward_list&),
merge(forward_list&, _Comp)): Add per C++11 as published (and
LWG 1310).
* include/debug/forward_list: Adjust.
* include/bits/forward_list.h (splice_after(const_iterator,
forward_list&&, const_iterator)): Only declare.
(_M_transfer_after): Remove.
(_M_splice_after(const_iterator, forward_list&&)): Change signature.
(splice_after(const_iterator, forward_list&&, const_iterator,
const_iterator)): Use the latter.
* include/bits/forward_list.tcc (splice_after(const_iterator,
forward_list&&, const_iterator)): Define here.
(_M_splice_after): Define, use throughout.
* testsuite/23_containers/forward_list/modifiers/6.cc: New.
* testsuite/23_containers/forward_list/operations/1.cc: Adjust.
-------------- next part --------------
Index: include/debug/forward_list
===================================================================
--- include/debug/forward_list (revision 186297)
+++ include/debug/forward_list (working copy)
@@ -418,6 +418,10 @@
}
void
+ splice_after(const_iterator __pos, forward_list& __list)
+ { splice_after(__pos, std::move(__list)); }
+
+ void
splice_after(const_iterator __pos, forward_list&& __list,
const_iterator __i)
{
@@ -440,6 +444,11 @@
}
void
+ splice_after(const_iterator __pos, forward_list& __list,
+ const_iterator __i)
+ { splice_after(__pos, std::move(__list), __i); }
+
+ void
splice_after(const_iterator __pos, forward_list&& __list,
const_iterator __before, const_iterator __last)
{
@@ -485,6 +494,11 @@
}
void
+ splice_after(const_iterator __pos, forward_list& __list,
+ const_iterator __before, const_iterator __last)
+ { splice_after(__pos, std::move(__list), __before, __last); }
+
+ void
remove(const _Tp& __val)
{
_Base_iterator __x = _Base::before_begin();
@@ -565,6 +579,10 @@
}
}
+ void
+ merge(forward_list& __list)
+ { merge(std::move(__list)); }
+
template<typename _Comp>
void
merge(forward_list&& __list, _Comp __comp)
@@ -584,6 +602,11 @@
}
}
+ template<typename _Comp>
+ void
+ merge(forward_list& __list, _Comp __comp)
+ { merge(std::move(__list), __comp); }
+
using _Base::sort;
using _Base::reverse;
Index: include/bits/forward_list.h
===================================================================
--- include/bits/forward_list.h (revision 186297)
+++ include/bits/forward_list.h (working copy)
@@ -53,15 +53,6 @@
_Fwd_list_node_base* _M_next;
_Fwd_list_node_base*
- _M_transfer_after(_Fwd_list_node_base* __begin)
- {
- _Fwd_list_node_base* __end = __begin;
- while (__end && __end->_M_next)
- __end = __end->_M_next;
- return _M_transfer_after(__begin, __end);
- }
-
- _Fwd_list_node_base*
_M_transfer_after(_Fwd_list_node_base* __begin,
_Fwd_list_node_base* __end)
{
@@ -1047,9 +1038,13 @@
splice_after(const_iterator __pos, forward_list&& __list)
{
if (!__list.empty())
- _M_splice_after(__pos, std::move(__list));
+ _M_splice_after(__pos, __list.before_begin(), __list.end());
}
+ void
+ splice_after(const_iterator __pos, forward_list& __list)
+ { splice_after(__pos, std::move(__list)); }
+
/**
* @brief Insert element from another %forward_list.
* @param __pos Iterator referencing the element to insert after.
@@ -1062,16 +1057,13 @@
*/
void
splice_after(const_iterator __pos, forward_list&& __list,
+ const_iterator __i);
+
+ void
+ splice_after(const_iterator __pos, forward_list& __list,
const_iterator __i)
- {
- const_iterator __j = __i;
- ++__j;
- if (__pos == __i || __pos == __j)
- return;
+ { splice_after(__pos, std::move(__list), __i); }
- splice_after(__pos, std::move(__list), __i, __j);
- }
-
/**
* @brief Insert range from another %forward_list.
* @param __pos Iterator referencing the element to insert after.
@@ -1086,9 +1078,15 @@
* Undefined if @a __pos is in (__before,__last).
*/
void
- splice_after(const_iterator __pos, forward_list&& __list,
- const_iterator __before, const_iterator __last);
+ splice_after(const_iterator __pos, forward_list&&,
+ const_iterator __before, const_iterator __last)
+ { _M_splice_after(__pos, __before, __last); }
+ void
+ splice_after(const_iterator __pos, forward_list&,
+ const_iterator __before, const_iterator __last)
+ { _M_splice_after(__pos, __before, __last); }
+
/**
* @brief Remove all elements equal to value.
* @param __val The value to remove.
@@ -1130,7 +1128,7 @@
*/
void
unique()
- { this->unique(std::equal_to<_Tp>()); }
+ { unique(std::equal_to<_Tp>()); }
/**
* @brief Remove consecutive elements satisfying a predicate.
@@ -1159,8 +1157,12 @@
*/
void
merge(forward_list&& __list)
- { this->merge(std::move(__list), std::less<_Tp>()); }
+ { merge(std::move(__list), std::less<_Tp>()); }
+ void
+ merge(forward_list& __list)
+ { merge(std::move(__list)); }
+
/**
* @brief Merge sorted lists according to comparison function.
* @param __list Sorted list to merge.
@@ -1176,6 +1178,11 @@
void
merge(forward_list&& __list, _Comp __comp);
+ template<typename _Comp>
+ void
+ merge(forward_list& __list, _Comp __comp)
+ { merge(std::move(__list), __comp); }
+
/**
* @brief Sort the elements of the list.
*
@@ -1184,7 +1191,7 @@
*/
void
sort()
- { this->sort(std::less<_Tp>()); }
+ { sort(std::less<_Tp>()); }
/**
* @brief Sort the forward_list using a comparison function.
@@ -1218,7 +1225,8 @@
// Called by splice_after and insert_after.
iterator
- _M_splice_after(const_iterator __pos, forward_list&& __list);
+ _M_splice_after(const_iterator __pos, const_iterator __before,
+ const_iterator __last);
// Called by forward_list(n).
void
Index: include/bits/forward_list.tcc
===================================================================
--- include/bits/forward_list.tcc (revision 186297)
+++ include/bits/forward_list.tcc (working copy)
@@ -223,22 +223,37 @@
template<typename _Tp, typename _Alloc>
typename forward_list<_Tp, _Alloc>::iterator
forward_list<_Tp, _Alloc>::
- _M_splice_after(const_iterator __pos, forward_list&& __list)
+ _M_splice_after(const_iterator __pos,
+ const_iterator __before, const_iterator __last)
{
_Node_base* __tmp = const_cast<_Node_base*>(__pos._M_node);
- iterator __before = __list.before_begin();
- return iterator(__tmp->_M_transfer_after(__before._M_node));
+ _Node_base* __b = const_cast<_Node_base*>(__before._M_node);
+ _Node_base* __end = __b;
+
+ while (__end && __end->_M_next != __last._M_node)
+ __end = __end->_M_next;
+
+ if (__b != __end)
+ return iterator(__tmp->_M_transfer_after(__b, __end));
+ else
+ return iterator(const_cast<_Node_base*>(__pos._M_node));
}
template<typename _Tp, typename _Alloc>
void
forward_list<_Tp, _Alloc>::
splice_after(const_iterator __pos, forward_list&&,
- const_iterator __before, const_iterator __last)
+ const_iterator __i)
{
+ const_iterator __j = __i;
+ ++__j;
+
+ if (__pos == __i || __pos == __j)
+ return;
+
_Node_base* __tmp = const_cast<_Node_base*>(__pos._M_node);
- __tmp->_M_transfer_after(const_cast<_Node_base*>(__before._M_node),
- const_cast<_Node_base*>(__last._M_node));
+ __tmp->_M_transfer_after(const_cast<_Node_base*>(__i._M_node),
+ const_cast<_Node_base*>(__j._M_node));
}
template<typename _Tp, typename _Alloc>
@@ -249,7 +264,7 @@
if (__n)
{
forward_list __tmp(__n, __val, get_allocator());
- return _M_splice_after(__pos, std::move(__tmp));
+ return _M_splice_after(__pos, __tmp.before_begin(), __tmp.end());
}
else
return iterator(const_cast<_Node_base*>(__pos._M_node));
@@ -264,7 +279,7 @@
{
forward_list __tmp(__first, __last, get_allocator());
if (!__tmp.empty())
- return _M_splice_after(__pos, std::move(__tmp));
+ return _M_splice_after(__pos, __tmp.before_begin(), __tmp.end());
else
return iterator(const_cast<_Node_base*>(__pos._M_node));
}
@@ -277,7 +292,7 @@
if (__il.size())
{
forward_list __tmp(__il, get_allocator());
- return _M_splice_after(__pos, std::move(__tmp));
+ return _M_splice_after(__pos, __tmp.before_begin(), __tmp.end());
}
else
return iterator(const_cast<_Node_base*>(__pos._M_node));
Index: testsuite/23_containers/forward_list/modifiers/6.cc
===================================================================
--- testsuite/23_containers/forward_list/modifiers/6.cc (revision 0)
+++ testsuite/23_containers/forward_list/modifiers/6.cc (revision 0)
@@ -0,0 +1,94 @@
+// { dg-options "-std=gnu++11" }
+
+// Copyright (C) 2012 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without Pred the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <forward_list>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+
+ std::forward_list<int> fl1(1, 5), fl2(1, 4), fl3(1, 3),
+ fl4(1, 2), fl5(1, 1), fl6(1, 0);
+
+ fl1.splice_after(fl1.before_begin(), fl2);
+
+ auto it = fl1.begin();
+
+ VERIFY( *it == 4 );
+
+ ++it;
+
+ VERIFY( *it == 5 );
+
+ fl3.splice_after(fl3.before_begin(), fl4, fl4.before_begin());
+
+ it = fl3.begin();
+
+ VERIFY( *it == 2 );
+
+ ++it;
+
+ VERIFY( *it == 3 );
+
+ fl5.splice_after(fl5.before_begin(), fl6, fl6.before_begin(), fl6.end());
+
+ it = fl5.begin();
+
+ VERIFY( *it == 0 );
+
+ ++it;
+
+ VERIFY( *it == 1 );
+
+ fl1.merge(fl2);
+
+ it = fl1.begin();
+
+ VERIFY( *it == 4 );
+
+ ++it;
+
+ VERIFY( *it == 5 );
+
+ fl1.merge(fl3, std::less<int>());
+
+ it = fl1.begin();
+
+ VERIFY( *it == 2 );
+
+ ++it;
+
+ VERIFY( *it == 3 );
+
+ ++it;
+
+ VERIFY( *it == 4 );
+
+ ++it;
+
+ VERIFY( *it == 5 );
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
Index: testsuite/23_containers/forward_list/operations/1.cc
===================================================================
--- testsuite/23_containers/forward_list/operations/1.cc (revision 186297)
+++ testsuite/23_containers/forward_list/operations/1.cc (working copy)
@@ -1,6 +1,6 @@
// { dg-options "-std=gnu++0x" }
-// Copyright (C) 2008, 2009 Free Software Foundation, Inc.
+// Copyright (C) 2008, 2009, 2012 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the
@@ -68,7 +68,7 @@
VERIFY(*befy == 10.0);
++befy;
- VERIFY(*befy == 15.0);
+ VERIFY(*befy == 14.0);
}
// This test verifies the following:
More information about the Libstdc++
mailing list