This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: PR 44436 Associative containers emplace/emplace_hint
- From: François Dumont <frs dot dumont at gmail dot com>
- To: Paolo Carlini <paolo dot carlini at oracle dot com>
- Cc: "libstdc++ at gcc dot gnu dot org" <libstdc++ at gcc dot gnu dot org>, gcc-patches <gcc-patches at gcc dot gnu dot org>
- Date: Sun, 16 Sep 2012 22:08:36 +0200
- Subject: Re: PR 44436 Associative containers emplace/emplace_hint
- References: <50538E96.8080907@gmail.com> <505396F8.1090602@oracle.com>
On 09/14/2012 10:43 PM, Paolo Carlini wrote:
On 09/14/2012 10:07 PM, François Dumont wrote:
Hi
Here is a patch to add emplace/emplace_hint on associative
containers in C++11 mode.
Ah, excellent! I will review the patch over the next couple of days.
I did some refactoring to use as much of the same code between
insert and emplace methods..
I have also change map::operator[] to now use the emplace logic
in C++11 so that we only need the value type to be default
constructible.
About this, can I ask you to likewise add completely similar testcases
too?
Good catch Paolo. In fact I simply forgot to add it to the patch.
2012-09-16 François Dumont <fdumont@gcc.gnu.org>
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 <tuple> 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.
* 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/modifiers/emplate/1.cc: New.
* testsuite/23_containers/map/operators/2.cc: New.
* testsuite/23_containers/multimap/modifiers/emplate/1.cc: New.
* testsuite/23_containers/set/modifiers/emplate/1.cc: New.
* testsuite/23_containers/multiset/modifiers/emplate/1.cc: New.
Ok to commit ?
François
Index: include/bits/stl_tree.h
===================================================================
--- include/bits/stl_tree.h (revision 191279)
+++ include/bits/stl_tree.h (working copy)
@@ -570,27 +570,50 @@
typedef std::reverse_iterator<const_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<typename _Arg>
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<typename _Arg>
iterator
- _M_insert_lower(_Base_ptr __x, _Base_ptr __y, _Arg&& __v);
+ _M_insert_lower(_Base_ptr __y, _Arg&& __v);
template<typename _Arg>
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 @@
template<typename _Arg>
iterator
_M_insert_equal_(const_iterator __position, _Arg&& __x);
+
+ template<typename... _Args>
+ pair<iterator, bool>
+ _M_emplace_unique(_Args&&... __args);
+
+ template<typename... _Args>
+ iterator
+ _M_emplace_equal(_Args&&... __args);
+
+ template<typename... _Args>
+ iterator
+ _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args);
+
+ template<typename... _Args>
+ iterator
+ _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args);
#else
pair<iterator, bool>
_M_insert_unique(const value_type& __x);
@@ -967,19 +1006,18 @@
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 @@
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 @@
__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<typename _Key, typename _Val, typename _KoV,
@@ -1264,64 +1302,55 @@
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
-#ifdef __GXX_EXPERIMENTAL_CXX0X__
- template<typename _Arg>
-#endif
pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
- _Compare, _Alloc>::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<iterator, bool>
- (_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<iterator, bool>
- (_M_insert_(__x, __y, _GLIBCXX_FORWARD(_Arg, __v)), true);
- return pair<iterator, bool>(__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<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
-#ifdef __GXX_EXPERIMENTAL_CXX0X__
- template<typename _Arg>
-#endif
- typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
+ pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
+ _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_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<typename _Key, typename _Val, typename _KeyOfValue,
@@ -1329,70 +1358,101 @@
#ifdef __GXX_EXPERIMENTAL_CXX0X__
template<typename _Arg>
#endif
+ pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
+ _Compare, _Alloc>::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<iterator, bool> _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<typename _Key, typename _Val, typename _KeyOfValue,
+ typename _Compare, typename _Alloc>
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ template<typename _Arg>
+#endif
typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::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<typename _Key, typename _Val, typename _KeyOfValue,
+ typename _Compare, typename _Alloc>
+ pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
+ _Compare, _Alloc>::_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<typename _Key, typename _Val, typename _KeyOfValue,
@@ -1403,66 +1463,247 @@
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)
+ _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<typename _Key, typename _Val, typename _KeyOfValue,
+ typename _Compare, typename _Alloc>
+ pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
+ _Compare, _Alloc>::_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<typename _Key, typename _Val, typename _KeyOfValue,
+ typename _Compare, typename _Alloc>
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ template<typename _Arg>
+#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 _Key, typename _Val, typename _KeyOfValue,
+ typename _Compare, typename _Alloc>
+ 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 _Key, typename _Val, typename _KeyOfValue,
+ typename _Compare, typename _Alloc>
+ 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 _Key, typename _Val, typename _KeyOfValue,
+ typename _Compare, typename _Alloc>
+ 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<typename _Key, typename _Val, typename _KeyOfValue,
+ typename _Compare, typename _Alloc>
+ template<typename... _Args>
+ pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
+ _Compare, _Alloc>::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<iterator, bool> _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<typename _Key, typename _Val, typename _KeyOfValue,
+ typename _Compare, typename _Alloc>
+ template<typename... _Args>
+ 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<typename _Key, typename _Val, typename _KeyOfValue,
+ typename _Compare, typename _Alloc>
+ template<typename... _Args>
+ 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<typename _Key, typename _Val, typename _KeyOfValue,
+ typename _Compare, typename _Alloc>
+ template<typename... _Args>
+ 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<typename _Key, typename _Val, typename _KoV,
typename _Cmp, typename _Alloc>
template<class _II>
Index: include/bits/stl_map.h
===================================================================
--- include/bits/stl_map.h (revision 191279)
+++ include/bits/stl_map.h (working copy)
@@ -61,6 +61,7 @@
#include <bits/concept_check.h>
#ifdef __GXX_EXPERIMENTAL_CXX0X__
#include <initializer_list>
+#include <tuple>
#endif
namespace std _GLIBCXX_VISIBILITY(default)
@@ -461,7 +462,13 @@
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<const key_type&>(__k),
+ std::tuple<>());
+#else
__i = insert(__i, value_type(__k, mapped_type()));
+#endif
return (*__i).second;
}
@@ -475,7 +482,9 @@
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,7 +517,65 @@
}
// 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<typename... _Args>
+ std::pair<iterator, bool>
+ 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<typename... _Args>
+ 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.
* @param __x Pair to be inserted (see std::make_pair for easy
Index: include/bits/stl_multimap.h
===================================================================
--- include/bits/stl_multimap.h (revision 191279)
+++ include/bits/stl_multimap.h (working copy)
@@ -433,7 +433,60 @@
{ 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<typename... _Args>
+ 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<typename... _Args>
+ 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
* of pairs).
Index: include/bits/stl_set.h
===================================================================
--- include/bits/stl_set.h (revision 191279)
+++ include/bits/stl_set.h (working copy)
@@ -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,8 +395,57 @@
{ _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<typename... _Args>
+ std::pair<iterator, bool>
+ 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<typename... _Args>
+ 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.
* @return A pair, of which the first element is an iterator that points
* to the possibly inserted element, and the second is a bool
Index: include/bits/stl_multiset.h
===================================================================
--- include/bits/stl_multiset.h (revision 191279)
+++ include/bits/stl_multiset.h (working copy)
@@ -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,7 +392,55 @@
{ _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<typename... _Args>
+ 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<typename... _Args>
+ 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.
* @return An iterator that points to the inserted element.
Index: include/debug/map.h
===================================================================
--- include/debug/map.h (revision 191279)
+++ include/debug/map.h (working copy)
@@ -203,6 +203,27 @@
using _Base::at;
// modifiers:
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ template<typename... _Args>
+ std::pair<iterator, bool>
+ emplace(_Args&&... __args)
+ {
+ auto __res = _Base::emplace(std::forward<_Args>(__args)...);
+ return std::pair<iterator, bool>(iterator(__res.first, this),
+ __res.second);
+ }
+
+ template<typename... _Args>
+ 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<iterator, bool>
insert(const value_type& __x)
{
Index: include/debug/multimap.h
===================================================================
--- include/debug/multimap.h (revision 191279)
+++ include/debug/multimap.h (working copy)
@@ -195,6 +195,25 @@
using _Base::max_size;
// modifiers:
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ template<typename... _Args>
+ iterator
+ emplace(_Args&&... __args)
+ {
+ return iterator(_Base::emplace(std::forward<_Args>(__args)...), this);
+ }
+
+ template<typename... _Args>
+ 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); }
Index: include/debug/set.h
===================================================================
--- include/debug/set.h (revision 191279)
+++ include/debug/set.h (working copy)
@@ -194,6 +194,27 @@
using _Base::max_size;
// modifiers:
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ template<typename... _Args>
+ std::pair<iterator, bool>
+ emplace(_Args&&... __args)
+ {
+ auto __res = _Base::emplace(std::forward<_Args>(__args)...);
+ return std::pair<iterator, bool>(iterator(__res.first, this),
+ __res.second);
+ }
+
+ template<typename... _Args>
+ 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<iterator, bool>
insert(const value_type& __x)
{
Index: include/debug/multiset.h
===================================================================
--- include/debug/multiset.h (revision 191279)
+++ include/debug/multiset.h (working copy)
@@ -194,6 +194,25 @@
using _Base::max_size;
// modifiers:
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ template<typename... _Args>
+ iterator
+ emplace(_Args&&... __args)
+ {
+ return iterator(_Base::emplace(std::forward<_Args>(__args)...), this);
+ }
+
+ template<typename... _Args>
+ 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); }
Index: testsuite/23_containers/set/modifiers/emplace/1.cc
===================================================================
--- testsuite/23_containers/set/modifiers/emplace/1.cc (revision 0)
+++ testsuite/23_containers/set/modifiers/emplace/1.cc (revision 0)
@@ -0,0 +1,81 @@
+// { dg-options "-std=gnu++0x" }
+
+// 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
+// <http://www.gnu.org/licenses/>.
+
+#include <vector>
+#include <set>
+#include <testsuite_hooks.h>
+
+class PathPoint
+{
+public:
+ PathPoint(char t, const std::vector<double>& c)
+ : type(t), coords(c) { }
+ PathPoint(char t, std::vector<double>&& c)
+ : type(t), coords(std::move(c)) { }
+ char getType() const { return type; }
+ const std::vector<double>& getCoords() const { return coords; }
+private:
+ char type;
+ std::vector<double> 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<PathPoint, PathPointLess> Set;
+ Set s;
+
+ std::vector<double> 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;
+}
Index: testsuite/23_containers/multiset/modifiers/emplace/1.cc
===================================================================
--- testsuite/23_containers/multiset/modifiers/emplace/1.cc (revision 0)
+++ testsuite/23_containers/multiset/modifiers/emplace/1.cc (revision 0)
@@ -0,0 +1,79 @@
+// { dg-options "-std=gnu++0x" }
+
+// 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
+// <http://www.gnu.org/licenses/>.
+
+#include <vector>
+#include <set>
+#include <testsuite_hooks.h>
+
+class PathPoint
+{
+public:
+ PathPoint(char t, const std::vector<double>& c)
+ : type(t), coords(c) { }
+ PathPoint(char t, std::vector<double>&& c)
+ : type(t), coords(std::move(c)) { }
+ char getType() const { return type; }
+ const std::vector<double>& getCoords() const { return coords; }
+private:
+ char type;
+ std::vector<double> 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<PathPoint, PathPointLess> Mset;
+ Mset ms;
+
+ std::vector<double> 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;
+}
Index: testsuite/23_containers/map/operators/2.cc
===================================================================
--- testsuite/23_containers/map/operators/2.cc (revision 0)
+++ testsuite/23_containers/map/operators/2.cc (revision 0)
@@ -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
+// <http://www.gnu.org/licenses/>.
+
+// This test verifies that the value type of a map need not be default copyable.
+
+// { dg-options "-std=gnu++11" }
+
+#include <map>
+#include <testsuite_hooks.h>
+#include <testsuite_rvalref.h>
+#include <testsuite_counter_type.h>
+
+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<int, Mapped> m1;
+ m1[0] = Mapped();
+
+ std::map<int, rvalstruct> m2;
+ m2[0] = rvalstruct(13);
+
+ std::map<int, DefaultConstructibleType> m3;
+ VERIFY( m3[0].val == 123 );
+ VERIFY( m3.size() == 1 );
+ m3[0] = 2;
+ VERIFY( m3[0].val == 2 );
+
+ std::map<counter_type, int> 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;
+}
Index: testsuite/23_containers/map/modifiers/emplace/1.cc
===================================================================
--- testsuite/23_containers/map/modifiers/emplace/1.cc (revision 0)
+++ testsuite/23_containers/map/modifiers/emplace/1.cc (revision 0)
@@ -0,0 +1,114 @@
+// { dg-options "-std=gnu++0x" }
+
+// 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
+// <http://www.gnu.org/licenses/>.
+
+#include <utility>
+#include <tuple>
+#include <vector>
+#include <map>
+#include <testsuite_hooks.h>
+
+class PathPoint
+{
+public:
+ PathPoint(char t, const std::vector<double>& c)
+ : type(t), coords(c) { }
+ PathPoint(char t, std::vector<double>&& c)
+ : type(t), coords(std::move(c)) { }
+ char getType() const { return type; }
+ const std::vector<double>& getCoords() const { return coords; }
+private:
+ char type;
+ std::vector<double> coords;
+};
+
+bool test __attribute__((unused)) = true;
+
+void test01()
+{
+ typedef std::map<char, std::vector<double>> Map;
+ Map m;
+
+ std::vector<double> 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<char, PathPoint> Map;
+ Map m;
+
+ vector<double> 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;
+}
Index: testsuite/23_containers/multimap/modifiers/emplace/1.cc
===================================================================
--- testsuite/23_containers/multimap/modifiers/emplace/1.cc (revision 0)
+++ testsuite/23_containers/multimap/modifiers/emplace/1.cc (revision 0)
@@ -0,0 +1,108 @@
+// { dg-options "-std=gnu++0x" }
+
+// 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
+// <http://www.gnu.org/licenses/>.
+
+#include <tuple>
+#include <vector>
+#include <map>
+#include <testsuite_hooks.h>
+
+class PathPoint
+{
+public:
+ PathPoint(char t, const std::vector<double>& c)
+ : type(t), coords(c) { }
+ PathPoint(char t, std::vector<double>&& c)
+ : type(t), coords(std::move(c)) { }
+ char getType() const { return type; }
+ const std::vector<double>& getCoords() const { return coords; }
+private:
+ char type;
+ std::vector<double> coords;
+};
+
+bool test __attribute__((unused)) = true;
+
+void test01()
+{
+ typedef std::multimap<char, std::vector<double>> MMap;
+ MMap mm;
+
+ std::vector<double> 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<char, PathPoint> Map;
+ Map m;
+
+ vector<double> 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;
+}
Index: testsuite/util/testsuite_container_traits.h
===================================================================
--- testsuite/util/testsuite_container_traits.h (revision 191279)
+++ testsuite/util/testsuite_container_traits.h (working copy)
@@ -148,6 +148,9 @@
typedef std::true_type has_erase;
typedef std::true_type has_insert;
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ typedef std::true_type has_emplace;
+#endif
};
template<typename _Tp1, typename _Tp2, typename _Tp3, typename _Tp4>
@@ -161,6 +164,9 @@
typedef std::true_type has_erase;
typedef std::true_type has_insert;
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ typedef std::true_type has_emplace;
+#endif
};
template<typename _Tp1, typename _Tp2, typename _Tp3>
@@ -173,6 +179,9 @@
typedef std::true_type has_erase;
typedef std::true_type has_insert;
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ typedef std::true_type has_emplace;
+#endif
};
template<typename _Tp1, typename _Tp2, typename _Tp3>
@@ -185,6 +194,9 @@
typedef std::true_type has_erase;
typedef std::true_type has_insert;
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ typedef std::true_type has_emplace;
+#endif
};
template<typename _Tp1, typename _Tp2>