From 4c58300a6e1e0c1712e419b7c57a46ea82fe6608 Mon Sep 17 00:00:00 2001 From: paolo Date: Sun, 8 Jan 2006 17:34:32 +0000 Subject: [PATCH] 2006-01-08 Paolo Carlini PR libstdc++/22102 (insert as close to hint as possible) * include/bits/stl_tree.h (_Rb_tree<>::_M_insert_lower, _M_insert_equal_lower): New. (_M_insert_equal(iterator, const _Val&), _M_insert_equal(const_iterator, const _Val&)): Use the above. * docs/html/ext/howto.html: Add an entry for DR 233. * testsuite/23_containers/multiset/modifiers/insert/22102.cc: New. * testsuite/23_containers/multimap/modifiers/insert/22102.cc: New. * testsuite/23_containers/set/insert/: Move... * testsuite/23_containers/set/modifiers/insert/: ...here. * testsuite/23_containers/map/insert/: Move... * testsuite/23_containers/map/modifiers/insert/: ...here. * testsuite/23_containers/multiset/insert/: Move... * testsuite/23_containers/multiset/modifiers/insert/: ...here. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@109473 138bc75d-0d04-0410-961f-82ee72b054a4 --- libstdc++-v3/ChangeLog | 18 +++ libstdc++-v3/docs/html/ext/howto.html | 7 + libstdc++-v3/include/bits/stl_tree.h | 49 ++++++- .../23_containers/map/{ => modifiers}/insert/1.cc | 0 .../map/{ => modifiers}/insert/16813.cc | 0 .../multimap/modifiers/insert/22102.cc | 141 +++++++++++++++++++++ .../multiset/{ => modifiers}/insert/1.cc | 0 .../multiset/{ => modifiers}/insert/2.cc | 0 .../multiset/modifiers/insert/22102.cc | 141 +++++++++++++++++++++ .../23_containers/set/{ => modifiers}/insert/1.cc | 0 10 files changed, 354 insertions(+), 2 deletions(-) rename libstdc++-v3/testsuite/23_containers/map/{ => modifiers}/insert/1.cc (100%) rename libstdc++-v3/testsuite/23_containers/map/{ => modifiers}/insert/16813.cc (100%) create mode 100644 libstdc++-v3/testsuite/23_containers/multimap/modifiers/insert/22102.cc rename libstdc++-v3/testsuite/23_containers/multiset/{ => modifiers}/insert/1.cc (100%) rename libstdc++-v3/testsuite/23_containers/multiset/{ => modifiers}/insert/2.cc (100%) create mode 100644 libstdc++-v3/testsuite/23_containers/multiset/modifiers/insert/22102.cc rename libstdc++-v3/testsuite/23_containers/set/{ => modifiers}/insert/1.cc (100%) diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 820d7c1..5e5e1b8 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,21 @@ +2006-01-08 Paolo Carlini + + PR libstdc++/22102 (insert as close to hint as possible) + * include/bits/stl_tree.h (_Rb_tree<>::_M_insert_lower, + _M_insert_equal_lower): New. + (_M_insert_equal(iterator, const _Val&), + _M_insert_equal(const_iterator, const _Val&)): Use the above. + * docs/html/ext/howto.html: Add an entry for DR 233. + * testsuite/23_containers/multiset/modifiers/insert/22102.cc: New. + * testsuite/23_containers/multimap/modifiers/insert/22102.cc: New. + + * testsuite/23_containers/set/insert/: Move... + * testsuite/23_containers/set/modifiers/insert/: ...here. + * testsuite/23_containers/map/insert/: Move... + * testsuite/23_containers/map/modifiers/insert/: ...here. + * testsuite/23_containers/multiset/insert/: Move... + * testsuite/23_containers/multiset/modifiers/insert/: ...here. + 2006-01-06 Paolo Carlini * include/bits/stl_tree.h (_Rb_tree<>::insert_unique): Rename diff --git a/libstdc++-v3/docs/html/ext/howto.html b/libstdc++-v3/docs/html/ext/howto.html index 9d86bc0..bc0b358 100644 --- a/libstdc++-v3/docs/html/ext/howto.html +++ b/libstdc++-v3/docs/html/ext/howto.html @@ -399,6 +399,13 @@ is specified in the conversion specification. +
233: + Insertion hints in associative containers +
+
Implement N1780, first check before then check after, insert as close + to hint as possible. +
+
235: No specification of default ctor for reverse_iterator
diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h index 031e37f..ecea171 100644 --- a/libstdc++-v3/include/bits/stl_tree.h +++ b/libstdc++-v3/include/bits/stl_tree.h @@ -548,6 +548,11 @@ _GLIBCXX_BEGIN_NAMESPACE(std) iterator _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v); + // _GLIBCXX_RESOLVE_LIB_DEFECTS + // 233. Insertion hints in associative containers. + iterator + _M_insert_lower(_Base_ptr __x, _Base_ptr __y, const value_type& __v); + const_iterator _M_insert(_Const_Base_ptr __x, _Const_Base_ptr __y, const value_type& __v); @@ -657,6 +662,11 @@ _GLIBCXX_BEGIN_NAMESPACE(std) iterator _M_insert_equal(const value_type& __x); + // _GLIBCXX_RESOLVE_LIB_DEFECTS + // 233. Insertion hints in associative containers. + iterator + _M_insert_equal_lower(const value_type& __x); + iterator _M_insert_unique(iterator __position, const value_type& __x); @@ -835,6 +845,24 @@ _GLIBCXX_BEGIN_NAMESPACE(std) template + typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator + _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: + _M_insert_lower(_Base_ptr __x, _Base_ptr __p, const _Val& __v) + { + bool __insert_left = (__x != 0 || __p == _M_end() + || !_M_impl._M_key_compare(_S_key(__p), + _KeyOfValue()(__v))); + + _Link_type __z = _M_create_node(__v); + + _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, + this->_M_impl._M_header); + ++_M_impl._M_node_count; + return iterator(__z); + } + + template typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: _M_insert(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v) @@ -871,6 +899,23 @@ _GLIBCXX_BEGIN_NAMESPACE(std) template + typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator + _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: + _M_insert_equal_lower(const _Val& __v) + { + _Link_type __x = _M_begin(); + _Link_type __y = _M_end(); + while (__x != 0) + { + __y = __x; + __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ? + _S_left(__x) : _S_right(__x); + } + return _M_insert_lower(__x, __y, __v); + } + + template void _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t) @@ -1110,7 +1155,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) return _M_insert(__after._M_node, __after._M_node, __v); } else - return _M_insert_equal(__v); + return _M_insert_equal_lower(__v); } } @@ -1164,7 +1209,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) return _M_insert(__after._M_node, __after._M_node, __v); } else - return const_iterator(_M_insert_equal(__v)); + return const_iterator(_M_insert_equal_lower(__v)); } } diff --git a/libstdc++-v3/testsuite/23_containers/map/insert/1.cc b/libstdc++-v3/testsuite/23_containers/map/modifiers/insert/1.cc similarity index 100% rename from libstdc++-v3/testsuite/23_containers/map/insert/1.cc rename to libstdc++-v3/testsuite/23_containers/map/modifiers/insert/1.cc diff --git a/libstdc++-v3/testsuite/23_containers/map/insert/16813.cc b/libstdc++-v3/testsuite/23_containers/map/modifiers/insert/16813.cc similarity index 100% rename from libstdc++-v3/testsuite/23_containers/map/insert/16813.cc rename to libstdc++-v3/testsuite/23_containers/map/modifiers/insert/16813.cc diff --git a/libstdc++-v3/testsuite/23_containers/multimap/modifiers/insert/22102.cc b/libstdc++-v3/testsuite/23_containers/multimap/modifiers/insert/22102.cc new file mode 100644 index 0000000..dfaf4c2 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/multimap/modifiers/insert/22102.cc @@ -0,0 +1,141 @@ +// 2006-01-07 Paolo Carlini + +// Copyright (C) 2006 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 2, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even 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 COPYING. If not, write to the Free +// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, +// USA. + +// 23.3.2 Class template multimap + +#include +#include + +// libstdc++/22102 +void test01() +{ + bool test __attribute__((unused)) = true; + typedef std::multimap Mmap; + typedef Mmap::value_type value_type; + typedef Mmap::iterator iterator; + + Mmap mm1; + + const iterator it1 = mm1.insert(value_type(0, 0)); + const iterator it2 = mm1.insert(value_type(1, 1)); + const iterator it3 = mm1.insert(value_type(2, 2)); + + const value_type vt1(2, 1); + const iterator it4 = mm1.insert(it1, vt1); + iterator it5 = it4; + iterator it6 = it4; + VERIFY( mm1.size() == 4 ); + VERIFY( *it4 == vt1 ); + VERIFY( ++it5 == it3 ); + VERIFY( --it6 == it2 ); + VERIFY( *it5 == *it3 ); + VERIFY( *it6 == *it2 ); + + const value_type vt2(2, 0); + const iterator it7 = mm1.insert(mm1.begin(), vt2); + iterator it8 = it7; + iterator it9 = it7; + VERIFY( mm1.size() == 5 ); + VERIFY( *it7 == vt2 ); + VERIFY( ++it8 == it4 ); + VERIFY( --it9 == it2 ); + VERIFY( *it8 == *it4 ); + VERIFY( *it9 == *it2 ); + + const value_type vt3(2, -1); + const iterator it10 = mm1.insert(it1, vt3); + iterator it11 = it10; + iterator it12 = it10; + VERIFY( mm1.size() == 6 ); + VERIFY( *it10 == vt3 ); + VERIFY( ++it11 == it7 ); + VERIFY( --it12 == it2 ); + VERIFY( *it11 == *it7 ); + VERIFY( *it12 == *it2 ); + + const value_type vt4(0, 1); + const iterator it13 = mm1.insert(it10, vt4); + iterator it14 = it13; + iterator it15 = it13; + VERIFY( mm1.size() == 7 ); + VERIFY( *it13 == vt4 ); + VERIFY( ++it14 == it2 ); + VERIFY( --it15 == it1 ); + VERIFY( *it14 == *it2 ); + VERIFY( *it15 == *it1 ); + + const value_type vt5(1, 0); + const iterator it16 = mm1.insert(it13, vt5); + iterator it17 = it16; + iterator it18 = it16; + VERIFY( mm1.size() == 8 ); + VERIFY( *it16 == vt5 ); + VERIFY( ++it17 == it2 ); + VERIFY( --it18 == it13 ); + VERIFY( *it17 == *it2 ); + VERIFY( *it18 == *it13 ); + + const value_type vt6(0, -1); + const iterator it19 = mm1.insert(it1, vt6); + iterator it20 = it19; + VERIFY( mm1.size() == 9 ); + VERIFY( *it19 == vt6 ); + VERIFY( it19 == mm1.begin() ); + VERIFY( ++it20 == it1 ); + VERIFY( *it20 == *it1 ); + + const value_type vt7(3, 3); + const iterator it21 = mm1.insert(it19, vt7); + iterator it22 = it21; + iterator it23 = it21; + VERIFY( mm1.size() == 10 ); + VERIFY( *it21 == vt7 ); + VERIFY( ++it22 == mm1.end() ); + VERIFY( --it23 == it3 ); + VERIFY( *it23 == *it3 ); + + const value_type vt8(2, 3); + const iterator it24 = mm1.insert(mm1.end(), vt8); + iterator it25 = it24; + iterator it26 = it24; + VERIFY( mm1.size() == 11 ); + VERIFY( *it24 == vt8 ); + VERIFY( ++it25 == it21 ); + VERIFY( --it26 == it3 ); + VERIFY( *it25 == *it21 ); + VERIFY( *it26 == *it3 ); + + const value_type vt9(3, 2); + const iterator it27 = mm1.insert(it3, vt9); + iterator it28 = it27; + iterator it29 = it27; + VERIFY( mm1.size() == 12 ); + VERIFY( *it27 == vt9 ); + VERIFY( ++it28 == it21 ); + VERIFY( --it29 == it24 ); + VERIFY( *it28 == *it21 ); + VERIFY( *it29 == *it24 ); +} + +int main() +{ + test01(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/multiset/insert/1.cc b/libstdc++-v3/testsuite/23_containers/multiset/modifiers/insert/1.cc similarity index 100% rename from libstdc++-v3/testsuite/23_containers/multiset/insert/1.cc rename to libstdc++-v3/testsuite/23_containers/multiset/modifiers/insert/1.cc diff --git a/libstdc++-v3/testsuite/23_containers/multiset/insert/2.cc b/libstdc++-v3/testsuite/23_containers/multiset/modifiers/insert/2.cc similarity index 100% rename from libstdc++-v3/testsuite/23_containers/multiset/insert/2.cc rename to libstdc++-v3/testsuite/23_containers/multiset/modifiers/insert/2.cc diff --git a/libstdc++-v3/testsuite/23_containers/multiset/modifiers/insert/22102.cc b/libstdc++-v3/testsuite/23_containers/multiset/modifiers/insert/22102.cc new file mode 100644 index 0000000..99b808f --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/multiset/modifiers/insert/22102.cc @@ -0,0 +1,141 @@ +// 2006-01-07 Paolo Carlini + +// Copyright (C) 2006 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 2, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even 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 COPYING. If not, write to the Free +// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, +// USA. + +// 23.3.4 Class template multiset + +#include +#include + +// libstdc++/22102 +void test01() +{ + bool test __attribute__((unused)) = true; + typedef std::multiset Mset; + typedef Mset::value_type value_type; + typedef Mset::iterator iterator; + + Mset ms1; + + const iterator it1 = ms1.insert(value_type(0)); + const iterator it2 = ms1.insert(value_type(1)); + const iterator it3 = ms1.insert(value_type(2)); + + const value_type vt1(2); + const iterator it4 = ms1.insert(it1, vt1); + iterator it5 = it4; + iterator it6 = it4; + VERIFY( ms1.size() == 4 ); + VERIFY( *it4 == vt1 ); + VERIFY( ++it5 == it3 ); + VERIFY( --it6 == it2 ); + VERIFY( *it5 == *it3 ); + VERIFY( *it6 == *it2 ); + + const value_type vt2(2); + const iterator it7 = ms1.insert(ms1.begin(), vt2); + iterator it8 = it7; + iterator it9 = it7; + VERIFY( ms1.size() == 5 ); + VERIFY( *it7 == vt2 ); + VERIFY( ++it8 == it4 ); + VERIFY( --it9 == it2 ); + VERIFY( *it8 == *it4 ); + VERIFY( *it9 == *it2 ); + + const value_type vt3(2); + const iterator it10 = ms1.insert(it1, vt3); + iterator it11 = it10; + iterator it12 = it10; + VERIFY( ms1.size() == 6 ); + VERIFY( *it10 == vt3 ); + VERIFY( ++it11 == it7 ); + VERIFY( --it12 == it2 ); + VERIFY( *it11 == *it7 ); + VERIFY( *it12 == *it2 ); + + const value_type vt4(0); + const iterator it13 = ms1.insert(it10, vt4); + iterator it14 = it13; + iterator it15 = it13; + VERIFY( ms1.size() == 7 ); + VERIFY( *it13 == vt4 ); + VERIFY( ++it14 == it2 ); + VERIFY( --it15 == it1 ); + VERIFY( *it14 == *it2 ); + VERIFY( *it15 == *it1 ); + + const value_type vt5(1); + const iterator it16 = ms1.insert(it13, vt5); + iterator it17 = it16; + iterator it18 = it16; + VERIFY( ms1.size() == 8 ); + VERIFY( *it16 == vt5 ); + VERIFY( ++it17 == it2 ); + VERIFY( --it18 == it13 ); + VERIFY( *it17 == *it2 ); + VERIFY( *it18 == *it13 ); + + const value_type vt6(0); + const iterator it19 = ms1.insert(it1, vt6); + iterator it20 = it19; + VERIFY( ms1.size() == 9 ); + VERIFY( *it19 == vt6 ); + VERIFY( it19 == ms1.begin() ); + VERIFY( ++it20 == it1 ); + VERIFY( *it20 == *it1 ); + + const value_type vt7(3); + const iterator it21 = ms1.insert(it19, vt7); + iterator it22 = it21; + iterator it23 = it21; + VERIFY( ms1.size() == 10 ); + VERIFY( *it21 == vt7 ); + VERIFY( ++it22 == ms1.end() ); + VERIFY( --it23 == it3 ); + VERIFY( *it23 == *it3 ); + + const value_type vt8(2); + const iterator it24 = ms1.insert(ms1.end(), vt8); + iterator it25 = it24; + iterator it26 = it24; + VERIFY( ms1.size() == 11 ); + VERIFY( *it24 == vt8 ); + VERIFY( ++it25 == it21 ); + VERIFY( --it26 == it3 ); + VERIFY( *it25 == *it21 ); + VERIFY( *it26 == *it3 ); + + const value_type vt9(3); + const iterator it27 = ms1.insert(it3, vt9); + iterator it28 = it27; + iterator it29 = it27; + VERIFY( ms1.size() == 12 ); + VERIFY( *it27 == vt9 ); + VERIFY( ++it28 == it21 ); + VERIFY( --it29 == it24 ); + VERIFY( *it28 == *it21 ); + VERIFY( *it29 == *it24 ); +} + +int main() +{ + test01(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/set/insert/1.cc b/libstdc++-v3/testsuite/23_containers/set/modifiers/insert/1.cc similarity index 100% rename from libstdc++-v3/testsuite/23_containers/set/insert/1.cc rename to libstdc++-v3/testsuite/23_containers/set/modifiers/insert/1.cc -- 2.7.4