First half of C++17's splicing maps and sets
This commit adds a node handle type, (located in __node_handle), and adds
extract() and insert() members to all map and set types, as well as their
implementations in __tree and __hash_table.
The second half of this feature is adding merge() members, which splice nodes
in bulk from one container into another. This will be committed in a follow-up.
Differential revision: https://reviews.llvm.org/D46845
llvm-svn: 338472
Cr-Mirrored-From: sso://chromium.googlesource.com/_direct/external/github.com/llvm/llvm-project
Cr-Mirrored-Commit: b0386a515b60c2f43eaaef986bd5b1cdc4448244
diff --git a/include/map b/include/map
index 97ce4d0..559ec48 100644
--- a/include/map
+++ b/include/map
@@ -40,6 +40,8 @@
typedef implementation-defined const_iterator;
typedef std::reverse_iterator<iterator> reverse_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
+ typedef unspecified node_type; // C++17
+ typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type; // C++17
class value_compare
: public binary_function<value_type, value_type, bool>
@@ -137,6 +139,11 @@
void insert(InputIterator first, InputIterator last);
void insert(initializer_list<value_type> il);
+ node_type extract(const_iterator position); // C++17
+ node_type extract(const key_type& x); // C++17
+ insert_return_type insert(node_type&& nh); // C++17
+ iterator insert(const_iterator hint, node_type&& nh); // C++17
+
template <class... Args>
pair<iterator, bool> try_emplace(const key_type& k, Args&&... args); // C++17
template <class... Args>
@@ -260,6 +267,7 @@
typedef implementation-defined const_iterator;
typedef std::reverse_iterator<iterator> reverse_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
+ typedef unspecified node_type; // C++17
class value_compare
: public binary_function<value_type,value_type,bool>
@@ -349,6 +357,11 @@
void insert(InputIterator first, InputIterator last);
void insert(initializer_list<value_type> il);
+ node_type extract(const_iterator position); // C++17
+ node_type extract(const key_type& x); // C++17
+ iterator insert(node_type&& nh); // C++17
+ iterator insert(const_iterator hint, node_type&& nh); // C++17
+
iterator erase(const_iterator position);
iterator erase(iterator position); // C++14
size_type erase(const key_type& k);
@@ -440,6 +453,7 @@
#include <__config>
#include <__tree>
+#include <__node_handle>
#include <iterator>
#include <memory>
#include <utility>
@@ -906,6 +920,11 @@
typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
+#if _LIBCPP_STD_VER > 14
+ typedef __map_node_handle<typename __base::__node, allocator_type> node_type;
+ typedef __insert_return_type<iterator, node_type> insert_return_type;
+#endif
+
_LIBCPP_INLINE_VISIBILITY
map()
_NOEXCEPT_(
@@ -1253,6 +1272,35 @@
_LIBCPP_INLINE_VISIBILITY
void clear() _NOEXCEPT {__tree_.clear();}
+#if _LIBCPP_STD_VER > 14
+ _LIBCPP_INLINE_VISIBILITY
+ insert_return_type insert(node_type&& __nh)
+ {
+ _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
+ "node_type with incompatible allocator passed to map::insert()");
+ return __tree_.template __node_handle_insert_unique<
+ node_type, insert_return_type>(_VSTD::move(__nh));
+ }
+ _LIBCPP_INLINE_VISIBILITY
+ iterator insert(const_iterator __hint, node_type&& __nh)
+ {
+ _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
+ "node_type with incompatible allocator passed to map::insert()");
+ return __tree_.template __node_handle_insert_unique<node_type>(
+ __hint.__i_, _VSTD::move(__nh));
+ }
+ _LIBCPP_INLINE_VISIBILITY
+ node_type extract(key_type const& __key)
+ {
+ return __tree_.template __node_handle_extract<node_type>(__key);
+ }
+ _LIBCPP_INLINE_VISIBILITY
+ node_type extract(const_iterator __it)
+ {
+ return __tree_.template __node_handle_extract<node_type>(__it.__i_);
+ }
+#endif
+
_LIBCPP_INLINE_VISIBILITY
void swap(map& __m)
_NOEXCEPT_(__is_nothrow_swappable<__base>::value)
@@ -1562,6 +1610,10 @@
typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
+#if _LIBCPP_STD_VER > 14
+ typedef __map_node_handle<typename __base::__node, allocator_type> node_type;
+#endif
+
_LIBCPP_INLINE_VISIBILITY
multimap()
_NOEXCEPT_(
@@ -1800,6 +1852,37 @@
_LIBCPP_INLINE_VISIBILITY
iterator erase(const_iterator __f, const_iterator __l)
{return __tree_.erase(__f.__i_, __l.__i_);}
+
+#if _LIBCPP_STD_VER > 14
+ _LIBCPP_INLINE_VISIBILITY
+ iterator insert(node_type&& __nh)
+ {
+ _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
+ "node_type with incompatible allocator passed to multimap::insert()");
+ return __tree_.template __node_handle_insert_multi<node_type>(
+ _VSTD::move(__nh));
+ }
+ _LIBCPP_INLINE_VISIBILITY
+ iterator insert(const_iterator __hint, node_type&& __nh)
+ {
+ _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
+ "node_type with incompatible allocator passed to multimap::insert()");
+ return __tree_.template __node_handle_insert_multi<node_type>(
+ __hint.__i_, _VSTD::move(__nh));
+ }
+ _LIBCPP_INLINE_VISIBILITY
+ node_type extract(key_type const& __key)
+ {
+ return __tree_.template __node_handle_extract<node_type>(__key);
+ }
+ _LIBCPP_INLINE_VISIBILITY
+ node_type extract(const_iterator __it)
+ {
+ return __tree_.template __node_handle_extract<node_type>(
+ __it.__i_);
+ }
+#endif
+
_LIBCPP_INLINE_VISIBILITY
void clear() {__tree_.clear();}