Patch Detail
get:
Show a patch.
patch:
Update a patch.
put:
Update a patch.
GET /api/1.2/patches/2226289/?format=api
{ "id": 2226289, "url": "http://patchwork.ozlabs.org/api/1.2/patches/2226289/?format=api", "web_url": "http://patchwork.ozlabs.org/project/gcc/patch/bmm.hhublw6j3q.gcc.gcc-TEST.fdumont.27.1.1@forge-stage.sourceware.org/", "project": { "id": 17, "url": "http://patchwork.ozlabs.org/api/1.2/projects/17/?format=api", "name": "GNU Compiler Collection", "link_name": "gcc", "list_id": "gcc-patches.gcc.gnu.org", "list_email": "gcc-patches@gcc.gnu.org", "web_url": null, "scm_url": null, "webscm_url": null, "list_archive_url": "", "list_archive_url_format": "", "commit_url_format": "" }, "msgid": "<bmm.hhublw6j3q.gcc.gcc-TEST.fdumont.27.1.1@forge-stage.sourceware.org>", "list_archive_url": null, "date": "2026-04-22T10:38:43", "name": "[v1,1/1] libstdc++: Add fancy pointer support in map and set", "commit_ref": null, "pull_url": null, "state": "new", "archived": false, "hash": "8d6451ec7f1861f198ae162191672f020f590b86", "submitter": { "id": 93220, "url": "http://patchwork.ozlabs.org/api/1.2/people/93220/?format=api", "name": "François Dumont via Sourceware Forge", "email": "forge-bot+fdumont@forge-stage.sourceware.org" }, "delegate": null, "mbox": "http://patchwork.ozlabs.org/project/gcc/patch/bmm.hhublw6j3q.gcc.gcc-TEST.fdumont.27.1.1@forge-stage.sourceware.org/mbox/", "series": [ { "id": 500988, "url": "http://patchwork.ozlabs.org/api/1.2/series/500988/?format=api", "web_url": "http://patchwork.ozlabs.org/project/gcc/list/?series=500988", "date": "2026-04-22T10:38:42", "name": "libstdc++: Add fancy pointer support in map and set", "version": 1, "mbox": "http://patchwork.ozlabs.org/series/500988/mbox/" } ], "comments": "http://patchwork.ozlabs.org/api/patches/2226289/comments/", "check": "pending", "checks": "http://patchwork.ozlabs.org/api/patches/2226289/checks/", "tags": {}, "related": [], "headers": { "Return-Path": "<gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org>", "X-Original-To": [ "incoming@patchwork.ozlabs.org", "gcc-patches@gcc.gnu.org" ], "Delivered-To": [ "patchwork-incoming@legolas.ozlabs.org", "gcc-patches@gcc.gnu.org" ], "Authentication-Results": [ "legolas.ozlabs.org;\n spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org\n (client-ip=38.145.34.32; helo=vm01.sourceware.org;\n envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org;\n receiver=patchwork.ozlabs.org)", "sourceware.org; dmarc=none (p=none dis=none)\n header.from=forge-stage.sourceware.org", "sourceware.org;\n spf=pass smtp.mailfrom=forge-stage.sourceware.org", "server2.sourceware.org;\n arc=none smtp.remote-ip=38.145.34.39" ], "Received": [ "from vm01.sourceware.org (vm01.sourceware.org [38.145.34.32])\n\t(using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)\n\t key-exchange x25519 server-signature ECDSA (secp384r1) server-digest SHA384)\n\t(No client certificate requested)\n\tby legolas.ozlabs.org (Postfix) with ESMTPS id 4g0xQy1srBz1yCv\n\tfor <incoming@patchwork.ozlabs.org>; Wed, 22 Apr 2026 21:12:58 +1000 (AEST)", "from vm01.sourceware.org (localhost [127.0.0.1])\n\tby sourceware.org (Postfix) with ESMTP id 373B54162851\n\tfor <incoming@patchwork.ozlabs.org>; Wed, 22 Apr 2026 11:12:56 +0000 (GMT)", "from forge-stage.sourceware.org (vm08.sourceware.org [38.145.34.39])\n by sourceware.org (Postfix) with ESMTPS id 608F049B0BB8\n for <gcc-patches@gcc.gnu.org>; Wed, 22 Apr 2026 10:39:49 +0000 (GMT)", "from forge-stage.sourceware.org (localhost [IPv6:::1])\n (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)\n key-exchange x25519 server-signature ECDSA (prime256v1) server-digest SHA256)\n (No client certificate requested)\n by forge-stage.sourceware.org (Postfix) with ESMTPS id 3D62042B6D\n for <gcc-patches@gcc.gnu.org>; Wed, 22 Apr 2026 10:39:49 +0000 (UTC)" ], "DKIM-Filter": [ "OpenDKIM Filter v2.11.0 sourceware.org 373B54162851", "OpenDKIM Filter v2.11.0 sourceware.org 608F049B0BB8" ], "DMARC-Filter": "OpenDMARC Filter v1.4.2 sourceware.org 608F049B0BB8", "ARC-Filter": "OpenARC Filter v1.0.0 sourceware.org 608F049B0BB8", "ARC-Seal": "i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1776854389; cv=none;\n b=a99IngsAKzce/sXvFtykkF/cGoxJbl6piQ1HX/m/v+TqfXkXPdWMT6uAgS+/r4GOko64fXnMhVbuozbwIAgKOeUTgp6qthDpKkJ1VaJtYFB9Z2IsN2/IiL0Jf6cpiGNuq7b9nhxznYMNT6gFgJUyOK48p++S07GSlR60LJX1DaE=", "ARC-Message-Signature": "i=1; a=rsa-sha256; d=sourceware.org; s=key;\n t=1776854389; c=relaxed/simple;\n bh=dJNT4Owz7it92yE115+BJXkXiymdjDlHW3/ihh3OfOo=;\n h=From:Date:Subject:MIME-Version:To:Message-ID;\n b=LKdkxrC3Ht9X4+z1VVomqIMOQSgqQ301SD7BvuulxhWhYWJ7u0dGqfdpsv6m3xuLG2YIjuWK2OZny+nQz9rIpgS+kTszYlkXuJ/z5Cgwk69gpmOIP1BMV4iWMehZvfamIBDP2i+EL1+Y/+YQf5Rjz3BlwYPMDTaiY3rf0b2poPQ=", "ARC-Authentication-Results": "i=1; server2.sourceware.org", "From": "=?utf-8?b?PT91dGYtOD9xP0ZyYW49QzM9QTdvaXNfRHVtb250X3ZpYV9Tb3VyY2V3YXJl?=\n\t=?utf-8?b?X0ZvcmdlPz0=?= <forge-bot+fdumont@forge-stage.sourceware.org>", "Date": "Wed, 22 Apr 2026 10:38:43 +0000", "Subject": "[PATCH v1 1/1] libstdc++: Add fancy pointer support in map and set", "MIME-Version": "1.0", "Content-Type": "text/plain; charset=UTF-8", "Content-Transfer-Encoding": "8bit", "To": "gcc-patches mailing list <gcc-patches@gcc.gnu.org>", "Message-ID": "\n <bmm.hhublw6j3q.gcc.gcc-TEST.fdumont.27.1.1@forge-stage.sourceware.org>", "X-Mailer": "batrachomyomachia", "X-Requested-Reviewer": "redi", "X-Pull-Request-Organization": "gcc", "X-Pull-Request-Repository": "gcc-TEST", "X-Pull-Request": "https://forge.sourceware.org/gcc/gcc-TEST/pulls/27", "References": "\n <bmm.hhublw6j3q.gcc.gcc-TEST.fdumont.27.1.0@forge-stage.sourceware.org>", "In-Reply-To": "\n <bmm.hhublw6j3q.gcc.gcc-TEST.fdumont.27.1.0@forge-stage.sourceware.org>", "X-Patch-URL": "\n https://forge.sourceware.org/fdumont/gcc-TEST/commit/8dc5a640903fea624e0f1aaad6cba183ee873196", "X-BeenThere": "gcc-patches@gcc.gnu.org", "X-Mailman-Version": "2.1.30", "Precedence": "list", "List-Id": "Gcc-patches mailing list <gcc-patches.gcc.gnu.org>", "List-Unsubscribe": "<https://gcc.gnu.org/mailman/options/gcc-patches>,\n <mailto:gcc-patches-request@gcc.gnu.org?subject=unsubscribe>", "List-Archive": "<https://gcc.gnu.org/pipermail/gcc-patches/>", "List-Post": "<mailto:gcc-patches@gcc.gnu.org>", "List-Help": "<mailto:gcc-patches-request@gcc.gnu.org?subject=help>", "List-Subscribe": "<https://gcc.gnu.org/mailman/listinfo/gcc-patches>,\n <mailto:gcc-patches-request@gcc.gnu.org?subject=subscribe>", "Reply-To": "gcc-patches mailing list <gcc-patches@gcc.gnu.org>,\n fdumont@gcc.gnu.org", "Errors-To": "gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org" }, "content": "From: François Dumont <frs.dumont@gmail.com>\n\nSupport fancy allocator pointer type in std::_Rb_tree<>.\n\nIn case of fancy pointer type the container is now storing the pointer to\n__rb_tree::_Node<_ValPtr> as a pointer to __rb_tree::_Node_base<_VoidPtr>.\n\nMany methods are adapted to take and return _Base_ptr in place of _Link_type\nwhich has been renamed into _Node_ptr.\n\nAs all node are stored as _Base_ptr have all methods working with this type\nand remove _Const_Base_ptr and _Const_Node_ptr and all methods associated with\nit.\n\nlibstdc++-v3/ChangeLog:\n\n\t* include/bits/stl_tree.h\n\t[_GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE]: New macro to control usage of the\n\tcode required to support fancy allocator pointer type.\n\t(_Rb_tree_node_base::_Const_Base_ptr): Remove.\n\t(_Rb_tree_node_base::_S_minimum, _Rb_tree_node_base::_S_maximum): Remove\n\toverloads for _Const_Base_ptr.\n\t(_Rb_tree_node_base::_M_base_ptr()): New.\n\t(_Rb_tree_node_base::_M_node_ptr<_NodePtr>()): New.\n\t(_Rb_tree_node::_Link_type): Remove.\n\t(__rb_tree::_Node_base<>): New.\n\t(__rb_tree::_Header<>): New.\n\t(__rb_tree::_Node<>): New.\n\t(_Rb_tree_increment(const _Rb_tree_node_base*)): Remove declaration.\n\t(_Rb_tree_decrement(const _Rb_tree_node_base*)): Remove declaration.\n\t(_Rb_tree_iterator<>::_Link_type): Rename into...\n\t(_Rb_tree_iterator<>::_Node_ptr): ...this.\n\t(_Rb_tree_const_iterator<>::_Link_type): Rename into...\n\t(_Rb_tree_const_iterator<>::_Node_ptr): ...this.\n\t(_Rb_tree_const_iterator<>::_M_const_cast): Remove.\n\t(_Rb_tree_const_iterator<>::_M_node): Change type into _Base_ptr.\n\t(__rb_tree::_Iterator<>): New.\n\t(__rb_tree::_Node_traits<>): New.\n\t(_Rb_tree<>::_Node_base, _Rb_tree::_Node): New.\n\t(_Rb_tree<>::_Link_type): Rename into...\n\t(_Rb_tree<>::_Node_ptr): ...this.\n\t(_Rb_tree<>::_Const_Base_ptr, _Rb_tree<>::_Const_Node_ptr): Remove.\n\t(_Rb_tree<>): Adapt to generalize usage of _Base_ptr in place of former\n\t_Link_type now _Node_ptr.\n\t(_Rb_tree<>::_M_mbegin): Remove.\n\t(_Rb_tree<>::_S_left(_Const_Base_ptr)): Remove.\n\t(_Rb_tree<>::_S_right(_Const_Base_ptr)): Remove.\n\t(_Rb_tree<>::_S_maximum(_Const_Base_ptr)): Remove.\n\t(_Rb_tree<>::_S_minimum(_Const_Base_ptr)): Remove.\n\t* testsuite/23_containers/map/allocator/ext_ptr.cc: New test case.\n\t* testsuite/23_containers/multimap/allocator/ext_ptr.cc: New test case.\n\t* testsuite/23_containers/multiset/allocator/ext_ptr.cc: New test case.\n\t* testsuite/23_containers/set/allocator/ext_ptr.cc: New test case.\n\t* testsuite/23_containers/set/requirements/explicit_instantiation/alloc_ptr.cc:\n\tNew test case.\n\t* testsuite/23_containers/set/requirements/explicit_instantiation/alloc_ptr_ignored.cc:\n\tNew test case.\n---\n libstdc++-v3/include/bits/stl_tree.h | 1376 ++++++++++++-----\n .../23_containers/map/allocator/ext_ptr.cc | 37 +\n .../multimap/allocator/ext_ptr.cc | 33 +\n .../multiset/allocator/ext_ptr.cc | 32 +\n .../23_containers/set/allocator/ext_ptr.cc | 32 +\n .../explicit_instantiation/alloc_ptr.cc | 86 ++\n .../alloc_ptr_ignored.cc | 4 +\n 7 files changed, 1221 insertions(+), 379 deletions(-)\n create mode 100644 libstdc++-v3/testsuite/23_containers/map/allocator/ext_ptr.cc\n create mode 100644 libstdc++-v3/testsuite/23_containers/multimap/allocator/ext_ptr.cc\n create mode 100644 libstdc++-v3/testsuite/23_containers/multiset/allocator/ext_ptr.cc\n create mode 100644 libstdc++-v3/testsuite/23_containers/set/allocator/ext_ptr.cc\n create mode 100644 libstdc++-v3/testsuite/23_containers/set/requirements/explicit_instantiation/alloc_ptr.cc\n create mode 100644 libstdc++-v3/testsuite/23_containers/set/requirements/explicit_instantiation/alloc_ptr_ignored.cc", "diff": "diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h\nindex bc27e191e8b8..c87591757e88 100644\n--- a/libstdc++-v3/include/bits/stl_tree.h\n+++ b/libstdc++-v3/include/bits/stl_tree.h\n@@ -66,6 +66,7 @@\n #include <bits/allocator.h>\n #include <bits/stl_function.h>\n #include <bits/cpp_type_traits.h>\n+#include <bits/ptr_traits.h>\n #include <ext/alloc_traits.h>\n #if __cplusplus >= 201103L\n # include <ext/aligned_buffer.h>\n@@ -74,6 +75,13 @@\n # include <bits/node_handle.h>\n #endif\n \n+#if __cplusplus < 201103L\n+# undef _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE\n+# define _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE 0\n+#elif ! defined _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE\n+# define _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE 1\n+#endif\n+\n namespace std _GLIBCXX_VISIBILITY(default)\n {\n _GLIBCXX_BEGIN_NAMESPACE_VERSION\n@@ -99,7 +107,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n struct _Rb_tree_node_base\n {\n typedef _Rb_tree_node_base* _Base_ptr;\n- typedef const _Rb_tree_node_base* _Const_Base_ptr;\n \n _Rb_tree_color\t_M_color;\n _Base_ptr\t\t_M_parent;\n@@ -113,13 +120,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n return __x;\n }\n \n- static _Const_Base_ptr\n- _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT\n- {\n- while (__x->_M_left != 0) __x = __x->_M_left;\n- return __x;\n- }\n-\n static _Base_ptr\n _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT\n {\n@@ -127,12 +127,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n return __x;\n }\n \n- static _Const_Base_ptr\n- _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT\n- {\n- while (__x->_M_right != 0) __x = __x->_M_right;\n- return __x;\n- }\n+ // This is not const-correct, but it's only used in a const access path\n+ // by std::_Rb_tree::_M_end() where the pointer is used to initialize a\n+ // const_iterator and so constness is restored.\n+ _Base_ptr\n+ _M_base_ptr() const _GLIBCXX_NOEXCEPT\n+ { return const_cast<_Rb_tree_node_base*>(this); }\n };\n \n // Helper type offering value initialization guarantee on the compare functor.\n@@ -213,8 +213,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n template<typename _Val>\n struct _Rb_tree_node : public _Rb_tree_node_base\n {\n- typedef _Rb_tree_node<_Val>* _Link_type;\n-\n #if __cplusplus < 201103L\n _Val _M_value_field;\n \n@@ -236,20 +234,140 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n _M_valptr() const\n { return _M_storage._M_ptr(); }\n #endif\n+\n+ _Rb_tree_node*\n+ _M_node_ptr() _GLIBCXX_NOEXCEPT\n+ { return this; }\n+ };\n+\n+#if _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE\n+namespace __rb_tree\n+{\n+ template<typename _VoidPtr>\n+ struct _Node_base\n+ {\n+ using _Base_ptr = __ptr_rebind<_VoidPtr, _Node_base>;\n+\n+ _Rb_tree_color\t_M_color;\n+ _Base_ptr\t\t_M_parent;\n+ _Base_ptr\t\t_M_left;\n+ _Base_ptr\t\t_M_right;\n+\n+ static _Base_ptr\n+ _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT\n+ {\n+\twhile (__x->_M_left) __x = __x->_M_left;\n+\treturn __x;\n+ }\n+\n+ static _Base_ptr\n+ _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT\n+ {\n+\twhile (__x->_M_right) __x = __x->_M_right;\n+\treturn __x;\n+ }\n+\n+ // This is not const-correct, but it's only used in a const access path\n+ // by std::_Rb_tree::_M_end() where the pointer is used to initialize a\n+ // const_iterator and so constness is restored.\n+ _Base_ptr\n+ _M_base_ptr() const noexcept\n+ {\n+\treturn pointer_traits<_Base_ptr>::pointer_to\n+\t (*const_cast<_Node_base*>(this));\n+ }\n+ };\n+\n+ // Helper type to manage default initialization of node count and header.\n+ template<typename _NodeBase>\n+ struct _Header\n+ {\n+ private:\n+ using _Base_ptr = typename _NodeBase::_Base_ptr;\n+\n+ public:\n+ _NodeBase\t\t_M_header;\n+ size_t\t\t_M_node_count; // Keeps track of size of tree.\n+\n+ _Header() noexcept\n+ {\n+\t_M_header._M_color = _S_red;\n+\t_M_reset();\n+ }\n+\n+ _Header(_Header&& __x) noexcept\n+ {\n+\tif (__x._M_header._M_parent)\n+\t _M_move_data(__x);\n+\telse\n+\t {\n+\t _M_header._M_color = _S_red;\n+\t _M_reset();\n+\t }\n+ }\n+\n+ void\n+ _M_move_data(_Header& __from)\n+ {\n+\t_M_header._M_color = __from._M_header._M_color;\n+\t_M_header._M_parent = __from._M_header._M_parent;\n+\t_M_header._M_left = __from._M_header._M_left;\n+\t_M_header._M_right = __from._M_header._M_right;\n+\t_M_header._M_parent->_M_parent = _M_header._M_base_ptr();\n+\t_M_node_count = __from._M_node_count;\n+\n+\t__from._M_reset();\n+ }\n+\n+ void\n+ _M_reset()\n+ {\n+\t_M_header._M_parent = nullptr;\n+\t_M_header._M_left = _M_header._M_right = _M_header._M_base_ptr();\n+\t_M_node_count = 0;\n+ }\n };\n \n+ template<typename _ValPtr>\n+ struct _Node : public __rb_tree::_Node_base<__ptr_rebind<_ValPtr, void>>\n+ {\n+ using value_type = typename pointer_traits<_ValPtr>::element_type;\n+ using _Node_ptr = __ptr_rebind<_ValPtr, _Node>;\n+\n+ _Node() noexcept { }\n+ ~_Node() { }\n+ _Node(_Node&&) = delete;\n+\n+ union _Uninit_storage\n+ {\n+\t_Uninit_storage() noexcept { }\n+\t~_Uninit_storage() { }\n+\n+\tvalue_type _M_data;\n+ };\n+ _Uninit_storage _M_u;\n+\n+ value_type*\n+ _M_valptr()\n+ { return std::addressof(_M_u._M_data); }\n+\n+ value_type const*\n+ _M_valptr() const\n+ { return std::addressof(_M_u._M_data); }\n+\n+ _Node_ptr\n+ _M_node_ptr() noexcept\n+ { return pointer_traits<_Node_ptr>::pointer_to(*this); }\n+ };\n+} // namespace __rb_tree\n+#endif // _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE\n+\n _GLIBCXX_PURE _Rb_tree_node_base*\n _Rb_tree_increment(_Rb_tree_node_base* __x) throw ();\n \n- _GLIBCXX_PURE const _Rb_tree_node_base*\n- _Rb_tree_increment(const _Rb_tree_node_base* __x) throw ();\n-\n _GLIBCXX_PURE _Rb_tree_node_base*\n _Rb_tree_decrement(_Rb_tree_node_base* __x) throw ();\n \n- _GLIBCXX_PURE const _Rb_tree_node_base*\n- _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw ();\n-\n template<typename _Tp>\n struct _Rb_tree_iterator\n {\n@@ -260,9 +378,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n typedef bidirectional_iterator_tag iterator_category;\n typedef ptrdiff_t\t\t\t difference_type;\n \n- typedef _Rb_tree_iterator<_Tp>\t\t_Self;\n typedef _Rb_tree_node_base::_Base_ptr\t_Base_ptr;\n- typedef _Rb_tree_node<_Tp>*\t\t_Link_type;\n+ typedef _Rb_tree_node<_Tp>*\t\t_Node_ptr;\n \n _Rb_tree_iterator() _GLIBCXX_NOEXCEPT\n : _M_node() { }\n@@ -273,49 +390,51 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \n reference\n operator*() const _GLIBCXX_NOEXCEPT\n- { return *static_cast<_Link_type>(_M_node)->_M_valptr(); }\n+ { return *static_cast<_Node_ptr>(_M_node)->_M_valptr(); }\n \n pointer\n operator->() const _GLIBCXX_NOEXCEPT\n- { return static_cast<_Link_type> (_M_node)->_M_valptr(); }\n+ { return static_cast<_Node_ptr>(_M_node)->_M_valptr(); }\n \n- _Self&\n+ _Rb_tree_iterator&\n operator++() _GLIBCXX_NOEXCEPT\n {\n \t_M_node = _Rb_tree_increment(_M_node);\n \treturn *this;\n }\n \n- _Self\n+ _Rb_tree_iterator\n operator++(int) _GLIBCXX_NOEXCEPT\n {\n-\t_Self __tmp = *this;\n+\t_Rb_tree_iterator __tmp = *this;\n \t_M_node = _Rb_tree_increment(_M_node);\n \treturn __tmp;\n }\n \n- _Self&\n+ _Rb_tree_iterator&\n operator--() _GLIBCXX_NOEXCEPT\n {\n \t_M_node = _Rb_tree_decrement(_M_node);\n \treturn *this;\n }\n \n- _Self\n+ _Rb_tree_iterator\n operator--(int) _GLIBCXX_NOEXCEPT\n {\n-\t_Self __tmp = *this;\n+\t_Rb_tree_iterator __tmp = *this;\n \t_M_node = _Rb_tree_decrement(_M_node);\n \treturn __tmp;\n }\n \n friend bool\n- operator==(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT\n+ operator==(const _Rb_tree_iterator& __x,\n+\t\t const _Rb_tree_iterator& __y) _GLIBCXX_NOEXCEPT\n { return __x._M_node == __y._M_node; }\n \n #if ! __cpp_lib_three_way_comparison\n friend bool\n- operator!=(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT\n+ operator!=(const _Rb_tree_iterator& __x,\n+\t\t const _Rb_tree_iterator& __y) _GLIBCXX_NOEXCEPT\n { return __x._M_node != __y._M_node; }\n #endif\n \n@@ -334,9 +453,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n typedef bidirectional_iterator_tag iterator_category;\n typedef ptrdiff_t\t\t\t difference_type;\n \n- typedef _Rb_tree_const_iterator<_Tp>\t\t_Self;\n- typedef _Rb_tree_node_base::_Const_Base_ptr\t_Base_ptr;\n- typedef const _Rb_tree_node<_Tp>*\t\t\t_Link_type;\n+ typedef _Rb_tree_node_base::_Base_ptr\t_Base_ptr;\n+ typedef const _Rb_tree_node<_Tp>*\t\t_Node_ptr;\n \n _Rb_tree_const_iterator() _GLIBCXX_NOEXCEPT\n : _M_node() { }\n@@ -348,55 +466,53 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n _Rb_tree_const_iterator(const iterator& __it) _GLIBCXX_NOEXCEPT\n : _M_node(__it._M_node) { }\n \n- iterator\n- _M_const_cast() const _GLIBCXX_NOEXCEPT\n- { return iterator(const_cast<typename iterator::_Base_ptr>(_M_node)); }\n-\n reference\n operator*() const _GLIBCXX_NOEXCEPT\n- { return *static_cast<_Link_type>(_M_node)->_M_valptr(); }\n+ { return *static_cast<_Node_ptr>(_M_node)->_M_valptr(); }\n \n pointer\n operator->() const _GLIBCXX_NOEXCEPT\n- { return static_cast<_Link_type>(_M_node)->_M_valptr(); }\n+ { return static_cast<_Node_ptr>(_M_node)->_M_valptr(); }\n \n- _Self&\n+ _Rb_tree_const_iterator&\n operator++() _GLIBCXX_NOEXCEPT\n {\n \t_M_node = _Rb_tree_increment(_M_node);\n \treturn *this;\n }\n \n- _Self\n+ _Rb_tree_const_iterator\n operator++(int) _GLIBCXX_NOEXCEPT\n {\n-\t_Self __tmp = *this;\n+\t_Rb_tree_const_iterator __tmp = *this;\n \t_M_node = _Rb_tree_increment(_M_node);\n \treturn __tmp;\n }\n \n- _Self&\n+ _Rb_tree_const_iterator&\n operator--() _GLIBCXX_NOEXCEPT\n {\n \t_M_node = _Rb_tree_decrement(_M_node);\n \treturn *this;\n }\n \n- _Self\n+ _Rb_tree_const_iterator\n operator--(int) _GLIBCXX_NOEXCEPT\n {\n-\t_Self __tmp = *this;\n+\t_Rb_tree_const_iterator __tmp = *this;\n \t_M_node = _Rb_tree_decrement(_M_node);\n \treturn __tmp;\n }\n \n friend bool\n- operator==(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT\n+ operator==(const _Rb_tree_const_iterator& __x,\n+\t\t const _Rb_tree_const_iterator& __y) _GLIBCXX_NOEXCEPT\n { return __x._M_node == __y._M_node; }\n \n #if ! __cpp_lib_three_way_comparison\n friend bool\n- operator!=(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT\n+ operator!=(const _Rb_tree_const_iterator& __x,\n+\t\t const _Rb_tree_const_iterator& __y) _GLIBCXX_NOEXCEPT\n { return __x._M_node != __y._M_node; }\n #endif\n \n@@ -415,6 +531,485 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,\n \t\t\t _Rb_tree_node_base& __header) throw ();\n \n+namespace __rb_tree\n+{\n+#if _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE\n+ template<bool _Const, typename _ValPtr>\n+ struct _Iterator\n+ {\n+ template<typename _Tp>\n+\tusing __maybe_const = __conditional_t<_Const, const _Tp, _Tp>;\n+\n+ using __ptr_traits =\tpointer_traits<_ValPtr>;\n+ using value_type =\ttypename __ptr_traits::element_type;\n+ using reference =\t\t__maybe_const<value_type>&;\n+ using pointer =\t\t__maybe_const<value_type>*;\n+\n+ using iterator_category =\tbidirectional_iterator_tag;\n+ using difference_type =\tptrdiff_t;\n+\n+ using _Node = __rb_tree::_Node<_ValPtr>;\n+ using _Node_base = __rb_tree::_Node_base<__ptr_rebind<_ValPtr, void>>;\n+ using _Base_ptr =\t typename _Node_base::_Base_ptr;\n+\n+ _Iterator() noexcept\n+ : _M_node() { }\n+\n+ constexpr explicit\n+ _Iterator(_Base_ptr __x) noexcept\n+ : _M_node(__x) { }\n+\n+ _Iterator(const _Iterator&) = default;\n+ _Iterator& operator=(const _Iterator&) = default;\n+\n+#ifdef __glibcxx_concepts\n+ constexpr\n+ _Iterator(const _Iterator<false, _ValPtr>& __it) requires _Const\n+#else\n+ template<bool _OtherConst,\n+\t typename = __enable_if_t<_Const && !_OtherConst>>\n+\tconstexpr\n+\t_Iterator(const _Iterator<_OtherConst, _ValPtr>& __it)\n+#endif\n+\t: _M_node(__it._M_node) { }\n+\n+ [[__nodiscard__]]\n+ reference\n+ operator*() const noexcept\n+ { return *static_cast<_Node&>(*_M_node)._M_valptr(); }\n+\n+ [[__nodiscard__]]\n+ pointer\n+ operator->() const noexcept\n+ { return static_cast<_Node&>(*_M_node)._M_valptr(); }\n+\n+ _GLIBCXX14_CONSTEXPR _Iterator&\n+ operator++() noexcept\n+ {\n+\tif (_M_node->_M_right)\n+\t {\n+\t _M_node = _M_node->_M_right;\n+\t while (_M_node->_M_left)\n+\t _M_node = _M_node->_M_left;\n+\t }\n+\telse\n+\t {\n+\t _Base_ptr __y = _M_node->_M_parent;\n+\t while (_M_node == __y->_M_right)\n+\t {\n+\t\t_M_node = __y;\n+\t\t__y = __y->_M_parent;\n+\t }\n+\t if (_M_node->_M_right != __y)\n+\t _M_node = __y;\n+\t }\n+\n+\treturn *this;\n+ }\n+\n+ _GLIBCXX14_CONSTEXPR _Iterator\n+ operator++(int) noexcept\n+ {\n+\t_Iterator __tmp(this->_M_node);\n+\t++*this;\n+\treturn __tmp;\n+ }\n+\n+ _GLIBCXX14_CONSTEXPR _Iterator&\n+ operator--() noexcept\n+ {\n+\tif (_M_node->_M_color == _S_red\n+\t && _M_node->_M_parent->_M_parent == _M_node)\n+\t _M_node = _M_node->_M_right;\n+\telse if (_M_node->_M_left)\n+\t {\n+\t _Base_ptr __y = _M_node->_M_left;\n+\t while (__y->_M_right)\n+\t __y = __y->_M_right;\n+\t _M_node = __y;\n+\t }\n+\telse\n+\t {\n+\t _Base_ptr __y = _M_node->_M_parent;\n+\t while (_M_node == __y->_M_left)\n+\t {\n+\t\t_M_node = __y;\n+\t\t__y = __y->_M_parent;\n+\t }\n+\t _M_node = __y;\n+\t }\n+\treturn *this;\n+ }\n+\n+ _GLIBCXX14_CONSTEXPR _Iterator\n+ operator--(int) noexcept\n+ {\n+\t_Iterator __tmp(this->_M_node);\n+\t--*this;\n+\treturn __tmp;\n+ }\n+\n+ [[__nodiscard__]]\n+ friend bool\n+ operator==(const _Iterator& __x, const _Iterator& __y) _GLIBCXX_NOEXCEPT\n+ { return __x._M_node == __y._M_node; }\n+\n+#if ! __cpp_lib_three_way_comparison\n+ [[__nodiscard__]]\n+ friend bool\n+ operator!=(const _Iterator& __x, const _Iterator& __y) _GLIBCXX_NOEXCEPT\n+ { return __x._M_node != __y._M_node; }\n+#endif\n+\n+ _Base_ptr _M_node;\n+ };\n+#endif // USE_ALLOC_PTR_FOR_RB_TREE\n+\n+ // Determine the node and iterator types used by std::_Rb_tree.\n+ template<typename _Val, typename _Ptr>\n+ struct _Node_traits;\n+\n+#if _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE <= 9000\n+ // Specialization for the simple case where the allocator's pointer type\n+ // is the same type as value_type*.\n+ // For ABI compatibility we can't change the types used for this case.\n+ template<typename _Val>\n+ struct _Node_traits<_Val, _Val*>\n+ {\n+ typedef _Rb_tree_node<_Val>\t\t_Node;\n+ typedef _Node*\t\t\t\t_Node_ptr;\n+ typedef _Rb_tree_node_base\t\t_Node_base;\n+ typedef _Node_base*\t\t\t_Base_ptr;\n+ typedef _Rb_tree_header\t\t\t_Header_t;\n+ typedef _Rb_tree_iterator<_Val>\t\t_Iterator;\n+ typedef _Rb_tree_const_iterator<_Val>\t_Const_iterator;\n+\n+ __attribute__((__nonnull__))\n+ static void\n+ _S_insert_and_rebalance(const bool __insert_left,\n+\t\t\t _Node_base* __x, _Node_base* __p,\n+\t\t\t _Node_base& __header) _GLIBCXX_USE_NOEXCEPT\n+ {\n+\treturn _Rb_tree_insert_and_rebalance(__insert_left, __x, __p, __header);\n+ }\n+\n+ __attribute__((__nonnull__,__returns_nonnull__))\n+ static _Node_base*\n+ _S_rebalance_for_erase(_Node_base* const __z,\n+\t\t\t _Node_base& __header) _GLIBCXX_USE_NOEXCEPT\n+ { return _Rb_tree_rebalance_for_erase(__z, __header); }\n+ };\n+#endif\n+\n+#if ! _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE\n+ // Always use the T* specialization.\n+ template<typename _Val, typename _Ptr>\n+ struct _Node_traits\n+ : _Node_traits<_Val, _Val*>\n+ { };\n+#else\n+ // Primary template used when the allocator uses fancy pointers.\n+ template<typename _Val, typename _ValPtr>\n+ struct _Node_traits\n+ {\n+ using _Node = __rb_tree::_Node<_ValPtr>;\n+ using _Node_ptr = __ptr_rebind<_ValPtr, _Node>;\n+ using _Node_base = __rb_tree::_Node_base<__ptr_rebind<_ValPtr, void>>;\n+ using _Base_ptr = __ptr_rebind<_ValPtr, _Node_base>;\n+ using _Header_t = __rb_tree::_Header<_Node_base>;\n+ using _Iterator = __rb_tree::_Iterator<false, _ValPtr>;\n+ using _Const_iterator = __rb_tree::_Iterator<true, _ValPtr>;\n+\n+ static void\n+ _Rotate_left(_Base_ptr __x, _Base_ptr& __root)\n+ {\n+\tconst _Base_ptr __y = __x->_M_right;\n+\n+\t__x->_M_right = __y->_M_left;\n+\tif (__y->_M_left)\n+\t __y->_M_left->_M_parent = __x;\n+\t__y->_M_parent = __x->_M_parent;\n+\n+\tif (__x == __root)\n+\t __root = __y;\n+\telse if (__x == __x->_M_parent->_M_left)\n+\t __x->_M_parent->_M_left = __y;\n+\telse\n+\t __x->_M_parent->_M_right = __y;\n+\t__y->_M_left = __x;\n+\t__x->_M_parent = __y;\n+ }\n+\n+ static void\n+ _Rotate_right(_Base_ptr __x, _Base_ptr& __root)\n+ {\n+\tconst _Base_ptr __y = __x->_M_left;\n+\n+\t__x->_M_left = __y->_M_right;\n+\tif (__y->_M_right)\n+\t __y->_M_right->_M_parent = __x;\n+\t__y->_M_parent = __x->_M_parent;\n+\n+\tif (__x == __root)\n+\t __root = __y;\n+\telse if (__x == __x->_M_parent->_M_right)\n+\t __x->_M_parent->_M_right = __y;\n+\telse\n+\t __x->_M_parent->_M_left = __y;\n+\t__y->_M_right = __x;\n+\t__x->_M_parent = __y;\n+ }\n+\n+ static void\n+ _S_insert_and_rebalance(const bool __insert_left,\n+\t\t\t _Base_ptr __x, _Base_ptr __p,\n+\t\t\t _Node_base& __header)\n+ {\n+\t_Base_ptr& __root = __header._M_parent;\n+\n+\t// Initialize fields in new node to insert.\n+\t__x->_M_parent = __p;\n+\t__x->_M_left = __x->_M_right = nullptr;\n+\t__x->_M_color = _S_red;\n+\n+\t// Insert.\n+\t// Make new node child of parent and maintain root, leftmost and\n+\t// rightmost nodes.\n+\t// N.B. First node is always inserted left.\n+\tif (__insert_left)\n+\t {\n+\t __p->_M_left = __x; // also makes leftmost = __x when __p == &__header\n+\n+\t if (std::__to_address(__p) == std::addressof(__header))\n+\t {\n+\t\t__header._M_parent = __x;\n+\t\t__header._M_right = __x;\n+\t }\n+\t else if (__p == __header._M_left)\n+\t __header._M_left = __x; // maintain leftmost pointing to min node\n+\t }\n+\telse\n+\t {\n+\t __p->_M_right = __x;\n+\n+\t if (__p == __header._M_right)\n+\t __header._M_right = __x; // maintain rightmost pointing to max node\n+\t }\n+\t// Rebalance.\n+\twhile (__x != __root\n+\t && __x->_M_parent->_M_color == _S_red)\n+\t {\n+\t const _Base_ptr __xpp = __x->_M_parent->_M_parent;\n+\n+\t if (__x->_M_parent == __xpp->_M_left)\n+\t {\n+\t\tconst _Base_ptr __y = __xpp->_M_right;\n+\t\tif (__y && __y->_M_color == _S_red)\n+\t\t {\n+\t\t __x->_M_parent->_M_color = _S_black;\n+\t\t __y->_M_color = _S_black;\n+\t\t __xpp->_M_color = _S_red;\n+\t\t __x = __xpp;\n+\t\t }\n+\t\telse\n+\t\t {\n+\t\t if (__x == __x->_M_parent->_M_right)\n+\t\t {\n+\t\t\t__x = __x->_M_parent;\n+\t\t\t_Rotate_left(__x, __root);\n+\t\t }\n+\t\t __x->_M_parent->_M_color = _S_black;\n+\t\t __xpp->_M_color = _S_red;\n+\t\t _Rotate_right(__xpp, __root);\n+\t\t }\n+\t }\n+\t else\n+\t {\n+\t\tconst _Base_ptr __y = __xpp->_M_left;\n+\t\tif (__y && __y->_M_color == _S_red)\n+\t\t {\n+\t\t __x->_M_parent->_M_color = _S_black;\n+\t\t __y->_M_color = _S_black;\n+\t\t __xpp->_M_color = _S_red;\n+\t\t __x = __xpp;\n+\t\t }\n+\t\telse\n+\t\t {\n+\t\t if (__x == __x->_M_parent->_M_left)\n+\t\t {\n+\t\t\t__x = __x->_M_parent;\n+\t\t\t_Rotate_right(__x, __root);\n+\t\t }\n+\t\t __x->_M_parent->_M_color = _S_black;\n+\t\t __xpp->_M_color = _S_red;\n+\t\t _Rotate_left(__xpp, __root);\n+\t\t }\n+\t }\n+\t }\n+\t__root->_M_color = _S_black;\n+ }\n+\n+ static _Base_ptr\n+ _S_rebalance_for_erase(_Base_ptr __z, _Node_base& __header)\n+ {\n+\t_Base_ptr& __root = __header._M_parent;\n+\t_Base_ptr& __leftmost = __header._M_left;\n+\t_Base_ptr& __rightmost = __header._M_right;\n+\t_Base_ptr __y = __z;\n+\t_Base_ptr __x{};\n+\t_Base_ptr __x_parent{};\n+\n+\tif (!__y->_M_left) // __z has at most one non-null child. y == z.\n+\t __x = __y->_M_right; // __x might be null.\n+\telse\n+\t if (!__y->_M_right) // __z has exactly one non-null child. y == z.\n+\t __x = __y->_M_left; // __x is not null.\n+\t else\n+\t {\n+\t // __z has two non-null children. Set __y to\n+\t __y = __y->_M_right; // __z's successor. __x might be null.\n+\t while (__y->_M_left)\n+\t\t__y = __y->_M_left;\n+\t __x = __y->_M_right;\n+\t }\n+\tif (__y != __z)\n+\t {\n+\t // relink y in place of z. y is z's successor\n+\t __z->_M_left->_M_parent = __y;\n+\t __y->_M_left = __z->_M_left;\n+\t if (__y != __z->_M_right)\n+\t {\n+\t\t__x_parent = __y->_M_parent;\n+\t\tif (__x)\n+\t\t __x->_M_parent = __y->_M_parent;\n+\t\t__y->_M_parent->_M_left = __x; // __y must be a child of _M_left\n+\t\t__y->_M_right = __z->_M_right;\n+\t\t__z->_M_right->_M_parent = __y;\n+\t }\n+\t else\n+\t __x_parent = __y;\n+\t if (__root == __z)\n+\t __root = __y;\n+\t else if (__z->_M_parent->_M_left == __z)\n+\t __z->_M_parent->_M_left = __y;\n+\t else\n+\t __z->_M_parent->_M_right = __y;\n+\t __y->_M_parent = __z->_M_parent;\n+\t std::swap(__y->_M_color, __z->_M_color);\n+\t __y = __z;\n+\t // __y now points to node to be actually deleted\n+\t }\n+\telse\n+\t { // __y == __z\n+\t __x_parent = __y->_M_parent;\n+\t if (__x)\n+\t __x->_M_parent = __y->_M_parent;\n+\t if (__root == __z)\n+\t __root = __x;\n+\t else\n+\t if (__z->_M_parent->_M_left == __z)\n+\t\t__z->_M_parent->_M_left = __x;\n+\t else\n+\t\t__z->_M_parent->_M_right = __x;\n+\t if (__leftmost == __z)\n+\t {\n+\t\tif (!__z->_M_right) // __z->_M_left must be null also\n+\t\t __leftmost = __z->_M_parent;\n+\t\t// makes __leftmost == _M_header if __z == __root\n+\t\telse\n+\t\t __leftmost = _Node_base::_S_minimum(__x);\n+\t }\n+\t if (__rightmost == __z)\n+\t {\n+\t\tif (__z->_M_left == 0) // __z->_M_right must be null also\n+\t\t __rightmost = __z->_M_parent;\n+\t\t// makes __rightmost == _M_header if __z == __root\n+\t\telse // __x == __z->_M_left\n+\t\t __rightmost = _Node_base::_S_maximum(__x);\n+\t }\n+\t }\n+\tif (__y->_M_color != _S_red)\n+\t {\n+\t while (__x != __root && (__x == 0 || __x->_M_color == _S_black))\n+\t if (__x == __x_parent->_M_left)\n+\t\t{\n+\t\t _Base_ptr __w = __x_parent->_M_right;\n+\t\t if (__w->_M_color == _S_red)\n+\t\t {\n+\t\t __w->_M_color = _S_black;\n+\t\t __x_parent->_M_color = _S_red;\n+\t\t _Rotate_left(__x_parent, __root);\n+\t\t __w = __x_parent->_M_right;\n+\t\t }\n+\t\t if ((!__w->_M_left || __w->_M_left->_M_color == _S_black) &&\n+\t\t (!__w->_M_right || __w->_M_right->_M_color == _S_black))\n+\t\t {\n+\t\t __w->_M_color = _S_red;\n+\t\t __x = __x_parent;\n+\t\t __x_parent = __x_parent->_M_parent;\n+\t\t }\n+\t\t else\n+\t\t {\n+\t\t if (!__w->_M_right || __w->_M_right->_M_color == _S_black)\n+\t\t\t{\n+\t\t\t __w->_M_left->_M_color = _S_black;\n+\t\t\t __w->_M_color = _S_red;\n+\t\t\t _Rotate_right(__w, __root);\n+\t\t\t __w = __x_parent->_M_right;\n+\t\t\t}\n+\t\t __w->_M_color = __x_parent->_M_color;\n+\t\t __x_parent->_M_color = _S_black;\n+\t\t if (__w->_M_right)\n+\t\t\t__w->_M_right->_M_color = _S_black;\n+\t\t _Rotate_left(__x_parent, __root);\n+\t\t break;\n+\t\t }\n+\t\t}\n+\t else\n+\t\t{\n+\t\t // same as above, with _M_right <-> _M_left.\n+\t\t _Base_ptr __w = __x_parent->_M_left;\n+\t\t if (__w->_M_color == _S_red)\n+\t\t {\n+\t\t __w->_M_color = _S_black;\n+\t\t __x_parent->_M_color = _S_red;\n+\t\t _Rotate_right(__x_parent, __root);\n+\t\t __w = __x_parent->_M_left;\n+\t\t }\n+\t\t if ((!__w->_M_right || __w->_M_right->_M_color == _S_black) &&\n+\t\t (!__w->_M_left || __w->_M_left->_M_color == _S_black))\n+\t\t {\n+\t\t __w->_M_color = _S_red;\n+\t\t __x = __x_parent;\n+\t\t __x_parent = __x_parent->_M_parent;\n+\t\t }\n+\t\t else\n+\t\t {\n+\t\t if (!__w->_M_left || __w->_M_left->_M_color == _S_black)\n+\t\t\t{\n+\t\t\t __w->_M_right->_M_color = _S_black;\n+\t\t\t __w->_M_color = _S_red;\n+\t\t\t _Rotate_left(__w, __root);\n+\t\t\t __w = __x_parent->_M_left;\n+\t\t\t}\n+\t\t __w->_M_color = __x_parent->_M_color;\n+\t\t __x_parent->_M_color = _S_black;\n+\t\t if (__w->_M_left)\n+\t\t\t__w->_M_left->_M_color = _S_black;\n+\t\t _Rotate_right(__x_parent, __root);\n+\t\t break;\n+\t\t }\n+\t\t}\n+\t if (__x)\n+\t __x->_M_color = _S_black;\n+\t }\n+\n+\treturn __y;\n+ }\n+ };\n+#endif\n+} // namespace __rb_tree\n+\n #if __cplusplus > 201402L\n template<typename _Tree1, typename _Cmp2>\n struct _Rb_tree_merge_helper { };\n@@ -425,15 +1020,23 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n class _Rb_tree\n {\n typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template\n-\trebind<_Rb_tree_node<_Val> >::other _Node_allocator;\n+\trebind<_Val>::other _Val_alloc_type;\n+\n+ typedef __gnu_cxx::__alloc_traits<_Val_alloc_type> _Val_alloc_traits;\n+ typedef typename _Val_alloc_traits::pointer _ValPtr;\n+ typedef __rb_tree::_Node_traits<_Val, _ValPtr> _Node_traits;\n+\n+ typedef typename _Node_traits::_Node_base\t\t_Node_base;\n+ typedef typename _Node_traits::_Node\t\t_Node;\n+\n+ typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template\n+\trebind<_Node>::other _Node_allocator;\n \n- typedef __gnu_cxx::__alloc_traits<_Node_allocator> _Alloc_traits;\n+ typedef __gnu_cxx::__alloc_traits<_Node_allocator> _Node_alloc_traits;\n \n protected:\n- typedef _Rb_tree_node_base* \t\t_Base_ptr;\n- typedef const _Rb_tree_node_base* \t_Const_Base_ptr;\n- typedef _Rb_tree_node<_Val>* \t\t_Link_type;\n- typedef const _Rb_tree_node<_Val>*\t_Const_Link_type;\n+ typedef typename _Node_traits::_Base_ptr\t_Base_ptr;\n+ typedef typename _Node_traits::_Node_ptr\t_Node_ptr;\n \n private:\n // Functor recycling a pool of nodes and using allocation once the pool\n@@ -445,13 +1048,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t{\n \t if (_M_root)\n \t {\n-\t _M_root->_M_parent = 0;\n+\t _M_root->_M_parent = _Base_ptr();\n \n \t if (_M_nodes->_M_left)\n \t\t_M_nodes = _M_nodes->_M_left;\n \t }\n \t else\n-\t _M_nodes = 0;\n+\t _M_nodes = _Base_ptr();\n \t}\n \n #if __cplusplus >= 201103L\n@@ -459,15 +1062,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n #endif\n \n \t~_Reuse_or_alloc_node()\n-\t{ _M_t._M_erase(static_cast<_Link_type>(_M_root)); }\n+\t{\n+\t if (_M_root)\n+\t _M_t._M_erase(static_cast<_Node&>(*_M_root)._M_node_ptr());\n+\t}\n \n \ttemplate<typename _Arg>\n-\t _Link_type\n+\t _Node_ptr\n \t operator()(_GLIBCXX_FWDREF(_Arg) __arg)\n \t {\n-\t _Link_type __node = static_cast<_Link_type>(_M_extract());\n-\t if (__node)\n+\t _Base_ptr __base = _M_extract();\n+\t if (__base)\n \t {\n+\t\t_Node_ptr __node = static_cast<_Node&>(*__base)._M_node_ptr();\n \t\t_M_t._M_destroy_node(__node);\n \t\t_M_t._M_construct_node(__node, _GLIBCXX_FORWARD(_Arg, __arg));\n \t\treturn __node;\n@@ -489,7 +1096,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t {\n \t if (_M_nodes->_M_right == __node)\n \t\t{\n-\t\t _M_nodes->_M_right = 0;\n+\t\t _M_nodes->_M_right = _Base_ptr();\n \n \t\t if (_M_nodes->_M_left)\n \t\t {\n@@ -503,10 +1110,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t\t }\n \t\t}\n \t else // __node is on the left.\n-\t\t_M_nodes->_M_left = 0;\n+\t\t_M_nodes->_M_left = _Base_ptr();\n \t }\n \t else\n-\t _M_root = 0;\n+\t _M_root = _Base_ptr();\n \n \t return __node;\n \t}\n@@ -524,7 +1131,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t: _M_t(__t) { }\n \n \ttemplate<typename _Arg>\n-\t _Link_type\n+\t _Node_ptr\n \t operator()(_GLIBCXX_FWDREF(_Arg) __arg) const\n \t { return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); }\n \n@@ -556,17 +1163,52 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n { return allocator_type(_M_get_Node_allocator()); }\n \n protected:\n- _Link_type\n+ _Node_ptr\n _M_get_node()\n- { return _Alloc_traits::allocate(_M_get_Node_allocator(), 1); }\n+ {\n+#if __cplusplus < 201102L || _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE\n+\treturn _Node_alloc_traits::allocate(_M_get_Node_allocator(), 1);\n+#else\n+#pragma GCC diagnostic push\n+#pragma GCC diagnostic ignored \"-Wc++17-extensions\" // if constexpr\n+\tusing __alloc_pointer = typename _Node_alloc_traits::pointer;\n+\tif constexpr (is_same<_Node_ptr, __alloc_pointer>::value)\n+\t return _Node_alloc_traits::allocate(_M_get_Node_allocator(), 1);\n+\telse\n+\t {\n+\t auto __ptr =\n+\t _Node_alloc_traits::allocate(_M_get_Node_allocator(), 1);\n+\t return std::__to_address(__ptr);\n+\t }\n+#pragma GCC diagnostic pop\n+#endif\n+ }\n \n void\n- _M_put_node(_Link_type __p) _GLIBCXX_NOEXCEPT\n- { _Alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); }\n+ _M_put_node(_Node_ptr __p) _GLIBCXX_NOEXCEPT\n+ {\n+#if __cplusplus < 201102L || _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE\n+\t_Node_alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1);\n+#else\n+#pragma GCC diagnostic push\n+#pragma GCC diagnostic ignored \"-Wc++17-extensions\" // if constexpr\n+\tusing __alloc_pointer = typename _Node_alloc_traits::pointer;\n+\tif constexpr (is_same<_Node_ptr, __alloc_pointer>::value)\n+\t _Node_alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1);\n+\telse\n+\t {\n+\t // When not using the allocator's pointer type internally we must\n+\t // convert __p to __alloc_pointer so it can be deallocated.\n+\t auto __ap = pointer_traits<__alloc_pointer>::pointer_to(*__p);\n+\t _Node_alloc_traits::deallocate(_M_get_Node_allocator(), __ap, 1);\n+\t }\n+#pragma GCC diagnostic pop\n+#endif\n+ }\n \n #if __cplusplus < 201103L\n void\n- _M_construct_node(_Link_type __node, const value_type& __x)\n+ _M_construct_node(_Node_ptr __node, const value_type& __x)\n {\n \t__try\n \t { get_allocator().construct(__node->_M_valptr(), __x); }\n@@ -577,79 +1219,80 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t }\n }\n \n- _Link_type\n+ _Node_ptr\n _M_create_node(const value_type& __x)\n {\n-\t_Link_type __tmp = _M_get_node();\n+\t_Node_ptr __tmp = _M_get_node();\n \t_M_construct_node(__tmp, __x);\n \treturn __tmp;\n }\n #else\n template<typename... _Args>\n \tvoid\n-\t_M_construct_node(_Link_type __node, _Args&&... __args)\n+\t_M_construct_node(_Node_ptr __node, _Args&&... __args)\n \t{\n \t __try\n \t {\n-\t ::new(__node) _Rb_tree_node<_Val>;\n-\t _Alloc_traits::construct(_M_get_Node_allocator(),\n-\t\t\t\t __node->_M_valptr(),\n-\t\t\t\t std::forward<_Args>(__args)...);\n+\t ::new(std::addressof(*__node)) _Node;\n+\t _Node_alloc_traits::construct(_M_get_Node_allocator(),\n+\t\t\t\t\t __node->_M_valptr(),\n+\t\t\t\t\t std::forward<_Args>(__args)...);\n \t }\n \t __catch(...)\n \t {\n-\t __node->~_Rb_tree_node<_Val>();\n+\t __node->~_Node();\n \t _M_put_node(__node);\n \t __throw_exception_again;\n \t }\n \t}\n \n template<typename... _Args>\n-\t_Link_type\n+\t_Node_ptr\n \t_M_create_node(_Args&&... __args)\n \t{\n-\t _Link_type __tmp = _M_get_node();\n+\t _Node_ptr __tmp = _M_get_node();\n \t _M_construct_node(__tmp, std::forward<_Args>(__args)...);\n \t return __tmp;\n \t}\n #endif\n \n void\n- _M_destroy_node(_Link_type __p) _GLIBCXX_NOEXCEPT\n+ _M_destroy_node(_Node_ptr __p) _GLIBCXX_NOEXCEPT\n {\n #if __cplusplus < 201103L\n \tget_allocator().destroy(__p->_M_valptr());\n #else\n-\t_Alloc_traits::destroy(_M_get_Node_allocator(), __p->_M_valptr());\n-\t__p->~_Rb_tree_node<_Val>();\n+\t_Node_alloc_traits::destroy(_M_get_Node_allocator(), __p->_M_valptr());\n+\t__p->~_Node();\n #endif\n }\n \n void\n- _M_drop_node(_Link_type __p) _GLIBCXX_NOEXCEPT\n+ _M_drop_node(_Node_ptr __p) _GLIBCXX_NOEXCEPT\n {\n \t_M_destroy_node(__p);\n \t_M_put_node(__p);\n }\n \n template<bool _MoveValue, typename _NodeGen>\n-\t_Link_type\n-\t_M_clone_node(_Link_type __x, _NodeGen& __node_gen)\n+\t_Node_ptr\n+\t_M_clone_node(_Node_ptr __x, _NodeGen& __node_gen)\n \t{\n #if __cplusplus >= 201103L\n \t using _Vp = __conditional_t<_MoveValue,\n \t\t\t\t value_type&&,\n \t\t\t\t const value_type&>;\n #endif\n-\t _Link_type __tmp\n+\t _Node_ptr __tmp\n \t = __node_gen(_GLIBCXX_FORWARD(_Vp, *__x->_M_valptr()));\n \t __tmp->_M_color = __x->_M_color;\n-\t __tmp->_M_left = 0;\n-\t __tmp->_M_right = 0;\n+\t __tmp->_M_left = __tmp->_M_right = _Base_ptr();\n \t return __tmp;\n \t}\n \n protected:\n+ typedef typename _Node_traits::_Header_t\t\t_Header_t;\n+\n #if _GLIBCXX_INLINE_VERSION\n template<typename _Key_compare>\n #else\n@@ -660,7 +1303,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \tstruct _Rb_tree_impl\n \t: public _Node_allocator\n \t, public _Rb_tree_key_compare<_Key_compare>\n-\t, public _Rb_tree_header\n+\t, public _Header_t\n \t{\n \t typedef _Rb_tree_key_compare<_Key_compare> _Base_key_compare;\n \n@@ -672,9 +1315,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t { }\n \n \t _Rb_tree_impl(const _Rb_tree_impl& __x)\n-\t : _Node_allocator(_Alloc_traits::_S_select_on_copy(__x))\n+\t : _Node_allocator(_Node_alloc_traits::_S_select_on_copy(__x))\n \t , _Base_key_compare(__x._M_key_compare)\n-\t , _Rb_tree_header()\n+\t , _Header_t()\n \t { }\n \n #if __cplusplus < 201103L\n@@ -694,7 +1337,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t _Rb_tree_impl(_Rb_tree_impl&& __x, _Node_allocator&& __a)\n \t : _Node_allocator(std::move(__a)),\n \t _Base_key_compare(std::move(__x)),\n-\t _Rb_tree_header(std::move(__x))\n+\t _Header_t(std::move(__x))\n \t { }\n \n \t _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a)\n@@ -710,7 +1353,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n _M_root() _GLIBCXX_NOEXCEPT\n { return this->_M_impl._M_header._M_parent; }\n \n- _Const_Base_ptr\n+ _Base_ptr\n _M_root() const _GLIBCXX_NOEXCEPT\n { return this->_M_impl._M_header._M_parent; }\n \n@@ -718,7 +1361,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n _M_leftmost() _GLIBCXX_NOEXCEPT\n { return this->_M_impl._M_header._M_left; }\n \n- _Const_Base_ptr\n+ _Base_ptr\n _M_leftmost() const _GLIBCXX_NOEXCEPT\n { return this->_M_impl._M_header._M_left; }\n \n@@ -726,35 +1369,29 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n _M_rightmost() _GLIBCXX_NOEXCEPT\n { return this->_M_impl._M_header._M_right; }\n \n- _Const_Base_ptr\n+ _Base_ptr\n _M_rightmost() const _GLIBCXX_NOEXCEPT\n { return this->_M_impl._M_header._M_right; }\n \n- _Link_type\n- _M_mbegin() const _GLIBCXX_NOEXCEPT\n- { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }\n-\n- _Link_type\n- _M_begin() _GLIBCXX_NOEXCEPT\n- { return _M_mbegin(); }\n-\n- _Const_Link_type\n+ _Base_ptr\n _M_begin() const _GLIBCXX_NOEXCEPT\n+ { return this->_M_impl._M_header._M_parent; }\n+\n+ _Node_ptr\n+ _M_begin_node() const _GLIBCXX_NOEXCEPT\n {\n-\treturn static_cast<_Const_Link_type>\n-\t (this->_M_impl._M_header._M_parent);\n+\t_Base_ptr __begin = this->_M_impl._M_header._M_parent;\n+\treturn __begin\n+\t ? static_cast<_Node&>(*__begin)._M_node_ptr()\n+\t : _Node_ptr();\n }\n \n _Base_ptr\n- _M_end() _GLIBCXX_NOEXCEPT\n- { return &this->_M_impl._M_header; }\n-\n- _Const_Base_ptr\n _M_end() const _GLIBCXX_NOEXCEPT\n- { return &this->_M_impl._M_header; }\n+ { return this->_M_impl._M_header._M_base_ptr(); }\n \n static const _Key&\n- _S_key(_Const_Link_type __x)\n+ _S_key(const _Node& __node)\n {\n #if __cplusplus >= 201103L\n \t// If we're asking for the key we're presumably using the comparison\n@@ -772,48 +1409,44 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n # endif // C++17\n #endif // C++11\n \n-\treturn _KeyOfValue()(*__x->_M_valptr());\n+\treturn _KeyOfValue()(*__node._M_valptr());\n }\n \n- static _Link_type\n- _S_left(_Base_ptr __x) _GLIBCXX_NOEXCEPT\n- { return static_cast<_Link_type>(__x->_M_left); }\n-\n- static _Const_Link_type\n- _S_left(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT\n- { return static_cast<_Const_Link_type>(__x->_M_left); }\n-\n- static _Link_type\n- _S_right(_Base_ptr __x) _GLIBCXX_NOEXCEPT\n- { return static_cast<_Link_type>(__x->_M_right); }\n-\n- static _Const_Link_type\n- _S_right(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT\n- { return static_cast<_Const_Link_type>(__x->_M_right); }\n+ static const _Key&\n+ _S_key(_Base_ptr __x)\n+ { return _S_key(static_cast<const _Node&>(*__x)); }\n \n static const _Key&\n- _S_key(_Const_Base_ptr __x)\n- { return _S_key(static_cast<_Const_Link_type>(__x)); }\n+ _S_key(_Node_ptr __x)\n+ { return _S_key(*__x); }\n \n static _Base_ptr\n- _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT\n- { return _Rb_tree_node_base::_S_minimum(__x); }\n+ _S_left(_Base_ptr __x) _GLIBCXX_NOEXCEPT\n+ { return __x->_M_left; }\n \n- static _Const_Base_ptr\n- _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT\n- { return _Rb_tree_node_base::_S_minimum(__x); }\n+ static _Node_ptr\n+ _S_left(_Node_ptr __x)\n+ {\n+\treturn __x->_M_left\n+\t ? static_cast<_Node&>(*__x->_M_left)._M_node_ptr()\n+\t : _Node_ptr();\n+ }\n \n static _Base_ptr\n- _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT\n- { return _Rb_tree_node_base::_S_maximum(__x); }\n+ _S_right(_Base_ptr __x) _GLIBCXX_NOEXCEPT\n+ { return __x->_M_right; }\n \n- static _Const_Base_ptr\n- _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT\n- { return _Rb_tree_node_base::_S_maximum(__x); }\n+ static _Node_ptr\n+ _S_right(_Node_ptr __x) _GLIBCXX_NOEXCEPT\n+ {\n+\treturn __x->_M_right\n+\t ? static_cast<_Node&>(*__x->_M_right)._M_node_ptr()\n+\t : _Node_ptr();\n+ }\n \n public:\n- typedef _Rb_tree_iterator<value_type> iterator;\n- typedef _Rb_tree_const_iterator<value_type> const_iterator;\n+ typedef typename _Node_traits::_Iterator\t\titerator;\n+ typedef typename _Node_traits::_Const_iterator\tconst_iterator;\n \n typedef std::reverse_iterator<iterator> reverse_iterator;\n typedef std::reverse_iterator<const_iterator> const_reverse_iterator;\n@@ -846,7 +1479,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t_M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v, _NodeGen&);\n \n iterator\n- _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Link_type __z);\n+ _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Node_ptr __z);\n \n template<typename _Arg>\n \titerator\n@@ -857,10 +1490,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t_M_insert_equal_lower(_Arg&& __x);\n \n iterator\n- _M_insert_lower_node(_Base_ptr __p, _Link_type __z);\n+ _M_insert_lower_node(_Base_ptr __p, _Node_ptr __z);\n \n iterator\n- _M_insert_equal_lower_node(_Link_type __z);\n+ _M_insert_equal_lower_node(_Node_ptr __z);\n #else\n template<typename _NodeGen>\n \titerator\n@@ -879,22 +1512,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n enum { __as_lvalue, __as_rvalue };\n \n template<bool _MoveValues, typename _NodeGen>\n-\t_Link_type\n-\t_M_copy(_Link_type, _Base_ptr, _NodeGen&);\n+\t_Base_ptr\n+\t_M_copy(_Node_ptr, _Base_ptr, _NodeGen&);\n \n template<bool _MoveValues, typename _NodeGen>\n-\t_Link_type\n+\t_Base_ptr\n \t_M_copy(const _Rb_tree& __x, _NodeGen& __gen)\n \t{\n-\t _Link_type __root =\n-\t _M_copy<_MoveValues>(__x._M_mbegin(), _M_end(), __gen);\n-\t _M_leftmost() = _S_minimum(__root);\n-\t _M_rightmost() = _S_maximum(__root);\n+\t _Base_ptr __root =\n+\t _M_copy<_MoveValues>(__x._M_begin_node(), _M_end(), __gen);\n+\t _M_leftmost() = _Node_base::_S_minimum(__root);\n+\t _M_rightmost() = _Node_base::_S_maximum(__root);\n \t _M_impl._M_node_count = __x._M_impl._M_node_count;\n \t return __root;\n \t}\n \n- _Link_type\n+ _Base_ptr\n _M_copy(const _Rb_tree& __x)\n {\n \t_Alloc_node __an(*this);\n@@ -902,22 +1535,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n }\n \n void\n- _M_erase(_Link_type __x);\n-\n- iterator\n- _M_lower_bound(_Link_type __x, _Base_ptr __y,\n-\t\t const _Key& __k);\n+ _M_erase(_Node_ptr __x);\n \n- const_iterator\n- _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y,\n+ _Base_ptr\n+ _M_lower_bound(_Base_ptr __x, _Base_ptr __y,\n \t\t const _Key& __k) const;\n \n- iterator\n- _M_upper_bound(_Link_type __x, _Base_ptr __y,\n-\t\t const _Key& __k);\n-\n- const_iterator\n- _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y,\n+ _Base_ptr\n+ _M_upper_bound(_Base_ptr __x, _Base_ptr __y,\n \t\t const _Key& __k) const;\n \n public:\n@@ -935,7 +1560,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n _Rb_tree(const _Rb_tree& __x)\n : _M_impl(__x._M_impl)\n {\n-\tif (__x._M_root() != 0)\n+\tif (__x._M_root())\n \t _M_root() = _M_copy(__x);\n }\n \n@@ -947,7 +1572,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n _Rb_tree(const _Rb_tree& __x, const allocator_type& __a)\n : _M_impl(__x._M_impl._M_key_compare, _Node_allocator(__a))\n {\n-\tif (__x._M_root() != nullptr)\n+\tif (__x._M_root())\n \t _M_root() = _M_copy(__x);\n }\n \n@@ -966,7 +1591,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, false_type)\n : _M_impl(__x._M_impl._M_key_compare, std::move(__a))\n {\n-\tif (__x._M_root() != nullptr)\n+\tif (__x._M_root())\n \t _M_move_data(__x, false_type{});\n }\n \n@@ -974,14 +1599,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)\n noexcept( noexcept(\n \t_Rb_tree(std::declval<_Rb_tree&&>(), std::declval<_Node_allocator&&>(),\n-\t\t std::declval<typename _Alloc_traits::is_always_equal>())) )\n+\t\t std::declval<typename _Node_alloc_traits::is_always_equal>())) )\n : _Rb_tree(std::move(__x), std::move(__a),\n-\t\t typename _Alloc_traits::is_always_equal{})\n+\t\t typename _Node_alloc_traits::is_always_equal{})\n { }\n #endif\n \n ~_Rb_tree() _GLIBCXX_NOEXCEPT\n- { _M_erase(_M_begin()); }\n+ { _M_erase(_M_begin_node()); }\n \n _Rb_tree&\n operator=(const _Rb_tree& __x);\n@@ -1001,11 +1626,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \n iterator\n end() _GLIBCXX_NOEXCEPT\n- { return iterator(&this->_M_impl._M_header); }\n+ { return iterator(_M_end()); }\n \n const_iterator\n end() const _GLIBCXX_NOEXCEPT\n- { return const_iterator(&this->_M_impl._M_header); }\n+ { return const_iterator(_M_end()); }\n \n reverse_iterator\n rbegin() _GLIBCXX_NOEXCEPT\n@@ -1033,7 +1658,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \n size_type\n max_size() const _GLIBCXX_NOEXCEPT\n- { return _Alloc_traits::max_size(_M_get_Node_allocator()); }\n+ { return _Node_alloc_traits::max_size(_M_get_Node_allocator()); }\n \n void\n swap(_Rb_tree& __t)\n@@ -1194,7 +1819,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \tconst_iterator __result = __position;\n \t++__result;\n \t_M_erase_aux(__position);\n-\treturn __result._M_const_cast();\n+\treturn iterator(__result._M_node);\n }\n \n // LWG 2059.\n@@ -1235,7 +1860,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n erase(const_iterator __first, const_iterator __last)\n {\n \t_M_erase_aux(__first, __last);\n-\treturn __last._M_const_cast();\n+\treturn iterator(__last._M_node);\n }\n #else\n void\n@@ -1250,7 +1875,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n void\n clear() _GLIBCXX_NOEXCEPT\n {\n-\t_M_erase(_M_begin());\n+\t_M_erase(_M_begin_node());\n \t_M_impl._M_reset();\n }\n \n@@ -1266,19 +1891,25 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \n iterator\n lower_bound(const key_type& __k)\n- { return _M_lower_bound(_M_begin(), _M_end(), __k); }\n+ { return iterator(_M_lower_bound(_M_begin(), _M_end(), __k)); }\n \n const_iterator\n lower_bound(const key_type& __k) const\n- { return _M_lower_bound(_M_begin(), _M_end(), __k); }\n+ {\n+\treturn const_iterator\n+\t (_M_lower_bound(_M_begin(), _M_end(), __k));\n+ }\n \n iterator\n upper_bound(const key_type& __k)\n- { return _M_upper_bound(_M_begin(), _M_end(), __k); }\n+ { return iterator(_M_upper_bound(_M_begin(), _M_end(), __k)); }\n \n const_iterator\n upper_bound(const key_type& __k) const\n- { return _M_upper_bound(_M_begin(), _M_end(), __k); }\n+ {\n+\treturn const_iterator\n+\t (_M_upper_bound(_M_begin(), _M_end(), __k));\n+ }\n \n pair<iterator, iterator>\n equal_range(const key_type& __k);\n@@ -1293,7 +1924,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t_M_find_tr(const _Kt& __k)\n \t{\n \t const _Rb_tree* __const_this = this;\n-\t return __const_this->_M_find_tr(__k)._M_const_cast();\n+\t return iterator(__const_this->_M_find_tr(__k)._M_node);\n \t}\n \n template<typename _Kt,\n@@ -1301,7 +1932,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \tconst_iterator\n \t_M_find_tr(const _Kt& __k) const\n \t{\n-\t auto __j = _M_lower_bound_tr(__k);\n+\t const_iterator __j(_M_lower_bound_tr(__k));\n \t if (__j != end() && _M_impl._M_key_compare(__k, _S_key(__j._M_node)))\n \t __j = end();\n \t return __j;\n@@ -1318,21 +1949,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \n template<typename _Kt,\n \t typename _Req = __has_is_transparent_t<_Compare, _Kt>>\n-\titerator\n-\t_M_lower_bound_tr(const _Kt& __k)\n-\t{\n-\t const _Rb_tree* __const_this = this;\n-\t return __const_this->_M_lower_bound_tr(__k)._M_const_cast();\n-\t}\n-\n- template<typename _Kt,\n-\t typename _Req = __has_is_transparent_t<_Compare, _Kt>>\n-\tconst_iterator\n+\t_Base_ptr\n \t_M_lower_bound_tr(const _Kt& __k) const\n \t{\n \t auto __x = _M_begin();\n \t auto __y = _M_end();\n-\t while (__x != 0)\n+\t while (__x)\n \t if (!_M_impl._M_key_compare(_S_key(__x), __k))\n \t {\n \t\t__y = __x;\n@@ -1340,26 +1962,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t }\n \t else\n \t __x = _S_right(__x);\n-\t return const_iterator(__y);\n-\t}\n-\n- template<typename _Kt,\n-\t typename _Req = __has_is_transparent_t<_Compare, _Kt>>\n-\titerator\n-\t_M_upper_bound_tr(const _Kt& __k)\n-\t{\n-\t const _Rb_tree* __const_this = this;\n-\t return __const_this->_M_upper_bound_tr(__k)._M_const_cast();\n+\t return __y;\n \t}\n \n template<typename _Kt,\n \t typename _Req = __has_is_transparent_t<_Compare, _Kt>>\n-\tconst_iterator\n+\t_Base_ptr\n \t_M_upper_bound_tr(const _Kt& __k) const\n \t{\n \t auto __x = _M_begin();\n \t auto __y = _M_end();\n-\t while (__x != 0)\n+\t while (__x)\n \t if (_M_impl._M_key_compare(__k, _S_key(__x)))\n \t {\n \t\t__y = __x;\n@@ -1367,7 +1980,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t }\n \t else\n \t __x = _S_right(__x);\n-\t return const_iterator(__y);\n+\t return __y;\n \t}\n \n template<typename _Kt,\n@@ -1377,7 +1990,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t{\n \t const _Rb_tree* __const_this = this;\n \t auto __ret = __const_this->_M_equal_range_tr(__k);\n-\t return { __ret.first._M_const_cast(), __ret.second._M_const_cast() };\n+\t return\n+\t { iterator(__ret.first._M_node), iterator(__ret.second._M_node) };\n \t}\n \n template<typename _Kt,\n@@ -1385,7 +1999,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \tpair<const_iterator, const_iterator>\n \t_M_equal_range_tr(const _Kt& __k) const\n \t{\n-\t auto __low = _M_lower_bound_tr(__k);\n+\t const_iterator __low(_M_lower_bound_tr(__k));\n \t auto __high = __low;\n \t auto& __cmp = _M_impl._M_key_compare;\n \t while (__high != end() && !__cmp(__k, _S_key(__high._M_node)))\n@@ -1401,7 +2015,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n #if __cplusplus >= 201103L\n _Rb_tree&\n operator=(_Rb_tree&&)\n- noexcept(_Alloc_traits::_S_nothrow_move()\n+ noexcept(_Node_alloc_traits::_S_nothrow_move()\n \t && is_nothrow_move_assignable<_Compare>::value);\n \n template<typename _Iterator>\n@@ -1434,6 +2048,23 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n #endif\n \n #if __glibcxx_node_extract // >= C++17\n+ static _Node_ptr\n+ _S_adapt(typename _Node_alloc_traits::pointer __ptr)\n+ {\n+#if _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE\n+\treturn __ptr;\n+#else\n+#pragma GCC diagnostic push\n+#pragma GCC diagnostic ignored \"-Wc++17-extensions\" // if constexpr\n+\tusing __alloc_ptr = typename _Node_alloc_traits::pointer;\n+\tif constexpr (is_same<_Node_ptr, __alloc_ptr>::value)\n+\t return __ptr;\n+\telse\n+\t return std::__to_address(__ptr);\n+#pragma GCC diagnostic pop\n+#endif\n+ }\n+\n public:\n /// Re-insert an extracted node.\n insert_return_type\n@@ -1450,7 +2081,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t if (__res.second)\n \t {\n \t\t__ret.position\n-\t\t = _M_insert_node(__res.first, __res.second, __nh._M_ptr);\n+\t\t = _M_insert_node(__res.first, __res.second,\n+\t\t\t\t _S_adapt(__nh._M_ptr));\n \t\t__nh.release();\n \t\t__ret.inserted = true;\n \t }\n@@ -1476,9 +2108,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);\n \t auto __res = _M_get_insert_equal_pos(__nh._M_key());\n \t if (__res.second)\n-\t __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr);\n+\t __ret = _M_insert_node(__res.first, __res.second,\n+\t\t\t\t _S_adapt(__nh._M_ptr));\n \t else\n-\t __ret = _M_insert_equal_lower_node(__nh._M_ptr);\n+\t __ret = _M_insert_equal_lower_node(_S_adapt(__nh._M_ptr));\n \t __nh.release();\n \t }\n \treturn __ret;\n@@ -1497,7 +2130,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t auto __res = _M_get_insert_hint_unique_pos(__hint, __nh._M_key());\n \t if (__res.second)\n \t {\n-\t\t__ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr);\n+\t\t__ret = _M_insert_node(__res.first, __res.second,\n+\t\t\t\t _S_adapt(__nh._M_ptr));\n \t\t__nh.release();\n \t }\n \t else\n@@ -1518,9 +2152,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);\n \t auto __res = _M_get_insert_hint_equal_pos(__hint, __nh._M_key());\n \t if (__res.second)\n-\t __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr);\n+\t __ret = _M_insert_node(__res.first, __res.second,\n+\t\t\t\t _S_adapt(__nh._M_ptr));\n \t else\n-\t __ret = _M_insert_equal_lower_node(__nh._M_ptr);\n+\t __ret = _M_insert_equal_lower_node(_S_adapt(__nh._M_ptr));\n \t __nh.release();\n \t }\n \treturn __ret;\n@@ -1530,10 +2165,25 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n node_type\n extract(const_iterator __pos)\n {\n-\tauto __ptr = _Rb_tree_rebalance_for_erase(\n-\t __pos._M_const_cast()._M_node, _M_impl._M_header);\n+\tauto __ptr = _Node_traits::_S_rebalance_for_erase\n+\t (__pos._M_node, _M_impl._M_header);\n \t--_M_impl._M_node_count;\n-\treturn { static_cast<_Link_type>(__ptr), _M_get_Node_allocator() };\n+\tauto __node_ptr = static_cast<_Node&>(*__ptr)._M_node_ptr();\n+#if _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE\n+\treturn { __node_ptr, _M_get_Node_allocator() };\n+#else\n+#pragma GCC diagnostic push\n+#pragma GCC diagnostic ignored \"-Wc++17-extensions\" // if constexpr\n+\tusing __alloc_ptr = typename _Node_alloc_traits::pointer;\n+\tif constexpr (is_same<_Node_ptr, __alloc_ptr>::value)\n+\t return { __node_ptr, _M_get_Node_allocator() };\n+\telse\n+\t {\n+\t auto __ap = pointer_traits<__alloc_ptr>::pointer_to(*__node_ptr);\n+\t return { __ap, _M_get_Node_allocator() };\n+\t }\n+#pragma GCC diagnostic pop\n+#endif\n }\n \n /// Extract a node.\n@@ -1567,11 +2217,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t if (__res.second)\n \t\t{\n \t\t auto& __src_impl = _Merge_helper::_S_get_impl(__src);\n-\t\t auto __ptr = _Rb_tree_rebalance_for_erase(\n-\t\t __pos._M_node, __src_impl._M_header);\n+\t\t auto __ptr = _Node_traits::_S_rebalance_for_erase\n+\t\t (__pos._M_node, __src_impl._M_header);\n \t\t --__src_impl._M_node_count;\n-\t\t _M_insert_node(__res.first, __res.second,\n-\t\t\t\t static_cast<_Link_type>(__ptr));\n+\t\t auto __node_ptr = static_cast<_Node&>(*__ptr)._M_node_ptr();\n+\t\t _M_insert_node(__res.first, __res.second, __node_ptr);\n \t\t}\n \t }\n \t}\n@@ -1589,11 +2239,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t if (__res.second)\n \t\t{\n \t\t auto& __src_impl = _Merge_helper::_S_get_impl(__src);\n-\t\t auto __ptr = _Rb_tree_rebalance_for_erase(\n-\t\t __pos._M_node, __src_impl._M_header);\n+\t\t auto __ptr = _Node_traits::_S_rebalance_for_erase\n+\t\t (__pos._M_node, __src_impl._M_header);\n \t\t --__src_impl._M_node_count;\n-\t\t _M_insert_node(__res.first, __res.second,\n-\t\t\t\t static_cast<_Link_type>(__ptr));\n+\t\t auto __node_ptr = static_cast<_Node&>(*__ptr)._M_node_ptr();\n+\t\t _M_insert_node(__res.first, __res.second, __node_ptr);\n \t\t}\n \t }\n \t}\n@@ -1666,7 +2316,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t}\n \n \t_Rb_tree& _M_t;\n-\t_Link_type _M_node;\n+\t_Node_ptr _M_node;\n };\n #endif // C++11\n };\n@@ -1704,7 +2354,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n _M_move_assign(_Rb_tree& __x, true_type)\n {\n clear();\n- if (__x._M_root() != nullptr)\n+ if (__x._M_root())\n \t_M_move_data(__x, true_type());\n std::__alloc_on_move(_M_get_Node_allocator(),\n \t\t\t __x._M_get_Node_allocator());\n@@ -1723,7 +2373,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n // structure.\n _Reuse_or_alloc_node __roan(*this);\n _M_impl._M_reset();\n- if (__x._M_root() != nullptr)\n+ if (__x._M_root())\n \t{\n \t _M_root() = _M_copy<__as_rvalue>(__x, __roan);\n \t __x.clear();\n@@ -1735,11 +2385,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n inline _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&\n _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::\n operator=(_Rb_tree&& __x)\n- noexcept(_Alloc_traits::_S_nothrow_move()\n+ noexcept(_Node_alloc_traits::_S_nothrow_move()\n \t && is_nothrow_move_assignable<_Compare>::value)\n {\n _M_impl._M_key_compare = std::move(__x._M_impl._M_key_compare);\n- _M_move_assign(__x, __bool_constant<_Alloc_traits::_S_nothrow_move()>());\n+ _M_move_assign(__x,\n+\t\t __bool_constant<_Node_alloc_traits::_S_nothrow_move()>());\n return *this;\n }\n \n@@ -1780,11 +2431,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t{\n \t // Note that _Key may be a constant type.\n #if __cplusplus >= 201103L\n-\t if (_Alloc_traits::_S_propagate_on_copy_assign())\n+\t if (_Node_alloc_traits::_S_propagate_on_copy_assign())\n \t {\n \t auto& __this_alloc = this->_M_get_Node_allocator();\n \t auto& __that_alloc = __x._M_get_Node_allocator();\n-\t if (!_Alloc_traits::_S_always_equal()\n+\t if (!_Node_alloc_traits::_S_always_equal()\n \t\t && __this_alloc != __that_alloc)\n \t\t{\n \t\t // Replacement allocator cannot free existing storage, we need\n@@ -1798,7 +2449,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t _Reuse_or_alloc_node __roan(*this);\n \t _M_impl._M_reset();\n \t _M_impl._M_key_compare = __x._M_impl._M_key_compare;\n-\t if (__x._M_root() != 0)\n+\t if (__x._M_root())\n \t _M_root() = _M_copy<__as_lvalue>(__x, __roan);\n \t}\n \n@@ -1822,14 +2473,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n #endif\n \t\t _NodeGen& __node_gen)\n {\n-\tbool __insert_left = (__x != 0 || __p == _M_end()\n+\tbool __insert_left = (__x || __p == _M_end()\n \t\t\t || _M_impl._M_key_compare(_KeyOfValue()(__v),\n \t\t\t\t\t\t\t_S_key(__p)));\n \n-\t_Link_type __z = __node_gen(_GLIBCXX_FORWARD(_Arg, __v));\n+\t_Base_ptr __z =\n+\t __node_gen(_GLIBCXX_FORWARD(_Arg, __v))->_M_base_ptr();\n \n-\t_Rb_tree_insert_and_rebalance(__insert_left, __z, __p,\n-\t\t\t\t this->_M_impl._M_header);\n+\t_Node_traits::_S_insert_and_rebalance\n+\t (__insert_left, __z, __p, this->_M_impl._M_header);\n \t++_M_impl._M_node_count;\n \treturn iterator(__z);\n }\n@@ -1851,10 +2503,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t\t\t || !_M_impl._M_key_compare(_S_key(__p),\n \t\t\t\t\t\t _KeyOfValue()(__v)));\n \n- _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));\n-\n- _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,\n-\t\t\t\t this->_M_impl._M_header);\n+ _Base_ptr __z =\n+\t_M_create_node(_GLIBCXX_FORWARD(_Arg, __v))->_M_base_ptr();\n+ _Node_traits::_S_insert_and_rebalance\n+\t(__insert_left, __z, __p, this->_M_impl._M_header);\n ++_M_impl._M_node_count;\n return iterator(__z);\n }\n@@ -1872,9 +2524,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n _M_insert_equal_lower(const _Val& __v)\n #endif\n {\n- _Link_type __x = _M_begin();\n+ _Base_ptr __x = _M_begin();\n _Base_ptr __y = _M_end();\n- while (__x != 0)\n+ while (__x)\n \t{\n \t __y = __x;\n \t __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?\n@@ -1886,25 +2538,27 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n template<typename _Key, typename _Val, typename _KoV,\n \t typename _Compare, typename _Alloc>\n template<bool _MoveValues, typename _NodeGen>\n- typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type\n+ typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Base_ptr\n _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::\n- _M_copy(_Link_type __x, _Base_ptr __p, _NodeGen& __node_gen)\n+ _M_copy(_Node_ptr __x, _Base_ptr __p, _NodeGen& __node_gen)\n {\n \t// Structural copy. __x and __p must be non-null.\n-\t_Link_type __top = _M_clone_node<_MoveValues>(__x, __node_gen);\n+\t_Node_ptr __top = _M_clone_node<_MoveValues>(__x, __node_gen);\n+\t_Base_ptr __top_base = __top->_M_base_ptr();\n \t__top->_M_parent = __p;\n \n \t__try\n \t {\n \t if (__x->_M_right)\n \t __top->_M_right =\n-\t\t_M_copy<_MoveValues>(_S_right(__x), __top, __node_gen);\n-\t __p = __top;\n+\t\t_M_copy<_MoveValues>(_S_right(__x), __top_base, __node_gen);\n+\t __p = __top_base;\n \t __x = _S_left(__x);\n \n-\t while (__x != 0)\n+\t while (__x)\n \t {\n-\t\t_Link_type __y = _M_clone_node<_MoveValues>(__x, __node_gen);\n+\t\t_Base_ptr __y =\n+\t\t _M_clone_node<_MoveValues>(__x, __node_gen)->_M_base_ptr();\n \t\t__p->_M_left = __y;\n \t\t__y->_M_parent = __p;\n \t\tif (__x->_M_right)\n@@ -1919,20 +2573,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t _M_erase(__top);\n \t __throw_exception_again;\n \t }\n-\treturn __top;\n+\treturn __top_base;\n }\n \n template<typename _Key, typename _Val, typename _KeyOfValue,\n \t typename _Compare, typename _Alloc>\n void\n _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::\n- _M_erase(_Link_type __x)\n+ _M_erase(_Node_ptr __x)\n {\n // Erase without rebalancing.\n- while (__x != 0)\n+ while (__x)\n \t{\n \t _M_erase(_S_right(__x));\n-\t _Link_type __y = _S_left(__x);\n+\t _Node_ptr __y = _S_left(__x);\n \t _M_drop_node(__x);\n \t __x = __y;\n \t}\n@@ -1941,65 +2595,33 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n template<typename _Key, typename _Val, typename _KeyOfValue,\n \t typename _Compare, typename _Alloc>\n typename _Rb_tree<_Key, _Val, _KeyOfValue,\n-\t\t _Compare, _Alloc>::iterator\n- _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::\n- _M_lower_bound(_Link_type __x, _Base_ptr __y,\n-\t\t const _Key& __k)\n- {\n- while (__x != 0)\n-\tif (!_M_impl._M_key_compare(_S_key(__x), __k))\n-\t __y = __x, __x = _S_left(__x);\n-\telse\n-\t __x = _S_right(__x);\n- return iterator(__y);\n- }\n-\n- template<typename _Key, typename _Val, typename _KeyOfValue,\n-\t typename _Compare, typename _Alloc>\n- typename _Rb_tree<_Key, _Val, _KeyOfValue,\n-\t\t _Compare, _Alloc>::const_iterator\n+\t\t _Compare, _Alloc>::_Base_ptr\n _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::\n- _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y,\n+ _M_lower_bound(_Base_ptr __x, _Base_ptr __y,\n \t\t const _Key& __k) const\n {\n- while (__x != 0)\n+ while (__x)\n \tif (!_M_impl._M_key_compare(_S_key(__x), __k))\n \t __y = __x, __x = _S_left(__x);\n \telse\n \t __x = _S_right(__x);\n- return const_iterator(__y);\n+ return __y;\n }\n \n template<typename _Key, typename _Val, typename _KeyOfValue,\n \t typename _Compare, typename _Alloc>\n typename _Rb_tree<_Key, _Val, _KeyOfValue,\n-\t\t _Compare, _Alloc>::iterator\n+\t\t _Compare, _Alloc>::_Base_ptr\n _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::\n- _M_upper_bound(_Link_type __x, _Base_ptr __y,\n-\t\t const _Key& __k)\n- {\n- while (__x != 0)\n-\tif (_M_impl._M_key_compare(__k, _S_key(__x)))\n-\t __y = __x, __x = _S_left(__x);\n-\telse\n-\t __x = _S_right(__x);\n- return iterator(__y);\n- }\n-\n- template<typename _Key, typename _Val, typename _KeyOfValue,\n-\t typename _Compare, typename _Alloc>\n- typename _Rb_tree<_Key, _Val, _KeyOfValue,\n-\t\t _Compare, _Alloc>::const_iterator\n- _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::\n- _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y,\n+ _M_upper_bound(_Base_ptr __x, _Base_ptr __y,\n \t\t const _Key& __k) const\n {\n- while (__x != 0)\n+ while (__x)\n \tif (_M_impl._M_key_compare(__k, _S_key(__x)))\n \t __y = __x, __x = _S_left(__x);\n \telse\n \t __x = _S_right(__x);\n- return const_iterator(__y);\n+ return __y;\n }\n \n template<typename _Key, typename _Val, typename _KeyOfValue,\n@@ -2011,9 +2633,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::\n equal_range(const _Key& __k)\n {\n- _Link_type __x = _M_begin();\n+ _Base_ptr __x = _M_begin();\n _Base_ptr __y = _M_end();\n- while (__x != 0)\n+ while (__x)\n \t{\n \t if (_M_impl._M_key_compare(_S_key(__x), __k))\n \t __x = _S_right(__x);\n@@ -2021,13 +2643,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t __y = __x, __x = _S_left(__x);\n \t else\n \t {\n-\t _Link_type __xu(__x);\n+\t _Base_ptr __xu(__x);\n \t _Base_ptr __yu(__y);\n \t __y = __x, __x = _S_left(__x);\n \t __xu = _S_right(__xu);\n-\t return pair<iterator,\n-\t\t\t iterator>(_M_lower_bound(__x, __y, __k),\n-\t\t\t\t _M_upper_bound(__xu, __yu, __k));\n+\t return make_pair(iterator(_M_lower_bound(__x, __y, __k)),\n+\t\t\t iterator(_M_upper_bound(__xu, __yu, __k)));\n \t }\n \t}\n return pair<iterator, iterator>(iterator(__y),\n@@ -2043,9 +2664,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::\n equal_range(const _Key& __k) const\n {\n- _Const_Link_type __x = _M_begin();\n- _Const_Base_ptr __y = _M_end();\n- while (__x != 0)\n+ _Base_ptr __x = _M_begin();\n+ _Base_ptr __y = _M_end();\n+ while (__x)\n \t{\n \t if (_M_impl._M_key_compare(_S_key(__x), __k))\n \t __x = _S_right(__x);\n@@ -2053,13 +2674,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t __y = __x, __x = _S_left(__x);\n \t else\n \t {\n-\t _Const_Link_type __xu(__x);\n-\t _Const_Base_ptr __yu(__y);\n+\t _Base_ptr __xu(__x);\n+\t _Base_ptr __yu(__y);\n \t __y = __x, __x = _S_left(__x);\n \t __xu = _S_right(__xu);\n-\t return pair<const_iterator,\n-\t\t\t const_iterator>(_M_lower_bound(__x, __y, __k),\n-\t\t\t\t\t _M_upper_bound(__xu, __yu, __k));\n+\t return make_pair(const_iterator(_M_lower_bound(__x, __y, __k)),\n+\t\t\t const_iterator(_M_upper_bound(__xu, __yu, __k)));\n \t }\n \t}\n return pair<const_iterator, const_iterator>(const_iterator(__y),\n@@ -2073,12 +2693,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n swap(_Rb_tree& __t)\n _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)\n {\n- if (_M_root() == 0)\n+ if (!_M_root())\n \t{\n-\t if (__t._M_root() != 0)\n+\t if (__t._M_root())\n \t _M_impl._M_move_data(__t._M_impl);\n \t}\n- else if (__t._M_root() == 0)\n+ else if (!__t._M_root())\n \t__t._M_impl._M_move_data(_M_impl);\n else\n \t{\n@@ -2093,8 +2713,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n // No need to swap header's color as it does not change.\n std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);\n \n- _Alloc_traits::_S_on_swap(_M_get_Node_allocator(),\n-\t\t\t\t__t._M_get_Node_allocator());\n+ _Node_alloc_traits::_S_on_swap(_M_get_Node_allocator(),\n+\t\t\t\t __t._M_get_Node_allocator());\n }\n \n template<typename _Key, typename _Val, typename _KeyOfValue,\n@@ -2107,10 +2727,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n _M_get_insert_unique_pos(const key_type& __k)\n {\n typedef pair<_Base_ptr, _Base_ptr> _Res;\n- _Link_type __x = _M_begin();\n+ _Base_ptr __x = _M_begin();\n _Base_ptr __y = _M_end();\n bool __comp = true;\n- while (__x != 0)\n+ while (__x)\n \t{\n \t __y = __x;\n \t __comp = _M_impl._M_key_compare(__k, _S_key(__x));\n@@ -2126,7 +2746,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t}\n if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))\n \treturn _Res(__x, __y);\n- return _Res(__j._M_node, 0);\n+ return _Res(__j._M_node, _Base_ptr());\n }\n \n template<typename _Key, typename _Val, typename _KeyOfValue,\n@@ -2139,9 +2759,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n _M_get_insert_equal_pos(const key_type& __k)\n {\n typedef pair<_Base_ptr, _Base_ptr> _Res;\n- _Link_type __x = _M_begin();\n+ _Base_ptr __x = _M_begin();\n _Base_ptr __y = _M_end();\n- while (__x != 0)\n+ while (__x)\n \t{\n \t __y = __x;\n \t __x = _M_impl._M_key_compare(__k, _S_key(__x)) ?\n@@ -2209,44 +2829,43 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n _M_get_insert_hint_unique_pos(const_iterator __position,\n \t\t\t\t const key_type& __k)\n {\n- iterator __pos = __position._M_const_cast();\n typedef pair<_Base_ptr, _Base_ptr> _Res;\n \n // end()\n- if (__pos._M_node == _M_end())\n+ if (__position._M_node == _M_end())\n \t{\n \t if (size() > 0\n \t && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k))\n-\t return _Res(0, _M_rightmost());\n+\t return _Res(_Base_ptr(), _M_rightmost());\n \t else\n \t return _M_get_insert_unique_pos(__k);\n \t}\n- else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node)))\n+ else if (_M_impl._M_key_compare(__k, _S_key(__position._M_node)))\n \t{\n \t // First, try before...\n-\t iterator __before = __pos;\n-\t if (__pos._M_node == _M_leftmost()) // begin()\n+\t iterator __before(__position._M_node);\n+\t if (__position._M_node == _M_leftmost()) // begin()\n \t return _Res(_M_leftmost(), _M_leftmost());\n \t else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k))\n \t {\n-\t if (_S_right(__before._M_node) == 0)\n-\t\treturn _Res(0, __before._M_node);\n+\t if (!_S_right(__before._M_node))\n+\t\treturn _Res(_Base_ptr(), __before._M_node);\n \t else\n-\t\treturn _Res(__pos._M_node, __pos._M_node);\n+\t\treturn _Res(__position._M_node, __position._M_node);\n \t }\n \t else\n \t return _M_get_insert_unique_pos(__k);\n \t}\n- else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k))\n+ else if (_M_impl._M_key_compare(_S_key(__position._M_node), __k))\n \t{\n \t // ... then try after.\n-\t iterator __after = __pos;\n-\t if (__pos._M_node == _M_rightmost())\n-\t return _Res(0, _M_rightmost());\n+\t iterator __after(__position._M_node);\n+\t if (__position._M_node == _M_rightmost())\n+\t return _Res(_Base_ptr(), _M_rightmost());\n \t else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node)))\n \t {\n-\t if (_S_right(__pos._M_node) == 0)\n-\t\treturn _Res(0, __pos._M_node);\n+\t if (!_S_right(__position._M_node))\n+\t\treturn _Res(_Base_ptr(), __position._M_node);\n \t else\n \t\treturn _Res(__after._M_node, __after._M_node);\n \t }\n@@ -2255,7 +2874,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t}\n else\n \t// Equivalent keys.\n-\treturn _Res(__pos._M_node, 0);\n+\treturn _Res(__position._M_node, _Base_ptr());\n }\n \n template<typename _Key, typename _Val, typename _KeyOfValue,\n@@ -2294,30 +2913,29 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::\n _M_get_insert_hint_equal_pos(const_iterator __position, const key_type& __k)\n {\n- iterator __pos = __position._M_const_cast();\n typedef pair<_Base_ptr, _Base_ptr> _Res;\n \n // end()\n- if (__pos._M_node == _M_end())\n+ if (__position._M_node == _M_end())\n \t{\n \t if (size() > 0\n \t && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost())))\n-\t return _Res(0, _M_rightmost());\n+\t return _Res(_Base_ptr(), _M_rightmost());\n \t else\n \t return _M_get_insert_equal_pos(__k);\n \t}\n- else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k))\n+ else if (!_M_impl._M_key_compare(_S_key(__position._M_node), __k))\n \t{\n \t // First, try before...\n-\t iterator __before = __pos;\n-\t if (__pos._M_node == _M_leftmost()) // begin()\n+\t iterator __before(__position._M_node);\n+\t if (__position._M_node == _M_leftmost()) // begin()\n \t return _Res(_M_leftmost(), _M_leftmost());\n \t else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node)))\n \t {\n-\t if (_S_right(__before._M_node) == 0)\n-\t\treturn _Res(0, __before._M_node);\n+\t if (!_S_right(__before._M_node))\n+\t\treturn _Res(_Base_ptr(), __before._M_node);\n \t else\n-\t\treturn _Res(__pos._M_node, __pos._M_node);\n+\t\treturn _Res(__position._M_node, __position._M_node);\n \t }\n \t else\n \t return _M_get_insert_equal_pos(__k);\n@@ -2325,18 +2943,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n else\n \t{\n \t // ... then try after.\n-\t iterator __after = __pos;\n-\t if (__pos._M_node == _M_rightmost())\n-\t return _Res(0, _M_rightmost());\n+\t iterator __after(__position._M_node);\n+\t if (__position._M_node == _M_rightmost())\n+\t return _Res(_Base_ptr(), _M_rightmost());\n \t else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k))\n \t {\n-\t if (_S_right(__pos._M_node) == 0)\n-\t\treturn _Res(0, __pos._M_node);\n+\t if (!_S_right(__position._M_node))\n+\t\treturn _Res(_Base_ptr(), __position._M_node);\n \t else\n \t\treturn _Res(__after._M_node, __after._M_node);\n \t }\n \t else\n-\t return _Res(0, 0);\n+\t return _Res(_Base_ptr(), _Base_ptr());\n \t}\n }\n \n@@ -2373,46 +2991,48 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t typename _Compare, typename _Alloc>\n auto\n _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::\n- _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z)\n+ _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Node_ptr __z)\n -> iterator\n {\n- bool __insert_left = (__x != 0 || __p == _M_end()\n+ bool __insert_left = (__x || __p == _M_end()\n \t\t\t || _M_impl._M_key_compare(_S_key(__z),\n \t\t\t\t\t\t _S_key(__p)));\n \n- _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,\n-\t\t\t\t this->_M_impl._M_header);\n+ _Base_ptr __base_z = __z->_M_base_ptr();\n+ _Node_traits::_S_insert_and_rebalance\n+\t(__insert_left, __base_z, __p, this->_M_impl._M_header);\n ++_M_impl._M_node_count;\n- return iterator(__z);\n+ return iterator(__base_z);\n }\n \n template<typename _Key, typename _Val, typename _KeyOfValue,\n \t typename _Compare, typename _Alloc>\n auto\n _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::\n- _M_insert_lower_node(_Base_ptr __p, _Link_type __z)\n+ _M_insert_lower_node(_Base_ptr __p, _Node_ptr __z)\n -> iterator\n {\n bool __insert_left = (__p == _M_end()\n \t\t\t || !_M_impl._M_key_compare(_S_key(__p),\n \t\t\t\t\t\t _S_key(__z)));\n \n- _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,\n-\t\t\t\t this->_M_impl._M_header);\n+ _Base_ptr __base_z = __z->_M_base_ptr();\n+ _Node_traits::_S_insert_and_rebalance\n+\t(__insert_left, __base_z, __p, this->_M_impl._M_header);\n ++_M_impl._M_node_count;\n- return iterator(__z);\n+ return iterator(__base_z);\n }\n \n template<typename _Key, typename _Val, typename _KeyOfValue,\n \t typename _Compare, typename _Alloc>\n auto\n _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::\n- _M_insert_equal_lower_node(_Link_type __z)\n+ _M_insert_equal_lower_node(_Node_ptr __z)\n -> iterator\n {\n- _Link_type __x = _M_begin();\n+ _Base_ptr __x = _M_begin();\n _Base_ptr __y = _M_end();\n- while (__x != 0)\n+ while (__x)\n \t{\n \t __y = __x;\n \t __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ?\n@@ -2487,11 +3107,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::\n _M_erase_aux(const_iterator __position)\n {\n- _Link_type __y =\n-\tstatic_cast<_Link_type>(_Rb_tree_rebalance_for_erase\n-\t\t\t\t(const_cast<_Base_ptr>(__position._M_node),\n-\t\t\t\t this->_M_impl._M_header));\n- _M_drop_node(__y);\n+ _Base_ptr __y = _Node_traits::_S_rebalance_for_erase\n+\t(__position._M_node, this->_M_impl._M_header);\n+ _M_drop_node(static_cast<_Node&>(*__y)._M_node_ptr());\n --_M_impl._M_node_count;\n }\n \n@@ -2527,7 +3145,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::\n find(const _Key& __k)\n {\n- iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);\n+ iterator __j(_M_lower_bound(_M_begin(), _M_end(), __k));\n return (__j == end()\n \t || _M_impl._M_key_compare(__k,\n \t\t\t\t\t_S_key(__j._M_node))) ? end() : __j;\n@@ -2540,7 +3158,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::\n find(const _Key& __k) const\n {\n- const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);\n+ const_iterator __j(_M_lower_bound(_M_begin(), _M_end(), __k));\n return (__j == end()\n \t || _M_impl._M_key_compare(__k,\n \t\t\t\t\t_S_key(__j._M_node))) ? end() : __j;\n@@ -2574,9 +3192,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());\n for (const_iterator __it = begin(); __it != end(); ++__it)\n \t{\n-\t _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);\n-\t _Const_Link_type __L = _S_left(__x);\n-\t _Const_Link_type __R = _S_right(__x);\n+\t _Base_ptr __x = __it._M_node;\n+\t _Base_ptr __L = _S_left(__x);\n+\t _Base_ptr __R = _S_right(__x);\n \n \t if (__x->_M_color == _S_red)\n \t if ((__L && __L->_M_color == _S_red)\n@@ -2592,9 +3210,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t return false;\n \t}\n \n- if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))\n+ if (_M_leftmost() != _Node_base::_S_minimum(_M_root()))\n \treturn false;\n- if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))\n+ if (_M_rightmost() != _Node_base::_S_maximum(_M_root()))\n \treturn false;\n return true;\n }\ndiff --git a/libstdc++-v3/testsuite/23_containers/map/allocator/ext_ptr.cc b/libstdc++-v3/testsuite/23_containers/map/allocator/ext_ptr.cc\nnew file mode 100644\nindex 000000000000..3d83738f86b3\n--- /dev/null\n+++ b/libstdc++-v3/testsuite/23_containers/map/allocator/ext_ptr.cc\n@@ -0,0 +1,37 @@\n+// { dg-do run { target c++11 } }\n+\n+#include <map>\n+#include <memory>\n+#include <testsuite_hooks.h>\n+#include <testsuite_allocator.h>\n+\n+struct T { int i; };\n+\n+bool operator<(const T& l, const T& r)\n+{ return l.i < r.i; }\n+\n+struct L : std::less<T>\n+{ };\n+\n+using __gnu_test::CustomPointerAlloc;\n+\n+template class std::map<T, int, L,\n+\t\t\tCustomPointerAlloc<std::pair<const T, int>>>;\n+\n+void test01()\n+{\n+ typedef CustomPointerAlloc<std::pair<const T, int>> alloc_type;\n+ typedef std::map<T, int, L, alloc_type> test_type;\n+ test_type v;\n+ v.insert({ T(), 0 });\n+ VERIFY( v.begin()->second == 0 );\n+ VERIFY( ++v.begin() == v.end() );\n+ v.insert({ T { 1 }, 1 });\n+ VERIFY( v.size() == 2 );\n+ VERIFY( v.find(T()) != v.end() );\n+}\n+\n+int main()\n+{\n+ test01();\n+}\ndiff --git a/libstdc++-v3/testsuite/23_containers/multimap/allocator/ext_ptr.cc b/libstdc++-v3/testsuite/23_containers/multimap/allocator/ext_ptr.cc\nnew file mode 100644\nindex 000000000000..41689ef43b7e\n--- /dev/null\n+++ b/libstdc++-v3/testsuite/23_containers/multimap/allocator/ext_ptr.cc\n@@ -0,0 +1,33 @@\n+// { dg-do run { target c++11 } }\n+\n+#include <map>\n+#include <memory>\n+#include <testsuite_hooks.h>\n+#include <testsuite_allocator.h>\n+\n+struct T { int i; };\n+\n+bool operator<(const T& l, const T& r)\n+{ return l.i < r.i; }\n+\n+struct L : std::less<T>\n+{ };\n+\n+using __gnu_test::CustomPointerAlloc;\n+\n+template class std::multimap<T, int, L,\n+\t\t\tCustomPointerAlloc<std::pair<const T, int>>>;\n+\n+void test01()\n+{\n+ typedef CustomPointerAlloc<std::pair<const T, int>> alloc_type;\n+ typedef std::multimap<T, int, L, alloc_type> test_type;\n+ test_type v;\n+ v.insert({ T(), 0 });\n+ VERIFY( ++v.begin() == v.end() );\n+}\n+\n+int main()\n+{\n+ test01();\n+}\ndiff --git a/libstdc++-v3/testsuite/23_containers/multiset/allocator/ext_ptr.cc b/libstdc++-v3/testsuite/23_containers/multiset/allocator/ext_ptr.cc\nnew file mode 100644\nindex 000000000000..589e6b0a617e\n--- /dev/null\n+++ b/libstdc++-v3/testsuite/23_containers/multiset/allocator/ext_ptr.cc\n@@ -0,0 +1,32 @@\n+// { dg-do run { target c++11 } }\n+\n+#include <set>\n+#include <memory>\n+#include <testsuite_hooks.h>\n+#include <testsuite_allocator.h>\n+\n+struct T { int i; };\n+\n+bool operator<(const T& l, const T& r)\n+{ return l.i < r.i; }\n+\n+struct L : std::less<T>\n+{ };\n+\n+using __gnu_test::CustomPointerAlloc;\n+\n+template class std::multiset<T, L, CustomPointerAlloc<T>>;\n+\n+void test01()\n+{\n+ typedef CustomPointerAlloc<T> alloc_type;\n+ typedef std::multiset<T, L, alloc_type> test_type;\n+ test_type v;\n+ v.insert(T());\n+ VERIFY( ++v.begin() == v.end() );\n+}\n+\n+int main()\n+{\n+ test01();\n+}\ndiff --git a/libstdc++-v3/testsuite/23_containers/set/allocator/ext_ptr.cc b/libstdc++-v3/testsuite/23_containers/set/allocator/ext_ptr.cc\nnew file mode 100644\nindex 000000000000..bbcf32b20be3\n--- /dev/null\n+++ b/libstdc++-v3/testsuite/23_containers/set/allocator/ext_ptr.cc\n@@ -0,0 +1,32 @@\n+// { dg-do run { target c++11 } }\n+\n+#include <set>\n+#include <memory>\n+#include <testsuite_hooks.h>\n+#include <testsuite_allocator.h>\n+\n+struct T { int i; };\n+\n+bool operator<(const T& l, const T& r)\n+{ return l.i < r.i; }\n+\n+struct L : std::less<T>\n+{ };\n+\n+using __gnu_test::CustomPointerAlloc;\n+\n+template class std::set<T, L, CustomPointerAlloc<T>>;\n+\n+void test01()\n+{\n+ typedef CustomPointerAlloc<T> alloc_type;\n+ typedef std::set<T, L, alloc_type> test_type;\n+ test_type v;\n+ v.insert(T());\n+ VERIFY( ++v.begin() == v.end() );\n+}\n+\n+int main()\n+{\n+ test01();\n+}\ndiff --git a/libstdc++-v3/testsuite/23_containers/set/requirements/explicit_instantiation/alloc_ptr.cc b/libstdc++-v3/testsuite/23_containers/set/requirements/explicit_instantiation/alloc_ptr.cc\nnew file mode 100644\nindex 000000000000..60b583a9b2be\n--- /dev/null\n+++ b/libstdc++-v3/testsuite/23_containers/set/requirements/explicit_instantiation/alloc_ptr.cc\n@@ -0,0 +1,86 @@\n+// { dg-do compile { target c++11 } }\n+\n+#include <set>\n+#include <testsuite_allocator.h>\n+\n+// An allocator that uses __gnu_cxx::_Pointer_adapter as its pointer type.\n+template class std::set<int, std::less<int>,\n+\t\t\t__gnu_test::CustomPointerAlloc<int>>;\n+\n+// Unlike __gnu_cxx::_Pointer_adapter, this fancy pointer supports neither\n+// implicit nor explicit conversions from raw pointers. The constructor from\n+// a raw pointer is explicit and requires a second parameter. The only way for\n+// containers to construct one of these pointers is pointer_traits::pointer_to.\n+template<typename T>\n+struct Pointer : __gnu_test::PointerBase<Pointer<T>, T>\n+{\n+ using Base = __gnu_test::PointerBase<Pointer<T>, T>;\n+\n+ Pointer() = default;\n+ Pointer(std::nullptr_t) : Base() { }\n+ explicit Pointer(T* p, int) : Base(p) { }\n+\n+ // Allow conversions to const_pointer and to void_pointer\n+ template<typename U, typename = typename std::enable_if<\n+ (!std::is_const<U>::value && std::is_same<T, const U>::value)\n+ || (std::is_void<T>::value && std::is_convertible<U*, T*>::value)\n+ >::type>\n+ Pointer(const Pointer<U>& p) : Base(p.operator->()) { }\n+\n+ template<typename U>\n+ static typename std::enable_if<std::is_same<U, T>::value, Pointer>::type\n+ pointer_to(U& t)\n+ { return Pointer(std::addressof(t), 1); }\n+};\n+\n+// A minimal allocator that uses Pointer as its pointer type.\n+template<typename T>\n+struct Allocator\n+{\n+ using value_type = T;\n+ using pointer = Pointer<T>;\n+\n+ Allocator() = default;\n+ template<typename U>\n+ Allocator(const Allocator<U>&) { }\n+\n+ pointer allocate(std::size_t n)\n+ { return pointer(std::allocator<T>().allocate(n), 1); }\n+\n+ void deallocate(pointer p, std::size_t n)\n+ {\n+ std::allocator<T>().deallocate(p.operator->(), n);\n+ }\n+\n+ bool operator==(const Allocator&) const { return true; }\n+ bool operator!=(const Allocator&) const { return false; }\n+};\n+\n+template class std::set<int, std::less<int>, Allocator<int>>;\n+\n+#include <testsuite_iterators.h>\n+\n+void\n+test_template_members(__gnu_test::input_container<short>& c)\n+{\n+ // Use member functions that are not included in explicit instantiations.\n+ std::set<int, std::less<int>, Allocator<int>> s(c.begin(), c.end());\n+ s.emplace(1);\n+ s.emplace_hint(s.begin(), 1);\n+ s.insert(c.begin(), c.end());\n+\n+ std::set<int, std::greater<int>, Allocator<int>> s1;\n+ s.merge(s1);\n+ std::multiset<int, std::greater<int>, Allocator<int>> m1;\n+ s.merge(m1);\n+\n+#ifdef __glibcxx_ranges_to_container\n+ short arr[2];\n+ __gnu_test::test_input_range<short> r(arr);\n+ std::set<int, std::less<int>, Allocator<int>> s2(std::from_range, r);\n+ s2.assign_range(r);\n+ s2.prepend_range(r);\n+ s2.append_range(r);\n+ s2.insert_range(s2.begin(), r);\n+#endif\n+}\ndiff --git a/libstdc++-v3/testsuite/23_containers/set/requirements/explicit_instantiation/alloc_ptr_ignored.cc b/libstdc++-v3/testsuite/23_containers/set/requirements/explicit_instantiation/alloc_ptr_ignored.cc\nnew file mode 100644\nindex 000000000000..fa06cf8f3a2f\n--- /dev/null\n+++ b/libstdc++-v3/testsuite/23_containers/set/requirements/explicit_instantiation/alloc_ptr_ignored.cc\n@@ -0,0 +1,4 @@\n+// { dg-options \"-D_GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE=0\" }\n+// { dg-do compile { target c++11 } }\n+\n+#include \"alloc_ptr.cc\"\n", "prefixes": [ "v1", "1/1" ] }