erik.pilkington updated this revision to Diff 164064.
erik.pilkington added a comment.
Ping! In the new patch:
- Uncomment __cpp_lib_node_extract, reverting r340544
- Rebase/Clean up the diff a bit
https://reviews.llvm.org/D48896
Files:
libcxx/include/__hash_table
libcxx/include/__node_handle
libcxx/include/__tree
libcxx/include/map
libcxx/include/set
libcxx/include/unordered_map
libcxx/include/unordered_set
libcxx/test/std/containers/associative/map/map.modifiers/merge.pass.cpp
libcxx/test/std/containers/associative/multimap/multimap.modifiers/merge.pass.cpp
libcxx/test/std/containers/associative/multiset/merge.pass.cpp
libcxx/test/std/containers/associative/set/merge.pass.cpp
libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/merge.pass.cpp
libcxx/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/merge.pass.cpp
libcxx/test/std/containers/unord/unord.multiset/merge.pass.cpp
libcxx/test/std/containers/unord/unord.set/merge.pass.cpp
Index: libcxx/test/std/containers/unord/unord.set/merge.pass.cpp
===================================================================
--- /dev/null
+++ libcxx/test/std/containers/unord/unord.set/merge.pass.cpp
@@ -0,0 +1,135 @@
+//===----------------------------------------------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <unordered_set>
+
+// class unordered_set
+
+// template <class C2>
+// void merge(unordered_set<key_type, C2, allocator_type>& source);
+
+#include <unordered_set>
+#include "test_macros.h"
+#include "Counter.h"
+
+template <class Set>
+bool set_equal(const Set& set, Set other)
+{
+ return set == other;
+}
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+template <class T>
+struct throw_hasher
+{
+ bool& should_throw_;
+
+ throw_hasher(bool& should_throw) : should_throw_(should_throw) {}
+
+ typedef size_t result_type;
+ typedef T argument_type;
+
+ size_t operator()(const T& p) const
+ {
+ if (should_throw_)
+ throw 0;
+ return std::hash<T>()(p);
+ }
+};
+#endif
+
+int main()
+{
+ {
+ std::unordered_set<int> src{1, 3, 5};
+ std::unordered_set<int> dst{2, 4, 5};
+ dst.merge(src);
+ assert(set_equal(src, {5}));
+ assert(set_equal(dst, {1, 2, 3, 4, 5}));
+ }
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+ {
+ bool do_throw = false;
+ typedef std::unordered_set<Counter<int>, throw_hasher<Counter<int>>> set_type;
+ set_type src({1, 3, 5}, 0, throw_hasher<Counter<int>>(do_throw));
+ set_type dst({2, 4, 5}, 0, throw_hasher<Counter<int>>(do_throw));
+
+ assert(Counter_base::gConstructed == 6);
+
+ do_throw = true;
+ try
+ {
+ dst.merge(src);
+ }
+ catch (int)
+ {
+ do_throw = false;
+ }
+ assert(!do_throw);
+ assert(set_equal(src, set_type({1, 3, 5}, 0, throw_hasher<Counter<int>>(do_throw))));
+ assert(set_equal(dst, set_type({2, 4, 5}, 0, throw_hasher<Counter<int>>(do_throw))));
+ }
+#endif
+ assert(Counter_base::gConstructed == 0);
+ struct equal
+ {
+ equal() = default;
+
+ bool operator()(const Counter<int>& lhs, const Counter<int>& rhs) const
+ {
+ return lhs == rhs;
+ }
+ };
+ struct hasher
+ {
+ hasher() = default;
+ typedef Counter<int> argument_type;
+ typedef size_t result_type;
+ size_t operator()(const Counter<int>& p) const { return std::hash<Counter<int>>()(p); }
+ };
+ {
+ typedef std::unordered_set<Counter<int>, std::hash<Counter<int>>, std::equal_to<Counter<int>>> first_set_type;
+ typedef std::unordered_set<Counter<int>, hasher, equal> second_set_type;
+ typedef std::unordered_multiset<Counter<int>, hasher, equal> third_set_type;
+
+ first_set_type first{1, 2, 3};
+ second_set_type second{2, 3, 4};
+ third_set_type third{1, 3};
+
+ assert(Counter_base::gConstructed == 8);
+
+ first.merge(second);
+ first.merge(std::move(second));
+ first.merge(third);
+ first.merge(std::move(third));
+
+ assert(set_equal(first, {1, 2, 3, 4}));
+ assert(set_equal(second, {2, 3}));
+ assert(set_equal(third, {1, 3}));
+
+ assert(Counter_base::gConstructed == 8);
+ }
+ assert(Counter_base::gConstructed == 0);
+ {
+ std::unordered_set<int> first;
+ {
+ std::unordered_set<int> second;
+ first.merge(second);
+ first.merge(std::move(second));
+ }
+ {
+ std::unordered_multiset<int> second;
+ first.merge(second);
+ first.merge(std::move(second));
+ }
+ }
+}
Index: libcxx/test/std/containers/unord/unord.multiset/merge.pass.cpp
===================================================================
--- /dev/null
+++ libcxx/test/std/containers/unord/unord.multiset/merge.pass.cpp
@@ -0,0 +1,135 @@
+//===----------------------------------------------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <unordered_set>
+
+// class unordered_multiset
+
+// template <class C2>
+// void merge(unordered_multiset<key_type, C2, allocator_type>& source);
+
+#include <unordered_set>
+#include "test_macros.h"
+#include "Counter.h"
+
+template <class Set>
+bool set_equal(const Set& set, Set other)
+{
+ return set == other;
+}
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+template <class T>
+struct throw_hasher
+{
+ bool& should_throw_;
+
+ throw_hasher(bool& should_throw) : should_throw_(should_throw) {}
+
+ typedef size_t result_type;
+ typedef T argument_type;
+
+ size_t operator()(const T& p) const
+ {
+ if (should_throw_)
+ throw 0;
+ return std::hash<T>()(p);
+ }
+};
+#endif
+
+int main()
+{
+ {
+ std::unordered_multiset<int> src{1, 3, 5};
+ std::unordered_multiset<int> dst{2, 4, 5};
+ dst.merge(src);
+ assert(set_equal(src, {}));
+ assert(set_equal(dst, {1, 2, 3, 4, 5, 5}));
+ }
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+ {
+ bool do_throw = false;
+ typedef std::unordered_multiset<Counter<int>, throw_hasher<Counter<int>>> set_type;
+ set_type src({1, 3, 5}, 0, throw_hasher<Counter<int>>(do_throw));
+ set_type dst({2, 4, 5}, 0, throw_hasher<Counter<int>>(do_throw));
+
+ assert(Counter_base::gConstructed == 6);
+
+ do_throw = true;
+ try
+ {
+ dst.merge(src);
+ }
+ catch (int)
+ {
+ do_throw = false;
+ }
+ assert(!do_throw);
+ assert(set_equal(src, set_type({1, 3, 5}, 0, throw_hasher<Counter<int>>(do_throw))));
+ assert(set_equal(dst, set_type({2, 4, 5}, 0, throw_hasher<Counter<int>>(do_throw))));
+ }
+#endif
+ assert(Counter_base::gConstructed == 0);
+ struct equal
+ {
+ equal() = default;
+
+ bool operator()(const Counter<int>& lhs, const Counter<int>& rhs) const
+ {
+ return lhs == rhs;
+ }
+ };
+ struct hasher
+ {
+ hasher() = default;
+ typedef Counter<int> argument_type;
+ typedef size_t result_type;
+ size_t operator()(const Counter<int>& p) const { return std::hash<Counter<int>>()(p); }
+ };
+ {
+ typedef std::unordered_multiset<Counter<int>, std::hash<Counter<int>>, std::equal_to<Counter<int>>> first_set_type;
+ typedef std::unordered_multiset<Counter<int>, hasher, equal> second_set_type;
+ typedef std::unordered_set<Counter<int>, hasher, equal> third_set_type;
+
+ first_set_type first{1, 2, 3};
+ second_set_type second{2, 3, 4};
+ third_set_type third{1, 3};
+
+ assert(Counter_base::gConstructed == 8);
+
+ first.merge(second);
+ first.merge(std::move(second));
+ first.merge(third);
+ first.merge(std::move(third));
+
+ assert(set_equal(first, {1, 2, 3, 4, 2, 3, 1, 3}));
+ assert(set_equal(second, {}));
+ assert(set_equal(third, {}));
+
+ assert(Counter_base::gConstructed == 8);
+ }
+ assert(Counter_base::gConstructed == 0);
+ {
+ std::unordered_multiset<int> first;
+ {
+ std::unordered_multiset<int> second;
+ first.merge(second);
+ first.merge(std::move(second));
+ }
+ {
+ std::unordered_set<int> second;
+ first.merge(second);
+ first.merge(std::move(second));
+ }
+ }
+}
Index: libcxx/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/merge.pass.cpp
===================================================================
--- /dev/null
+++ libcxx/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/merge.pass.cpp
@@ -0,0 +1,138 @@
+//===----------------------------------------------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <unordered_map>
+
+// class unordered_multimap
+
+// template <class C2>
+// void merge(unordered_multimap<key_type, C2, allocator_type>& source);
+
+#include <unordered_map>
+#include "test_macros.h"
+#include "Counter.h"
+
+template <class Map>
+bool map_equal(const Map& map, Map other)
+{
+ return map == other;
+}
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+template <class T>
+struct throw_hasher
+{
+ bool& should_throw_;
+
+ throw_hasher(bool& should_throw) : should_throw_(should_throw) {}
+
+ typedef size_t result_type;
+ typedef T argument_type;
+
+ size_t operator()(const T& p) const
+ {
+ if (should_throw_)
+ throw 0;
+ return std::hash<T>()(p);
+ }
+};
+#endif
+
+int main()
+{
+ {
+ std::unordered_multimap<int, int> src{{1, 0}, {3, 0}, {5, 0}};
+ std::unordered_multimap<int, int> dst{{2, 0}, {4, 0}, {5, 0}};
+ dst.merge(src);
+ assert(map_equal(src, {}));
+ assert(map_equal(dst, {{1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}, {5, 0}}));
+ }
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+ {
+ bool do_throw = false;
+ typedef std::unordered_multimap<Counter<int>, int, throw_hasher<Counter<int>>> map_type;
+ map_type src({{1, 0}, {3, 0}, {5, 0}}, 0, throw_hasher<Counter<int>>(do_throw));
+ map_type dst({{2, 0}, {4, 0}, {5, 0}}, 0, throw_hasher<Counter<int>>(do_throw));
+
+ assert(Counter_base::gConstructed == 6);
+
+ do_throw = true;
+ try
+ {
+ dst.merge(src);
+ }
+ catch (int)
+ {
+ do_throw = false;
+ }
+ assert(!do_throw);
+ assert(map_equal(src, map_type({{1, 0}, {3, 0}, {5, 0}}, 0, throw_hasher<Counter<int>>(do_throw))));
+ assert(map_equal(dst, map_type({{2, 0}, {4, 0}, {5, 0}}, 0, throw_hasher<Counter<int>>(do_throw))));
+ }
+#endif
+ assert(Counter_base::gConstructed == 0);
+ struct equal
+ {
+ equal() = default;
+
+ bool operator()(const Counter<int>& lhs, const Counter<int>& rhs) const
+ {
+ return lhs == rhs;
+ }
+ };
+ struct hasher
+ {
+ hasher() = default;
+ typedef Counter<int> argument_type;
+ typedef size_t result_type;
+ size_t operator()(const Counter<int>& p) const
+ {
+ return std::hash<Counter<int>>()(p);
+ }
+ };
+ {
+ typedef std::unordered_multimap<Counter<int>, int, std::hash<Counter<int>>, std::equal_to<Counter<int>>> first_map_type;
+ typedef std::unordered_multimap<Counter<int>, int, hasher, equal> second_map_type;
+ typedef std::unordered_map<Counter<int>, int, hasher, equal> third_map_type;
+
+ first_map_type first{{1, 0}, {2, 0}, {3, 0}};
+ second_map_type second{{2, 0}, {3, 0}, {4, 0}};
+ third_map_type third{{1, 0}, {3, 0}};
+
+ assert(Counter_base::gConstructed == 8);
+
+ first.merge(second);
+ first.merge(std::move(second));
+ first.merge(third);
+ first.merge(std::move(third));
+
+ assert(map_equal(first, {{1, 0}, {2, 0}, {3, 0}, {4, 0}, {2, 0}, {3, 0}, {1, 0}, {3, 0}}));
+ assert(map_equal(second, {}));
+ assert(map_equal(third, {}));
+
+ assert(Counter_base::gConstructed == 8);
+ }
+ assert(Counter_base::gConstructed == 0);
+ {
+ std::unordered_multimap<int, int> first;
+ {
+ std::unordered_multimap<int, int> second;
+ first.merge(second);
+ first.merge(std::move(second));
+ }
+ {
+ std::unordered_map<int, int> second;
+ first.merge(second);
+ first.merge(std::move(second));
+ }
+ }
+}
Index: libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/merge.pass.cpp
===================================================================
--- /dev/null
+++ libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/merge.pass.cpp
@@ -0,0 +1,138 @@
+//===----------------------------------------------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <unordered_map>
+
+// class unordered_map
+
+// template <class C2>
+// void merge(unordered_map<key_type, C2, allocator_type>& source);
+
+#include <unordered_map>
+#include "test_macros.h"
+#include "Counter.h"
+
+template <class Map>
+bool map_equal(const Map& map, Map other)
+{
+ return map == other;
+}
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+template <class T>
+struct throw_hasher
+{
+ bool& should_throw_;
+
+ throw_hasher(bool& should_throw) : should_throw_(should_throw) {}
+
+ typedef size_t result_type;
+ typedef T argument_type;
+
+ size_t operator()(const T& p) const
+ {
+ if (should_throw_)
+ throw 0;
+ return std::hash<T>()(p);
+ }
+};
+#endif
+
+int main()
+{
+ {
+ std::unordered_map<int, int> src{{1, 0}, {3, 0}, {5, 0}};
+ std::unordered_map<int, int> dst{{2, 0}, {4, 0}, {5, 0}};
+ dst.merge(src);
+ assert(map_equal(src, {{5,0}}));
+ assert(map_equal(dst, {{1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}}));
+ }
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+ {
+ bool do_throw = false;
+ typedef std::unordered_map<Counter<int>, int, throw_hasher<Counter<int>>> map_type;
+ map_type src({{1, 0}, {3, 0}, {5, 0}}, 0, throw_hasher<Counter<int>>(do_throw));
+ map_type dst({{2, 0}, {4, 0}, {5, 0}}, 0, throw_hasher<Counter<int>>(do_throw));
+
+ assert(Counter_base::gConstructed == 6);
+
+ do_throw = true;
+ try
+ {
+ dst.merge(src);
+ }
+ catch (int)
+ {
+ do_throw = false;
+ }
+ assert(!do_throw);
+ assert(map_equal(src, map_type({{1, 0}, {3, 0}, {5, 0}}, 0, throw_hasher<Counter<int>>(do_throw))));
+ assert(map_equal(dst, map_type({{2, 0}, {4, 0}, {5, 0}}, 0, throw_hasher<Counter<int>>(do_throw))));
+ }
+#endif
+ assert(Counter_base::gConstructed == 0);
+ struct equal
+ {
+ equal() = default;
+
+ bool operator()(const Counter<int>& lhs, const Counter<int>& rhs) const
+ {
+ return lhs == rhs;
+ }
+ };
+ struct hasher
+ {
+ hasher() = default;
+ typedef Counter<int> argument_type;
+ typedef size_t result_type;
+ size_t operator()(const Counter<int>& p) const
+ {
+ return std::hash<Counter<int>>()(p);
+ }
+ };
+ {
+ typedef std::unordered_map<Counter<int>, int, std::hash<Counter<int>>, std::equal_to<Counter<int>>> first_map_type;
+ typedef std::unordered_map<Counter<int>, int, hasher, equal> second_map_type;
+ typedef std::unordered_multimap<Counter<int>, int, hasher, equal> third_map_type;
+
+ first_map_type first{{1, 0}, {2, 0}, {3, 0}};
+ second_map_type second{{2, 0}, {3, 0}, {4, 0}};
+ third_map_type third{{1, 0}, {3, 0}};
+
+ assert(Counter_base::gConstructed == 8);
+
+ first.merge(second);
+ first.merge(std::move(second));
+ first.merge(third);
+ first.merge(std::move(third));
+
+ assert(map_equal(first, {{1, 0}, {2, 0}, {3, 0}, {4, 0}}));
+ assert(map_equal(second, {{2, 0}, {3, 0}}));
+ assert(map_equal(third, {{1, 0}, {3, 0}}));
+
+ assert(Counter_base::gConstructed == 8);
+ }
+ assert(Counter_base::gConstructed == 0);
+ {
+ std::unordered_map<int, int> first;
+ {
+ std::unordered_map<int, int> second;
+ first.merge(second);
+ first.merge(std::move(second));
+ }
+ {
+ std::unordered_multimap<int, int> second;
+ first.merge(second);
+ first.merge(std::move(second));
+ }
+ }
+}
Index: libcxx/test/std/containers/associative/set/merge.pass.cpp
===================================================================
--- /dev/null
+++ libcxx/test/std/containers/associative/set/merge.pass.cpp
@@ -0,0 +1,125 @@
+//===----------------------------------------------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <set>
+
+// class set
+
+// template <class C2>
+// void merge(set<key_type, C2, allocator_type>& source);
+
+#include <set>
+#include "test_macros.h"
+#include "Counter.h"
+
+template <class Set>
+bool set_equal(const Set& set, Set other)
+{
+ return set == other;
+}
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+struct throw_comparator
+{
+ bool& should_throw_;
+
+ throw_comparator(bool& should_throw) : should_throw_(should_throw) {}
+
+ template <class T>
+ bool operator()(const T& lhs, const T& rhs) const
+ {
+ if (should_throw_)
+ throw 0;
+ return lhs < rhs;
+ }
+};
+#endif
+
+int main()
+{
+ {
+ std::set<int> src{1, 3, 5};
+ std::set<int> dst{2, 4, 5};
+ dst.merge(src);
+ assert(set_equal(src, {5}));
+ assert(set_equal(dst, {1, 2, 3, 4, 5}));
+ }
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+ {
+ bool do_throw = false;
+ typedef std::set<Counter<int>, throw_comparator> set_type;
+ set_type src({1, 3, 5}, throw_comparator(do_throw));
+ set_type dst({2, 4, 5}, throw_comparator(do_throw));
+
+ assert(Counter_base::gConstructed == 6);
+
+ do_throw = true;
+ try
+ {
+ dst.merge(src);
+ }
+ catch (int)
+ {
+ do_throw = false;
+ }
+ assert(!do_throw);
+ assert(set_equal(src, set_type({1, 3, 5}, throw_comparator(do_throw))));
+ assert(set_equal(dst, set_type({2, 4, 5}, throw_comparator(do_throw))));
+ }
+#endif
+ assert(Counter_base::gConstructed == 0);
+ struct comparator
+ {
+ comparator() = default;
+
+ bool operator()(const Counter<int>& lhs, const Counter<int>& rhs) const
+ {
+ return lhs < rhs;
+ }
+ };
+ {
+ typedef std::set<Counter<int>, std::less<Counter<int>>> first_set_type;
+ typedef std::set<Counter<int>, comparator> second_set_type;
+ typedef std::multiset<Counter<int>, comparator> third_set_type;
+
+ first_set_type first{1, 2, 3};
+ second_set_type second{2, 3, 4};
+ third_set_type third{1, 3};
+
+ assert(Counter_base::gConstructed == 8);
+
+ first.merge(second);
+ first.merge(std::move(second));
+ first.merge(third);
+ first.merge(std::move(third));
+
+ assert(set_equal(first, {1, 2, 3, 4}));
+ assert(set_equal(second, {2, 3}));
+ assert(set_equal(third, {1, 3}));
+
+ assert(Counter_base::gConstructed == 8);
+ }
+ assert(Counter_base::gConstructed == 0);
+ {
+ std::set<int> first;
+ {
+ std::set<int> second;
+ first.merge(second);
+ first.merge(std::move(second));
+ }
+ {
+ std::multiset<int> second;
+ first.merge(second);
+ first.merge(std::move(second));
+ }
+ }
+}
Index: libcxx/test/std/containers/associative/multiset/merge.pass.cpp
===================================================================
--- /dev/null
+++ libcxx/test/std/containers/associative/multiset/merge.pass.cpp
@@ -0,0 +1,134 @@
+//===----------------------------------------------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <set>
+
+// class multiset
+
+// template <class C2>
+// void merge(multiset<Key, C2, Allocator>& source);
+//
+// template <class C2>
+// void merge(multiset<Key, C2, Allocator>&& source);
+//
+// template <class C2>
+// void merge(set<Key, C2, Allocator>& source);
+//
+// template <class C2>
+// void merge(set<Key, C2, Allocator>&& source);
+
+#include <set>
+#include "test_macros.h"
+#include "Counter.h"
+
+template <class Set>
+bool set_equal(const Set& set, Set other)
+{
+ return set == other;
+}
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+struct throw_comparator
+{
+ bool& should_throw_;
+
+ throw_comparator(bool& should_throw) : should_throw_(should_throw) {}
+
+ template <class T>
+ bool operator()(const T& lhs, const T& rhs) const
+ {
+ if (should_throw_)
+ throw 0;
+ return lhs < rhs;
+ }
+};
+#endif
+
+int main()
+{
+ {
+ std::multiset<int> src{1, 3, 5};
+ std::multiset<int> dst{2, 4, 5};
+ dst.merge(src);
+ assert(set_equal(src, {}));
+ assert(set_equal(dst, {1, 2, 3, 4, 5, 5}));
+ }
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+ {
+ bool do_throw = false;
+ typedef std::multiset<Counter<int>, throw_comparator> set_type;
+ set_type src({1, 3, 5}, throw_comparator(do_throw));
+ set_type dst({2, 4, 5}, throw_comparator(do_throw));
+
+ assert(Counter_base::gConstructed == 6);
+
+ do_throw = true;
+ try
+ {
+ dst.merge(src);
+ }
+ catch (int)
+ {
+ do_throw = false;
+ }
+ assert(!do_throw);
+ assert(set_equal(src, set_type({1, 3, 5}, throw_comparator(do_throw))));
+ assert(set_equal(dst, set_type({2, 4, 5}, throw_comparator(do_throw))));
+ }
+#endif
+ assert(Counter_base::gConstructed == 0);
+ struct comparator
+ {
+ comparator() = default;
+
+ bool operator()(const Counter<int>& lhs, const Counter<int>& rhs) const
+ {
+ return lhs < rhs;
+ }
+ };
+ {
+ typedef std::multiset<Counter<int>, std::less<Counter<int>>> first_set_type;
+ typedef std::multiset<Counter<int>, comparator> second_set_type;
+ typedef std::set<Counter<int>, comparator> third_set_type;
+
+ first_set_type first{1, 2, 3};
+ second_set_type second{2, 3, 4};
+ third_set_type third{1, 3};
+
+ assert(Counter_base::gConstructed == 8);
+
+ first.merge(second);
+ first.merge(std::move(second));
+ first.merge(third);
+ first.merge(std::move(third));
+
+ assert(set_equal(first, {1, 1, 2, 2, 3, 3, 3, 4}));
+ assert(set_equal(second, {}));
+ assert(set_equal(third, {}));
+
+ assert(Counter_base::gConstructed == 8);
+ }
+ assert(Counter_base::gConstructed == 0);
+ {
+ std::multiset<int> first;
+ {
+ std::multiset<int> second;
+ first.merge(second);
+ first.merge(std::move(second));
+ }
+ {
+ std::set<int> second;
+ first.merge(second);
+ first.merge(std::move(second));
+ }
+ }
+}
Index: libcxx/test/std/containers/associative/multimap/multimap.modifiers/merge.pass.cpp
===================================================================
--- /dev/null
+++ libcxx/test/std/containers/associative/multimap/multimap.modifiers/merge.pass.cpp
@@ -0,0 +1,125 @@
+//===----------------------------------------------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <map>
+
+// class multimap
+
+// template <class C2>
+// void merge(multimap<key_type, C2, allocator_type>& source);
+
+#include <map>
+#include "test_macros.h"
+#include "Counter.h"
+
+template <class Map>
+bool map_equal(const Map& map, Map other)
+{
+ return map == other;
+}
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+struct throw_comparator
+{
+ bool& should_throw_;
+
+ throw_comparator(bool& should_throw) : should_throw_(should_throw) {}
+
+ template <class T>
+ bool operator()(const T& lhs, const T& rhs) const
+ {
+ if (should_throw_)
+ throw 0;
+ return lhs < rhs;
+ }
+};
+#endif
+
+int main()
+{
+ {
+ std::multimap<int, int> src{{1, 0}, {3, 0}, {5, 0}};
+ std::multimap<int, int> dst{{2, 0}, {4, 0}, {5, 0}};
+ dst.merge(src);
+ assert(map_equal(src, {}));
+ assert(map_equal(dst, {{1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}, {5, 0}}));
+ }
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+ {
+ bool do_throw = false;
+ typedef std::multimap<Counter<int>, int, throw_comparator> map_type;
+ map_type src({{1, 0}, {3, 0}, {5, 0}}, throw_comparator(do_throw));
+ map_type dst({{2, 0}, {4, 0}, {5, 0}}, throw_comparator(do_throw));
+
+ assert(Counter_base::gConstructed == 6);
+
+ do_throw = true;
+ try
+ {
+ dst.merge(src);
+ }
+ catch (int)
+ {
+ do_throw = false;
+ }
+ assert(!do_throw);
+ assert(map_equal(src, map_type({{1, 0}, {3, 0}, {5, 0}}, throw_comparator(do_throw))));
+ assert(map_equal(dst, map_type({{2, 0}, {4, 0}, {5, 0}}, throw_comparator(do_throw))));
+ }
+#endif
+ assert(Counter_base::gConstructed == 0);
+ struct comparator
+ {
+ comparator() = default;
+
+ bool operator()(const Counter<int>& lhs, const Counter<int>& rhs) const
+ {
+ return lhs < rhs;
+ }
+ };
+ {
+ typedef std::multimap<Counter<int>, int, std::less<Counter<int>>> first_map_type;
+ typedef std::multimap<Counter<int>, int, comparator> second_map_type;
+ typedef std::map<Counter<int>, int, comparator> third_map_type;
+
+ first_map_type first{{1, 0}, {2, 0}, {3, 0}};
+ second_map_type second{{2, 0}, {3, 0}, {4, 0}};
+ third_map_type third{{1, 0}, {3, 0}};
+
+ assert(Counter_base::gConstructed == 8);
+
+ first.merge(second);
+ first.merge(std::move(second));
+ first.merge(third);
+ first.merge(std::move(third));
+
+ assert(map_equal(first, {{1, 0}, {1, 0}, {2, 0}, {2, 0}, {3, 0}, {3, 0}, {3, 0}, {4, 0}}));
+ assert(map_equal(second, {}));
+ assert(map_equal(third, {}));
+
+ assert(Counter_base::gConstructed == 8);
+ }
+ assert(Counter_base::gConstructed == 0);
+ {
+ std::multimap<int, int> first;
+ {
+ std::multimap<int, int> second;
+ first.merge(second);
+ first.merge(std::move(second));
+ }
+ {
+ std::multimap<int, int> second;
+ first.merge(second);
+ first.merge(std::move(second));
+ }
+ }
+}
Index: libcxx/test/std/containers/associative/map/map.modifiers/merge.pass.cpp
===================================================================
--- /dev/null
+++ libcxx/test/std/containers/associative/map/map.modifiers/merge.pass.cpp
@@ -0,0 +1,125 @@
+//===----------------------------------------------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <map>
+
+// class map
+
+// template <class C2>
+// void merge(map<key_type, C2, allocator_type>& source);
+
+#include <map>
+#include "test_macros.h"
+#include "Counter.h"
+
+template <class Map>
+bool map_equal(const Map& map, Map other)
+{
+ return map == other;
+}
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+struct throw_comparator
+{
+ bool& should_throw_;
+
+ throw_comparator(bool& should_throw) : should_throw_(should_throw) {}
+
+ template <class T>
+ bool operator()(const T& lhs, const T& rhs) const
+ {
+ if (should_throw_)
+ throw 0;
+ return lhs < rhs;
+ }
+};
+#endif
+
+int main()
+{
+ {
+ std::map<int, int> src{{1, 0}, {3, 0}, {5, 0}};
+ std::map<int, int> dst{{2, 0}, {4, 0}, {5, 0}};
+ dst.merge(src);
+ assert(map_equal(src, {{5,0}}));
+ assert(map_equal(dst, {{1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}}));
+ }
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+ {
+ bool do_throw = false;
+ typedef std::map<Counter<int>, int, throw_comparator> map_type;
+ map_type src({{1, 0}, {3, 0}, {5, 0}}, throw_comparator(do_throw));
+ map_type dst({{2, 0}, {4, 0}, {5, 0}}, throw_comparator(do_throw));
+
+ assert(Counter_base::gConstructed == 6);
+
+ do_throw = true;
+ try
+ {
+ dst.merge(src);
+ }
+ catch (int)
+ {
+ do_throw = false;
+ }
+ assert(!do_throw);
+ assert(map_equal(src, map_type({{1, 0}, {3, 0}, {5, 0}}, throw_comparator(do_throw))));
+ assert(map_equal(dst, map_type({{2, 0}, {4, 0}, {5, 0}}, throw_comparator(do_throw))));
+ }
+#endif
+ assert(Counter_base::gConstructed == 0);
+ struct comparator
+ {
+ comparator() = default;
+
+ bool operator()(const Counter<int>& lhs, const Counter<int>& rhs) const
+ {
+ return lhs < rhs;
+ }
+ };
+ {
+ typedef std::map<Counter<int>, int, std::less<Counter<int>>> first_map_type;
+ typedef std::map<Counter<int>, int, comparator> second_map_type;
+ typedef std::multimap<Counter<int>, int, comparator> third_map_type;
+
+ first_map_type first{{1, 0}, {2, 0}, {3, 0}};
+ second_map_type second{{2, 0}, {3, 0}, {4, 0}};
+ third_map_type third{{1, 0}, {3, 0}};
+
+ assert(Counter_base::gConstructed == 8);
+
+ first.merge(second);
+ first.merge(std::move(second));
+ first.merge(third);
+ first.merge(std::move(third));
+
+ assert(map_equal(first, {{1, 0}, {2, 0}, {3, 0}, {4, 0}}));
+ assert(map_equal(second, {{2, 0}, {3, 0}}));
+ assert(map_equal(third, {{1, 0}, {3, 0}}));
+
+ assert(Counter_base::gConstructed == 8);
+ }
+ assert(Counter_base::gConstructed == 0);
+ {
+ std::map<int, int> first;
+ {
+ std::map<int, int> second;
+ first.merge(second);
+ first.merge(std::move(second));
+ }
+ {
+ std::multimap<int, int> second;
+ first.merge(second);
+ first.merge(std::move(second));
+ }
+ }
+}
Index: libcxx/include/unordered_set
===================================================================
--- libcxx/include/unordered_set
+++ libcxx/include/unordered_set
@@ -127,6 +127,15 @@
iterator erase(const_iterator first, const_iterator last);
void clear() noexcept;
+ template<class H2, class P2>
+ void merge(unordered_set<Key, H2, P2, Allocator>& source); // C++17
+ template<class H2, class P2>
+ void merge(unordered_set<Key, H2, P2, Allocator>&& source); // C++17
+ template<class H2, class P2>
+ void merge(unordered_multiset<Key, H2, P2, Allocator>& source); // C++17
+ template<class H2, class P2>
+ void merge(unordered_multiset<Key, H2, P2, Allocator>&& source); // C++17
+
void swap(unordered_set&)
noexcept(allocator_traits<Allocator>::is_always_equal::value &&
noexcept(swap(declval<hasher&>(), declval<hasher&>())) &&
@@ -282,6 +291,15 @@
iterator erase(const_iterator first, const_iterator last);
void clear() noexcept;
+ template<class H2, class P2>
+ void merge(unordered_multiset<Key, H2, P2, Allocator>& source); // C++17
+ template<class H2, class P2>
+ void merge(unordered_multiset<Key, H2, P2, Allocator>&& source); // C++17
+ template<class H2, class P2>
+ void merge(unordered_set<Key, H2, P2, Allocator>& source); // C++17
+ template<class H2, class P2>
+ void merge(unordered_set<Key, H2, P2, Allocator>&& source); // C++17
+
void swap(unordered_multiset&)
noexcept(allocator_traits<Allocator>::is_always_equal::value &&
noexcept(swap(declval<hasher&>(), declval<hasher&>())) &&
@@ -347,6 +365,9 @@
_LIBCPP_BEGIN_NAMESPACE_STD
+template <class _Value, class _Hash, class _Pred, class _Alloc>
+class unordered_multiset;
+
template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
class _Alloc = allocator<_Value> >
class _LIBCPP_TEMPLATE_VIS unordered_set
@@ -384,6 +405,8 @@
typedef __insert_return_type<iterator, node_type> insert_return_type;
#endif
+ _LIBCPP_INLINE_VISIBILITY __table& __get_table() { return __table_; }
+
_LIBCPP_INLINE_VISIBILITY
unordered_set()
_NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
@@ -589,6 +612,39 @@
{
return __table_.template __node_handle_extract<node_type>(__it);
}
+
+ template<class _H2, class _P2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ __table_.__node_handle_merge_unique(__source.__get_table());
+ }
+ template<class _H2, class _P2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ __table_.__node_handle_merge_unique(__source.__get_table());
+ }
+ template<class _H2, class _P2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ __table_.__node_handle_merge_unique(__source.__get_table());
+ }
+ template<class _H2, class _P2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ __table_.__node_handle_merge_unique(__source.__get_table());
+ }
#endif
_LIBCPP_INLINE_VISIBILITY
@@ -937,6 +993,8 @@
typedef __set_node_handle<typename __table::__node, allocator_type> node_type;
#endif
+ _LIBCPP_INLINE_VISIBILITY __table& __get_table() { return __table_; }
+
_LIBCPP_INLINE_VISIBILITY
unordered_multiset()
_NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
@@ -1101,6 +1159,39 @@
{
return __table_.template __node_handle_extract<node_type>(__key);
}
+
+ template <class _H2, class _P2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ return __table_.__node_handle_merge_multi(__source.__get_table());
+ }
+ template <class _H2, class _P2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ return __table_.__node_handle_merge_multi(__source.__get_table());
+ }
+ template <class _H2, class _P2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ return __table_.__node_handle_merge_multi(__source.__get_table());
+ }
+ template <class _H2, class _P2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ return __table_.__node_handle_merge_multi(__source.__get_table());
+ }
#endif
_LIBCPP_INLINE_VISIBILITY
Index: libcxx/include/unordered_map
===================================================================
--- libcxx/include/unordered_map
+++ libcxx/include/unordered_map
@@ -153,6 +153,15 @@
iterator erase(const_iterator first, const_iterator last);
void clear() noexcept;
+ template<class H2, class P2>
+ void merge(unordered_map<Key, T, H2, P2, Allocator>& source); // C++17
+ template<class H2, class P2>
+ void merge(unordered_map<Key, T, H2, P2, Allocator>&& source); // C++17
+ template<class H2, class P2>
+ void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source); // C++17
+ template<class H2, class P2>
+ void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source); // C++17
+
void swap(unordered_map&)
noexcept(
(!allocator_type::propagate_on_container_swap::value ||
@@ -325,6 +334,15 @@
iterator erase(const_iterator first, const_iterator last);
void clear() noexcept;
+ template<class H2, class P2>
+ void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source); // C++17
+ template<class H2, class P2>
+ void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source); // C++17
+ template<class H2, class P2>
+ void merge(unordered_map<Key, T, H2, P2, Allocator>& source); // C++17
+ template<class H2, class P2>
+ void merge(unordered_map<Key, T, H2, P2, Allocator>&& source); // C++17
+
void swap(unordered_multimap&)
noexcept(
(!allocator_type::propagate_on_container_swap::value ||
@@ -807,6 +825,9 @@
template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
};
+template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
+class unordered_multimap;
+
template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
class _Alloc = allocator<pair<const _Key, _Tp> > >
class _LIBCPP_TEMPLATE_VIS unordered_map
@@ -864,6 +885,8 @@
typedef __insert_return_type<iterator, node_type> insert_return_type;
#endif
+ _LIBCPP_INLINE_VISIBILITY __table& __get_table() { return __table_; }
+
_LIBCPP_INLINE_VISIBILITY
unordered_map()
_NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
@@ -1187,6 +1210,39 @@
return __table_.template __node_handle_extract<node_type>(
__it.__i_);
}
+
+ template <class _H2, class _P2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ return __table_.__node_handle_merge_unique(__source.__get_table());
+ }
+ template <class _H2, class _P2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>&& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ return __table_.__node_handle_merge_unique(__source.__get_table());
+ }
+ template <class _H2, class _P2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ return __table_.__node_handle_merge_unique(__source.__get_table());
+ }
+ template <class _H2, class _P2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>&& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ return __table_.__node_handle_merge_unique(__source.__get_table());
+ }
#endif
_LIBCPP_INLINE_VISIBILITY
@@ -1645,6 +1701,8 @@
typedef __map_node_handle<__node, allocator_type> node_type;
#endif
+ _LIBCPP_INLINE_VISIBILITY __table& __get_table() { return __table_; }
+
_LIBCPP_INLINE_VISIBILITY
unordered_multimap()
_NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
@@ -1846,6 +1904,39 @@
return __table_.template __node_handle_extract<node_type>(
__it.__i_);
}
+
+ template <class _H2, class _P2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ return __table_.__node_handle_merge_multi(__source.__get_table());
+ }
+ template <class _H2, class _P2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>&& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ return __table_.__node_handle_merge_multi(__source.__get_table());
+ }
+ template <class _H2, class _P2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ return __table_.__node_handle_merge_multi(__source.__get_table());
+ }
+ template <class _H2, class _P2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>&& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ return __table_.__node_handle_merge_multi(__source.__get_table());
+ }
#endif
_LIBCPP_INLINE_VISIBILITY
Index: libcxx/include/set
===================================================================
--- libcxx/include/set
+++ libcxx/include/set
@@ -128,6 +128,15 @@
iterator erase(const_iterator first, const_iterator last);
void clear() noexcept;
+ template<class C2>
+ void merge(set<Key, C2, Allocator>& source); // C++17
+ template<class C2>
+ void merge(set<Key, C2, Allocator>&& source); // C++17
+ template<class C2>
+ void merge(multiset<Key, C2, Allocator>& source); // C++17
+ template<class C2>
+ void merge(multiset<Key, C2, Allocator>&& source); // C++17
+
void swap(set& s)
noexcept(
__is_nothrow_swappable<key_compare>::value &&
@@ -316,6 +325,15 @@
iterator erase(const_iterator first, const_iterator last);
void clear() noexcept;
+ template<class C2>
+ void merge(multiset<Key, C2, Allocator>& source); // C++17
+ template<class C2>
+ void merge(multiset<Key, C2, Allocator>&& source); // C++17
+ template<class C2>
+ void merge(set<Key, C2, Allocator>& source); // C++17
+ template<class C2>
+ void merge(set<Key, C2, Allocator>&& source); // C++17
+
void swap(multiset& s)
noexcept(
__is_nothrow_swappable<key_compare>::value &&
@@ -409,6 +427,9 @@
_LIBCPP_BEGIN_NAMESPACE_STD
+template <class _Key, class _Compare, class _Allocator>
+class multiset;
+
template <class _Key, class _Compare = less<_Key>,
class _Allocator = allocator<_Key> >
class _LIBCPP_TEMPLATE_VIS set
@@ -448,6 +469,8 @@
typedef __insert_return_type<iterator, node_type> insert_return_type;
#endif
+ _LIBCPP_INLINE_VISIBILITY __base& __get_tree() { return __tree_; }
+
_LIBCPP_INLINE_VISIBILITY
set()
_NOEXCEPT_(
@@ -680,6 +703,38 @@
{
return __tree_.template __node_handle_extract<node_type>(__it);
}
+ template <class _C2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(set<key_type, _C2, allocator_type>& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ __tree_.__node_handle_merge_unique(__source.__get_tree());
+ }
+ template <class _C2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(set<key_type, _C2, allocator_type>&& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ __tree_.__node_handle_merge_unique(__source.__get_tree());
+ }
+ template <class _C2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(multiset<key_type, _C2, allocator_type>& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ __tree_.__node_handle_merge_unique(__source.__get_tree());
+ }
+ template <class _C2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(multiset<key_type, _C2, allocator_type>&& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ __tree_.__node_handle_merge_unique(__source.__get_tree());
+ }
#endif
_LIBCPP_INLINE_VISIBILITY
@@ -890,6 +945,8 @@
typedef __set_node_handle<typename __base::__node, allocator_type> node_type;
#endif
+ _LIBCPP_INLINE_VISIBILITY __base& __get_tree() { return __tree_; }
+
// construct/copy/destroy:
_LIBCPP_INLINE_VISIBILITY
multiset()
@@ -1121,6 +1178,38 @@
{
return __tree_.template __node_handle_extract<node_type>(__it);
}
+ template <class _C2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(multiset<key_type, _C2, allocator_type>& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ __tree_.__node_handle_merge_multi(__source.__get_tree());
+ }
+ template <class _C2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(multiset<key_type, _C2, allocator_type>&& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ __tree_.__node_handle_merge_multi(__source.__get_tree());
+ }
+ template <class _C2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(set<key_type, _C2, allocator_type>& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ __tree_.__node_handle_merge_multi(__source.__get_tree());
+ }
+ template <class _C2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(set<key_type, _C2, allocator_type>&& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ __tree_.__node_handle_merge_multi(__source.__get_tree());
+ }
#endif
_LIBCPP_INLINE_VISIBILITY
Index: libcxx/include/map
===================================================================
--- libcxx/include/map
+++ libcxx/include/map
@@ -167,6 +167,15 @@
iterator erase(const_iterator first, const_iterator last);
void clear() noexcept;
+ template<class C2>
+ void merge(map<Key, T, C2, Allocator>& source); // C++17
+ template<class C2>
+ void merge(map<Key, T, C2, Allocator>&& source); // C++17
+ template<class C2>
+ void merge(multimap<Key, T, C2, Allocator>& source); // C++17
+ template<class C2>
+ void merge(multimap<Key, T, C2, Allocator>&& source); // C++17
+
void swap(map& m)
noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
is_nothrow_swappable<key_compare>::value); // C++17
@@ -368,6 +377,15 @@
iterator erase(const_iterator first, const_iterator last);
void clear() noexcept;
+ template<class C2>
+ void merge(multimap<Key, T, C2, Allocator>& source); // C++17
+ template<class C2>
+ void merge(multimap<Key, T, C2, Allocator>&& source); // C++17
+ template<class C2>
+ void merge(map<Key, T, C2, Allocator>& source); // C++17
+ template<class C2>
+ void merge(map<Key, T, C2, Allocator>&& source); // C++17
+
void swap(multimap& m)
noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
is_nothrow_swappable<key_compare>::value); // C++17
@@ -925,6 +943,8 @@
typedef __insert_return_type<iterator, node_type> insert_return_type;
#endif
+ _LIBCPP_INLINE_VISIBILITY __base& __get_tree() { return __tree_; }
+
_LIBCPP_INLINE_VISIBILITY
map()
_NOEXCEPT_(
@@ -1299,6 +1319,38 @@
{
return __tree_.template __node_handle_extract<node_type>(__it.__i_);
}
+ template <class _C2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(map<key_type, mapped_type, _C2, allocator_type>& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ __tree_.__node_handle_merge_unique(__source.__get_tree());
+ }
+ template <class _C2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(map<key_type, mapped_type, _C2, allocator_type>&& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ __tree_.__node_handle_merge_unique(__source.__get_tree());
+ }
+ template <class _C2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(multimap<key_type, mapped_type, _C2, allocator_type>& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ __tree_.__node_handle_merge_unique(__source.__get_tree());
+ }
+ template <class _C2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(multimap<key_type, mapped_type, _C2, allocator_type>&& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ __tree_.__node_handle_merge_unique(__source.__get_tree());
+ }
#endif
_LIBCPP_INLINE_VISIBILITY
@@ -1614,6 +1666,8 @@
typedef __map_node_handle<typename __base::__node, allocator_type> node_type;
#endif
+ _LIBCPP_INLINE_VISIBILITY __base& __get_tree() { return __tree_; }
+
_LIBCPP_INLINE_VISIBILITY
multimap()
_NOEXCEPT_(
@@ -1881,6 +1935,38 @@
return __tree_.template __node_handle_extract<node_type>(
__it.__i_);
}
+ template <class _C2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(multimap<key_type, mapped_type, _C2, allocator_type>& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ return __tree_.__node_handle_merge_multi(__source.__get_tree());
+ }
+ template <class _C2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(multimap<key_type, mapped_type, _C2, allocator_type>&& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ return __tree_.__node_handle_merge_multi(__source.__get_tree());
+ }
+ template <class _C2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(map<key_type, mapped_type, _C2, allocator_type>& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ return __tree_.__node_handle_merge_multi(__source.__get_tree());
+ }
+ template <class _C2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(map<key_type, mapped_type, _C2, allocator_type>&& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ return __tree_.__node_handle_merge_multi(__source.__get_tree());
+ }
#endif
_LIBCPP_INLINE_VISIBILITY
Index: libcxx/include/__tree
===================================================================
--- libcxx/include/__tree
+++ libcxx/include/__tree
@@ -1341,11 +1341,15 @@
#endif // !_LIBCPP_CXX03_LANG
+ _LIBCPP_INLINE_VISIBILITY
pair<iterator, bool> __node_insert_unique(__node_pointer __nd);
+ _LIBCPP_INLINE_VISIBILITY
iterator __node_insert_unique(const_iterator __p,
__node_pointer __nd);
+ _LIBCPP_INLINE_VISIBILITY
iterator __node_insert_multi(__node_pointer __nd);
+ _LIBCPP_INLINE_VISIBILITY
iterator __node_insert_multi(const_iterator __p, __node_pointer __nd);
@@ -1358,13 +1362,19 @@
template <class _NodeHandle>
_LIBCPP_INLINE_VISIBILITY
iterator __node_handle_insert_unique(const_iterator, _NodeHandle&&);
+ template <class _Tree>
+ _LIBCPP_INLINE_VISIBILITY
+ void __node_handle_merge_unique(_Tree& __source);
template <class _NodeHandle>
_LIBCPP_INLINE_VISIBILITY
iterator __node_handle_insert_multi(_NodeHandle&&);
template <class _NodeHandle>
_LIBCPP_INLINE_VISIBILITY
iterator __node_handle_insert_multi(const_iterator, _NodeHandle&&);
+ template <class _Tree>
+ _LIBCPP_INLINE_VISIBILITY
+ void __node_handle_merge_multi(_Tree& __source);
template <class _NodeHandle>
@@ -2471,6 +2481,30 @@
return _NodeHandle(__np, __alloc());
}
+template <class _Tp, class _Compare, class _Allocator>
+template <class _Tree>
+_LIBCPP_INLINE_VISIBILITY
+void
+__tree<_Tp, _Compare, _Allocator>::__node_handle_merge_unique(_Tree& __source)
+{
+ static_assert(is_same<typename _Tree::__node_pointer, __node_pointer>::value, "");
+
+ for (typename _Tree::iterator __i = __source.begin();
+ __i != __source.end();)
+ {
+ __node_pointer __src_ptr = __i.__get_np();
+ __parent_pointer __parent;
+ __node_base_pointer& __child = __find_equal(
+ __parent, _NodeTypes::__get_key(__src_ptr->__value_));
+ ++__i;
+ if (__child != nullptr)
+ continue;
+ __source.__remove_node_pointer(__src_ptr);
+ __insert_node_at(__parent, __child,
+ static_cast<__node_base_pointer>(__src_ptr));
+ }
+}
+
template <class _Tp, class _Compare, class _Allocator>
template <class _NodeHandle>
_LIBCPP_INLINE_VISIBILITY
@@ -2507,6 +2541,28 @@
return iterator(__ptr);
}
+template <class _Tp, class _Compare, class _Allocator>
+template <class _Tree>
+_LIBCPP_INLINE_VISIBILITY
+void
+__tree<_Tp, _Compare, _Allocator>::__node_handle_merge_multi(_Tree& __source)
+{
+ static_assert(is_same<typename _Tree::__node_pointer, __node_pointer>::value, "");
+
+ for (typename _Tree::iterator __i = __source.begin();
+ __i != __source.end();)
+ {
+ __node_pointer __src_ptr = __i.__get_np();
+ __parent_pointer __parent;
+ __node_base_pointer& __child = __find_leaf_high(
+ __parent, _NodeTypes::__get_key(__src_ptr->__value_));
+ ++__i;
+ __source.__remove_node_pointer(__src_ptr);
+ __insert_node_at(__parent, __child,
+ static_cast<__node_base_pointer>(__src_ptr));
+ }
+}
+
#endif // _LIBCPP_STD_VER > 14
template <class _Tp, class _Compare, class _Allocator>
Index: libcxx/include/__node_handle
===================================================================
--- libcxx/include/__node_handle
+++ libcxx/include/__node_handle
@@ -26,8 +26,7 @@
#if _LIBCPP_STD_VER > 14
-// FIXME: Uncomment this when we support the 'merge' functionality.
-// #define __cpp_lib_node_extract 201606L
+#define __cpp_lib_node_extract 201606L
// Specialized in __tree & __hash_table for their _NodeType.
template <class _NodeType, class _Alloc>
Index: libcxx/include/__hash_table
===================================================================
--- libcxx/include/__hash_table
+++ libcxx/include/__hash_table
@@ -1058,8 +1058,26 @@
);
}
+private:
+ _LIBCPP_INLINE_VISIBILITY
+ __next_pointer __node_insert_multi_prepare(size_t __cp_hash,
+ value_type& __cp_val);
+ _LIBCPP_INLINE_VISIBILITY
+ void __node_insert_multi_perform(__node_pointer __cp,
+ __next_pointer __pn) _NOEXCEPT;
+
+ _LIBCPP_INLINE_VISIBILITY
+ __next_pointer __node_insert_unique_prepare(size_t __nd_hash,
+ value_type& __nd_val);
+ _LIBCPP_INLINE_VISIBILITY
+ void __node_insert_unique_perform(__node_pointer __ptr) _NOEXCEPT;
+
+public:
+ _LIBCPP_INLINE_VISIBILITY
pair<iterator, bool> __node_insert_unique(__node_pointer __nd);
+ _LIBCPP_INLINE_VISIBILITY
iterator __node_insert_multi(__node_pointer __nd);
+ _LIBCPP_INLINE_VISIBILITY
iterator __node_insert_multi(const_iterator __p,
__node_pointer __nd);
@@ -1170,13 +1188,19 @@
_LIBCPP_INLINE_VISIBILITY
iterator __node_handle_insert_unique(const_iterator __hint,
_NodeHandle&& __nh);
+ template <class _Table>
+ _LIBCPP_INLINE_VISIBILITY
+ void __node_handle_merge_unique(_Table& __source);
template <class _NodeHandle>
_LIBCPP_INLINE_VISIBILITY
iterator __node_handle_insert_multi(_NodeHandle&& __nh);
template <class _NodeHandle>
_LIBCPP_INLINE_VISIBILITY
iterator __node_handle_insert_multi(const_iterator __hint, _NodeHandle&& __nh);
+ template <class _Table>
+ _LIBCPP_INLINE_VISIBILITY
+ void __node_handle_merge_multi(_Table& __source);
template <class _NodeHandle>
_LIBCPP_INLINE_VISIBILITY
@@ -1850,93 +1874,100 @@
}
template <class _Tp, class _Hash, class _Equal, class _Alloc>
-pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd)
+_LIBCPP_INLINE_VISIBILITY
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_prepare(
+ size_t __hash, value_type& __value)
{
- __nd->__hash_ = hash_function()(__nd->__value_);
size_type __bc = bucket_count();
- bool __inserted = false;
- __next_pointer __ndptr;
- size_t __chash;
+
if (__bc != 0)
{
- __chash = __constrain_hash(__nd->__hash_, __bc);
- __ndptr = __bucket_list_[__chash];
+ size_t __chash = __constrain_hash(__hash, __bc);
+ __next_pointer __ndptr = __bucket_list_[__chash];
if (__ndptr != nullptr)
{
for (__ndptr = __ndptr->__next_; __ndptr != nullptr &&
__constrain_hash(__ndptr->__hash(), __bc) == __chash;
__ndptr = __ndptr->__next_)
{
- if (key_eq()(__ndptr->__upcast()->__value_, __nd->__value_))
- goto __done;
+ if (key_eq()(__ndptr->__upcast()->__value_, __value))
+ return __ndptr;
}
}
}
+ if (size()+1 > __bc * max_load_factor() || __bc == 0)
{
- if (size()+1 > __bc * max_load_factor() || __bc == 0)
- {
- rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
- size_type(ceil(float(size() + 1) / max_load_factor()))));
- __bc = bucket_count();
- __chash = __constrain_hash(__nd->__hash_, __bc);
- }
- // insert_after __bucket_list_[__chash], or __first_node if bucket is null
- __next_pointer __pn = __bucket_list_[__chash];
- if (__pn == nullptr)
- {
- __pn =__p1_.first().__ptr();
- __nd->__next_ = __pn->__next_;
- __pn->__next_ = __nd->__ptr();
- // fix up __bucket_list_
- __bucket_list_[__chash] = __pn;
- if (__nd->__next_ != nullptr)
- __bucket_list_[__constrain_hash(__nd->__next_->__hash(), __bc)] = __nd->__ptr();
- }
- else
- {
- __nd->__next_ = __pn->__next_;
- __pn->__next_ = __nd->__ptr();
- }
+ rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
+ size_type(ceil(float(size() + 1) / max_load_factor()))));
+ }
+ return nullptr;
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+_LIBCPP_INLINE_VISIBILITY
+void
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_perform(
+ __node_pointer __nd) _NOEXCEPT
+{
+ size_type __bc = bucket_count();
+ size_t __chash = __constrain_hash(__nd->__hash(), __bc);
+ // insert_after __bucket_list_[__chash], or __first_node if bucket is null
+ __next_pointer __pn = __bucket_list_[__chash];
+ if (__pn == nullptr)
+ {
+ __pn =__p1_.first().__ptr();
+ __nd->__next_ = __pn->__next_;
+ __pn->__next_ = __nd->__ptr();
+ // fix up __bucket_list_
+ __bucket_list_[__chash] = __pn;
+ if (__nd->__next_ != nullptr)
+ __bucket_list_[__constrain_hash(__nd->__next_->__hash(), __bc)] = __nd->__ptr();
+ }
+ else
+ {
+ __nd->__next_ = __pn->__next_;
+ __pn->__next_ = __nd->__ptr();
+ }
+ ++size();
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd)
+{
+ __nd->__hash_ = hash_function()(__nd->__value_);
+ __next_pointer __ndptr =
+ __node_insert_unique_prepare(__nd->__hash(), __nd->__value_);
+ bool __inserted = false;
+ if (__ndptr == nullptr)
+ {
+ __node_insert_unique_perform(__nd);
__ndptr = __nd->__ptr();
- // increment size
- ++size();
__inserted = true;
}
-__done:
#if _LIBCPP_DEBUG_LEVEL >= 2
return pair<iterator, bool>(iterator(__ndptr, this), __inserted);
#else
return pair<iterator, bool>(iterator(__ndptr), __inserted);
#endif
}
template <class _Tp, class _Hash, class _Equal, class _Alloc>
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp)
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_prepare(
+ size_t __cp_hash, value_type& __cp_val)
{
- __cp->__hash_ = hash_function()(__cp->__value_);
size_type __bc = bucket_count();
if (size()+1 > __bc * max_load_factor() || __bc == 0)
{
rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
size_type(ceil(float(size() + 1) / max_load_factor()))));
__bc = bucket_count();
}
- size_t __chash = __constrain_hash(__cp->__hash_, __bc);
+ size_t __chash = __constrain_hash(__cp_hash, __bc);
__next_pointer __pn = __bucket_list_[__chash];
- if (__pn == nullptr)
- {
- __pn =__p1_.first().__ptr();
- __cp->__next_ = __pn->__next_;
- __pn->__next_ = __cp->__ptr();
- // fix up __bucket_list_
- __bucket_list_[__chash] = __pn;
- if (__cp->__next_ != nullptr)
- __bucket_list_[__constrain_hash(__cp->__next_->__hash(), __bc)]
- = __cp->__ptr();
- }
- else
+ if (__pn != nullptr)
{
for (bool __found = false; __pn->__next_ != nullptr &&
__constrain_hash(__pn->__next_->__hash(), __bc) == __chash;
@@ -1947,15 +1978,39 @@
// true true loop
// false true set __found to true
// true false break
- if (__found != (__pn->__next_->__hash() == __cp->__hash_ &&
- key_eq()(__pn->__next_->__upcast()->__value_, __cp->__value_)))
+ if (__found != (__pn->__next_->__hash() == __cp_hash &&
+ key_eq()(__pn->__next_->__upcast()->__value_, __cp_val)))
{
if (!__found)
__found = true;
else
break;
}
}
+ }
+ return __pn;
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+void
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_perform(
+ __node_pointer __cp, __next_pointer __pn) _NOEXCEPT
+{
+ size_type __bc = bucket_count();
+ size_t __chash = __constrain_hash(__cp->__hash_, __bc);
+ if (__pn == nullptr)
+ {
+ __pn =__p1_.first().__ptr();
+ __cp->__next_ = __pn->__next_;
+ __pn->__next_ = __cp->__ptr();
+ // fix up __bucket_list_
+ __bucket_list_[__chash] = __pn;
+ if (__cp->__next_ != nullptr)
+ __bucket_list_[__constrain_hash(__cp->__next_->__hash(), __bc)]
+ = __cp->__ptr();
+ }
+ else
+ {
__cp->__next_ = __pn->__next_;
__pn->__next_ = __cp->__ptr();
if (__cp->__next_ != nullptr)
@@ -1966,6 +2021,17 @@
}
}
++size();
+}
+
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp)
+{
+ __cp->__hash_ = hash_function()(__cp->__value_);
+ __next_pointer __pn = __node_insert_multi_prepare(__cp->__hash(), __cp->__value_);
+ __node_insert_multi_perform(__cp, __pn);
+
#if _LIBCPP_DEBUG_LEVEL >= 2
return iterator(__cp->__ptr(), this);
#else
@@ -2216,6 +2282,33 @@
return _NodeHandle(remove(__p).release(), __alloc);
}
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Table>
+_LIBCPP_INLINE_VISIBILITY
+void
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_unique(
+ _Table& __source)
+{
+ static_assert(is_same<__node, typename _Table::__node>::value, "");
+
+ for (typename _Table::iterator __it = __source.begin();
+ __it != __source.end();)
+ {
+ __node_pointer __src_ptr = __it.__node_->__upcast();
+ size_t __hash = hash_function()(__src_ptr->__value_);
+ __next_pointer __ndptr =
+ __node_insert_unique_prepare(__hash, __src_ptr->__value_);
+ if (__ndptr == nullptr)
+ {
+ (void)__source.remove(__it++).release();
+ __src_ptr->__hash_ = __hash;
+ __node_insert_unique_perform(__src_ptr);
+ }
+ else
+ ++__it;
+ }
+}
+
template <class _Tp, class _Hash, class _Equal, class _Alloc>
template <class _NodeHandle>
_LIBCPP_INLINE_VISIBILITY
@@ -2244,6 +2337,27 @@
return __result;
}
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Table>
+_LIBCPP_INLINE_VISIBILITY
+void
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_multi(
+ _Table& __source)
+{
+ static_assert(is_same<typename _Table::__node, __node>::value, "");
+
+ for (typename _Table::iterator __it = __source.begin();
+ __it != __source.end();)
+ {
+ __node_pointer __src_ptr = __it.__node_->__upcast();
+ size_t __src_hash = hash_function()(__src_ptr->__value_);
+ __next_pointer __pn =
+ __node_insert_multi_prepare(__src_hash, __src_ptr->__value_);
+ (void)__source.remove(__it++).release();
+ __src_ptr->__hash_ = __src_hash;
+ __node_insert_multi_perform(__src_ptr, __pn);
+ }
+}
#endif // _LIBCPP_STD_VER > 14
template <class _Tp, class _Hash, class _Equal, class _Alloc>
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
