[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 00:57:00 GMT 2012
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).
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.
* include/bits/forward_list.tcc: ... define, fixed, here.
(splice_after(const_iterator, forward_list&&, const_iterator,
const_iterator)): Fix (complexity is really O(distance(first,
last)), nothing less).
* 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)
@@ -1050,6 +1050,10 @@
_M_splice_after(__pos, std::move(__list));
}
+ 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 +1066,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.
@@ -1089,6 +1090,11 @@
splice_after(const_iterator __pos, forward_list&& __list,
const_iterator __before, const_iterator __last);
+ void
+ splice_after(const_iterator __pos, forward_list& __list,
+ const_iterator __before, const_iterator __last)
+ { splice_after(__pos, std::move(__list), __before, __last); }
+
/**
* @brief Remove all elements equal to value.
* @param __val The value to remove.
@@ -1130,7 +1136,7 @@
*/
void
unique()
- { this->unique(std::equal_to<_Tp>()); }
+ { unique(std::equal_to<_Tp>()); }
/**
* @brief Remove consecutive elements satisfying a predicate.
@@ -1159,8 +1165,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 +1186,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 +1199,7 @@
*/
void
sort()
- { this->sort(std::less<_Tp>()); }
+ { sort(std::less<_Tp>()); }
/**
* @brief Sort the forward_list using a comparison function.
Index: include/bits/forward_list.tcc
===================================================================
--- include/bits/forward_list.tcc (revision 186297)
+++ include/bits/forward_list.tcc (working copy)
@@ -233,12 +233,34 @@
template<typename _Tp, typename _Alloc>
void
forward_list<_Tp, _Alloc>::
+ splice_after(const_iterator __pos, forward_list&& __list,
+ 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*>(__i._M_node),
+ const_cast<_Node_base*>(__j._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)
{
_Node_base* __tmp = const_cast<_Node_base*>(__pos._M_node);
+ _Node_base* __end = const_cast<_Node_base*>(__before._M_node);
+
+ while (__end && __end->_M_next != __last._M_node)
+ __end = __end->_M_next;
+
__tmp->_M_transfer_after(const_cast<_Node_base*>(__before._M_node),
- const_cast<_Node_base*>(__last._M_node));
+ __end);
}
template<typename _Tp, typename _Alloc>
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,93 @@
+// { 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