OSDN Git Service

2011-12-09 Fran├žois Dumont <fdumont@gcc.gnu.org>
authorfdumont <fdumont@138bc75d-0d04-0410-961f-82ee72b054a4>
Fri, 9 Dec 2011 20:01:04 +0000 (20:01 +0000)
committerfdumont <fdumont@138bc75d-0d04-0410-961f-82ee72b054a4>
Fri, 9 Dec 2011 20:01:04 +0000 (20:01 +0000)
* include/bits/hashtable.h (_Hashtable<>::emplace,
_Hashtable<>::emplace_hint): Add.
* include/debug/unordered_set (unordered_set<>::emplace,
unordered_set<>::emplace_hint, unordered_multiset<>::emplace,
unordered_multiset<>::emplace_hint): Add.
* include/profile/unordered_set: Likewise.
* include/debug/unordered_map (unordered_map<>::emplace,
unordered_map<>::emplace_hint, unordered_multimap<>::emplace,
unordered_multimap<>::emplace_hint): Add.
* include/profile/unordered_map: Likewise.
* testsuite/23_containers/unordered_map/modifiers/emplace.cc: New.
* testsuite/23_containers/unordered_multimap/modifiers/emplace.cc:
New.
* testsuite/23_containers/unordered_set/modifiers/emplace.cc: New.
* testsuite/23_containers/unordered_multiset/modifiers/emplace.cc:
New.
* testsuite/util/testsuite_container_traits.h
(traits_base::has_emplace): Add and defined as std::true_type for
unordered containers.
* testsuite/util/exception/safety.h (emplace, emplace_hint): Add and
use them in basic_safety exception test case.
* doc/xml/manual/status_cxx2011.xml: Update unordered containers
status.

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@182174 138bc75d-0d04-0410-961f-82ee72b054a4

libstdc++-v3/ChangeLog
libstdc++-v3/doc/xml/manual/status_cxx2011.xml
libstdc++-v3/include/bits/hashtable.h
libstdc++-v3/include/debug/unordered_map
libstdc++-v3/include/debug/unordered_set
libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/emplace.cc [new file with mode: 0644]
libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/emplace.cc [new file with mode: 0644]
libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/emplace.cc [new file with mode: 0644]
libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/emplace.cc [new file with mode: 0644]
libstdc++-v3/testsuite/util/exception/safety.h
libstdc++-v3/testsuite/util/testsuite_container_traits.h

index bf5224e..5ade2a0 100644 (file)
@@ -1,3 +1,29 @@
+2011-12-09  Fran├žois Dumont <fdumont@gcc.gnu.org>
+
+       * include/bits/hashtable.h (_Hashtable<>::emplace,
+       _Hashtable<>::emplace_hint): Add.
+       * include/debug/unordered_set (unordered_set<>::emplace,
+       unordered_set<>::emplace_hint, unordered_multiset<>::emplace,
+       unordered_multiset<>::emplace_hint): Add.
+       * include/profile/unordered_set: Likewise.
+       * include/debug/unordered_map (unordered_map<>::emplace,
+       unordered_map<>::emplace_hint, unordered_multimap<>::emplace,
+       unordered_multimap<>::emplace_hint): Add.
+       * include/profile/unordered_map: Likewise.
+       * testsuite/23_containers/unordered_map/modifiers/emplace.cc: New.
+       * testsuite/23_containers/unordered_multimap/modifiers/emplace.cc:
+       New.
+       * testsuite/23_containers/unordered_set/modifiers/emplace.cc: New.
+       * testsuite/23_containers/unordered_multiset/modifiers/emplace.cc:
+       New.
+       * testsuite/util/testsuite_container_traits.h
+       (traits_base::has_emplace): Add and defined as std::true_type for
+       unordered containers.
+       * testsuite/util/exception/safety.h (emplace, emplace_hint): Add and
+       use them in basic_safety exception test case.
+       * doc/xml/manual/status_cxx2011.xml: Update unordered containers
+       status.
+
 2011-12-08  Jonathan Wakely  <jwakely.gcc@gmail.com>
 
        * include/bits/atomic_base.h (__calculate_memory_order): Rename to...
index f47710e..1f39ce5 100644 (file)
@@ -1403,11 +1403,10 @@ particular release.
       <entry>Missing emplace members</entry>
     </row>
     <row>
-      <?dbhtml bgcolor="#B0B0B0" ?>
       <entry>23.2.5</entry>
       <entry>Unordered associative containers</entry>
-      <entry>Partial</entry>
-      <entry>Missing emplace members</entry>
+      <entry>Y</entry>
+      <entry/>
     </row>
     <row>
       <entry>23.3</entry>
index 712b1df..3874cbc 100644 (file)
@@ -467,6 +467,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
        _Insert_Conv_Type;
 
     protected:
+      template<typename... _Args>
+       std::pair<iterator, bool>
+       _M_emplace(std::true_type, _Args&&... __args);
+
+      template<typename... _Args>
+       iterator
+       _M_emplace(std::false_type, _Args&&... __args);
+
       template<typename _Arg>
        std::pair<iterator, bool>
        _M_insert(_Arg&&, std::true_type);
@@ -476,7 +484,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
        _M_insert(_Arg&&, std::false_type);
 
     public:
-      // Insert and erase
+      // Emplace, insert and erase
+      template<typename... _Args>
+       _Insert_Return_Type
+       emplace(_Args&&... __args)
+       { return _M_emplace(integral_constant<bool, __unique_keys>(),
+                           std::forward<_Args>(__args)...); }
+
+      template<typename... _Args>
+       iterator
+       emplace_hint(const_iterator, _Args&&... __args)
+       { return _Insert_Conv_Type()(emplace(std::forward<_Args>(__args)...)); }
+
       _Insert_Return_Type
       insert(const value_type& __v)
       { return _M_insert(__v, integral_constant<bool, __unique_keys>()); }
@@ -1160,6 +1179,128 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       return __prev_n;
     }
 
+  template<typename _Key, typename _Value,
+          typename _Allocator, typename _ExtractKey, typename _Equal,
+          typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
+          bool __chc, bool __cit, bool __uk>
+    template<typename... _Args>
+      std::pair<typename _Hashtable<_Key, _Value, _Allocator,
+                                   _ExtractKey, _Equal, _H1,
+                                   _H2, _Hash, _RehashPolicy,
+                                   __chc, __cit, __uk>::iterator, bool>
+      _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
+                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
+      _M_emplace(std::true_type, _Args&&... __args)
+      {
+       // First build the node to get access to the hash code
+       _Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...);
+       __try
+         {
+           const key_type& __k = this->_M_extract(__new_node->_M_v);
+           typename _Hashtable::_Hash_code_type __code
+             = this->_M_hash_code(__k);
+           size_type __bkt
+             = this->_M_bucket_index(__k, __code, _M_bucket_count);
+
+           if (_Node* __p = _M_find_node(__bkt, __k, __code))
+             {
+               // There is already an equivalent node, no insertion
+               _M_deallocate_node(__new_node);
+               return std::make_pair(iterator(__p), false);
+             }
+
+           // We are going to insert this node
+           this->_M_store_code(__new_node, __code);
+           const _RehashPolicyState& __saved_state
+             = _M_rehash_policy._M_state();
+           std::pair<bool, std::size_t> __do_rehash
+             = _M_rehash_policy._M_need_rehash(_M_bucket_count,
+                                               _M_element_count, 1);
+
+           if (__do_rehash.first)
+             {
+               _M_rehash(__do_rehash.second, __saved_state);
+               __bkt = this->_M_bucket_index(__k, __code, _M_bucket_count);
+             }
+
+           if (_M_buckets[__bkt])
+             _M_insert_after(__bkt, _M_buckets[__bkt], __new_node);
+           else 
+             _M_insert_bucket_begin(__bkt, __new_node);
+           ++_M_element_count;
+           return std::make_pair(iterator(__new_node), true);
+         }
+       __catch(...)
+         {
+           _M_deallocate_node(__new_node);
+           __throw_exception_again;
+         }
+      }
+
+  template<typename _Key, typename _Value,
+          typename _Allocator, typename _ExtractKey, typename _Equal,
+          typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
+          bool __chc, bool __cit, bool __uk>
+    template<typename... _Args>
+      typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
+                         _H1, _H2, _Hash, _RehashPolicy,
+                         __chc, __cit, __uk>::iterator
+      _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
+                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
+      _M_emplace(std::false_type, _Args&&... __args)
+      {
+       const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
+       std::pair<bool, std::size_t> __do_rehash
+         = _M_rehash_policy._M_need_rehash(_M_bucket_count,
+                                           _M_element_count, 1);
+
+       // First build the node to get its hash code
+       _Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...);
+       __try
+         {
+           const key_type& __k = this->_M_extract(__new_node->_M_v);
+           typename _Hashtable::_Hash_code_type __code
+             = this->_M_hash_code(__k);
+           this->_M_store_code(__new_node, __code);
+           size_type __bkt
+             = this->_M_bucket_index(__k, __code, _M_bucket_count);
+
+           // Second find the node, avoid rehash if compare throws.
+           _Node* __prev = _M_find_node(__bkt, __k, __code);
+           
+           if (__do_rehash.first)
+             {
+               _M_rehash(__do_rehash.second, __saved_state);
+               __bkt = this->_M_bucket_index(__k, __code, _M_bucket_count);
+               // __prev is still valid because rehash do not invalidate nodes
+             }
+
+           if (__prev)
+             // Insert after the previous equivalent node
+             _M_insert_after(__bkt, __prev, __new_node);
+           else if (_M_buckets[__bkt])
+             // Bucket is not empty and the inserted node has no equivalent in
+             // the hashtable. We must insert the new node at the beginning or
+             // end of the bucket to preserve equivalent elements relative
+             // positions.
+             if (__bkt != _M_begin_bucket_index)
+               // We insert the new node at the beginning
+               _M_insert_after(__bkt, _M_buckets[__bkt], __new_node);
+             else
+               // We insert the new node at the end
+               _M_insert_after(__bkt, _M_bucket_end(__bkt), __new_node);
+           else
+             _M_insert_bucket_begin(__bkt, __new_node);
+           ++_M_element_count;
+           return iterator(__new_node);
+         }
+       __catch(...)
+         {
+           _M_deallocate_node(__new_node);
+           __throw_exception_again;
+         }
+      }
+
   // Insert v in bucket n (assumes no element with its key already present).
   template<typename _Key, typename _Value,
           typename _Allocator, typename _ExtractKey, typename _Equal,
@@ -1300,7 +1441,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
              _M_deallocate_node(__new_node);
            __throw_exception_again;
          }
-
       }
 
   template<typename _Key, typename _Value,
index 6ad46b6..cf84948 100644 (file)
@@ -204,6 +204,29 @@ namespace __debug
       cend(size_type __b) const
       { return const_local_iterator(_Base::cend(__b), __b, this); }
 
+      template<typename... _Args>
+       std::pair<iterator, bool>
+       emplace(_Args&&... __args)
+       {
+         size_type __bucket_count = this->bucket_count();
+         std::pair<_Base_iterator, bool> __res
+           = _Base::emplace(std::forward<_Args>(__args)...);
+         _M_check_rehashed(__bucket_count);
+         return std::make_pair(iterator(__res.first, this), __res.second);
+       }
+
+      template<typename... _Args>
+       iterator
+       emplace_hint(const_iterator __hint, _Args&&... __args)
+       {
+         __glibcxx_check_insert(__hint);
+         size_type __bucket_count = this->bucket_count();
+         _Base_iterator __it = _Base::emplace_hint(__hint.base(),
+                                       std::forward<_Args>(__args)...);
+         _M_check_rehashed(__bucket_count);
+         return iterator(__it, this);
+       }
+
       std::pair<iterator, bool>
       insert(const value_type& __obj)
       {
@@ -587,6 +610,29 @@ namespace __debug
       cend(size_type __b) const
       { return const_local_iterator(_Base::cend(__b), __b, this); }
 
+      template<typename... _Args>
+       iterator
+       emplace(_Args&&... __args)
+       {
+         size_type __bucket_count = this->bucket_count();
+         _Base_iterator __it
+           = _Base::emplace(std::forward<_Args>(__args)...);
+         _M_check_rehashed(__bucket_count);
+         return iterator(__it, this);
+       }
+
+      template<typename... _Args>
+       iterator
+       emplace_hint(const_iterator __hint, _Args&&... __args)
+       {
+         __glibcxx_check_insert(__hint);
+         size_type __bucket_count = this->bucket_count();
+         _Base_iterator __it = _Base::emplace_hint(__hint.base(),
+                                       std::forward<_Args>(__args)...);
+         _M_check_rehashed(__bucket_count);
+         return iterator(__it, this);
+       }
+
       iterator
       insert(const value_type& __obj)
       {
index 2f41bc3..ba44040 100644 (file)
@@ -204,6 +204,29 @@ namespace __debug
       cend(size_type __b) const
       { return const_local_iterator(_Base::cend(__b), __b, this); }
 
+      template<typename... _Args>
+       std::pair<iterator, bool>
+       emplace(_Args&&... __args)
+       {
+         size_type __bucket_count = this->bucket_count();
+         std::pair<_Base_iterator, bool> __res
+           = _Base::emplace(std::forward<_Args>(__args)...);
+         _M_check_rehashed(__bucket_count);
+         return std::make_pair(iterator(__res.first, this), __res.second);
+       }
+
+      template<typename... _Args>
+       iterator
+       emplace_hint(const_iterator __hint, _Args&&... __args)
+       {
+         __glibcxx_check_insert(__hint);
+         size_type __bucket_count = this->bucket_count();
+         _Base_iterator __it = _Base::emplace_hint(__hint.base(),
+                                       std::forward<_Args>(__args)...);
+         _M_check_rehashed(__bucket_count);
+         return iterator(__it, this);
+       }
+
       std::pair<iterator, bool>
       insert(const value_type& __obj)
       {
@@ -582,6 +605,29 @@ namespace __debug
       cend(size_type __b) const
       { return const_local_iterator(_Base::cend(__b), __b, this); }
 
+      template<typename... _Args>
+       iterator
+       emplace(_Args&&... __args)
+       {
+         size_type __bucket_count = this->bucket_count();
+         _Base_iterator __it
+           = _Base::emplace(std::forward<_Args>(__args)...);
+         _M_check_rehashed(__bucket_count);
+         return iterator(__it, this);
+       }
+
+      template<typename... _Args>
+       iterator
+       emplace_hint(const_iterator __hint, _Args&&... __args)
+       {
+         __glibcxx_check_insert(__hint);
+         size_type __bucket_count = this->bucket_count();
+         _Base_iterator __it = _Base::emplace_hint(__hint.base(),
+                                       std::forward<_Args>(__args)...);
+         _M_check_rehashed(__bucket_count);
+         return iterator(__it, this);
+       }
+
       iterator
       insert(const value_type& __obj)
       {
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/emplace.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/emplace.cc
new file mode 100644 (file)
index 0000000..0a0dff8
--- /dev/null
@@ -0,0 +1,116 @@
+// { dg-options "-std=gnu++0x" }
+
+// Copyright (C) 2011 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/>.
+
+// range insert
+
+#include <utility>
+#include <tuple>
+#include <vector>
+#include <unordered_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::unordered_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 unordered_map<char, PathPoint> Map;
+  Map m;
+
+  std::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;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/emplace.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/emplace.cc
new file mode 100644 (file)
index 0000000..40aef98
--- /dev/null
@@ -0,0 +1,110 @@
+// { dg-options "-std=gnu++0x" }
+
+// Copyright (C) 2011 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/>.
+
+// range insert
+
+#include <tuple>
+#include <vector>
+#include <unordered_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::unordered_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 unordered_multimap<char, PathPoint> Map;
+  Map m;
+
+  std::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;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/emplace.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/emplace.cc
new file mode 100644 (file)
index 0000000..057e326
--- /dev/null
@@ -0,0 +1,88 @@
+// { dg-options "-std=gnu++0x" }
+
+// Copyright (C) 2011 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/>.
+
+// range insert
+
+#include <vector>
+#include <unordered_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 PathPointHasher
+{
+  std::size_t operator() (const PathPoint& __pp) const
+  { return __pp.getType(); }
+};
+
+struct PathPointEqual
+{
+  bool operator() (const PathPoint& __lhs, const PathPoint& __rhs) const
+  { return __lhs.getType() == __rhs.getType(); }
+};
+
+bool test __attribute__((unused)) = true;
+
+void test01()
+{
+  typedef std::unordered_multiset<PathPoint, PathPointHasher,
+                                 PathPointEqual> 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;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/emplace.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/emplace.cc
new file mode 100644 (file)
index 0000000..2ae4e76
--- /dev/null
@@ -0,0 +1,89 @@
+// { dg-options "-std=gnu++0x" }
+
+// Copyright (C) 2011 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/>.
+
+// range insert
+
+#include <vector>
+#include <unordered_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 PathPointHasher
+{
+  std::size_t operator() (const PathPoint& __pp) const
+  { return __pp.getType(); }
+};
+
+struct PathPointEqual
+{
+  bool operator() (const PathPoint& __lhs, const PathPoint& __rhs) const
+  { return __lhs.getType() == __rhs.getType(); }
+};
+
+bool test __attribute__((unused)) = true;
+
+void test01()
+{
+  typedef std::unordered_set<PathPoint, PathPointHasher, PathPointEqual> 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 b85f7fe..5041898 100644 (file)
@@ -826,6 +826,110 @@ namespace __gnu_test
        operator()(_Tp&, _Tp&) { }
       };
 
+    template<typename _Tp,
+            bool = traits<_Tp>::has_emplace::value>
+      struct emplace;
+
+    // Specialization for most containers.
+    template<typename _Tp>
+      struct emplace<_Tp, true>
+      {
+       typedef _Tp                                     container_type;
+       typedef typename container_type::value_type     value_type;
+       typedef typename container_type::size_type      size_type;
+
+       void
+       operator()(_Tp& __test)
+       {
+         try
+           {
+             const value_type cv = generate_unique<value_type>();
+             __test.emplace(cv);
+           }
+         catch(const __gnu_cxx::forced_error&)
+           { throw; }
+       }
+
+       // Assumes containers start out equivalent.
+       void
+       operator()(_Tp& __control, _Tp& __test)
+       {
+         try
+           {
+             const value_type cv = generate_unique<value_type>();
+             __test.emplace(cv);
+           }
+         catch(const __gnu_cxx::forced_error&)
+           { throw; }
+       }
+      };
+
+    // Specialization, empty.
+    template<typename _Tp>
+      struct emplace<_Tp, false>
+      {
+       void
+       operator()(_Tp&) { }
+
+       void
+       operator()(_Tp&, _Tp&) { }
+      };
+
+    template<typename _Tp,
+            bool = traits<_Tp>::has_emplace::value>
+      struct emplace_hint;
+
+    // Specialization for most containers.
+    template<typename _Tp>
+      struct emplace_hint<_Tp, true>
+      {
+       typedef _Tp                                     container_type;
+       typedef typename container_type::value_type     value_type;
+
+       void
+       operator()(_Tp& __test)
+       {
+         try
+           {
+             const value_type cv = generate_unique<value_type>();
+             const size_type sz = std::distance(__test.begin(), __test.end());
+             size_type s = generate(sz);
+             auto i = __test.begin();
+             std::advance(i, s);
+             __test.emplace_hint(i, cv);
+           }
+         catch(const __gnu_cxx::forced_error&)
+           { throw; }
+       }
+
+       // Assumes containers start out equivalent.
+       void
+       operator()(_Tp& __control, _Tp& __test)
+       {
+         try
+           {
+             const value_type cv = generate_unique<value_type>();
+             const size_type sz = std::distance(__test.begin(), __test.end());
+             size_type s = generate(sz);
+             auto i = __test.begin();
+             std::advance(i, s);
+             __test.emplace_hint(i, cv);
+           }
+         catch(const __gnu_cxx::forced_error&)
+           { throw; }
+       }
+      };
+
+    // Specialization, empty.
+    template<typename _Tp>
+      struct emplace_hint<_Tp, false>
+      {
+       void
+       operator()(_Tp&) { }
+
+       void
+       operator()(_Tp&, _Tp&) { }
+      };
 
     template<typename _Tp, bool = traits<_Tp>::is_associative::value
                                  || traits<_Tp>::is_unordered::value>
@@ -1023,6 +1127,8 @@ namespace __gnu_test
       typedef erase_point<container_type>              erase_point;
       typedef erase_range<container_type>              erase_range;
       typedef insert_point<container_type>             insert_point;
+      typedef emplace<container_type>                  emplace;
+      typedef emplace_hint<container_type>             emplace_hint;
       typedef pop_front<container_type>                pop_front;
       typedef pop_back<container_type>                         pop_back;
       typedef push_front<container_type>               push_front;
@@ -1039,6 +1145,8 @@ namespace __gnu_test
       erase_point              _M_erasep;
       erase_range              _M_eraser;
       insert_point             _M_insertp;
+      emplace                  _M_emplace;
+      emplace_hint             _M_emplaceh;
       pop_front                        _M_popf;
       pop_back                 _M_popb;
       push_front               _M_pushf;
@@ -1098,6 +1206,8 @@ namespace __gnu_test
        _M_functions.push_back(function_type(base_type::_M_erasep));
        _M_functions.push_back(function_type(base_type::_M_eraser));
        _M_functions.push_back(function_type(base_type::_M_insertp));
+       _M_functions.push_back(function_type(base_type::_M_emplace));
+       _M_functions.push_back(function_type(base_type::_M_emplaceh));
        _M_functions.push_back(function_type(base_type::_M_popf));
        _M_functions.push_back(function_type(base_type::_M_popb));
        _M_functions.push_back(function_type(base_type::_M_pushf));
index 4d8ff99..cce91b7 100644 (file)
@@ -43,6 +43,7 @@ namespace __gnu_test
     typedef std::false_type    has_throwing_erase;
     typedef std::false_type    has_insert;
     typedef std::false_type    has_insert_after;
+    typedef std::false_type    has_emplace;
     typedef std::false_type    has_push_pop;
     typedef std::false_type    has_size_type_constructor;
   };
@@ -216,6 +217,7 @@ namespace __gnu_test
 
       typedef std::true_type   has_erase;
       typedef std::true_type   has_insert;
+      typedef std::true_type   has_emplace;
     };
 
   template<typename _Tp1, typename _Tp2, typename _Tp3,
@@ -230,6 +232,7 @@ namespace __gnu_test
 
       typedef std::true_type   has_erase;
       typedef std::true_type   has_insert;
+      typedef std::true_type   has_emplace;
     };
 
   template<typename _Tp1, typename _Tp2, typename _Tp3, typename _Tp4>
@@ -242,6 +245,7 @@ namespace __gnu_test
 
       typedef std::true_type   has_erase;
       typedef std::true_type   has_insert;
+      typedef std::true_type   has_emplace;
     };
 
   template<typename _Tp1, typename _Tp2, typename _Tp3, typename _Tp4>
@@ -254,6 +258,7 @@ namespace __gnu_test
 
       typedef std::true_type   has_erase;
       typedef std::true_type   has_insert;
+      typedef std::true_type   has_emplace;
     };
 } // namespace __gnu_test