From 55826ab6d1d050a8892e6dc45cf035c94db98dd0 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Fran=C3=A7ois=20Dumont?= Date: Mon, 24 Sep 2012 19:53:36 +0000 Subject: [PATCH] re PR libstdc++/44436 ([C++0x] Implement emplace* in associative containers) MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit 2012-09-24 François Dumont PR libstdc++/44436 * include/bits/stl_tree.h (_Rb_tree<>::_M_insert_): Take _Base_ptr rather than _Const_Base_ptr. (_Rb_tree<>::_M_insert_node): New. (_Rb_tree<>::_M_get_insert_unique_pos): New, search code of _M_insert_unique method. (_Rb_tree<>::_M_insert_unique): Use latter. (_Rb_tree<>::_M_emplace_unique): New, likewise. (_Rb_tree<>::_M_get_insert_equal_pos): New, search code of _M_insert_equal method. (_Rb_tree<>::_M_insert_equal): Use latter. (_Rb_tree<>::_M_emplace_equal): New, likewise. (_Rb_tree<>::_M_get_insert_hint_unique_pos): New, search code of _M_insert_unique_ method. (_Rb_tree<>::_M_insert_unique_): Use latter. (_Rb_tree<>::_M_emplace_hint_unique): New, likewise. (_Rb_tree<>::_M_get_insert_hint_equal_pos): New, search code of _M_insert_equal_ method. (_Rb_tree<>::_M_insert_equal_): Use latter. (_Rb_tree<>::_M_emplace_hint_equal): New, likewise. (_Rb_tree<>::_M_insert_lower): Remove first _Base_ptr parameter, useless as always null. * include/bits/stl_map.h: Include in C++11. (map<>::operator[](const key_type&)): Use _Rb_tree<>::_M_emplace_hint_unique in C++11. (map<>::operator[](key_type&&)): Likewise. (map<>::emplace): New. (map<>::emplace_hint): New. * include/bits/stl_multimap.h (multimap<>::emplace): New. (multimap<>::emplace_hint): New. * include/bits/stl_set.h (set<>::emplace): New. (set<>::emplace_hint): New. * include/bits/stl_multiset.h (multiset<>::emplace): New. (multiset<>::emplace_hint): New. * include/debug/map.h (std::__debug::map<>::emplace): New. (std::__debug::map<>::emplace_hint): New. * include/debug/multimap.h (std::__debug::multimap<>::emplace): New. (std::__debug::multimap<>::emplace_hint): New. * include/debug/set.h (std::__debug::set<>::emplace): New. (std::__debug::set<>::emplace_hint): New. * include/debug/multiset.h (std::__debug::multiset<>::emplace): New. (std::__debug::multiset<>::emplace_hint): New. * include/profile/map.h (std::__profile::map<>::emplace): New. (std::__profile::map<>::emplace_hint): New. * include/profile/multimap.h (std::__profile::multimap<>::emplace): New. (std::__profile::multimap<>::emplace_hint): New. * include/profile/set.h (std::__profile::set<>::emplace): New. (std::__profile::set<>::emplace_hint): New. * include/profile/multiset.h (std::__profile::multiset<>::emplace): New. (std::__profile::multiset<>::emplace_hint): New. * testsuite/util/testsuite_container_traits.h: Signal that emplace and emplace_hint are available on std::map, std::multimap, std::set and std::multiset in C++11. * testsuite/23_containers/map/operators/2.cc: New. * testsuite/23_containers/map/modifiers/emplace/1.cc: New. * testsuite/23_containers/multimap/modifiers/emplace/1.cc: New. * testsuite/23_containers/set/modifiers/emplace/1.cc: New. * testsuite/23_containers/multiset/modifiers/emplace/1.cc: New. From-SVN: r191679 --- libstdc++-v3/ChangeLog | 66 +++ libstdc++-v3/include/bits/stl_map.h | 69 ++- libstdc++-v3/include/bits/stl_multimap.h | 55 ++- libstdc++-v3/include/bits/stl_multiset.h | 50 ++- libstdc++-v3/include/bits/stl_set.h | 51 ++- libstdc++-v3/include/bits/stl_tree.h | 465 ++++++++++++++++----- libstdc++-v3/include/debug/map.h | 21 + libstdc++-v3/include/debug/multimap.h | 19 + libstdc++-v3/include/debug/multiset.h | 19 + libstdc++-v3/include/debug/set.h | 21 + libstdc++-v3/include/profile/map.h | 25 +- libstdc++-v3/include/profile/multimap.h | 17 + libstdc++-v3/include/profile/multiset.h | 15 + libstdc++-v3/include/profile/set.h | 19 + .../23_containers/map/modifiers/emplace/1.cc | 114 +++++ .../testsuite/23_containers/map/operators/2.cc | 87 ++++ .../23_containers/multimap/modifiers/emplace/1.cc | 108 +++++ .../23_containers/multiset/modifiers/emplace/1.cc | 79 ++++ .../23_containers/set/modifiers/emplace/1.cc | 81 ++++ .../testsuite/util/testsuite_container_traits.h | 12 + 20 files changed, 1277 insertions(+), 116 deletions(-) create mode 100644 libstdc++-v3/testsuite/23_containers/map/modifiers/emplace/1.cc create mode 100644 libstdc++-v3/testsuite/23_containers/map/operators/2.cc create mode 100644 libstdc++-v3/testsuite/23_containers/multimap/modifiers/emplace/1.cc create mode 100644 libstdc++-v3/testsuite/23_containers/multiset/modifiers/emplace/1.cc create mode 100644 libstdc++-v3/testsuite/23_containers/set/modifiers/emplace/1.cc diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 920bd33..98d3551 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,5 +1,71 @@ 2012-09-24 François Dumont + PR libstdc++/44436 + * include/bits/stl_tree.h + (_Rb_tree<>::_M_insert_): Take _Base_ptr rather than + _Const_Base_ptr. + (_Rb_tree<>::_M_insert_node): New. + (_Rb_tree<>::_M_get_insert_unique_pos): New, search code of + _M_insert_unique method. + (_Rb_tree<>::_M_insert_unique): Use latter. + (_Rb_tree<>::_M_emplace_unique): New, likewise. + (_Rb_tree<>::_M_get_insert_equal_pos): New, search code of + _M_insert_equal method. + (_Rb_tree<>::_M_insert_equal): Use latter. + (_Rb_tree<>::_M_emplace_equal): New, likewise. + (_Rb_tree<>::_M_get_insert_hint_unique_pos): New, search code of + _M_insert_unique_ method. + (_Rb_tree<>::_M_insert_unique_): Use latter. + (_Rb_tree<>::_M_emplace_hint_unique): New, likewise. + (_Rb_tree<>::_M_get_insert_hint_equal_pos): New, search code of + _M_insert_equal_ method. + (_Rb_tree<>::_M_insert_equal_): Use latter. + (_Rb_tree<>::_M_emplace_hint_equal): New, likewise. + (_Rb_tree<>::_M_insert_lower): Remove first _Base_ptr parameter, + useless as always null. + * include/bits/stl_map.h: Include in C++11. + (map<>::operator[](const key_type&)): Use + _Rb_tree<>::_M_emplace_hint_unique in C++11. + (map<>::operator[](key_type&&)): Likewise. + (map<>::emplace): New. + (map<>::emplace_hint): New. + * include/bits/stl_multimap.h (multimap<>::emplace): New. + (multimap<>::emplace_hint): New. + * include/bits/stl_set.h (set<>::emplace): New. + (set<>::emplace_hint): New. + * include/bits/stl_multiset.h (multiset<>::emplace): New. + (multiset<>::emplace_hint): New. + * include/debug/map.h (std::__debug::map<>::emplace): New. + (std::__debug::map<>::emplace_hint): New. + * include/debug/multimap.h (std::__debug::multimap<>::emplace): + New. + (std::__debug::multimap<>::emplace_hint): New. + * include/debug/set.h (std::__debug::set<>::emplace): New. + (std::__debug::set<>::emplace_hint): New. + * include/debug/multiset.h (std::__debug::multiset<>::emplace): + New. + (std::__debug::multiset<>::emplace_hint): New. + * include/profile/map.h (std::__profile::map<>::emplace): New. + (std::__profile::map<>::emplace_hint): New. + * include/profile/multimap.h (std::__profile::multimap<>::emplace): + New. + (std::__profile::multimap<>::emplace_hint): New. + * include/profile/set.h (std::__profile::set<>::emplace): New. + (std::__profile::set<>::emplace_hint): New. + * include/profile/multiset.h (std::__profile::multiset<>::emplace): + New. + (std::__profile::multiset<>::emplace_hint): New. + * testsuite/util/testsuite_container_traits.h: Signal that emplace + and emplace_hint are available on std::map, std::multimap, + std::set and std::multiset in C++11. + * testsuite/23_containers/map/operators/2.cc: New. + * testsuite/23_containers/map/modifiers/emplace/1.cc: New. + * testsuite/23_containers/multimap/modifiers/emplace/1.cc: New. + * testsuite/23_containers/set/modifiers/emplace/1.cc: New. + * testsuite/23_containers/multiset/modifiers/emplace/1.cc: New. + +2012-09-24 François Dumont + * testsuite/performance/23_containers/insert_erase/41975.cc: Use __uset_hashtable rather than removed __unordered_set. diff --git a/libstdc++-v3/include/bits/stl_map.h b/libstdc++-v3/include/bits/stl_map.h index cfd478a..14f4457 100644 --- a/libstdc++-v3/include/bits/stl_map.h +++ b/libstdc++-v3/include/bits/stl_map.h @@ -61,6 +61,7 @@ #include #ifdef __GXX_EXPERIMENTAL_CXX0X__ #include +#include #endif namespace std _GLIBCXX_VISIBILITY(default) @@ -461,7 +462,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER iterator __i = lower_bound(__k); // __i->first is greater than or equivalent to __k. if (__i == end() || key_comp()(__k, (*__i).first)) +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + __i = _M_t._M_emplace_hint_unique(__i, std::piecewise_construct, + std::tuple(__k), + std::tuple<>()); +#else __i = insert(__i, value_type(__k, mapped_type())); +#endif return (*__i).second; } @@ -475,7 +482,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER iterator __i = lower_bound(__k); // __i->first is greater than or equivalent to __k. if (__i == end() || key_comp()(__k, (*__i).first)) - __i = insert(__i, std::make_pair(std::move(__k), mapped_type())); + __i = _M_t._M_emplace_hint_unique(__i, std::piecewise_construct, + std::forward_as_tuple(std::move(__k)), + std::tuple<>()); return (*__i).second; } #endif @@ -508,6 +517,64 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER } // modifiers +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + /** + * @brief Attempts to build and insert a std::pair into the %map. + * + * @param __args Arguments used to generate a new pair instance (see + * std::piecewise_contruct for passing arguments to each + * part of the pair constructor). + * + * @return A pair, of which the first element is an iterator that points + * to the possibly inserted pair, and the second is a bool that + * is true if the pair was actually inserted. + * + * This function attempts to build and insert a (key, value) %pair into + * the %map. + * A %map relies on unique keys and thus a %pair is only inserted if its + * first element (the key) is not already present in the %map. + * + * Insertion requires logarithmic time. + */ + template + std::pair + emplace(_Args&&... __args) + { return _M_t._M_emplace_unique(std::forward<_Args>(__args)...); } + + /** + * @brief Attempts to build and insert a std::pair into the %map. + * + * @param __pos An iterator that serves as a hint as to where the pair + * should be inserted. + * @param __args Arguments used to generate a new pair instance (see + * std::piecewise_contruct for passing arguments to each + * part of the pair constructor). + * @return An iterator that points to the element with key of the + * std::pair built from @a __args (may or may not be that + * std::pair). + * + * This function is not concerned about whether the insertion took place, + * and thus does not return a boolean like the single-argument emplace() + * does. + * Note that the first parameter is only a hint and can potentially + * improve the performance of the insertion process. A bad hint would + * cause no gains in efficiency. + * + * See + * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html + * for more on @a hinting. + * + * Insertion requires logarithmic time (if the hint is not taken). + */ + template + iterator + emplace_hint(const_iterator __pos, _Args&&... __args) + { + return _M_t._M_emplace_hint_unique(__pos, + std::forward<_Args>(__args)...); + } +#endif + /** * @brief Attempts to insert a std::pair into the %map. diff --git a/libstdc++-v3/include/bits/stl_multimap.h b/libstdc++-v3/include/bits/stl_multimap.h index 6fc4787..a0fb27e2 100644 --- a/libstdc++-v3/include/bits/stl_multimap.h +++ b/libstdc++-v3/include/bits/stl_multimap.h @@ -108,7 +108,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER __glibcxx_class_requires(_Tp, _SGIAssignableConcept) __glibcxx_class_requires4(_Compare, bool, _Key, _Key, _BinaryFunctionConcept) - __glibcxx_class_requires2(value_type, _Alloc_value_type, _SameTypeConcept) + __glibcxx_class_requires2(value_type, _Alloc_value_type, _SameTypeConcept) public: class value_compare @@ -433,6 +433,59 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { return _M_t.max_size(); } // modifiers +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + /** + * @brief Build and insert a std::pair into the %multimap. + * + * @param __args Arguments used to generate a new pair instance (see + * std::piecewise_contruct for passing arguments to each + * part of the pair constructor). + * + * @return An iterator that points to the inserted (key,value) pair. + * + * This function builds and inserts a (key, value) %pair into the + * %multimap. + * Contrary to a std::map the %multimap does not rely on unique keys and + * thus multiple pairs with the same key can be inserted. + * + * Insertion requires logarithmic time. + */ + template + iterator + emplace(_Args&&... __args) + { return _M_t._M_emplace_equal(std::forward<_Args>(__args)...); } + + /** + * @brief Builds and inserts a std::pair into the %multimap. + * + * @param __pos An iterator that serves as a hint as to where the pair + * should be inserted. + * @param __args Arguments used to generate a new pair instance (see + * std::piecewise_contruct for passing arguments to each + * part of the pair constructor). + * @return An iterator that points to the inserted (key,value) pair. + * + * This function inserts a (key, value) pair into the %multimap. + * Contrary to a std::map the %multimap does not rely on unique keys and + * thus multiple pairs with the same key can be inserted. + * Note that the first parameter is only a hint and can potentially + * improve the performance of the insertion process. A bad hint would + * cause no gains in efficiency. + * + * For more on @a hinting, see: + * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html + * + * Insertion requires logarithmic time (if the hint is not taken). + */ + template + iterator + emplace_hint(const_iterator __pos, _Args&&... __args) + { + return _M_t._M_emplace_hint_equal(__pos, + std::forward<_Args>(__args)...); + } +#endif + /** * @brief Inserts a std::pair into the %multimap. * @param __x Pair to be inserted (see std::make_pair for easy creation diff --git a/libstdc++-v3/include/bits/stl_multiset.h b/libstdc++-v3/include/bits/stl_multiset.h index ecf9e54..2448742 100644 --- a/libstdc++-v3/include/bits/stl_multiset.h +++ b/libstdc++-v3/include/bits/stl_multiset.h @@ -1,7 +1,7 @@ // Multiset implementation -*- C++ -*- // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, -// 2011 Free Software Foundation, Inc. +// 2011, 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 @@ -392,6 +392,54 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { _M_t.swap(__x._M_t); } // insert/erase +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + /** + * @brief Builds and inserts an element into the %multiset. + * @param __args Arguments used to generate the element instance to be + * inserted. + * @return An iterator that points to the inserted element. + * + * This function inserts an element into the %multiset. Contrary + * to a std::set the %multiset does not rely on unique keys and thus + * multiple copies of the same element can be inserted. + * + * Insertion requires logarithmic time. + */ + template + iterator + emplace(_Args&&... __args) + { return _M_t._M_emplace_equal(std::forward<_Args>(__args)...); } + + /** + * @brief Builds and inserts an element into the %multiset. + * @param __pos An iterator that serves as a hint as to where the + * element should be inserted. + * @param __args Arguments used to generate the element instance to be + * inserted. + * @return An iterator that points to the inserted element. + * + * This function inserts an element into the %multiset. Contrary + * to a std::set the %multiset does not rely on unique keys and thus + * multiple copies of the same element can be inserted. + * + * Note that the first parameter is only a hint and can potentially + * improve the performance of the insertion process. A bad hint would + * cause no gains in efficiency. + * + * See http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html + * for more on @a hinting. + * + * Insertion requires logarithmic time (if the hint is not taken). + */ + template + iterator + emplace_hint(const_iterator __pos, _Args&&... __args) + { + return _M_t._M_emplace_hint_equal(__pos, + std::forward<_Args>(__args)...); + } +#endif + /** * @brief Inserts an element into the %multiset. * @param __x Element to be inserted. diff --git a/libstdc++-v3/include/bits/stl_set.h b/libstdc++-v3/include/bits/stl_set.h index 312e57a..c3c1870 100644 --- a/libstdc++-v3/include/bits/stl_set.h +++ b/libstdc++-v3/include/bits/stl_set.h @@ -1,7 +1,7 @@ // Set implementation -*- C++ -*- // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, -// 2011 Free Software Foundation, Inc. +// 2011, 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 @@ -395,6 +395,55 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { _M_t.swap(__x._M_t); } // insert/erase +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + /** + * @brief Attempts to build and insert an element into the %set. + * @param __args Arguments used to generate an element. + * @return A pair, of which the first element is an iterator that points + * to the possibly inserted element, and the second is a bool + * that is true if the element was actually inserted. + * + * This function attempts to build and insert an element into the %set. + * A %set relies on unique keys and thus an element is only inserted if + * it is not already present in the %set. + * + * Insertion requires logarithmic time. + */ + template + std::pair + emplace(_Args&&... __args) + { return _M_t._M_emplace_unique(std::forward<_Args>(__args)...); } + + /** + * @brief Attempts to insert an element into the %set. + * @param __pos An iterator that serves as a hint as to where the + * element should be inserted. + * @param __args Arguments used to generate the element to be + * inserted. + * @return An iterator that points to the element with key equivalent to + * the one generated from @a __args (may or may not be the + * element itself). + * + * This function is not concerned about whether the insertion took place, + * and thus does not return a boolean like the single-argument emplace() + * does. Note that the first parameter is only a hint and can + * potentially improve the performance of the insertion process. A bad + * hint would cause no gains in efficiency. + * + * For more on @a hinting, see: + * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html + * + * Insertion requires logarithmic time (if the hint is not taken). + */ + template + iterator + emplace_hint(const_iterator __pos, _Args&&... __args) + { + return _M_t._M_emplace_hint_unique(__pos, + std::forward<_Args>(__args)...); + } +#endif + /** * @brief Attempts to insert an element into the %set. * @param __x Element to be inserted. diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h index ee56bbc..f2adb96 100644 --- a/libstdc++-v3/include/bits/stl_tree.h +++ b/libstdc++-v3/include/bits/stl_tree.h @@ -570,27 +570,50 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typedef std::reverse_iterator const_reverse_iterator; private: + pair<_Base_ptr, _Base_ptr> + _M_get_insert_unique_pos(const key_type& __k); + + pair<_Base_ptr, _Base_ptr> + _M_get_insert_equal_pos(const key_type& __k); + + pair<_Base_ptr, _Base_ptr> + _M_get_insert_hint_unique_pos(const_iterator __pos, + const key_type& __k); + + pair<_Base_ptr, _Base_ptr> + _M_get_insert_hint_equal_pos(const_iterator __pos, + const key_type& __k); + #ifdef __GXX_EXPERIMENTAL_CXX0X__ template iterator - _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __y, _Arg&& __v); + _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v); + + iterator + _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Link_type __z); template iterator - _M_insert_lower(_Base_ptr __x, _Base_ptr __y, _Arg&& __v); + _M_insert_lower(_Base_ptr __y, _Arg&& __v); template iterator _M_insert_equal_lower(_Arg&& __x); + + iterator + _M_insert_lower_node(_Base_ptr __p, _Link_type __z); + + iterator + _M_insert_equal_lower_node(_Link_type __z); #else iterator - _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __y, + _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); + _M_insert_lower(_Base_ptr __y, const value_type& __v); iterator _M_insert_equal_lower(const value_type& __x); @@ -726,6 +749,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template iterator _M_insert_equal_(const_iterator __position, _Arg&& __x); + + template + pair + _M_emplace_unique(_Args&&... __args); + + template + iterator + _M_emplace_equal(_Args&&... __args); + + template + iterator + _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args); + + template + iterator + _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args); #else pair _M_insert_unique(const value_type& __x); @@ -967,19 +1006,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: #ifdef __GXX_EXPERIMENTAL_CXX0X__ - _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, _Arg&& __v) + _M_insert_(_Base_ptr __x, _Base_ptr __p, _Arg&& __v) #else - _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v) + _M_insert_(_Base_ptr __x, _Base_ptr __p, const _Val& __v) #endif { bool __insert_left = (__x != 0 || __p == _M_end() - || _M_impl._M_key_compare(_KeyOfValue()(__v), + || _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__p))); _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v)); - _Rb_tree_insert_and_rebalance(__insert_left, __z, - const_cast<_Base_ptr>(__p), + _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, this->_M_impl._M_header); ++_M_impl._M_node_count; return iterator(__z); @@ -993,18 +1031,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: #ifdef __GXX_EXPERIMENTAL_CXX0X__ - _M_insert_lower(_Base_ptr __x, _Base_ptr __p, _Arg&& __v) + _M_insert_lower(_Base_ptr __p, _Arg&& __v) #else - _M_insert_lower(_Base_ptr __x, _Base_ptr __p, const _Val& __v) + _M_insert_lower(_Base_ptr __p, const _Val& __v) #endif { - bool __insert_left = (__x != 0 || __p == _M_end() + bool __insert_left = (__p == _M_end() || !_M_impl._M_key_compare(_S_key(__p), _KeyOfValue()(__v))); _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v)); - _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, + _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, this->_M_impl._M_header); ++_M_impl._M_node_count; return iterator(__z); @@ -1031,7 +1069,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ? _S_left(__x) : _S_right(__x); } - return _M_insert_lower(__x, __y, _GLIBCXX_FORWARD(_Arg, __v)); + return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v)); } template -#ifdef __GXX_EXPERIMENTAL_CXX0X__ - template -#endif pair::iterator, bool> + _Compare, _Alloc>::_Base_ptr, + typename _Rb_tree<_Key, _Val, _KeyOfValue, + _Compare, _Alloc>::_Base_ptr> _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: -#ifdef __GXX_EXPERIMENTAL_CXX0X__ - _M_insert_unique(_Arg&& __v) -#else - _M_insert_unique(const _Val& __v) -#endif + _M_get_insert_unique_pos(const key_type& __k) { + typedef pair<_Base_ptr, _Base_ptr> _Res; _Link_type __x = _M_begin(); _Link_type __y = _M_end(); bool __comp = true; while (__x != 0) { __y = __x; - __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)); + __comp = _M_impl._M_key_compare(__k, _S_key(__x)); __x = __comp ? _S_left(__x) : _S_right(__x); } iterator __j = iterator(__y); if (__comp) { if (__j == begin()) - return pair - (_M_insert_(__x, __y, _GLIBCXX_FORWARD(_Arg, __v)), true); + return _Res(__x, __y); else --__j; } - if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v))) - return pair - (_M_insert_(__x, __y, _GLIBCXX_FORWARD(_Arg, __v)), true); - return pair(__j, false); + if (_M_impl._M_key_compare(_S_key(__j._M_node), __k)) + return _Res(__x, __y); + return _Res(__j._M_node, 0); } template -#ifdef __GXX_EXPERIMENTAL_CXX0X__ - template -#endif - typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator + pair::_Base_ptr, + typename _Rb_tree<_Key, _Val, _KeyOfValue, + _Compare, _Alloc>::_Base_ptr> _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: -#ifdef __GXX_EXPERIMENTAL_CXX0X__ - _M_insert_equal(_Arg&& __v) -#else - _M_insert_equal(const _Val& __v) -#endif + _M_get_insert_equal_pos(const key_type& __k) { + typedef pair<_Base_ptr, _Base_ptr> _Res; _Link_type __x = _M_begin(); _Link_type __y = _M_end(); while (__x != 0) { __y = __x; - __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ? + __x = _M_impl._M_key_compare(__k, _S_key(__x)) ? _S_left(__x) : _S_right(__x); } - return _M_insert_(__x, __y, _GLIBCXX_FORWARD(_Arg, __v)); + return _Res(__x, __y); + } + + template +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + template +#endif + pair::iterator, bool> + _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + _M_insert_unique(_Arg&& __v) +#else + _M_insert_unique(const _Val& __v) +#endif + { + typedef pair _Res; + pair<_Base_ptr, _Base_ptr> __res + = _M_get_insert_unique_pos(_KeyOfValue()(__v)); + + if (__res.second) + return _Res(_M_insert_(__res.first, __res.second, + _GLIBCXX_FORWARD(_Arg, __v)), + true); + + return _Res(iterator(static_cast<_Link_type>(__res.first)), false); } template::iterator _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: #ifdef __GXX_EXPERIMENTAL_CXX0X__ - _M_insert_unique_(const_iterator __position, _Arg&& __v) + _M_insert_equal(_Arg&& __v) #else - _M_insert_unique_(const_iterator __position, const _Val& __v) + _M_insert_equal(const _Val& __v) #endif { + pair<_Base_ptr, _Base_ptr> __res + = _M_get_insert_equal_pos(_KeyOfValue()(__v)); + return _M_insert_(__res.first, __res.second, _GLIBCXX_FORWARD(_Arg, __v)); + } + + template + pair::_Base_ptr, + typename _Rb_tree<_Key, _Val, _KeyOfValue, + _Compare, _Alloc>::_Base_ptr> + _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: + _M_get_insert_hint_unique_pos(const_iterator __position, + const key_type& __k) + { + iterator __pos = __position._M_const_cast(); + typedef pair<_Base_ptr, _Base_ptr> _Res; + // end() - if (__position._M_node == _M_end()) + if (__pos._M_node == _M_end()) { if (size() > 0 - && _M_impl._M_key_compare(_S_key(_M_rightmost()), - _KeyOfValue()(__v))) - return _M_insert_(0, _M_rightmost(), _GLIBCXX_FORWARD(_Arg, __v)); + && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k)) + return _Res(0, _M_rightmost()); else - return _M_insert_unique(_GLIBCXX_FORWARD(_Arg, __v)).first; + return _M_get_insert_unique_pos(__k); } - else if (_M_impl._M_key_compare(_KeyOfValue()(__v), - _S_key(__position._M_node))) + else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node))) { // First, try before... - const_iterator __before = __position; - if (__position._M_node == _M_leftmost()) // begin() - return _M_insert_(_M_leftmost(), _M_leftmost(), - _GLIBCXX_FORWARD(_Arg, __v)); - else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), - _KeyOfValue()(__v))) + iterator __before = __pos; + if (__pos._M_node == _M_leftmost()) // begin() + return _Res(_M_leftmost(), _M_leftmost()); + else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k)) { if (_S_right(__before._M_node) == 0) - return _M_insert_(0, __before._M_node, - _GLIBCXX_FORWARD(_Arg, __v)); + return _Res(0, __before._M_node); else - return _M_insert_(__position._M_node, - __position._M_node, - _GLIBCXX_FORWARD(_Arg, __v)); + return _Res(__pos._M_node, __pos._M_node); } else - return _M_insert_unique(_GLIBCXX_FORWARD(_Arg, __v)).first; + return _M_get_insert_unique_pos(__k); } - else if (_M_impl._M_key_compare(_S_key(__position._M_node), - _KeyOfValue()(__v))) + else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k)) { // ... then try after. - const_iterator __after = __position; - if (__position._M_node == _M_rightmost()) - return _M_insert_(0, _M_rightmost(), - _GLIBCXX_FORWARD(_Arg, __v)); - else if (_M_impl._M_key_compare(_KeyOfValue()(__v), - _S_key((++__after)._M_node))) + iterator __after = __pos; + if (__pos._M_node == _M_rightmost()) + return _Res(0, _M_rightmost()); + else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node))) { - if (_S_right(__position._M_node) == 0) - return _M_insert_(0, __position._M_node, - _GLIBCXX_FORWARD(_Arg, __v)); + if (_S_right(__pos._M_node) == 0) + return _Res(0, __pos._M_node); else - return _M_insert_(__after._M_node, __after._M_node, - _GLIBCXX_FORWARD(_Arg, __v)); + return _Res(__after._M_node, __after._M_node); } else - return _M_insert_unique(_GLIBCXX_FORWARD(_Arg, __v)).first; + return _M_get_insert_unique_pos(__k); } else // Equivalent keys. - return __position._M_const_cast(); + return _Res(__pos._M_node, 0); } template::iterator _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: #ifdef __GXX_EXPERIMENTAL_CXX0X__ - _M_insert_equal_(const_iterator __position, _Arg&& __v) + _M_insert_unique_(const_iterator __position, _Arg&& __v) #else - _M_insert_equal_(const_iterator __position, const _Val& __v) + _M_insert_unique_(const_iterator __position, const _Val& __v) #endif { + pair<_Base_ptr, _Base_ptr> __res + = _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v)); + + if (__res.second) + return _M_insert_(__res.first, __res.second, + _GLIBCXX_FORWARD(_Arg, __v)); + return iterator(static_cast<_Link_type>(__res.first)); + } + + template + pair::_Base_ptr, + typename _Rb_tree<_Key, _Val, _KeyOfValue, + _Compare, _Alloc>::_Base_ptr> + _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: + _M_get_insert_hint_equal_pos(const_iterator __position, const key_type& __k) + { + iterator __pos = __position._M_const_cast(); + typedef pair<_Base_ptr, _Base_ptr> _Res; + // end() - if (__position._M_node == _M_end()) + if (__pos._M_node == _M_end()) { if (size() > 0 - && !_M_impl._M_key_compare(_KeyOfValue()(__v), - _S_key(_M_rightmost()))) - return _M_insert_(0, _M_rightmost(), - _GLIBCXX_FORWARD(_Arg, __v)); + && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost()))) + return _Res(0, _M_rightmost()); else - return _M_insert_equal(_GLIBCXX_FORWARD(_Arg, __v)); + return _M_get_insert_equal_pos(__k); } - else if (!_M_impl._M_key_compare(_S_key(__position._M_node), - _KeyOfValue()(__v))) + else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k)) { // First, try before... - const_iterator __before = __position; - if (__position._M_node == _M_leftmost()) // begin() - return _M_insert_(_M_leftmost(), _M_leftmost(), - _GLIBCXX_FORWARD(_Arg, __v)); - else if (!_M_impl._M_key_compare(_KeyOfValue()(__v), - _S_key((--__before)._M_node))) + iterator __before = __pos; + if (__pos._M_node == _M_leftmost()) // begin() + return _Res(_M_leftmost(), _M_leftmost()); + else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node))) { if (_S_right(__before._M_node) == 0) - return _M_insert_(0, __before._M_node, - _GLIBCXX_FORWARD(_Arg, __v)); + return _Res(0, __before._M_node); else - return _M_insert_(__position._M_node, - __position._M_node, - _GLIBCXX_FORWARD(_Arg, __v)); + return _Res(__pos._M_node, __pos._M_node); } else - return _M_insert_equal(_GLIBCXX_FORWARD(_Arg, __v)); + return _M_get_insert_equal_pos(__k); } else { // ... then try after. - const_iterator __after = __position; - if (__position._M_node == _M_rightmost()) - return _M_insert_(0, _M_rightmost(), - _GLIBCXX_FORWARD(_Arg, __v)); - else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), - _KeyOfValue()(__v))) + iterator __after = __pos; + if (__pos._M_node == _M_rightmost()) + return _Res(0, _M_rightmost()); + else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k)) { - if (_S_right(__position._M_node) == 0) - return _M_insert_(0, __position._M_node, - _GLIBCXX_FORWARD(_Arg, __v)); + if (_S_right(__pos._M_node) == 0) + return _Res(0, __pos._M_node); else - return _M_insert_(__after._M_node, __after._M_node, - _GLIBCXX_FORWARD(_Arg, __v)); + return _Res(__after._M_node, __after._M_node); } else - return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v)); + return _Res(0, 0); } } + template +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + template +#endif + typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator + _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + _M_insert_equal_(const_iterator __position, _Arg&& __v) +#else + _M_insert_equal_(const_iterator __position, const _Val& __v) +#endif + { + pair<_Base_ptr, _Base_ptr> __res + = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v)); + + if (__res.second) + return _M_insert_(__res.first, __res.second, + _GLIBCXX_FORWARD(_Arg, __v)); + + return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v)); + } + +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + template + typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator + _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: + _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z) + { + bool __insert_left = (__x != 0 || __p == _M_end() + || _M_impl._M_key_compare(_S_key(__z), + _S_key(__p))); + + _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>::iterator + _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: + _M_insert_lower_node(_Base_ptr __p, _Link_type __z) + { + bool __insert_left = (__p == _M_end() + || !_M_impl._M_key_compare(_S_key(__p), + _S_key(__z))); + + _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>::iterator + _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: + _M_insert_equal_lower_node(_Link_type __z) + { + _Link_type __x = _M_begin(); + _Link_type __y = _M_end(); + while (__x != 0) + { + __y = __x; + __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ? + _S_left(__x) : _S_right(__x); + } + return _M_insert_lower_node(__y, __z); + } + + template + template + pair::iterator, bool> + _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: + _M_emplace_unique(_Args&&... __args) + { + _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); + + __try + { + typedef pair _Res; + auto __res = _M_get_insert_unique_pos(_S_key(__z)); + if (__res.second) + return _Res(_M_insert_node(__res.first, __res.second, __z), true); + + _M_destroy_node(__z); + return _Res(iterator(static_cast<_Link_type>(__res.first)), false); + } + __catch(...) + { + _M_destroy_node(__z); + __throw_exception_again; + } + } + + template + template + typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator + _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: + _M_emplace_equal(_Args&&... __args) + { + _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); + + __try + { + auto __res = _M_get_insert_equal_pos(_S_key(__z)); + return _M_insert_node(__res.first, __res.second, __z); + } + __catch(...) + { + _M_destroy_node(__z); + __throw_exception_again; + } + } + + template + template + typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator + _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: + _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args) + { + _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); + + __try + { + auto __res = _M_get_insert_hint_unique_pos(__pos, _S_key(__z)); + + if (__res.second) + return _M_insert_node(__res.first, __res.second, __z); + + _M_destroy_node(__z); + return iterator(static_cast<_Link_type>(__res.first)); + } + __catch(...) + { + _M_destroy_node(__z); + __throw_exception_again; + } + } + + template + template + typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator + _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: + _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args) + { + _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); + + __try + { + auto __res = _M_get_insert_hint_equal_pos(__pos, _S_key(__z)); + + if (__res.second) + return _M_insert_node(__res.first, __res.second, __z); + + return _M_insert_equal_lower_node(__z); + } + __catch(...) + { + _M_destroy_node(__z); + __throw_exception_again; + } + } +#endif + template template diff --git a/libstdc++-v3/include/debug/map.h b/libstdc++-v3/include/debug/map.h index 95871ac..254988c 100644 --- a/libstdc++-v3/include/debug/map.h +++ b/libstdc++-v3/include/debug/map.h @@ -203,6 +203,27 @@ namespace __debug using _Base::at; // modifiers: +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + template + std::pair + emplace(_Args&&... __args) + { + auto __res = _Base::emplace(std::forward<_Args>(__args)...); + return std::pair(iterator(__res.first, this), + __res.second); + } + + template + iterator + emplace_hint(const_iterator __pos, _Args&&... __args) + { + __glibcxx_check_insert(__pos); + return iterator(_Base::emplace_hint(__pos.base(), + std::forward<_Args>(__args)...), + this); + } +#endif + std::pair insert(const value_type& __x) { diff --git a/libstdc++-v3/include/debug/multimap.h b/libstdc++-v3/include/debug/multimap.h index e1e09bc..e46a742 100644 --- a/libstdc++-v3/include/debug/multimap.h +++ b/libstdc++-v3/include/debug/multimap.h @@ -195,6 +195,25 @@ namespace __debug using _Base::max_size; // modifiers: +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + template + iterator + emplace(_Args&&... __args) + { + return iterator(_Base::emplace(std::forward<_Args>(__args)...), this); + } + + template + iterator + emplace_hint(const_iterator __pos, _Args&&... __args) + { + __glibcxx_check_insert(__pos); + return iterator(_Base::emplace_hint(__pos.base(), + std::forward<_Args>(__args)...), + this); + } +#endif + iterator insert(const value_type& __x) { return iterator(_Base::insert(__x), this); } diff --git a/libstdc++-v3/include/debug/multiset.h b/libstdc++-v3/include/debug/multiset.h index c7f38ea..0459846 100644 --- a/libstdc++-v3/include/debug/multiset.h +++ b/libstdc++-v3/include/debug/multiset.h @@ -194,6 +194,25 @@ namespace __debug using _Base::max_size; // modifiers: +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + template + iterator + emplace(_Args&&... __args) + { + return iterator(_Base::emplace(std::forward<_Args>(__args)...), this); + } + + template + iterator + emplace_hint(const_iterator __pos, _Args&&... __args) + { + __glibcxx_check_insert(__pos); + return iterator(_Base::emplace_hint(__pos.base(), + std::forward<_Args>(__args)...), + this); + } +#endif + iterator insert(const value_type& __x) { return iterator(_Base::insert(__x), this); } diff --git a/libstdc++-v3/include/debug/set.h b/libstdc++-v3/include/debug/set.h index d6dc06f..44cbe94 100644 --- a/libstdc++-v3/include/debug/set.h +++ b/libstdc++-v3/include/debug/set.h @@ -194,6 +194,27 @@ namespace __debug using _Base::max_size; // modifiers: +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + template + std::pair + emplace(_Args&&... __args) + { + auto __res = _Base::emplace(std::forward<_Args>(__args)...); + return std::pair(iterator(__res.first, this), + __res.second); + } + + template + iterator + emplace_hint(const_iterator __pos, _Args&&... __args) + { + __glibcxx_check_insert(__pos); + return iterator(_Base::emplace_hint(__pos.base(), + std::forward<_Args>(__args)...), + this); + } +#endif + std::pair insert(const value_type& __x) { diff --git a/libstdc++-v3/include/profile/map.h b/libstdc++-v3/include/profile/map.h index 42c32aa..cc01d90 100644 --- a/libstdc++-v3/include/profile/map.h +++ b/libstdc++-v3/include/profile/map.h @@ -236,6 +236,29 @@ namespace __profile } // modifiers: +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + template + std::pair + emplace(_Args&&... __args) + { + __profcxx_map_to_unordered_map_insert(this, size(), 1); + auto __res = _Base::emplace(std::forward<_Args>(__args)...); + return std::pair(iterator(__res.first), + __res.second); + } + + template + iterator + emplace_hint(const_iterator __pos, _Args&&... __args) + { + size_type size_before = size(); + auto __res = _Base::emplace_hint(__pos.base(), + std::forward<_Args>(__args)...)); + __profcxx_map_to_unordered_map_insert(this, size_before, + size() - size_before); + } +#endif + std::pair insert(const value_type& __x) { @@ -282,7 +305,7 @@ namespace __profile { size_type size_before = size(); iterator __i = iterator(_Base::insert(__position, __x)); - __profcxx_map_to_unordered_map_insert(this, size_before, + __profcxx_map_to_unordered_map_insert(this, size_before, size() - size_before); return __i; } diff --git a/libstdc++-v3/include/profile/multimap.h b/libstdc++-v3/include/profile/multimap.h index 608d6b7..2268161 100644 --- a/libstdc++-v3/include/profile/multimap.h +++ b/libstdc++-v3/include/profile/multimap.h @@ -180,6 +180,23 @@ namespace __profile using _Base::max_size; // modifiers: +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + template + iterator + emplace(_Args&&... __args) + { + return iterator(_Base::emplace(std::forward<_Args>(__args)...)); + } + + template + iterator + emplace_hint(const_iterator __pos, _Args&&... __args) + { + return iterator(_Base::emplace_hint(__pos, + std::forward<_Args>(__args)...)); + } +#endif + iterator insert(const value_type& __x) { return iterator(_Base::insert(__x)); } diff --git a/libstdc++-v3/include/profile/multiset.h b/libstdc++-v3/include/profile/multiset.h index a577938..f76b4fa 100644 --- a/libstdc++-v3/include/profile/multiset.h +++ b/libstdc++-v3/include/profile/multiset.h @@ -180,6 +180,21 @@ namespace __profile using _Base::max_size; // modifiers: +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + template + iterator + emplace(_Args&&... __args) + { return iterator(_Base::emplace(std::forward<_Args>(__args)...)); } + + template + iterator + emplace_hint(const_iterator __pos, _Args&&... __args) + { + return iterator(_Base::emplace_hint(__pos, + std::forward<_Args>(__args)...)); + } +#endif + iterator insert(const value_type& __x) { return iterator(_Base::insert(__x)); } diff --git a/libstdc++-v3/include/profile/set.h b/libstdc++-v3/include/profile/set.h index 47261e9..c0aa180 100644 --- a/libstdc++-v3/include/profile/set.h +++ b/libstdc++-v3/include/profile/set.h @@ -180,6 +180,25 @@ namespace __profile using _Base::max_size; // modifiers: +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + template + std::pair + emplace(_Args&&... __args) + { + auto __res = _Base::emplace(std::forward<_Args>(__args)...); + return std::pair(iterator(__res.first), + __res.second); + } + + template + iterator + emplace_hint(const_iterator __pos, _Args&&... __args) + { + return iterator(_Base::emplace_hint(__pos, + std::forward<_Args>(__args)...)); + } +#endif + std::pair insert(const value_type& __x) { diff --git a/libstdc++-v3/testsuite/23_containers/map/modifiers/emplace/1.cc b/libstdc++-v3/testsuite/23_containers/map/modifiers/emplace/1.cc new file mode 100644 index 0000000..bd25604 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/map/modifiers/emplace/1.cc @@ -0,0 +1,114 @@ +// { dg-options "-std=c++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 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 COPYING3. If not see +// . + +#include +#include +#include +#include +#include + +class PathPoint +{ +public: + PathPoint(char t, const std::vector& c) + : type(t), coords(c) { } + PathPoint(char t, std::vector&& c) + : type(t), coords(std::move(c)) { } + char getType() const { return type; } + const std::vector& getCoords() const { return coords; } +private: + char type; + std::vector coords; +}; + +bool test __attribute__((unused)) = true; + +void test01() +{ + typedef std::map> Map; + Map m; + + std::vector coord1 = { 0.0, 1.0, 2.0 }; + + auto ret = m.emplace('a', coord1); + VERIFY( ret.second ); + VERIFY( m.size() == 1 ); + VERIFY( ret.first->first == 'a' ); + + coord1[0] = 3.0; + ret = m.emplace('a', coord1); + VERIFY( !ret.second ); + VERIFY( m.size() == 1 ); + VERIFY( ret.first->first == 'a' ); + VERIFY( ret.first->second[0] == 0.0 ); + + auto it = m.emplace_hint(m.begin(), 'b', coord1); + VERIFY( it != m.end() ); + VERIFY( it->first == 'b' ); + VERIFY( it->second[0] == 3.0 ); + + double *px = &coord1[0]; + ret = m.emplace('c', std::move(coord1)); + VERIFY( ret.second ); + VERIFY( ret.first->first == 'c' ); + VERIFY( &(ret.first->second[0]) == px ); +} + +void test02() +{ + using namespace std; + typedef map Map; + Map m; + + vector coord1 = { 0.0, 1.0, 2.0 }; + + auto ret = m.emplace(piecewise_construct, + make_tuple('a'), make_tuple('a', coord1)); + VERIFY( ret.second ); + VERIFY( m.size() == 1 ); + VERIFY( ret.first->first == 'a' ); + + coord1[0] = 3.0; + ret = m.emplace(piecewise_construct, + make_tuple('a'), make_tuple( 'b', coord1)); + VERIFY( !ret.second ); + VERIFY( m.size() == 1 ); + VERIFY( ret.first->first == 'a' ); + VERIFY( ret.first->second.getCoords()[0] == 0.0 ); + + auto it = m.emplace_hint(m.begin(), piecewise_construct, + make_tuple('b'), make_tuple('c', coord1)); + VERIFY( it != m.end() ); + VERIFY( it->first == 'b' ); + VERIFY( it->second.getCoords()[0] == 3.0 ); + + double *px = &coord1[0]; + ret = m.emplace(piecewise_construct, + make_tuple('c'), make_tuple('d', move(coord1))); + VERIFY( ret.second ); + VERIFY( ret.first->first == 'c' ); + VERIFY( &(ret.first->second.getCoords()[0]) == px ); +} + +int main() +{ + test01(); + test02(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/map/operators/2.cc b/libstdc++-v3/testsuite/23_containers/map/operators/2.cc new file mode 100644 index 0000000..0d8a183 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/map/operators/2.cc @@ -0,0 +1,87 @@ +// 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 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 COPYING3. If not see +// . + +// This test verifies that the value type of a map need not be default copyable. + +// { dg-options "-std=c++11" } + +#include +#include +#include +#include + +struct Mapped +{ + Mapped() = default; + explicit Mapped(const Mapped&) = default; +}; + +struct DefaultConstructibleType +{ + int val; + + DefaultConstructibleType() : val(123) + {} + + DefaultConstructibleType(const DefaultConstructibleType&) = delete; + DefaultConstructibleType(DefaultConstructibleType&&) = delete; + + DefaultConstructibleType& operator=(int x) + { + val = x; + return *this; + } +}; + +void test01() +{ + bool test __attribute__((unused)) = true; + + using __gnu_test::rvalstruct; + using __gnu_test::counter_type; + + std::map m1; + m1[0] = Mapped(); + + std::map m2; + m2[0] = rvalstruct(13); + + std::map m3; + VERIFY( m3[0].val == 123 ); + VERIFY( m3.size() == 1 ); + m3[0] = 2; + VERIFY( m3[0].val == 2 ); + + std::map m4; + VERIFY( m4[counter_type(1)] == 0 ); + VERIFY( counter_type::specialize_count == 1 ); + VERIFY( counter_type::copy_count == 0 ); + VERIFY( counter_type::move_count == 1 ); + + counter_type k(2); + counter_type::reset(); + + VERIFY( m4[k] == 0 ); + VERIFY( counter_type::copy_count == 1 ); + VERIFY( counter_type::move_count == 0 ); +} + +int main() +{ + test01(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/multimap/modifiers/emplace/1.cc b/libstdc++-v3/testsuite/23_containers/multimap/modifiers/emplace/1.cc new file mode 100644 index 0000000..71ca8a9 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/multimap/modifiers/emplace/1.cc @@ -0,0 +1,108 @@ +// { dg-options "-std=c++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 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 COPYING3. If not see +// . + +#include +#include +#include +#include + +class PathPoint +{ +public: + PathPoint(char t, const std::vector& c) + : type(t), coords(c) { } + PathPoint(char t, std::vector&& c) + : type(t), coords(std::move(c)) { } + char getType() const { return type; } + const std::vector& getCoords() const { return coords; } +private: + char type; + std::vector coords; +}; + +bool test __attribute__((unused)) = true; + +void test01() +{ + typedef std::multimap> MMap; + MMap mm; + + std::vector coord1 = { 0.0, 1.0, 2.0 }; + + auto it = mm.emplace('a', coord1); + VERIFY( mm.size() == 1 ); + VERIFY( it->first == 'a' ); + + coord1[0] = 3.0; + it = mm.emplace('a', coord1); + VERIFY( mm.size() == 2 ); + VERIFY( it->first == 'a' ); + VERIFY( it->second[0] == 3.0 ); + + it = mm.emplace_hint(mm.begin(), 'b', coord1); + VERIFY( it != mm.end() ); + VERIFY( it->first == 'b' ); + VERIFY( it->second[0] == 3.0 ); + + double *px = &coord1[0]; + it = mm.emplace('c', std::move(coord1)); + VERIFY( it->first == 'c' ); + VERIFY( &(it->second[0]) == px ); +} + +void test02() +{ + using namespace std; + typedef multimap Map; + Map m; + + vector coord1 = { 0.0, 1.0, 2.0 }; + + auto it = m.emplace(piecewise_construct, + make_tuple('a'), make_tuple('a', coord1)); + VERIFY( m.size() == 1 ); + VERIFY( it->first == 'a' ); + + coord1[0] = 3.0; + it = m.emplace(piecewise_construct, + make_tuple('a'), make_tuple( 'b', coord1)); + VERIFY( m.size() == 2 ); + VERIFY( it->first == 'a' ); + VERIFY( it->second.getCoords()[0] == 3.0 ); + + it = m.emplace_hint(m.begin(), piecewise_construct, + make_tuple('b'), make_tuple('c', coord1)); + VERIFY( it != m.end() ); + VERIFY( it->first == 'b' ); + VERIFY( it->second.getCoords()[0] == 3.0 ); + + double *px = &coord1[0]; + it = m.emplace(piecewise_construct, + make_tuple('c'), make_tuple('d', move(coord1))); + VERIFY( it->first == 'c' ); + VERIFY( &(it->second.getCoords()[0]) == px ); +} + + +int main() +{ + test01(); + test02(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/multiset/modifiers/emplace/1.cc b/libstdc++-v3/testsuite/23_containers/multiset/modifiers/emplace/1.cc new file mode 100644 index 0000000..3a1e38c --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/multiset/modifiers/emplace/1.cc @@ -0,0 +1,79 @@ +// { dg-options "-std=c++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 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 COPYING3. If not see +// . + +#include +#include +#include + +class PathPoint +{ +public: + PathPoint(char t, const std::vector& c) + : type(t), coords(c) { } + PathPoint(char t, std::vector&& c) + : type(t), coords(std::move(c)) { } + char getType() const { return type; } + const std::vector& getCoords() const { return coords; } +private: + char type; + std::vector coords; +}; + +struct PathPointLess +{ + bool operator() (const PathPoint& __lhs, const PathPoint& __rhs) const + { return __lhs.getType() < __rhs.getType(); } +}; + +bool test __attribute__((unused)) = true; + +void test01() +{ + typedef std::multiset Mset; + Mset ms; + + std::vector coord1 = { 0.0, 1.0, 2.0 }; + + auto it = ms.emplace('a', coord1); + VERIFY( ms.size() == 1 ); + VERIFY( it->getType() == 'a' ); + + coord1[0] = 3.0; + it = ms.emplace('a', coord1); + VERIFY( ms.size() == 2 ); + VERIFY( it->getType() == 'a' ); + VERIFY( it->getCoords()[0] == 3.0 ); + + it = ms.emplace_hint(ms.begin(), 'b', coord1); + VERIFY( it != ms.end() ); + VERIFY( it->getType() == 'b' ); + VERIFY( it->getCoords()[0] == 3.0 ); + + double *px = &coord1[0]; + it = ms.emplace('c', std::move(coord1)); + VERIFY( ms.size() == 4 ); + VERIFY( it->getType() == 'c' ); + VERIFY( &(it->getCoords()[0]) == px ); +} + +int main() +{ + test01(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/set/modifiers/emplace/1.cc b/libstdc++-v3/testsuite/23_containers/set/modifiers/emplace/1.cc new file mode 100644 index 0000000..34c4c19 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/set/modifiers/emplace/1.cc @@ -0,0 +1,81 @@ +// { dg-options "-std=c++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 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 COPYING3. If not see +// . + +#include +#include +#include + +class PathPoint +{ +public: + PathPoint(char t, const std::vector& c) + : type(t), coords(c) { } + PathPoint(char t, std::vector&& c) + : type(t), coords(std::move(c)) { } + char getType() const { return type; } + const std::vector& getCoords() const { return coords; } +private: + char type; + std::vector coords; +}; + +struct PathPointLess +{ + bool operator() (const PathPoint& __lhs, const PathPoint& __rhs) const + { return __lhs.getType() < __rhs.getType(); } +}; + +bool test __attribute__((unused)) = true; + +void test01() +{ + typedef std::set Set; + Set s; + + std::vector coord1 = { 0.0, 1.0, 2.0 }; + + auto ret = s.emplace('a', coord1); + VERIFY( ret.second ); + VERIFY( s.size() == 1 ); + VERIFY( ret.first->getType() == 'a' ); + + coord1[0] = 3.0; + ret = s.emplace('a', coord1); + VERIFY( !ret.second ); + VERIFY( s.size() == 1 ); + VERIFY( ret.first->getType() == 'a' ); + VERIFY( ret.first->getCoords()[0] == 0.0 ); + + auto it = s.emplace_hint(s.begin(), 'b', coord1); + VERIFY( it != s.end() ); + VERIFY( it->getType() == 'b' ); + VERIFY( it->getCoords()[0] == 3.0 ); + + double *px = &coord1[0]; + ret = s.emplace('c', std::move(coord1)); + VERIFY( ret.second ); + VERIFY( ret.first->getType() == 'c' ); + VERIFY( &(ret.first->getCoords()[0]) == px ); +} + +int main() +{ + test01(); + return 0; +} diff --git a/libstdc++-v3/testsuite/util/testsuite_container_traits.h b/libstdc++-v3/testsuite/util/testsuite_container_traits.h index cce91b7..5d8aae0 100644 --- a/libstdc++-v3/testsuite/util/testsuite_container_traits.h +++ b/libstdc++-v3/testsuite/util/testsuite_container_traits.h @@ -148,6 +148,9 @@ namespace __gnu_test typedef std::true_type has_erase; typedef std::true_type has_insert; +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + typedef std::true_type has_emplace; +#endif }; template @@ -161,6 +164,9 @@ namespace __gnu_test typedef std::true_type has_erase; typedef std::true_type has_insert; +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + typedef std::true_type has_emplace; +#endif }; template @@ -173,6 +179,9 @@ namespace __gnu_test typedef std::true_type has_erase; typedef std::true_type has_insert; +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + typedef std::true_type has_emplace; +#endif }; template @@ -185,6 +194,9 @@ namespace __gnu_test typedef std::true_type has_erase; typedef std::true_type has_insert; +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + typedef std::true_type has_emplace; +#endif }; template -- 2.7.4