2012-09-24 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.
	* 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.


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

6 files changed, 481 insertions, 0 deletions

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 00000000000..bd2560439d4
--- /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
+// <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;
+}
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 00000000000..0d8a183d8ea
--- /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
+// <http://www.gnu.org/licenses/>.
+
+// This test verifies that the value type of a map need not be default copyable.
+
+// { dg-options "-std=c++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;
+}
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 00000000000..71ca8a91d76
--- /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
+// <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;
+}
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 00000000000..3a1e38ccf61
--- /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
+// <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;
+}
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 00000000000..34c4c192d3e
--- /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
+// <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;
+}
diff --git a/libstdc++-v3/testsuite/util/testsuite_container_traits.h b/libstdc++-v3/testsuite/util/testsuite_container_traits.h
index cce91b739bf..5d8aae04fe0 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<typename _Tp1, typename _Tp2, typename _Tp3, typename _Tp4>
@@ -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<typename _Tp1, typename _Tp2, typename _Tp3>
@@ -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<typename _Tp1, typename _Tp2, typename _Tp3>
@@ -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<typename _Tp1, typename _Tp2>