From 2dbe56bdfbf6c570cf23073f0c596da6bd1531c8 Mon Sep 17 00:00:00 2001 From: Jonathan Wakely Date: Thu, 22 Sep 2016 14:58:49 +0100 Subject: [PATCH] Implement C++17 node extraction and insertion (P0083R5) * doc/xml/manual/status_cxx2017.xml: Document status. * doc/html/*: Regenerate. * include/Makefile.am: Add bits/node_handle.h and reorder. * include/Makefile.in: Regenerate. * include/bits/hashtable.h (_Hashtable::node_type) (_Hashtable::insert_return_type, _Hashtable::_M_reinsert_node) (_Hashtable::_M_reinsert_node_multi, _Hashtable::extract) (_Hashtable::_M_merge_unique, _Hashtable::_M_merge_multi): Define. (_Hash_merge_helper): Define primary template. * include/bits/node_handle.h: New header. * include/bits/stl_map.h (map): Declare _Rb_tree_merge_helper as friend. (map::node_type, map::insert_return_type, map::extract, map::merge) (map::insert(node_type&&), map::insert(const_iterator, node_type&&)): Define new members. (_Rb_tree_merge_helper): Specialize for map. * include/bits/stl_multimap.h (multimap): Declare _Rb_tree_merge_helper as friend. (multimap::node_type, multimap::extract, multimap::merge) (multimap::insert(node_type&&)) (multimap::insert(const_iterator, node_type&&)): Define. (_Rb_tree_merge_helper): Specialize for multimap. * include/bits/stl_multiset.h (multiset): Declare _Rb_tree_merge_helper as friend. (multiset::node_type, multiset::extract, multiset::merge) (multiset::insert(node_type&&)) (multiset::insert(const_iterator, node_type&&)): Define. * include/bits/stl_set.h (set): Declare _Rb_tree_merge_helper as friend. (set::node_type, set::insert_return_type, set::extract, set::merge) (set::insert(node_type&&), set::insert(const_iterator, node_type&&)): Define. (_Rb_tree_merge_helper): Specialize for set. * include/bits/stl_tree.h (_Rb_tree): Declare _Rb_tree<> as friend. (_Rb_tree::node_type, _Rb_tree::insert_return_type) (_Rb_tree::_M_reinsert_node_unique, _Rb_tree::_M_reinsert_node_equal) (_Rb_tree::_M_reinsert_node_hint_unique) (_Rb_tree::_M_reinsert_node_hint_equal, _Rb_tree::extract) (_Rb_tree::_M_merge_unique, _Rb_tree::_M_merge_equal): Define. (_Rb_tree_merge_helper): Specialize for multiset. * include/bits/unordered_map.h (unordered_map): Declare unordered_map<> and unordered_multimap<> as friends. (unordered_map::node_type, unordered_map::insert_return_type) (unordered_map::extract, unordered_map::merge) (unordered_map::insert(node_type&&)) (unordered_map::insert(const_iterator, node_type&&)) (unordered_multimap): Declare _Hash_merge_helper as friend. (unordered_multimap::node_type, unordered_multimap::extract) (unordered_multimap::merge, unordered_multimap::insert(node_type&&)) (unordered_multimap::insert(const_iterator, node_type&&)): Define. (_Hash_merge_helper): Specialize for unordered maps and multimaps. * include/bits/unordered_set.h (unordered_set, unordered_multiset): Declare _Hash_merge_helper as friend. (unordered_set::node_type, unordered_set::insert_return_type) (unordered_set::extract, unordered_set::merge) (unordered_set::insert(node_type&&)) (unordered_set::insert(const_iterator, node_type&&)): Define. (unordered_multiset::node_type, unordered_multiset::extract) (unordered_multiset::merge, unordered_multiset::insert(node_type&&)) (unordered_multiset::insert(const_iterator, node_type&&)): Define. (_Hash_merge_helper): Specialize for unordered sets and multisets. * include/debug/map.h (map): Add using declarations or forwarding functions for new members. * include/debug/map.h (multimap): Likewise. * include/debug/map.h (multiset): Likewise. * include/debug/map.h (set): Likewise. * include/debug/unordered_map (unordered_map, unordered_multimap): Likewise. * include/debug/unordered_set( unordered_set, unordered_multiset): Likewise. * python/libstdcxx/v6/printers.py (get_value_from_aligned_membuf): New helper function. (get_value_from_list_node, get_value_from_Rb_tree_node): Use helper. (StdNodeHandlePrinter): Define printer for node handles. (build_libstdcxx_dictionary): Register StdNodeHandlePrinter. * testsuite/23_containers/map/modifiers/extract.cc: New. * testsuite/23_containers/map/modifiers/merge.cc: New. * testsuite/23_containers/multimap/modifiers/extract.cc: New. * testsuite/23_containers/multimap/modifiers/merge.cc: New. * testsuite/23_containers/multiset/modifiers/extract.cc: New. * testsuite/23_containers/multiset/modifiers/merge.cc: New. * testsuite/23_containers/set/modifiers/extract.cc: New. * testsuite/23_containers/set/modifiers/merge.cc: New. * testsuite/23_containers/unordered_map/modifiers/extract.cc: New. * testsuite/23_containers/unordered_map/modifiers/merge.cc: New. * testsuite/23_containers/unordered_multimap/modifiers/extract.cc: New. * testsuite/23_containers/unordered_multimap/modifiers/merge.cc: New. * testsuite/23_containers/unordered_multiset/modifiers/extract.cc: New. * testsuite/23_containers/unordered_multiset/modifiers/merge.cc: New. * testsuite/23_containers/unordered_set/modifiers/extract.cc: New. * testsuite/23_containers/unordered_set/modifiers/merge.cc: New. * testsuite/23_containers/unordered_set/instantiation_neg.cc: Adjust dg-error lineno. * testsuite/libstdc++-prettyprinters/cxx17.cc: Test node handles. From-SVN: r240363 --- libstdc++-v3/ChangeLog | 100 ++++++ .../doc/html/manual/profile_mode_devel.html | 2 +- libstdc++-v3/doc/html/manual/status.html | 4 +- .../doc/xml/manual/status_cxx2017.xml | 3 +- libstdc++-v3/include/Makefile.am | 3 +- libstdc++-v3/include/Makefile.in | 3 +- libstdc++-v3/include/bits/hashtable.h | 141 ++++++++ libstdc++-v3/include/bits/node_handle.h | 330 ++++++++++++++++++ libstdc++-v3/include/bits/stl_map.h | 83 +++++ libstdc++-v3/include/bits/stl_multimap.h | 82 +++++ libstdc++-v3/include/bits/stl_multiset.h | 81 +++++ libstdc++-v3/include/bits/stl_set.h | 81 +++++ libstdc++-v3/include/bits/stl_tree.h | 197 ++++++++++- libstdc++-v3/include/bits/unordered_map.h | 178 +++++++++- libstdc++-v3/include/bits/unordered_set.h | 172 +++++++++ libstdc++-v3/include/debug/map.h | 46 ++- libstdc++-v3/include/debug/multimap.h | 34 ++ libstdc++-v3/include/debug/multiset.h | 34 ++ libstdc++-v3/include/debug/set.h | 45 +++ libstdc++-v3/include/debug/unordered_map | 94 ++++- libstdc++-v3/include/debug/unordered_set | 93 +++++ libstdc++-v3/python/libstdcxx/v6/printers.py | 58 ++- .../23_containers/map/modifiers/extract.cc | 147 ++++++++ .../23_containers/map/modifiers/merge.cc | 147 ++++++++ .../multimap/modifiers/extract.cc | 141 ++++++++ .../23_containers/multimap/modifiers/merge.cc | 119 +++++++ .../multiset/modifiers/extract.cc | 129 +++++++ .../23_containers/multiset/modifiers/merge.cc | 117 +++++++ .../23_containers/set/modifiers/extract.cc | 138 ++++++++ .../23_containers/set/modifiers/merge.cc | 143 ++++++++ .../unordered_map/modifiers/extract.cc | 148 ++++++++ .../unordered_map/modifiers/merge.cc | 140 ++++++++ .../unordered_multimap/modifiers/extract.cc | 138 ++++++++ .../unordered_multimap/modifiers/merge.cc | 123 +++++++ .../unordered_multiset/modifiers/extract.cc | 128 +++++++ .../unordered_multiset/modifiers/merge.cc | 121 +++++++ .../unordered_set/instantiation_neg.cc | 2 +- .../unordered_set/modifiers/extract.cc | 140 ++++++++ .../unordered_set/modifiers/merge.cc | 140 ++++++++ .../libstdc++-prettyprinters/cxx17.cc | 16 +- 40 files changed, 4019 insertions(+), 22 deletions(-) create mode 100644 libstdc++-v3/include/bits/node_handle.h create mode 100644 libstdc++-v3/testsuite/23_containers/map/modifiers/extract.cc create mode 100644 libstdc++-v3/testsuite/23_containers/map/modifiers/merge.cc create mode 100644 libstdc++-v3/testsuite/23_containers/multimap/modifiers/extract.cc create mode 100644 libstdc++-v3/testsuite/23_containers/multimap/modifiers/merge.cc create mode 100644 libstdc++-v3/testsuite/23_containers/multiset/modifiers/extract.cc create mode 100644 libstdc++-v3/testsuite/23_containers/multiset/modifiers/merge.cc create mode 100644 libstdc++-v3/testsuite/23_containers/set/modifiers/extract.cc create mode 100644 libstdc++-v3/testsuite/23_containers/set/modifiers/merge.cc create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/extract.cc create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/merge.cc create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/extract.cc create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/merge.cc create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/extract.cc create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/merge.cc create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/extract.cc create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/merge.cc diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 16a49549af4..9376bfbdf2f 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,103 @@ +2016-09-22 Jonathan Wakely + + Implement C++17 node extraction and insertion (P0083R5) + * doc/xml/manual/status_cxx2017.xml: Document status. + * doc/html/*: Regenerate. + * include/Makefile.am: Add bits/node_handle.h and reorder. + * include/Makefile.in: Regenerate. + * include/bits/hashtable.h (_Hashtable::node_type) + (_Hashtable::insert_return_type, _Hashtable::_M_reinsert_node) + (_Hashtable::_M_reinsert_node_multi, _Hashtable::extract) + (_Hashtable::_M_merge_unique, _Hashtable::_M_merge_multi): Define. + (_Hash_merge_helper): Define primary template. + * include/bits/node_handle.h: New header. + * include/bits/stl_map.h (map): Declare _Rb_tree_merge_helper as + friend. + (map::node_type, map::insert_return_type, map::extract, map::merge) + (map::insert(node_type&&), map::insert(const_iterator, node_type&&)): + Define new members. + (_Rb_tree_merge_helper): Specialize for map. + * include/bits/stl_multimap.h (multimap): Declare _Rb_tree_merge_helper + as friend. + (multimap::node_type, multimap::extract, multimap::merge) + (multimap::insert(node_type&&)) + (multimap::insert(const_iterator, node_type&&)): Define. + (_Rb_tree_merge_helper): Specialize for multimap. + * include/bits/stl_multiset.h (multiset): Declare _Rb_tree_merge_helper + as friend. + (multiset::node_type, multiset::extract, multiset::merge) + (multiset::insert(node_type&&)) + (multiset::insert(const_iterator, node_type&&)): Define. + * include/bits/stl_set.h (set): Declare _Rb_tree_merge_helper as + friend. + (set::node_type, set::insert_return_type, set::extract, set::merge) + (set::insert(node_type&&), set::insert(const_iterator, node_type&&)): + Define. + (_Rb_tree_merge_helper): Specialize for set. + * include/bits/stl_tree.h (_Rb_tree): Declare _Rb_tree<> as friend. + (_Rb_tree::node_type, _Rb_tree::insert_return_type) + (_Rb_tree::_M_reinsert_node_unique, _Rb_tree::_M_reinsert_node_equal) + (_Rb_tree::_M_reinsert_node_hint_unique) + (_Rb_tree::_M_reinsert_node_hint_equal, _Rb_tree::extract) + (_Rb_tree::_M_merge_unique, _Rb_tree::_M_merge_equal): Define. + (_Rb_tree_merge_helper): Specialize for multiset. + * include/bits/unordered_map.h (unordered_map): Declare + unordered_map<> and unordered_multimap<> as friends. + (unordered_map::node_type, unordered_map::insert_return_type) + (unordered_map::extract, unordered_map::merge) + (unordered_map::insert(node_type&&)) + (unordered_map::insert(const_iterator, node_type&&)) + (unordered_multimap): Declare _Hash_merge_helper as friend. + (unordered_multimap::node_type, unordered_multimap::extract) + (unordered_multimap::merge, unordered_multimap::insert(node_type&&)) + (unordered_multimap::insert(const_iterator, node_type&&)): Define. + (_Hash_merge_helper): Specialize for unordered maps and multimaps. + * include/bits/unordered_set.h (unordered_set, unordered_multiset): + Declare _Hash_merge_helper as friend. + (unordered_set::node_type, unordered_set::insert_return_type) + (unordered_set::extract, unordered_set::merge) + (unordered_set::insert(node_type&&)) + (unordered_set::insert(const_iterator, node_type&&)): Define. + (unordered_multiset::node_type, unordered_multiset::extract) + (unordered_multiset::merge, unordered_multiset::insert(node_type&&)) + (unordered_multiset::insert(const_iterator, node_type&&)): Define. + (_Hash_merge_helper): Specialize for unordered sets and multisets. + * include/debug/map.h (map): Add using declarations or forwarding + functions for new members. + * include/debug/map.h (multimap): Likewise. + * include/debug/map.h (multiset): Likewise. + * include/debug/map.h (set): Likewise. + * include/debug/unordered_map (unordered_map, unordered_multimap): + Likewise. + * include/debug/unordered_set( unordered_set, unordered_multiset): + Likewise. + * python/libstdcxx/v6/printers.py (get_value_from_aligned_membuf): New + helper function. + (get_value_from_list_node, get_value_from_Rb_tree_node): Use helper. + (StdNodeHandlePrinter): Define printer for node handles. + (build_libstdcxx_dictionary): Register StdNodeHandlePrinter. + * testsuite/23_containers/map/modifiers/extract.cc: New. + * testsuite/23_containers/map/modifiers/merge.cc: New. + * testsuite/23_containers/multimap/modifiers/extract.cc: New. + * testsuite/23_containers/multimap/modifiers/merge.cc: New. + * testsuite/23_containers/multiset/modifiers/extract.cc: New. + * testsuite/23_containers/multiset/modifiers/merge.cc: New. + * testsuite/23_containers/set/modifiers/extract.cc: New. + * testsuite/23_containers/set/modifiers/merge.cc: New. + * testsuite/23_containers/unordered_map/modifiers/extract.cc: New. + * testsuite/23_containers/unordered_map/modifiers/merge.cc: New. + * testsuite/23_containers/unordered_multimap/modifiers/extract.cc: + New. + * testsuite/23_containers/unordered_multimap/modifiers/merge.cc: New. + * testsuite/23_containers/unordered_multiset/modifiers/extract.cc: + New. + * testsuite/23_containers/unordered_multiset/modifiers/merge.cc: New. + * testsuite/23_containers/unordered_set/modifiers/extract.cc: New. + * testsuite/23_containers/unordered_set/modifiers/merge.cc: New. + * testsuite/23_containers/unordered_set/instantiation_neg.cc: Adjust + dg-error lineno. + * testsuite/libstdc++-prettyprinters/cxx17.cc: Test node handles. + 2016-09-22 Ville Voutilainen Fix tests on old arm platforms for optional. diff --git a/libstdc++-v3/doc/html/manual/profile_mode_devel.html b/libstdc++-v3/doc/html/manual/profile_mode_devel.html index 2521dd66811..db96f989b24 100644 --- a/libstdc++-v3/doc/html/manual/profile_mode_devel.html +++ b/libstdc++-v3/doc/html/manual/profile_mode_devel.html @@ -64,4 +64,4 @@ include/profile/impl/profiler_trace.h. Use __trace_vector_to_list as an example.

Add documentation in file doc/xml/manual/profile_mode.xml. -

Prev Up Next
Implementation Issues Home Diagnostics
+

Prev Up Next
Implementation Issues Home Diagnostics
\ No newline at end of file diff --git a/libstdc++-v3/doc/html/manual/status.html b/libstdc++-v3/doc/html/manual/status.html index e82739aa1ce..3c589791b50 100644 --- a/libstdc++-v3/doc/html/manual/status.html +++ b/libstdc++-v3/doc/html/manual/status.html @@ -666,11 +666,11 @@ Feature-testing recommendations for C++. 6.1 __cpp_lib_map_try_emplace >= 201411, __cpp_lib_unordered_map_try_emplace >= 201411 - Splicing Maps and Sets + Splicing Maps and Sets P0083R3 - No __cpp_lib_node_extract >= 201606 Non-member size() and more + 7 __cpp_lib_node_extract >= 201606 Non-member size() and more N4280 diff --git a/libstdc++-v3/doc/xml/manual/status_cxx2017.xml b/libstdc++-v3/doc/xml/manual/status_cxx2017.xml index ff966272311..76eaaa0fa22 100644 --- a/libstdc++-v3/doc/xml/manual/status_cxx2017.xml +++ b/libstdc++-v3/doc/xml/manual/status_cxx2017.xml @@ -562,14 +562,13 @@ Feature-testing recommendations for C++. - Splicing Maps and Sets P0083R3 - No + 7 __cpp_lib_node_extract >= 201606 diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am index 9cd18dfa3b9..778225899c3 100644 --- a/libstdc++-v3/include/Makefile.am +++ b/libstdc++-v3/include/Makefile.am @@ -129,7 +129,7 @@ bits_headers = \ ${bits_srcdir}/specfun.h \ ${bits_srcdir}/memoryfwd.h \ ${bits_srcdir}/move.h \ - ${bits_srcdir}/std_mutex.h \ + ${bits_srcdir}/node_handle.h \ ${bits_srcdir}/ostream.tcc \ ${bits_srcdir}/ostream_insert.h \ ${bits_srcdir}/parse_numbers.h \ @@ -159,6 +159,7 @@ bits_headers = \ ${bits_srcdir}/shared_ptr_base.h \ ${bits_srcdir}/slice_array.h \ ${bits_srcdir}/sstream.tcc \ + ${bits_srcdir}/std_mutex.h \ ${bits_srcdir}/stl_algo.h \ ${bits_srcdir}/stl_algobase.h \ ${bits_srcdir}/stl_bvector.h \ diff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefile.in index d799860d095..502a89e1fb0 100644 --- a/libstdc++-v3/include/Makefile.in +++ b/libstdc++-v3/include/Makefile.in @@ -419,7 +419,7 @@ bits_headers = \ ${bits_srcdir}/specfun.h \ ${bits_srcdir}/memoryfwd.h \ ${bits_srcdir}/move.h \ - ${bits_srcdir}/std_mutex.h \ + ${bits_srcdir}/node_handle.h \ ${bits_srcdir}/ostream.tcc \ ${bits_srcdir}/ostream_insert.h \ ${bits_srcdir}/parse_numbers.h \ @@ -449,6 +449,7 @@ bits_headers = \ ${bits_srcdir}/shared_ptr_base.h \ ${bits_srcdir}/slice_array.h \ ${bits_srcdir}/sstream.tcc \ + ${bits_srcdir}/std_mutex.h \ ${bits_srcdir}/stl_algo.h \ ${bits_srcdir}/stl_algobase.h \ ${bits_srcdir}/stl_bvector.h \ diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 6d7134a8a30..be67741ab5a 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -33,6 +33,9 @@ #pragma GCC system_header #include +#if __cplusplus > 201402L +# include +#endif namespace std _GLIBCXX_VISIBILITY(default) { @@ -308,6 +311,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION using const_local_iterator = typename __hashtable_base:: const_local_iterator; +#if __cplusplus > 201402L + using node_type = _Node_handle<_Key, _Value, __node_alloc_type>; + using insert_return_type = _Node_insert_return; +#endif + private: __bucket_type* _M_buckets = &_M_single_bucket; size_type _M_bucket_count = 1; @@ -762,6 +770,135 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // DR 1189. // reserve, if present, comes from _Rehash_base. +#if __cplusplus > 201402L + /// Re-insert an extracted node into a container with unique keys. + insert_return_type + _M_reinsert_node(node_type&& __nh) + { + insert_return_type __ret; + if (__nh.empty()) + __ret.position = end(); + else + { + __glibcxx_assert(get_allocator() == __nh.get_allocator()); + + const key_type& __k = __nh._M_key(); + __hash_code __code = this->_M_hash_code(__k); + size_type __bkt = _M_bucket_index(__k, __code); + if (__node_type* __n = _M_find_node(__bkt, __k, __code)) + { + __ret.node = std::move(__nh); + __ret.position = iterator(__n); + __ret.inserted = false; + } + else + { + __ret.position + = _M_insert_unique_node(__bkt, __code, __nh._M_ptr); + __nh._M_ptr = nullptr; + __ret.inserted = true; + } + } + return __ret; + } + + /// Re-insert an extracted node into a container with equivalent keys. + iterator + _M_reinsert_node_multi(const_iterator __hint, node_type&& __nh) + { + iterator __ret; + if (__nh.empty()) + __ret = end(); + else + { + __glibcxx_assert(get_allocator() == __nh.get_allocator()); + + auto __code = this->_M_hash_code(__nh._M_key()); + auto __node = std::exchange(__nh._M_ptr, nullptr); + // FIXME: this deallocates the node on exception. + __ret = _M_insert_multi_node(__hint._M_cur, __code, __node); + } + return __ret; + } + + /// Extract a node. + node_type + extract(const_iterator __pos) + { + __node_type* __n = __pos._M_cur; + size_t __bkt = _M_bucket_index(__n); + + // Look for previous node to unlink it from the erased one, this + // is why we need buckets to contain the before begin to make + // this search fast. + __node_base* __prev_n = _M_get_previous_node(__bkt, __n); + + if (__prev_n == _M_buckets[__bkt]) + _M_remove_bucket_begin(__bkt, __n->_M_next(), + __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0); + else if (__n->_M_nxt) + { + size_type __next_bkt = _M_bucket_index(__n->_M_next()); + if (__next_bkt != __bkt) + _M_buckets[__next_bkt] = __prev_n; + } + + __prev_n->_M_nxt = __n->_M_nxt; + __n->_M_nxt = nullptr; + --_M_element_count; + return { __n, this->_M_node_allocator() }; + } + + /// Extract a node. + node_type + extract(const _Key& __k) + { + node_type __nh; + auto __pos = find(__k); + if (__pos != end()) + __nh = extract(const_iterator(__pos)); + return __nh; + } + + /// Merge from a compatible container into one with unique keys. + template + void + _M_merge_unique(_Compatible_Hashtable& __src) noexcept + { + static_assert(is_same_v, "Node types are compatible"); + __glibcxx_assert(get_allocator() == __src.get_allocator()); + + for (auto __i = __src.begin(), __end = __src.end(); __i != __end;) + { + auto __pos = __i++; + const key_type& __k = this->_M_extract()(__pos._M_cur->_M_v()); + __hash_code __code = this->_M_hash_code(__k); + size_type __bkt = _M_bucket_index(__k, __code); + if (_M_find_node(__bkt, __k, __code) == nullptr) + { + auto __nh = __src.extract(__pos); + _M_insert_unique_node(__bkt, __code, __nh._M_ptr); + __nh._M_ptr = nullptr; + } + } + } + + /// Merge from a compatible container into one with equivalent keys. + template + void + _M_merge_multi(_Compatible_Hashtable& __src) noexcept + { + static_assert(is_same_v, "Node types are compatible"); + __glibcxx_assert(get_allocator() == __src.get_allocator()); + + this->reserve(size() + __src.size()); + for (auto __i = __src.begin(), __end = __src.end(); __i != __end;) + _M_reinsert_node_multi(cend(), __src.extract(__i++)); + } +#endif // C++17 + private: // Helper rehash method used when keys are unique. void _M_rehash_aux(size_type __n, std::true_type); @@ -2078,6 +2215,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_buckets = __new_buckets; } +#if __cplusplus > 201402L + template class _Hash_merge_helper { }; +#endif // C++17 + _GLIBCXX_END_NAMESPACE_VERSION } // namespace std diff --git a/libstdc++-v3/include/bits/node_handle.h b/libstdc++-v3/include/bits/node_handle.h new file mode 100644 index 00000000000..60c28838820 --- /dev/null +++ b/libstdc++-v3/include/bits/node_handle.h @@ -0,0 +1,330 @@ +// Node handles for containers -*- C++ -*- + +// Copyright (C) 2016 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// . + +/** @file bits/node_handle.h + * This is an internal header file, included by other library headers. + * Do not attempt to use it directly. + * @headername{map,set,unordered_map,unordered_set} + */ + +#ifndef _NODE_HANDLE +#define _NODE_HANDLE 1 + +#pragma GCC system_header + +#if __cplusplus > 201402L +# define __cpp_lib_node_extract 201606 + +#include +#include +#include +#include + +namespace std _GLIBCXX_VISIBILITY(default) +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION + + /// Base class for node handle types of maps and sets. + template + class _Node_handle_common + { + using _AllocTraits = allocator_traits<_NodeAlloc>; + + public: + using allocator_type = __alloc_rebind<_NodeAlloc, _Val>; + + allocator_type + get_allocator() const noexcept + { + __glibcxx_assert(!this->empty()); + return allocator_type(*_M_alloc); + } + + explicit operator bool() const noexcept { return _M_ptr != nullptr; } + + bool empty() const noexcept { return _M_ptr == nullptr; } + + protected: + constexpr _Node_handle_common() noexcept : _M_ptr(), _M_alloc() {} + + ~_Node_handle_common() { _M_destroy(); } + + _Node_handle_common(_Node_handle_common&& __nh) noexcept + : _M_ptr(__nh._M_ptr), _M_alloc(std::move(__nh._M_alloc)) + { + __nh._M_ptr = nullptr; + __nh._M_alloc = nullopt; + } + + _Node_handle_common& + operator=(_Node_handle_common&& __nh) noexcept + { + _M_destroy(); + _M_ptr = __nh._M_ptr; + if constexpr (is_move_assignable_v<_NodeAlloc>) + { + if (_AllocTraits::propagate_on_container_move_assignment::value + || !this->_M_alloc) + this->_M_alloc = std::move(__nh._M_alloc); + else + __glibcxx_assert(this->_M_alloc == __nh._M_alloc); + } + else + __glibcxx_assert(_M_alloc); + __nh._M_ptr = nullptr; + __nh._M_alloc = nullopt; + return *this; + } + + _Node_handle_common(typename _AllocTraits::pointer __ptr, + const _NodeAlloc& __alloc) + : _M_ptr(__ptr), _M_alloc(__alloc) { } + + void + _M_swap(_Node_handle_common& __nh) noexcept + { + using std::swap; + swap(_M_ptr, __nh._M_ptr); + if (_AllocTraits::propagate_on_container_swap + || !_M_alloc || !__nh._M_alloc) + _M_alloc.swap(__nh._M_alloc); + else + __glibcxx_assert(_M_alloc == __nh._M_alloc); + } + + private: + void + _M_destroy() noexcept + { + if (_M_ptr != nullptr) + { + allocator_type __alloc(*_M_alloc); + allocator_traits::destroy(__alloc, + _M_ptr->_M_valptr()); + _AllocTraits::deallocate(*_M_alloc, _M_ptr, 1); + } + } + + protected: + typename _AllocTraits::pointer _M_ptr; + private: + optional<_NodeAlloc> _M_alloc; + + template + friend class _Rb_tree; + }; + + /// Node handle type for maps. + template + class _Node_handle : public _Node_handle_common<_Value, _NodeAlloc> + { + public: + constexpr _Node_handle() noexcept = default; + ~_Node_handle() = default; + _Node_handle(_Node_handle&&) noexcept = default; + + _Node_handle& + operator=(_Node_handle&&) noexcept = default; + + using key_type = _Key; + using mapped_type = typename _Value::second_type; + + key_type& + key() const noexcept + { + __glibcxx_assert(!this->empty()); + return *_M_pkey; + } + + mapped_type& + mapped() const noexcept + { + __glibcxx_assert(!this->empty()); + return *_M_pmapped; + } + + void + swap(_Node_handle& __nh) noexcept + { + this->_M_swap(__nh); + using std::swap; + swap(_M_pkey, __nh._M_pkey); + swap(_M_pmapped, __nh._M_pmapped); + } + + friend void + swap(_Node_handle& __x, _Node_handle& __y) + noexcept(noexcept(__x.swap(__y))) + { __x.swap(__y); } + + private: + using _AllocTraits = allocator_traits<_NodeAlloc>; + + using _PtrTraits = pointer_traits; + + _Node_handle(typename _AllocTraits::pointer __ptr, + const _NodeAlloc& __alloc) + : _Node_handle_common<_Value, _NodeAlloc>(__ptr, __alloc) + { + if (__ptr) + { + auto& __key = const_cast<_Key&>(__ptr->_M_valptr()->first); + _M_pkey = _S_pointer_to(__key); + _M_pmapped = _S_pointer_to(__ptr->_M_valptr()->second); + } + else + { + _M_pkey = nullptr; + _M_pmapped = nullptr; + } + } + + template + using __pointer = __ptr_rebind; + + __pointer<_Key> _M_pkey = nullptr; + __pointer _M_pmapped = nullptr; + + template + __pointer<_Tp> + _S_pointer_to(_Tp& __obj) + { return pointer_traits<__pointer<_Tp>>::pointer_to(__obj); } + + const key_type& + _M_key() const noexcept { return key(); } + + template + friend class _Rb_tree; + + template + friend class _Hashtable; + }; + + /// Node handle type for sets. + template + class _Node_handle<_Value, _Value, _NodeAlloc> + : public _Node_handle_common<_Value, _NodeAlloc> + { + public: + constexpr _Node_handle() noexcept = default; + ~_Node_handle() = default; + _Node_handle(_Node_handle&&) noexcept = default; + + _Node_handle& + operator=(_Node_handle&&) noexcept = default; + + using value_type = _Value; + + value_type& + value() const noexcept + { + __glibcxx_assert(!this->empty()); + return *this->_M_ptr->_M_valptr(); + } + + void + swap(_Node_handle& __nh) noexcept + { this->_M_swap(__nh); } + + friend void + swap(_Node_handle& __x, _Node_handle& __y) + noexcept(noexcept(__x.swap(__y))) + { __x.swap(__y); } + + private: + using _AllocTraits = allocator_traits<_NodeAlloc>; + + _Node_handle(typename _AllocTraits::pointer __ptr, + const _NodeAlloc& __alloc) + : _Node_handle_common<_Value, _NodeAlloc>(__ptr, __alloc) { } + + const value_type& + _M_key() const noexcept { return value(); } + + template + friend class _Rb_tree; + + template + friend class _Hashtable; + }; + + /// Return type of insert(node_handle&&) on unique maps/sets. + template + struct _Node_insert_return + { + bool inserted = false; + _Iterator position = _Iterator(); + _NodeHandle node; + + template + decltype(auto) get() & + { return std::get<_Idx>(std::tie(inserted, position, node)); } + + template + decltype(auto) get() const & + { return std::get<_Idx>(std::tie(inserted, position, node)); } + + template + decltype(auto) get() && + { + return std::move(std::get<_Idx>(std::tie(inserted, position, node))); + } + + template + decltype(auto) get() const && + { + return std::move(std::get<_Idx>(std::tie(inserted, position, node))); + } + }; + + template + struct tuple_size<_Node_insert_return<_Iterator, _NodeHandle>> + : integral_constant { }; + + template + struct tuple_element<0, _Node_insert_return<_Iterator, _NodeHandle>> + { using type = bool; }; + + template + struct tuple_element<1, _Node_insert_return<_Iterator, _NodeHandle>> + { using type = _Iterator; }; + + template + struct tuple_element<2, _Node_insert_return<_Iterator, _NodeHandle>> + { using type = _NodeHandle; }; + +_GLIBCXX_END_NAMESPACE_VERSION +} // namespace std + +#endif // C++17 +#endif diff --git a/libstdc++-v3/include/bits/stl_map.h b/libstdc++-v3/include/bits/stl_map.h index 29bade7298b..f9482e29579 100644 --- a/libstdc++-v3/include/bits/stl_map.h +++ b/libstdc++-v3/include/bits/stl_map.h @@ -67,6 +67,9 @@ namespace std _GLIBCXX_VISIBILITY(default) { _GLIBCXX_BEGIN_NAMESPACE_CONTAINER + template + class multimap; + /** * @brief A standard container made up of (key,value) pairs, which can be * retrieved based on a key, in logarithmic time. @@ -153,6 +156,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER typedef typename _Rep_type::reverse_iterator reverse_iterator; typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; +#if __cplusplus > 201402L + using node_type = typename _Rep_type::node_type; + using insert_return_type = typename _Rep_type::insert_return_type; +#endif + // [23.3.1.1] construct/copy/destroy // (get_allocator() is also listed in this section) @@ -593,6 +601,57 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER } #endif +#if __cplusplus > 201402L + /// Extract a node. + node_type + extract(const_iterator __pos) + { return _M_t.extract(__pos); } + + /// Extract a node. + node_type + extract(const key_type& __x) + { return _M_t.extract(__x); } + + /// Re-insert an extracted node. + insert_return_type + insert(node_type&& __nh) + { return _M_t._M_reinsert_node_unique(std::move(__nh)); } + + /// Re-insert an extracted node. + iterator + insert(const_iterator __hint, node_type&& __nh) + { return _M_t._M_reinsert_node_hint_unique(__hint, std::move(__nh)); } + + template + friend class _Rb_tree_merge_helper; + + template + void + merge(map<_Key, _Tp, _C2, _Alloc>& __source) + { + using _Merge_helper = _Rb_tree_merge_helper; + _M_t._M_merge_unique(_Merge_helper::_S_get_tree(__source)); + } + + template + void + merge(map<_Key, _Tp, _C2, _Alloc>&& __source) + { merge(__source); } + + template + void + merge(multimap<_Key, _Tp, _C2, _Alloc>& __source) + { + using _Merge_helper = _Rb_tree_merge_helper; + _M_t._M_merge_unique(_Merge_helper::_S_get_tree(__source)); + } + + template + void + merge(multimap<_Key, _Tp, _C2, _Alloc>&& __source) + { merge(__source); } +#endif // C++17 + #if __cplusplus > 201402L #define __cpp_lib_map_try_emplace 201411 /** @@ -1365,6 +1424,30 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { __x.swap(__y); } _GLIBCXX_END_NAMESPACE_CONTAINER + +#if __cplusplus > 201402L +_GLIBCXX_BEGIN_NAMESPACE_VERSION + // Allow std::map access to internals of compatible maps. + template + struct + _Rb_tree_merge_helper<_GLIBCXX_STD_C::map<_Key, _Val, _Cmp1, _Alloc>, + _Cmp2> + { + private: + friend class _GLIBCXX_STD_C::map<_Key, _Val, _Cmp1, _Alloc>; + + static auto& + _S_get_tree(_GLIBCXX_STD_C::map<_Key, _Val, _Cmp2, _Alloc>& __map) + { return __map._M_t; } + + static auto& + _S_get_tree(_GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp2, _Alloc>& __map) + { return __map._M_t; } + }; +_GLIBCXX_END_NAMESPACE_VERSION +#endif // C++17 + } // namespace std #endif /* _STL_MAP_H */ diff --git a/libstdc++-v3/include/bits/stl_multimap.h b/libstdc++-v3/include/bits/stl_multimap.h index 0bb379fed5f..2b56824b449 100644 --- a/libstdc++-v3/include/bits/stl_multimap.h +++ b/libstdc++-v3/include/bits/stl_multimap.h @@ -65,6 +65,9 @@ namespace std _GLIBCXX_VISIBILITY(default) { _GLIBCXX_BEGIN_NAMESPACE_CONTAINER + template + class map; + /** * @brief A standard container made up of (key,value) pairs, which can be * retrieved based on a key, in logarithmic time. @@ -151,6 +154,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER typedef typename _Rep_type::reverse_iterator reverse_iterator; typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; +#if __cplusplus > 201402L + using node_type = typename _Rep_type::node_type; +#endif + // [23.3.2] construct/copy/destroy // (get_allocator() is also listed in this section) @@ -595,6 +602,57 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { this->insert(__l.begin(), __l.end()); } #endif +#if __cplusplus > 201402L + /// Extract a node. + node_type + extract(const_iterator __pos) + { return _M_t.extract(__pos); } + + /// Extract a node. + node_type + extract(const key_type& __x) + { return _M_t.extract(__x); } + + /// Re-insert an extracted node. + iterator + insert(node_type&& __nh) + { return _M_t._M_reinsert_node_equal(std::move(__nh)); } + + /// Re-insert an extracted node. + iterator + insert(const_iterator __hint, node_type&& __nh) + { return _M_t._M_reinsert_node_hint_equal(__hint, std::move(__nh)); } + + template + friend class _Rb_tree_merge_helper; + + template + void + merge(multimap<_Key, _Tp, _C2, _Alloc>& __source) + { + using _Merge_helper = _Rb_tree_merge_helper; + _M_t._M_merge_equal(_Merge_helper::_S_get_tree(__source)); + } + + template + void + merge(multimap<_Key, _Tp, _C2, _Alloc>&& __source) + { merge(__source); } + + template + void + merge(map<_Key, _Tp, _C2, _Alloc>& __source) + { + using _Merge_helper = _Rb_tree_merge_helper; + _M_t._M_merge_equal(_Merge_helper::_S_get_tree(__source)); + } + + template + void + merge(map<_Key, _Tp, _C2, _Alloc>&& __source) + { merge(__source); } +#endif // C++17 + #if __cplusplus >= 201103L // _GLIBCXX_RESOLVE_LIB_DEFECTS // DR 130. Associative erase should return an iterator. @@ -1030,6 +1088,30 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { __x.swap(__y); } _GLIBCXX_END_NAMESPACE_CONTAINER + +#if __cplusplus > 201402L +_GLIBCXX_BEGIN_NAMESPACE_VERSION + // Allow std::multimap access to internals of compatible maps. + template + struct + _Rb_tree_merge_helper<_GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp1, _Alloc>, + _Cmp2> + { + private: + friend class _GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp1, _Alloc>; + + static auto& + _S_get_tree(_GLIBCXX_STD_C::map<_Key, _Val, _Cmp2, _Alloc>& __map) + { return __map._M_t; } + + static auto& + _S_get_tree(_GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp2, _Alloc>& __map) + { return __map._M_t; } + }; +_GLIBCXX_END_NAMESPACE_VERSION +#endif // C++17 + } // namespace std #endif /* _STL_MULTIMAP_H */ diff --git a/libstdc++-v3/include/bits/stl_multiset.h b/libstdc++-v3/include/bits/stl_multiset.h index 13b253c64c5..d7312dff621 100644 --- a/libstdc++-v3/include/bits/stl_multiset.h +++ b/libstdc++-v3/include/bits/stl_multiset.h @@ -65,6 +65,9 @@ namespace std _GLIBCXX_VISIBILITY(default) { _GLIBCXX_BEGIN_NAMESPACE_CONTAINER + template + class set; + /** * @brief A standard container made up of elements, which can be retrieved * in logarithmic time. @@ -133,6 +136,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER typedef typename _Rep_type::size_type size_type; typedef typename _Rep_type::difference_type difference_type; +#if __cplusplus > 201402L + using node_type = typename _Rep_type::node_type; +#endif + // allocation/deallocation /** * @brief Default constructor creates no elements. @@ -538,6 +545,57 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { this->insert(__l.begin(), __l.end()); } #endif +#if __cplusplus > 201402L + /// Extract a node. + node_type + extract(const_iterator __pos) + { return _M_t.extract(__pos); } + + /// Extract a node. + node_type + extract(const key_type& __x) + { return _M_t.extract(__x); } + + /// Re-insert an extracted node. + iterator + insert(node_type&& __nh) + { return _M_t._M_reinsert_node_equal(std::move(__nh)); } + + /// Re-insert an extracted node. + iterator + insert(const_iterator __hint, node_type&& __nh) + { return _M_t._M_reinsert_node_hint_equal(__hint, std::move(__nh)); } + + template + friend class _Rb_tree_merge_helper; + + template + void + merge(multiset<_Key, _Compare1, _Alloc>& __source) + { + using _Merge_helper = _Rb_tree_merge_helper; + _M_t._M_merge_equal(_Merge_helper::_S_get_tree(__source)); + } + + template + void + merge(multiset<_Key, _Compare1, _Alloc>&& __source) + { merge(__source); } + + template + void + merge(set<_Key, _Compare1, _Alloc>& __source) + { + using _Merge_helper = _Rb_tree_merge_helper; + _M_t._M_merge_equal(_Merge_helper::_S_get_tree(__source)); + } + + template + void + merge(set<_Key, _Compare1, _Alloc>&& __source) + { merge(__source); } +#endif // C++17 + #if __cplusplus >= 201103L // _GLIBCXX_RESOLVE_LIB_DEFECTS // DR 130. Associative erase should return an iterator. @@ -881,6 +939,29 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { __x.swap(__y); } _GLIBCXX_END_NAMESPACE_CONTAINER + +#if __cplusplus > 201402L +_GLIBCXX_BEGIN_NAMESPACE_VERSION + // Allow std::multiset access to internals of compatible sets. + template + struct + _Rb_tree_merge_helper<_GLIBCXX_STD_C::multiset<_Val, _Cmp1, _Alloc>, + _Cmp2> + { + private: + friend class _GLIBCXX_STD_C::multiset<_Val, _Cmp1, _Alloc>; + + static auto& + _S_get_tree(_GLIBCXX_STD_C::set<_Val, _Cmp2, _Alloc>& __set) + { return __set._M_t; } + + static auto& + _S_get_tree(_GLIBCXX_STD_C::multiset<_Val, _Cmp2, _Alloc>& __set) + { return __set._M_t; } + }; +_GLIBCXX_END_NAMESPACE_VERSION +#endif // C++17 + } // namespace std #endif /* _STL_MULTISET_H */ diff --git a/libstdc++-v3/include/bits/stl_set.h b/libstdc++-v3/include/bits/stl_set.h index c104310f121..fd96dd4bb58 100644 --- a/libstdc++-v3/include/bits/stl_set.h +++ b/libstdc++-v3/include/bits/stl_set.h @@ -65,6 +65,9 @@ namespace std _GLIBCXX_VISIBILITY(default) { _GLIBCXX_BEGIN_NAMESPACE_CONTAINER + template + class multiset; + /** * @brief A standard container made up of unique keys, which can be * retrieved in logarithmic time. @@ -135,6 +138,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER typedef typename _Rep_type::difference_type difference_type; //@} +#if __cplusplus > 201402L + using node_type = typename _Rep_type::node_type; + using insert_return_type = typename _Rep_type::insert_return_type; +#endif + // allocation/deallocation /** * @brief Default constructor creates no elements. @@ -553,6 +561,57 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { this->insert(__l.begin(), __l.end()); } #endif +#if __cplusplus > 201402L + /// Extract a node. + node_type + extract(const_iterator __pos) + { return _M_t.extract(__pos); } + + /// Extract a node. + node_type + extract(const key_type& __x) + { return _M_t.extract(__x); } + + /// Re-insert an extracted node. + insert_return_type + insert(node_type&& __nh) + { return _M_t._M_reinsert_node_unique(std::move(__nh)); } + + /// Re-insert an extracted node. + iterator + insert(const_iterator __hint, node_type&& __nh) + { return _M_t._M_reinsert_node_hint_unique(__hint, std::move(__nh)); } + + template + friend class _Rb_tree_merge_helper; + + template + void + merge(set<_Key, _Compare1, _Alloc>& __source) + { + using _Merge_helper = _Rb_tree_merge_helper; + _M_t._M_merge_unique(_Merge_helper::_S_get_tree(__source)); + } + + template + void + merge(set<_Key, _Compare1, _Alloc>&& __source) + { merge(__source); } + + template + void + merge(multiset<_Key, _Compare1, _Alloc>& __source) + { + using _Merge_helper = _Rb_tree_merge_helper; + _M_t._M_merge_unique(_Merge_helper::_S_get_tree(__source)); + } + + template + void + merge(multiset<_Key, _Compare1, _Alloc>&& __source) + { merge(__source); } +#endif // C++17 + #if __cplusplus >= 201103L // _GLIBCXX_RESOLVE_LIB_DEFECTS // DR 130. Associative erase should return an iterator. @@ -897,5 +956,27 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { __x.swap(__y); } _GLIBCXX_END_NAMESPACE_CONTAINER + +#if __cplusplus > 201402L +_GLIBCXX_BEGIN_NAMESPACE_VERSION + // Allow std::set access to internals of compatible sets. + template + struct + _Rb_tree_merge_helper<_GLIBCXX_STD_C::set<_Val, _Cmp1, _Alloc>, _Cmp2> + { + private: + friend class _GLIBCXX_STD_C::set<_Val, _Cmp1, _Alloc>; + + static auto& + _S_get_tree(_GLIBCXX_STD_C::set<_Val, _Cmp2, _Alloc>& __set) + { return __set._M_t; } + + static auto& + _S_get_tree(_GLIBCXX_STD_C::multiset<_Val, _Cmp2, _Alloc>& __set) + { return __set._M_t; } + }; +_GLIBCXX_END_NAMESPACE_VERSION +#endif // C++17 + } //namespace std #endif /* _STL_SET_H */ diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h index 02b00b01c54..32da609e38d 100644 --- a/libstdc++-v3/include/bits/stl_tree.h +++ b/libstdc++-v3/include/bits/stl_tree.h @@ -66,7 +66,10 @@ #include #include #if __cplusplus >= 201103L -#include +# include +#endif +#if __cplusplus > 201402L +# include #endif namespace std _GLIBCXX_VISIBILITY(default) @@ -356,6 +359,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { typedef void type; }; #endif +#if __cplusplus > 201402L + template + struct _Rb_tree_merge_helper { }; +#endif + template > class _Rb_tree @@ -735,6 +743,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typedef std::reverse_iterator reverse_iterator; typedef std::reverse_iterator const_reverse_iterator; +#if __cplusplus > 201402L + using node_type = _Node_handle<_Key, _Val, _Node_allocator>; + using insert_return_type = _Node_insert_return; +#endif + pair<_Base_ptr, _Base_ptr> _M_get_insert_unique_pos(const key_type& __k); @@ -1274,6 +1287,172 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION void _M_move_assign(_Rb_tree&, std::false_type); #endif + +#if __cplusplus > 201402L + public: + /// Re-insert an extracted node. + insert_return_type + _M_reinsert_node_unique(node_type&& __nh) + { + insert_return_type __ret; + if (__nh.empty()) + __ret.position = end(); + else + { + __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc); + + auto __res = _M_get_insert_unique_pos(__nh._M_key()); + if (__res.second) + { + __ret.position + = _M_insert_node(__res.first, __res.second, __nh._M_ptr); + __nh._M_ptr = nullptr; + __ret.inserted = true; + } + else + { + __ret.node = std::move(__nh); + __ret.position = iterator(__res.first); + __ret.inserted = false; + } + } + return __ret; + } + + /// Re-insert an extracted node. + iterator + _M_reinsert_node_equal(node_type&& __nh) + { + iterator __ret; + if (__nh.empty()) + __ret = end(); + else + { + __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc); + auto __res = _M_get_insert_equal_pos(__nh._M_key()); + if (__res.second) + __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr); + else + __ret = _M_insert_equal_lower_node(__nh._M_ptr); + __nh._M_ptr = nullptr; + } + return __ret; + } + + /// Re-insert an extracted node. + iterator + _M_reinsert_node_hint_unique(const_iterator __hint, node_type&& __nh) + { + iterator __ret; + if (__nh.empty()) + __ret = end(); + else + { + __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc); + auto __res = _M_get_insert_hint_unique_pos(__hint, __nh._M_key()); + if (__res.second) + { + __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr); + __nh._M_ptr = nullptr; + } + else + __ret = iterator(__res.first); + } + return __ret; + } + + /// Re-insert an extracted node. + iterator + _M_reinsert_node_hint_equal(const_iterator __hint, node_type&& __nh) + { + iterator __ret; + if (__nh.empty()) + __ret = end(); + else + { + __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc); + auto __res = _M_get_insert_hint_equal_pos(__hint, __nh._M_key()); + if (__res.second) + __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr); + else + __ret = _M_insert_equal_lower_node(__nh._M_ptr); + __nh._M_ptr = nullptr; + } + return __ret; + } + + /// Extract a node. + node_type + extract(const_iterator __pos) + { + auto __ptr = _Rb_tree_rebalance_for_erase( + __pos._M_const_cast()._M_node, _M_impl._M_header); + --_M_impl._M_node_count; + return { static_cast<_Link_type>(__ptr), _M_get_Node_allocator() }; + } + + /// Extract a node. + node_type + extract(const key_type& __k) + { + node_type __nh; + auto __pos = find(__k); + if (__pos != end()) + __nh = extract(const_iterator(__pos)); + return __nh; + } + + template + using _Compatible_tree + = _Rb_tree<_Key, _Val, _KeyOfValue, _Compare2, _Alloc>; + + template + friend class _Rb_tree_merge_helper; + + /// Merge from a compatible container into one with unique keys. + template + void + _M_merge_unique(_Compatible_tree<_Compare2>& __src) noexcept + { + using _Merge_helper = _Rb_tree_merge_helper<_Rb_tree, _Compare2>; + for (auto __i = __src.begin(), __end = __src.end(); __i != __end;) + { + auto __pos = __i++; + auto __res = _M_get_insert_unique_pos(_KeyOfValue()(*__pos)); + if (__res.second) + { + auto& __src_impl = _Merge_helper::_S_get_impl(__src); + auto __ptr = _Rb_tree_rebalance_for_erase( + __pos._M_node, __src_impl._M_header); + --__src_impl._M_node_count; + _M_insert_node(__res.first, __res.second, + static_cast<_Link_type>(__ptr)); + } + } + } + + /// Merge from a compatible container into one with equivalent keys. + template + void + _M_merge_equal(_Compatible_tree<_Compare2>& __src) noexcept + { + using _Merge_helper = _Rb_tree_merge_helper<_Rb_tree, _Compare2>; + for (auto __i = __src.begin(), __end = __src.end(); __i != __end;) + { + auto __pos = __i++; + auto __res = _M_get_insert_equal_pos(_KeyOfValue()(*__pos)); + if (__res.second) + { + auto& __src_impl = _Merge_helper::_S_get_impl(__src); + auto __ptr = _Rb_tree_rebalance_for_erase( + __pos._M_node, __src_impl._M_header); + --__src_impl._M_node_count; + _M_insert_node(__res.first, __res.second, + static_cast<_Link_type>(__ptr)); + } + } + } +#endif // C++17 }; template 201402L + // Allow access to internals of compatible _Rb_tree specializations. + template + struct _Rb_tree_merge_helper<_Rb_tree<_Key, _Val, _Sel, _Cmp1, _Alloc>, + _Cmp2> + { + private: + friend class _Rb_tree<_Key, _Val, _Sel, _Cmp1, _Alloc>; + + static auto& + _S_get_impl(_Rb_tree<_Key, _Val, _Sel, _Cmp2, _Alloc>& __tree) + { return __tree._M_impl; } + }; +#endif // C++17 + _GLIBCXX_END_NAMESPACE_VERSION } // namespace diff --git a/libstdc++-v3/include/bits/unordered_map.h b/libstdc++-v3/include/bits/unordered_map.h index a26ee1afa99..ab8a7621e0d 100644 --- a/libstdc++-v3/include/bits/unordered_map.h +++ b/libstdc++-v3/include/bits/unordered_map.h @@ -68,6 +68,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER __detail::_Default_ranged_hash, __detail::_Prime_rehash_policy, _Tr>; + template + class unordered_multimap; + /** * @brief A standard container composed of unique keys (containing * at most one of each key value) that associates values of another type @@ -126,6 +129,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER typedef typename _Hashtable::difference_type difference_type; //@} +#if __cplusplus > 201402L + using node_type = typename _Hashtable::node_type; + using insert_return_type = typename _Hashtable::insert_return_type; +#endif + //construct/destroy/copy /// Default constructor. @@ -409,8 +417,27 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER emplace_hint(const_iterator __pos, _Args&&... __args) { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); } - #if __cplusplus > 201402L + /// Extract a node. + node_type + extract(const_iterator __pos) + { return _M_h.extract(__pos); } + + /// Extract a node. + node_type + extract(const key_type& __key) + { return _M_h.extract(__key); } + + /// Re-insert an extracted node. + insert_return_type + insert(node_type&& __nh) + { return _M_h._M_reinsert_node(std::move(__nh)); } + + /// Re-insert an extracted node. + iterator + insert(const_iterator, node_type&& __nh) + { return _M_h._M_reinsert_node(std::move(__nh)).position; } + #define __cpp_lib_unordered_map_try_emplace 201411 /** * @brief Attempts to build and insert a std::pair into the @@ -524,7 +551,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER std::forward<_Args>(__args)...)); return __i; } -#endif +#endif // C++17 //@{ /** @@ -817,6 +844,37 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER noexcept( noexcept(_M_h.swap(__x._M_h)) ) { _M_h.swap(__x._M_h); } +#if __cplusplus > 201402L + template + friend class _Hash_merge_helper; + + template + void + merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source) + { + using _Merge_helper = _Hash_merge_helper; + _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source)); + } + + template + void + merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source) + { merge(__source); } + + template + void + merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source) + { + using _Merge_helper = _Hash_merge_helper; + _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source)); + } + + template + void + merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source) + { merge(__source); } +#endif // C++17 + // observers. /// Returns the hash functor object with which the %unordered_map was @@ -1052,8 +1110,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER template friend bool - operator==(const unordered_map<_Key1, _Tp1, _Hash1, _Pred1, _Alloc1>&, - const unordered_map<_Key1, _Tp1, _Hash1, _Pred1, _Alloc1>&); + operator==(const unordered_map<_Key1, _Tp1, _Hash1, _Pred1, _Alloc1>&, + const unordered_map<_Key1, _Tp1, _Hash1, _Pred1, _Alloc1>&); }; /** @@ -1114,6 +1172,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER typedef typename _Hashtable::difference_type difference_type; //@} +#if __cplusplus > 201402L + using node_type = typename _Hashtable::node_type; +#endif + //construct/destroy/copy /// Default constructor. @@ -1468,6 +1530,28 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER insert(initializer_list __l) { _M_h.insert(__l); } +#if __cplusplus > 201402L + /// Extract a node. + node_type + extract(const_iterator __pos) + { return _M_h.extract(__pos); } + + /// Extract a node. + node_type + extract(const key_type& __key) + { return _M_h.extract(__key); } + + /// Re-insert an extracted node. + iterator + insert(node_type&& __nh) + { return _M_h._M_reinsert_node_multi(cend(), std::move(__nh)); } + + /// Re-insert an extracted node. + iterator + insert(const_iterator __hint, node_type&& __nh) + { return _M_h._M_reinsert_node_multi(__hint, std::move(__nh)); } +#endif // C++17 + //@{ /** * @brief Erases an element from an %unordered_multimap. @@ -1551,6 +1635,39 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER noexcept( noexcept(_M_h.swap(__x._M_h)) ) { _M_h.swap(__x._M_h); } +#if __cplusplus > 201402L + template + friend class _Hash_merge_helper; + + template + void + merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source) + { + using _Merge_helper + = _Hash_merge_helper; + _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source)); + } + + template + void + merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source) + { merge(__source); } + + template + void + merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source) + { + using _Merge_helper + = _Hash_merge_helper; + _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source)); + } + + template + void + merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source) + { merge(__source); } +#endif // C++17 + // observers. /// Returns the hash functor object with which the %unordered_multimap @@ -1786,6 +1903,59 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { return !(__x == __y); } _GLIBCXX_END_NAMESPACE_CONTAINER + +#if __cplusplus > 201402L +_GLIBCXX_BEGIN_NAMESPACE_VERSION + // Allow std::unordered_map access to internals of compatible maps. + template + struct _Hash_merge_helper< + _GLIBCXX_STD_C::unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>, + _Hash2, _Eq2> + { + private: + template + using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>; + template + using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>; + + friend unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>; + + static auto& + _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map) + { return __map._M_h; } + + static auto& + _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map) + { return __map._M_h; } + }; + + // Allow std::unordered_multimap access to internals of compatible maps. + template + struct _Hash_merge_helper< + _GLIBCXX_STD_C::unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>, + _Hash2, _Eq2> + { + private: + template + using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>; + template + using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>; + + friend unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>; + + static auto& + _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map) + { return __map._M_h; } + + static auto& + _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map) + { return __map._M_h; } + }; +_GLIBCXX_END_NAMESPACE_VERSION +#endif // C++17 + } // namespace std #endif /* _UNORDERED_MAP_H */ diff --git a/libstdc++-v3/include/bits/unordered_set.h b/libstdc++-v3/include/bits/unordered_set.h index 1e65b547522..e5bb2beb80d 100644 --- a/libstdc++-v3/include/bits/unordered_set.h +++ b/libstdc++-v3/include/bits/unordered_set.h @@ -65,6 +65,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER __detail::_Default_ranged_hash, __detail::_Prime_rehash_policy, _Tr>; + template + class unordered_multiset; + /** * @brief A standard container composed of unique keys (containing * at most one of each key value) in which the elements' keys are @@ -120,6 +123,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER typedef typename _Hashtable::difference_type difference_type; //@} +#if __cplusplus > 201402L + using node_type = typename _Hashtable::node_type; + using insert_return_type = typename _Hashtable::insert_return_type; +#endif + // construct/destroy/copy /// Default constructor. @@ -470,6 +478,28 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER insert(initializer_list __l) { _M_h.insert(__l); } +#if __cplusplus > 201402L + /// Extract a node. + node_type + extract(const_iterator __pos) + { return _M_h.extract(__pos); } + + /// Extract a node. + node_type + extract(const key_type& __key) + { return _M_h.extract(__key); } + + /// Re-insert an extracted node. + insert_return_type + insert(node_type&& __nh) + { return _M_h._M_reinsert_node(std::move(__nh)); } + + /// Re-insert an extracted node. + iterator + insert(const_iterator, node_type&& __nh) + { return _M_h._M_reinsert_node(std::move(__nh)).position; } +#endif // C++17 + //@{ /** * @brief Erases an element from an %unordered_set. @@ -552,6 +582,37 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER noexcept( noexcept(_M_h.swap(__x._M_h)) ) { _M_h.swap(__x._M_h); } +#if __cplusplus > 201402L + template + friend class _Hash_merge_helper; + + template + void + merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source) + { + using _Merge_helper = _Hash_merge_helper; + _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source)); + } + + template + void + merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source) + { merge(__source); } + + template + void + merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source) + { + using _Merge_helper = _Hash_merge_helper; + _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source)); + } + + template + void + merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source) + { merge(__source); } +#endif // C++17 + // observers. /// Returns the hash functor object with which the %unordered_set was @@ -793,6 +854,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER typedef typename _Hashtable::difference_type difference_type; //@} +#if __cplusplus > 201402L + using node_type = typename _Hashtable::node_type; +#endif + // construct/destroy/copy /// Default constructor. @@ -1121,6 +1186,28 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER insert(initializer_list __l) { _M_h.insert(__l); } +#if __cplusplus > 201402L + /// Extract a node. + node_type + extract(const_iterator __pos) + { return _M_h.extract(__pos); } + + /// Extract a node. + node_type + extract(const key_type& __key) + { return _M_h.extract(__key); } + + /// Re-insert an extracted node. + iterator + insert(node_type&& __nh) + { return _M_h._M_reinsert_node_multi(cend(), std::move(__nh)); } + + /// Re-insert an extracted node. + iterator + insert(const_iterator __hint, node_type&& __nh) + { return _M_h._M_reinsert_node_multi(__hint, std::move(__nh)); } +#endif // C++17 + //@{ /** * @brief Erases an element from an %unordered_multiset. @@ -1208,6 +1295,39 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER noexcept( noexcept(_M_h.swap(__x._M_h)) ) { _M_h.swap(__x._M_h); } +#if __cplusplus > 201402L + template + friend class _Hash_merge_helper; + + template + void + merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source) + { + using _Merge_helper + = _Hash_merge_helper; + _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source)); + } + + template + void + merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source) + { merge(__source); } + + template + void + merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source) + { + using _Merge_helper + = _Hash_merge_helper; + _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source)); + } + + template + void + merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source) + { merge(__source); } +#endif // C++17 + // observers. /// Returns the hash functor object with which the %unordered_multiset @@ -1429,6 +1549,58 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { return !(__x == __y); } _GLIBCXX_END_NAMESPACE_CONTAINER + +#if __cplusplus > 201402L +_GLIBCXX_BEGIN_NAMESPACE_VERSION + // Allow std::unordered_set access to internals of compatible sets. + template + struct _Hash_merge_helper< + _GLIBCXX_STD_C::unordered_set<_Val, _Hash1, _Eq1, _Alloc>, _Hash2, _Eq2> + { + private: + template + using unordered_set = _GLIBCXX_STD_C::unordered_set<_Tp...>; + template + using unordered_multiset = _GLIBCXX_STD_C::unordered_multiset<_Tp...>; + + friend unordered_set<_Val, _Hash1, _Eq1, _Alloc>; + + static auto& + _S_get_table(unordered_set<_Val, _Hash2, _Eq2, _Alloc>& __set) + { return __set._M_h; } + + static auto& + _S_get_table(unordered_multiset<_Val, _Hash2, _Eq2, _Alloc>& __set) + { return __set._M_h; } + }; + + // Allow std::unordered_multiset access to internals of compatible sets. + template + struct _Hash_merge_helper< + _GLIBCXX_STD_C::unordered_multiset<_Val, _Hash1, _Eq1, _Alloc>, + _Hash2, _Eq2> + { + private: + template + using unordered_set = _GLIBCXX_STD_C::unordered_set<_Tp...>; + template + using unordered_multiset = _GLIBCXX_STD_C::unordered_multiset<_Tp...>; + + friend unordered_multiset<_Val, _Hash1, _Eq1, _Alloc>; + + static auto& + _S_get_table(unordered_set<_Val, _Hash2, _Eq2, _Alloc>& __set) + { return __set._M_h; } + + static auto& + _S_get_table(unordered_multiset<_Val, _Hash2, _Eq2, _Alloc>& __set) + { return __set._M_h; } + }; +_GLIBCXX_END_NAMESPACE_VERSION +#endif // C++17 + } // namespace std #endif /* _UNORDERED_SET_H */ diff --git a/libstdc++-v3/include/debug/map.h b/libstdc++-v3/include/debug/map.h index 432bed39cfb..51cd140a122 100644 --- a/libstdc++-v3/include/debug/map.h +++ b/libstdc++-v3/include/debug/map.h @@ -397,8 +397,52 @@ namespace __debug std::forward<_Obj>(__obj)), this); } -#endif +#endif // C++17 + +#if __cplusplus > 201402L + using node_type = typename _Base::node_type; + + struct insert_return_type + { + bool inserted; + iterator position; + node_type node; + }; + + node_type + extract(const_iterator __position) + { + __glibcxx_check_erase(__position); + this->_M_invalidate_if(_Equal(__position.base())); + return _Base::extract(__position.base()); + } + + node_type + extract(const key_type& __key) + { + const auto __position = find(__key); + if (__position != end()) + return extract(__position); + return {}; + } + + insert_return_type + insert(node_type&& __nh) + { + auto __ret = _Base::insert(std::move(__nh)); + iterator __pos = iterator(__ret.position, this); + return { __ret.inserted, __pos, std::move(__ret.node) }; + } + + iterator + insert(const_iterator __hint, node_type&& __nh) + { + __glibcxx_check_insert(__hint); + return iterator(_Base::insert(__hint.base(), std::move(__nh)), this); + } + using _Base::merge; +#endif // C++17 #if __cplusplus >= 201103L iterator diff --git a/libstdc++-v3/include/debug/multimap.h b/libstdc++-v3/include/debug/multimap.h index 30e7b196f2f..0cecedb5b38 100644 --- a/libstdc++-v3/include/debug/multimap.h +++ b/libstdc++-v3/include/debug/multimap.h @@ -296,6 +296,40 @@ namespace __debug _Base::insert(__first, __last); } +#if __cplusplus > 201402L + using node_type = typename _Base::node_type; + + node_type + extract(const_iterator __position) + { + __glibcxx_check_erase(__position); + this->_M_invalidate_if(_Equal(__position.base())); + return _Base::extract(__position.base()); + } + + node_type + extract(const key_type& __key) + { + const auto __position = find(__key); + if (__position != end()) + return extract(__position); + return {}; + } + + iterator + insert(node_type&& __nh) + { return iterator(_Base::insert(std::move(__nh)), this); } + + iterator + insert(const_iterator __hint, node_type&& __nh) + { + __glibcxx_check_insert(__hint); + return iterator(_Base::insert(__hint.base(), std::move(__nh)), this); + } + + using _Base::merge; +#endif // C++17 + #if __cplusplus >= 201103L iterator erase(const_iterator __position) diff --git a/libstdc++-v3/include/debug/multiset.h b/libstdc++-v3/include/debug/multiset.h index 67eb7e18fb7..2d68a3df92c 100644 --- a/libstdc++-v3/include/debug/multiset.h +++ b/libstdc++-v3/include/debug/multiset.h @@ -287,6 +287,40 @@ namespace __debug { _Base::insert(__l); } #endif +#if __cplusplus > 201402L + using node_type = typename _Base::node_type; + + node_type + extract(const_iterator __position) + { + __glibcxx_check_erase(__position); + this->_M_invalidate_if(_Equal(__position.base())); + return _Base::extract(__position.base()); + } + + node_type + extract(const key_type& __key) + { + const auto __position = find(__key); + if (__position != end()) + return extract(__position); + return {}; + } + + iterator + insert(node_type&& __nh) + { return iterator(_Base::insert(std::move(__nh)), this); } + + iterator + insert(const_iterator __hint, node_type&& __nh) + { + __glibcxx_check_insert(__hint); + return iterator(_Base::insert(__hint.base(), std::move(__nh)), this); + } + + using _Base::merge; +#endif // C++17 + #if __cplusplus >= 201103L iterator erase(const_iterator __position) diff --git a/libstdc++-v3/include/debug/set.h b/libstdc++-v3/include/debug/set.h index ede4103acd8..89376384458 100644 --- a/libstdc++-v3/include/debug/set.h +++ b/libstdc++-v3/include/debug/set.h @@ -296,6 +296,51 @@ namespace __debug { _Base::insert(__l); } #endif +#if __cplusplus > 201402L + using node_type = typename _Base::node_type; + + struct insert_return_type + { + bool inserted; + iterator position; + node_type node; + }; + + node_type + extract(const_iterator __position) + { + __glibcxx_check_erase(__position); + this->_M_invalidate_if(_Equal(__position.base())); + return _Base::extract(__position.base()); + } + + node_type + extract(const key_type& __key) + { + const auto __position = find(__key); + if (__position != end()) + return extract(__position); + return {}; + } + + insert_return_type + insert(node_type&& __nh) + { + auto __ret = _Base::insert(std::move(__nh)); + iterator __pos = iterator(__ret.position, this); + return { __ret.inserted, __pos, std::move(__ret.node) }; + } + + iterator + insert(const_iterator __hint, node_type&& __nh) + { + __glibcxx_check_insert(__hint); + return iterator(_Base::insert(__hint.base(), std::move(__nh)), this); + } + + using _Base::merge; +#endif // C++17 + #if __cplusplus >= 201103L iterator erase(const_iterator __position) diff --git a/libstdc++-v3/include/debug/unordered_map b/libstdc++-v3/include/debug/unordered_map index 873f36a3499..4a834c67eba 100644 --- a/libstdc++-v3/include/debug/unordered_map +++ b/libstdc++-v3/include/debug/unordered_map @@ -458,8 +458,59 @@ namespace __debug std::forward<_Obj>(__obj)), this); } -#endif +#endif // C++17 + +#if __cplusplus > 201402L + using node_type = typename _Base::node_type; + + struct insert_return_type + { + bool inserted; + iterator position; + node_type node; + }; + node_type + extract(const_iterator __position) + { + __glibcxx_check_erase(__position); + _Base_const_iterator __victim = __position.base(); + this->_M_invalidate_if( + [__victim](_Base_const_iterator __it) { return __it == __victim; } + ); + this->_M_invalidate_local_if( + [__victim](_Base_const_local_iterator __it) { + return __it._M_curr() == __victim._M_cur; + }); + return _Base::extract(__position.base()); + } + + node_type + extract(const key_type& __key) + { + const auto __position = find(__key); + if (__position != end()) + return extract(__position); + return {}; + } + + insert_return_type + insert(node_type&& __nh) + { + auto __ret = _Base::insert(std::move(__nh)); + iterator __pos = iterator(__ret.position, this); + return { __ret.inserted, __pos, std::move(__ret.node) }; + } + + iterator + insert(const_iterator __hint, node_type&& __nh) + { + __glibcxx_check_insert(__hint); + return iterator(_Base::insert(__hint.base(), std::move(__nh)), this); + } + + using _Base::merge; +#endif // C++17 iterator find(const key_type& __key) @@ -913,6 +964,47 @@ namespace __debug _M_check_rehashed(__bucket_count); } +#if __cplusplus > 201402L + using node_type = typename _Base::node_type; + + node_type + extract(const_iterator __position) + { + __glibcxx_check_erase(__position); + _Base_const_iterator __victim = __position.base(); + this->_M_invalidate_if( + [__victim](_Base_const_iterator __it) { return __it == __victim; } + ); + this->_M_invalidate_local_if( + [__victim](_Base_const_local_iterator __it) { + return __it._M_curr() == __victim._M_cur; + }); + return _Base::extract(__position.base()); + } + + node_type + extract(const key_type& __key) + { + const auto __position = find(__key); + if (__position != end()) + return extract(__position); + return {}; + } + + iterator + insert(node_type&& __nh) + { return iterator(_Base::insert(std::move(__nh)), this); } + + iterator + insert(const_iterator __hint, node_type&& __nh) + { + __glibcxx_check_insert(__hint); + return iterator(_Base::insert(__hint.base(), std::move(__nh)), this); + } + + using _Base::merge; +#endif // C++17 + iterator find(const key_type& __key) { return iterator(_Base::find(__key), this); } diff --git a/libstdc++-v3/include/debug/unordered_set b/libstdc++-v3/include/debug/unordered_set index 6a4dba6475d..f8587c06bfc 100644 --- a/libstdc++-v3/include/debug/unordered_set +++ b/libstdc++-v3/include/debug/unordered_set @@ -370,6 +370,58 @@ namespace __debug _M_check_rehashed(__bucket_count); } +#if __cplusplus > 201402L + using node_type = typename _Base::node_type; + + struct insert_return_type + { + bool inserted; + iterator position; + node_type node; + }; + + node_type + extract(const_iterator __position) + { + __glibcxx_check_erase(__position); + _Base_const_iterator __victim = __position.base(); + this->_M_invalidate_if( + [__victim](_Base_const_iterator __it) { return __it == __victim; } + ); + this->_M_invalidate_local_if( + [__victim](_Base_const_local_iterator __it) { + return __it._M_curr() == __victim._M_cur; + }); + return _Base::extract(__position.base()); + } + + node_type + extract(const key_type& __key) + { + const auto __position = find(__key); + if (__position != end()) + return extract(__position); + return {}; + } + + insert_return_type + insert(node_type&& __nh) + { + auto __ret = _Base::insert(std::move(__nh)); + iterator __pos = iterator(__ret.position, this); + return { __ret.inserted, __pos, std::move(__ret.node) }; + } + + iterator + insert(const_iterator __hint, node_type&& __nh) + { + __glibcxx_check_insert(__hint); + return iterator(_Base::insert(__hint.base(), std::move(__nh)), this); + } + + using _Base::merge; +#endif // C++17 + iterator find(const key_type& __key) { return iterator(_Base::find(__key), this); } @@ -821,6 +873,47 @@ namespace __debug _M_check_rehashed(__bucket_count); } +#if __cplusplus > 201402L + using node_type = typename _Base::node_type; + + node_type + extract(const_iterator __position) + { + __glibcxx_check_erase(__position); + _Base_const_iterator __victim = __position.base(); + this->_M_invalidate_if( + [__victim](_Base_const_iterator __it) { return __it == __victim; } + ); + this->_M_invalidate_local_if( + [__victim](_Base_const_local_iterator __it) { + return __it._M_curr() == __victim._M_cur; + }); + return _Base::extract(__position.base()); + } + + node_type + extract(const key_type& __key) + { + const auto __position = find(__key); + if (__position != end()) + return extract(__position); + return {}; + } + + iterator + insert(node_type&& __nh) + { return iterator(_Base::insert(std::move(__nh)), this); } + + iterator + insert(const_iterator __hint, node_type&& __nh) + { + __glibcxx_check_insert(__hint); + return iterator(_Base::insert(__hint.base(), std::move(__nh)), this); + } + + using _Base::merge; +#endif // C++17 + iterator find(const key_type& __key) { return iterator(_Base::find(__key), this); } diff --git a/libstdc++-v3/python/libstdcxx/v6/printers.py b/libstdc++-v3/python/libstdcxx/v6/printers.py index 18c6f6b6a38..b5fc2a02aa5 100644 --- a/libstdc++-v3/python/libstdcxx/v6/printers.py +++ b/libstdc++-v3/python/libstdcxx/v6/printers.py @@ -130,6 +130,10 @@ class UniquePointerPrinter: return ('std::unique_ptr<%s> containing %s' % (str(v.type.target()), str(v))) +def get_value_from_aligned_membuf(buf, valtype): + """Returns the value held in a __gnu_cxx::__aligned_membuf.""" + return buf['_M_storage'].address.cast(valtype.pointer()).dereference() + def get_value_from_list_node(node): """Returns the value held in an _List_node<_Val>""" try: @@ -139,9 +143,8 @@ def get_value_from_list_node(node): return node['_M_data'] elif member == '_M_storage': # C++11 implementation, node stores value in __aligned_membuf - p = node['_M_storage']['_M_storage'].address - p = p.cast(node.type.template_argument(0).pointer()) - return p.dereference() + valtype = node.type.template_argument(0) + return get_value_from_aligned_membuf(node['_M_storage'], valtype) except: pass raise ValueError("Unsupported implementation for %s" % str(node.type)) @@ -461,9 +464,8 @@ def get_value_from_Rb_tree_node(node): return node['_M_value_field'] elif member == '_M_storage': # C++11 implementation, node stores value in __aligned_membuf - p = node['_M_storage']['_M_storage'].address - p = p.cast(node.type.template_argument(0).pointer()) - return p.dereference() + valtype = node.type.template_argument(0) + return get_value_from_aligned_membuf(node['_M_storage'], valtype) except: pass raise ValueError("Unsupported implementation for %s" % str(node.type)) @@ -1017,6 +1019,48 @@ class StdVariantPrinter(SingleObjContainerPrinter): return "%s [index %d] containing %s" % (self.typename, self.index, self.visualizer.to_string()) return "%s [index %d]" % (self.typename, self.index) +class StdNodeHandlePrinter(SingleObjContainerPrinter): + "Print a container node handle" + + def __init__(self, typename, val): + self.value_type = val.type.template_argument(1) + nodetype = val.type.template_argument(2).template_argument(0) + self.is_rb_tree_node = nodetype.name.startswith('std::_Rb_tree_node') + self.is_map_node = val.type.template_argument(0) != self.value_type + nodeptr = val['_M_ptr'] + if nodeptr: + if self.is_rb_tree_node: + contained_value = get_value_from_Rb_tree_node(nodeptr.dereference()) + else: + contained_value = get_value_from_aligned_membuf(nodeptr['_M_storage'], + self.value_type) + visualizer = gdb.default_visualizer(contained_value) + else: + contained_value = None + visualizer = None + optalloc = val['_M_alloc'] + self.alloc = optalloc['_M_payload'] if optalloc['_M_engaged'] else None + super(StdNodeHandlePrinter, self).__init__(contained_value, visualizer, + 'array') + + def to_string(self): + + desc = 'node handle for ' + if not self.is_rb_tree_node: + desc += 'unordered ' + if self.is_map_node: + desc += 'map'; + else: + desc += 'set'; + + if self.contained_value: + desc += ' with element' + if hasattr(self.visualizer, 'children'): + return "%s = %s" % (desc, self.visualizer.to_string()) + return desc + else: + return 'empty %s' % desc + class StdExpStringViewPrinter: "Print a std::basic_string_view or std::experimental::basic_string_view" @@ -1491,6 +1535,8 @@ def build_libstdcxx_dictionary (): 'basic_string_view', StdExpStringViewPrinter) libstdcxx_printer.add_version('std::', 'variant', StdVariantPrinter) + libstdcxx_printer.add_version('std::', + '_Node_handle', StdNodeHandlePrinter) # Extensions. libstdcxx_printer.add_version('__gnu_cxx::', 'slist', StdSlistPrinter) diff --git a/libstdc++-v3/testsuite/23_containers/map/modifiers/extract.cc b/libstdc++-v3/testsuite/23_containers/map/modifiers/extract.cc new file mode 100644 index 00000000000..dbbcc803ba7 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/map/modifiers/extract.cc @@ -0,0 +1,147 @@ +// Copyright (C) 2016 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-options "-std=gnu++17" } + +#include +#include +#include + +using test_type = std::map; + +void +test01() +{ + bool test __attribute__((unused)) = true; + + test_type c{ {1, 10}, {2, 20}, {3, 30} }; + test_type::node_type node; + test_type::insert_return_type ins; + test_type::iterator pos; + + node = c.extract(0); + VERIFY( !node ); + VERIFY( node.empty() ); + VERIFY( c.size() == 3 ); + + ins = c.insert(std::move(node)); + VERIFY( !node ); + VERIFY( node.empty() ); + VERIFY( c.size() == 3 ); + VERIFY( !ins.inserted ); + VERIFY( !ins.node ); + VERIFY( ins.position == c.end() ); + + node = c.extract(1); + VERIFY( (bool)node ); + VERIFY( !node.empty() ); + VERIFY( c.size() == 2 ); + VERIFY( c.count(1) == 0 ); + VERIFY( node.get_allocator() == c.get_allocator() ); + VERIFY( node.key() == 1 ); + VERIFY( node.mapped() == 10 ); + + node.key() = 4; + node.mapped() = 40; + VERIFY( node.key() == 4 ); + VERIFY( node.mapped() == 40 ); + + ins = c.insert(std::move(node)); + VERIFY( !node ); + VERIFY( node.empty() ); + VERIFY( c.size() == 3 ); + VERIFY( ins.inserted ); + VERIFY( !ins.node ); + VERIFY( ins.position != c.end() ); + VERIFY( ins.position->first == 4 ); + VERIFY( ins.position->second == 40 ); + VERIFY( c.count(1) == 0 ); + VERIFY( c.count(4) == 1 ); + VERIFY( std::is_sorted(c.begin(), c.end()) ); + + pos = c.insert(c.begin(), std::move(node)); + VERIFY( !node ); + VERIFY( node.empty() ); + VERIFY( c.size() == 3 ); + VERIFY( pos == c.end() ); + + node = c.extract(2); + pos = c.insert(c.begin(), std::move(node)); + VERIFY( c.size() == 3 ); + VERIFY( pos != c.end() ); + VERIFY( pos->first == 2 ); + VERIFY( pos->second == 20 ); + + test_type c2 = c; + node = c2.extract(3); + ins = c.insert(std::move(node)); + VERIFY( node.empty() ); + VERIFY( ins.position != c.end() ); + VERIFY( !ins.inserted ); + VERIFY( !ins.node.empty() ); + VERIFY( ins.node.key() == 3 ); + VERIFY( ins.node.mapped() == 30 ); + VERIFY( ins.position->first == ins.node.key() ); +} + +void +test02() +{ + bool test __attribute__((unused)) = true; + + test_type c{ {1, 10}, {2, 20}, {3, 30} }; + test_type::node_type node; + test_type::insert_return_type ins; + + node = c.extract(c.begin()); + VERIFY( (bool)node ); + VERIFY( !node.empty() ); + VERIFY( c.size() == 2 ); + VERIFY( node.get_allocator() == c.get_allocator() ); + VERIFY( node.key() == 1 ); + VERIFY( node.mapped() == 10 ); + + ins = c.insert(std::move(node)); + VERIFY( node.empty() ); + VERIFY( c.size() == 3 ); + VERIFY( ins.inserted ); + VERIFY( !ins.node ); + VERIFY( ins.position != c.end() ); + VERIFY( ins.position->first == 1 ); + VERIFY( ins.position->second == 10 ); +} + +void +test03() +{ + struct less : std::less { }; + using std::is_same_v; + using compat_type1 = std::map; + static_assert( is_same_v ); + using compat_type2 = std::multimap; + static_assert( is_same_v ); + using compat_type3 = std::multimap; + static_assert( is_same_v ); +} + +int +main() +{ + test01(); + test02(); + test03(); +} diff --git a/libstdc++-v3/testsuite/23_containers/map/modifiers/merge.cc b/libstdc++-v3/testsuite/23_containers/map/modifiers/merge.cc new file mode 100644 index 00000000000..c978ed21e07 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/map/modifiers/merge.cc @@ -0,0 +1,147 @@ +// Copyright (C) 2016 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-options "-std=gnu++17" } + +#include +#include +#include + +using test_type = std::map; + +void +test01() +{ + bool test __attribute__((unused)) = true; + + const test_type c0{ {1, 10}, {2, 20}, {3, 30} }; + test_type c1 = c0, c2 = c0; + + c1.merge(c2); + VERIFY( c1 == c0 ); + VERIFY( c2 == c0 ); + + c1.clear(); + c1.merge(c2); + VERIFY( c1 == c0 ); + VERIFY( c2.empty() ); + + c2.merge(std::move(c1)); + VERIFY( c1.empty() ); + VERIFY( c2 == c0 ); +} + +void +test02() +{ + bool test __attribute__((unused)) = true; + + const test_type c0{ {1, 10}, {2, 20}, {3, 30} }; + test_type c1 = c0; + std::map> c2( c0.begin(), c0.end() ); + + c1.merge(c2); + VERIFY( c1 == c0 ); + VERIFY( std::equal(c2.begin(), c2.end(), c0.begin(), c0.end()) ); + + c1.clear(); + c1.merge(c2); + VERIFY( c1 == c0 ); + VERIFY( c2.empty() ); + + c2.merge(std::move(c1)); + VERIFY( c1.empty() ); + VERIFY( std::equal(c2.begin(), c2.end(), c0.begin(), c0.end()) ); +} + +void +test03() +{ + bool test __attribute__((unused)) = true; + + const test_type c0{ {1, 10}, {2, 20}, {3, 30} }; + test_type c1 = c0; + std::map> c2( c0.begin(), c0.end() ); + + c1.merge(c2); + VERIFY( c1 == c0 ); + VERIFY( std::equal(c2.rbegin(), c2.rend(), c0.begin(), c0.end()) ); + + c1.clear(); + c1.merge(c2); + VERIFY( c1 == c0 ); + VERIFY( c2.empty() ); + + c2.merge(c1); + VERIFY( c1.empty() ); + VERIFY( std::equal(c2.rbegin(), c2.rend(), c0.begin(), c0.end()) ); + + c1.merge(std::move(c2)); + VERIFY( c1 == c0 ); + VERIFY( c2.empty() ); +} + +void +test04() +{ + bool test __attribute__((unused)) = true; + + const test_type c0{ {1, 10}, {2, 20}, {3, 30} }; + test_type c1 = c0; + std::multimap> c2( c0.begin(), c0.end() ); + + c1.merge(c2); + VERIFY( c1 == c0 ); + VERIFY( std::equal(c2.rbegin(), c2.rend(), c0.begin(), c0.end()) ); + + c1.clear(); + c1.merge(c2); + VERIFY( c1 == c0 ); + VERIFY( c2.empty() ); + + c2.merge(c1); + VERIFY( c1.empty() ); + VERIFY( std::equal(c2.rbegin(), c2.rend(), c0.begin(), c0.end()) ); + + c1 = c0; + c2.merge(c1); + VERIFY( c1.empty() ); + VERIFY( c2.size() == (2 * c0.size()) ); + VERIFY( std::is_sorted(c2.begin(), c2.end(), c2.value_comp()) ); + + c1.merge(c2); + VERIFY( c1 == c0 ); + VERIFY( std::equal(c2.rbegin(), c2.rend(), c0.begin(), c0.end()) ); + + c1.merge(std::move(c2)); + VERIFY( c1 == c0 ); + VERIFY( std::equal(c2.rbegin(), c2.rend(), c0.begin(), c0.end()) ); + + c1.clear(); + c1.merge(std::move(c2)); + VERIFY( c1 == c0 ); + VERIFY( c2.empty() ); +} + +int +main() +{ + test01(); + test02(); + test03(); + test04(); +} diff --git a/libstdc++-v3/testsuite/23_containers/multimap/modifiers/extract.cc b/libstdc++-v3/testsuite/23_containers/multimap/modifiers/extract.cc new file mode 100644 index 00000000000..cad131ceadf --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/multimap/modifiers/extract.cc @@ -0,0 +1,141 @@ +// Copyright (C) 2016 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-options "-std=gnu++17" } + +#include +#include +#include + +using test_type = std::multimap; + +void +test01() +{ + bool test __attribute__((unused)) = true; + + test_type c{ {1, 10}, { 1, 11 }, {2, 20}, { 2, 21}, {3, 30}, { 3, 31 } }; + test_type::node_type node; + test_type::iterator pos; + + node = c.extract(0); + VERIFY( !node ); + VERIFY( node.empty() ); + VERIFY( c.size() == 6 ); + + pos = c.insert(std::move(node)); + VERIFY( !node ); + VERIFY( node.empty() ); + VERIFY( c.size() == 6 ); + VERIFY( pos == c.end() ); + + node = c.extract(1); + VERIFY( (bool)node ); + VERIFY( !node.empty() ); + VERIFY( c.size() == 5 ); + VERIFY( c.count(1) == 1 ); + VERIFY( node.get_allocator() == c.get_allocator() ); + VERIFY( node.key() == 1 ); + int mapped = node.mapped(); + VERIFY( mapped == 10 || mapped == 11 ); + + node.key() = 4; + node.mapped() = 40; + VERIFY( node.key() == 4 ); + VERIFY( node.mapped() == 40 ); + + pos = c.insert(std::move(node)); + VERIFY( !node ); + VERIFY( node.empty() ); + VERIFY( c.size() == 6 ); + VERIFY( pos != c.end() ); + VERIFY( pos->first == 4 ); + VERIFY( pos->second == 40 ); + VERIFY( c.count(1) == 1 ); + VERIFY( c.count(4) == 1 ); + VERIFY( std::is_sorted(c.begin(), c.end()) ); + + pos = c.insert(c.begin(), std::move(node)); + VERIFY( !node ); + VERIFY( node.empty() ); + VERIFY( c.size() == 6 ); + VERIFY( pos == c.end() ); + + node = c.extract(1); + mapped = node.mapped(); + pos = c.insert(c.begin(), std::move(node)); + VERIFY( !node ); + VERIFY( c.size() == 6 ); + VERIFY( pos != c.end() ); + VERIFY( pos->first == 1 ); + VERIFY( pos->second == mapped ); + + test_type c2 = c; + node = c2.extract(1); + mapped = node.mapped(); + pos = c.insert(std::move(node)); + VERIFY( pos != c.end() ); + VERIFY( node.empty() ); + VERIFY( pos->first == 1 ); + VERIFY( pos->second == mapped ); +} + +void +test02() +{ + bool test __attribute__((unused)) = true; + + test_type c{ {1, 10}, { 1, 11 }, {2, 20}, { 2, 21}, {3, 30}, { 3, 31 } }; + test_type::node_type node; + test_type::iterator pos; + + node = c.extract(c.begin()); + VERIFY( !node.empty() ); + VERIFY( c.size() == 5 ); + VERIFY( node.get_allocator() == c.get_allocator() ); + VERIFY( node.key() == 1 ); + VERIFY( node.mapped() == 10 ); + + pos = c.insert(std::next(c.begin()), std::move(node)); + VERIFY( node.empty() ); + VERIFY( c.size() == 6 ); + VERIFY( pos != c.end() ); + VERIFY( pos->first == 1 ); + VERIFY( pos->second == 10 ); + VERIFY( pos == std::next(c.begin()) ); +} + +void +test03() +{ + struct less : std::less { }; + using std::is_same_v; + using compat_type1 = std::multimap; + static_assert( is_same_v ); + using compat_type2 = std::map; + static_assert( is_same_v ); + using compat_type3 = std::map; + static_assert( is_same_v ); +} + +int +main() +{ + test01(); + test02(); + test03(); +} diff --git a/libstdc++-v3/testsuite/23_containers/multimap/modifiers/merge.cc b/libstdc++-v3/testsuite/23_containers/multimap/modifiers/merge.cc new file mode 100644 index 00000000000..70541ff7fbe --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/multimap/modifiers/merge.cc @@ -0,0 +1,119 @@ +// Copyright (C) 2016 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-options "-std=gnu++17" } + +#include +#include +#include + +using test_type = std::multimap; + +void +test01() +{ + bool test __attribute__((unused)) = true; + + const test_type c0{ {1, 10}, {1, 11}, {2, 20}, {2, 21}, {3, 30}, {3, 31} }; + test_type c1 = c0, c2 = c0; + + c1.merge(c2); + for (auto& i : c1) + VERIFY( c1.count(i.first) == (2 * c0.count(i.first)) ); + VERIFY( c2.empty() ); + + c1.clear(); + c2 = c0; + c1.merge(std::move(c2)); + VERIFY( c1 == c0 ); + VERIFY( c2.empty() ); +} + +void +test02() +{ + bool test __attribute__((unused)) = true; + + const test_type c0{ {1, 10}, {1, 11}, {2, 20}, {2, 21}, {3, 30}, {3, 31} }; + test_type c1 = c0; + std::multimap> c2( c0.begin(), c0.end() ); + + c1.merge(c2); + VERIFY( c1.size() == (2 * c0.size()) ); + for (auto& i : c1) + VERIFY( c1.count(i.first) == (2 * c0.count(i.first)) ); + VERIFY( c2.empty() ); + + c1.clear(); + c2.insert( c0.begin(), c0.end() ); + c1.merge(std::move(c2)); + VERIFY( c1 == c0 ); + VERIFY( c2.empty() ); +} + +void +test03() +{ + bool test __attribute__((unused)) = true; + + const test_type c0{ {1, 10}, {1, 11}, {2, 20}, {2, 21}, {3, 30}, {3, 31} }; + test_type c1 = c0; + std::multimap> c2( c0.begin(), c0.end() ); + + c1.merge(c2); + VERIFY( c1.size() == (2 * c0.size()) ); + for (auto& i : c1) + VERIFY( c1.count(i.first) == (2 * c0.count(i.first)) ); + VERIFY( c2.empty() ); + + c1.clear(); + c2.insert( c0.begin(), c0.end() ); + c1.merge(std::move(c2)); + VERIFY( c1 == c0 ); + VERIFY( c2.empty() ); +} + +void +test04() +{ + bool test __attribute__((unused)) = true; + + const test_type c0{ {1, 10}, {1, 11}, {2, 20}, {2, 21}, {3, 30}, {3, 31} }; + test_type c1 = c0; + std::map> c2( c0.begin(), c0.end() ); + + c1.merge(c2); + VERIFY( c1.size() == (1.5 * c0.size()) ); + for (auto& i : c1) + VERIFY( c1.count(i.first) == (1.5 * c0.count(i.first)) ); + VERIFY( c2.empty() ); + + c1.clear(); + c2.insert( c0.begin(), c0.end() ); + c1.merge(std::move(c2)); + VERIFY( c1.size() == (0.5 * c0.size()) ); + VERIFY( c2.empty() ); +} + +int +main() +{ + test01(); + test02(); + test03(); + test04(); +} diff --git a/libstdc++-v3/testsuite/23_containers/multiset/modifiers/extract.cc b/libstdc++-v3/testsuite/23_containers/multiset/modifiers/extract.cc new file mode 100644 index 00000000000..56c2a286f45 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/multiset/modifiers/extract.cc @@ -0,0 +1,129 @@ +// Copyright (C) 2016 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-options "-std=gnu++17" } + +#include +#include +#include + +using test_type = std::multiset; + +void +test01() +{ + bool test __attribute__((unused)) = true; + + test_type c{ 1, 1, 2, 2, 3, 3 }; + test_type::node_type node; + test_type::iterator pos; + + node = c.extract(0); + VERIFY( !node ); + VERIFY( node.empty() ); + VERIFY( c.size() == 6 ); + + pos = c.insert(std::move(node)); + VERIFY( !node ); + VERIFY( node.empty() ); + VERIFY( c.size() == 6 ); + VERIFY( pos == c.end() ); + + node = c.extract(1); + VERIFY( (bool)node ); + VERIFY( !node.empty() ); + VERIFY( c.size() == 5 ); + VERIFY( node.get_allocator() == c.get_allocator() ); + VERIFY( node.value() == 1 ); + + node.value() = 4; + VERIFY( node.value() == 4 ); + + pos = c.insert(std::move(node)); + VERIFY( !node ); + VERIFY( node.empty() ); + VERIFY( c.size() == 6 ); + VERIFY( pos != c.end() ); + VERIFY( *pos == 4 ); + VERIFY( c.count(1) == 1 ); + VERIFY( c.count(4) == 1 ); + VERIFY( std::is_sorted(c.begin(), c.end()) ); + + pos = c.insert(c.begin(), std::move(node)); + VERIFY( !node ); + VERIFY( node.empty() ); + VERIFY( c.size() == 6 ); + VERIFY( pos == c.end() ); + + node = c.extract(1); + pos = c.insert(c.begin(), std::move(node)); + VERIFY( !node ); + VERIFY( c.size() == 6 ); + VERIFY( pos != c.end() ); + VERIFY( *pos == 1 ); + + test_type c2 = c; + node = c2.extract(1); + pos = c.insert(std::move(node)); + VERIFY( pos != c.end() ); + VERIFY( node.empty() ); + VERIFY( *pos == 1 ); +} + +void +test02() +{ + bool test __attribute__((unused)) = true; + + test_type c{ 1, 1, 2, 2, 3, 3 }; + test_type::node_type node; + test_type::iterator pos; + + node = c.extract(c.begin()); + VERIFY( !node.empty() ); + VERIFY( c.size() == 5 ); + VERIFY( node.get_allocator() == c.get_allocator() ); + VERIFY( node.value() == 1 ); + + pos = c.insert(std::next(c.begin()), std::move(node)); + VERIFY( node.empty() ); + VERIFY( c.size() == 6 ); + VERIFY( pos != c.end() ); + VERIFY( *pos == 1 ); + VERIFY( pos == std::next(c.begin()) ); +} + +void +test03() +{ + struct less : std::less { }; + using std::is_same_v; + using compat_type1 = std::multiset; + static_assert( is_same_v ); + using compat_type2 = std::set; + static_assert( is_same_v ); + using compat_type3 = std::set; + static_assert( is_same_v ); +} + +int +main() +{ + test01(); + test02(); + test03(); +} diff --git a/libstdc++-v3/testsuite/23_containers/multiset/modifiers/merge.cc b/libstdc++-v3/testsuite/23_containers/multiset/modifiers/merge.cc new file mode 100644 index 00000000000..ba422b889c4 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/multiset/modifiers/merge.cc @@ -0,0 +1,117 @@ +// Copyright (C) 2016 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-options "-std=gnu++17" } + +#include +#include +#include + +using test_type = std::multiset; + +void +test01() +{ + bool test __attribute__((unused)) = true; + + test_type c0{ 1, 1, 2, 2, 3, 3 }; + test_type c1 = c0, c2 = c0; + + c1.merge(c2); + for (auto i : c1) + VERIFY( c1.count(i) == (2 * c0.count(i)) ); + VERIFY( c2.empty() ); + + c1.clear(); + c2 = c0; + c1.merge(std::move(c2)); + VERIFY( c1 == c0 ); + VERIFY( c2.empty() ); +} + +void +test02() +{ + bool test __attribute__((unused)) = true; + + test_type c0{ 1, 1, 2, 2, 3, 3 }; + test_type c1 = c0; + std::multiset> c2( c0.begin(), c0.end() ); + + c1.merge(c2); + VERIFY( c1.size() == (2 * c0.size()) ); + for (auto i : c1) + VERIFY( c1.count(i) == (2 * c0.count(i)) ); + VERIFY( c2.empty() ); + + c1.clear(); + c2.insert( c0.begin(), c0.end() ); + c1.merge(std::move(c2)); + VERIFY( c1 == c0 ); + VERIFY( c2.empty() ); +} + +void +test03() +{ + const test_type c0{ 1, 1, 2, 2, 3, 3 }; + test_type c1 = c0; + std::multiset> c2( c0.begin(), c0.end() ); + + c1.merge(c2); + VERIFY( c1.size() == (2 * c0.size()) ); + for (auto i : c1) + VERIFY( c1.count(i) == (2 * c0.count(i)) ); + VERIFY( c2.empty() ); + + c1.clear(); + c2.insert( c0.begin(), c0.end() ); + c1.merge(std::move(c2)); + VERIFY( c1 == c0 ); + VERIFY( c2.empty() ); +} + +void +test04() +{ + bool test __attribute__((unused)) = true; + + const test_type c0{ 1, 1, 2, 2, 3, 3 }; + test_type c1 = c0; + std::set> c2( c0.begin(), c0.end() ); + + c1.merge(c2); + VERIFY( c1.size() == (1.5 * c0.size()) ); + for (auto& i : c1) + VERIFY( c1.count(i) == (1.5 * c0.count(i)) ); + VERIFY( c2.empty() ); + + c1.clear(); + c2.insert( c0.begin(), c0.end() ); + c1.merge(std::move(c2)); + VERIFY( c1.size() == (0.5 * c0.size()) ); + VERIFY( c2.empty() ); +} + +int +main() +{ + test01(); + test02(); + test03(); + test04(); +} diff --git a/libstdc++-v3/testsuite/23_containers/set/modifiers/extract.cc b/libstdc++-v3/testsuite/23_containers/set/modifiers/extract.cc new file mode 100644 index 00000000000..db5872a499a --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/set/modifiers/extract.cc @@ -0,0 +1,138 @@ +// Copyright (C) 2016 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-options "-std=gnu++17" } + +#include +#include +#include + +using test_type = std::set; + +void +test01() +{ + bool test __attribute__((unused)) = true; + + test_type c{ 1, 2, 3 }; + test_type::node_type node; + test_type::insert_return_type ins; + test_type::iterator pos; + + node = c.extract(0); + VERIFY( !node ); + VERIFY( node.empty() ); + VERIFY( c.size() == 3 ); + + ins = c.insert(std::move(node)); + VERIFY( !node ); + VERIFY( node.empty() ); + VERIFY( c.size() == 3 ); + VERIFY( !ins.inserted ); + VERIFY( !ins.node ); + VERIFY( ins.position == c.end() ); + + node = c.extract(1); + VERIFY( (bool)node ); + VERIFY( !node.empty() ); + VERIFY( c.size() == 2 ); + VERIFY( node.get_allocator() == c.get_allocator() ); + VERIFY( node.value() == 1 ); + + node.value() = 4; + VERIFY( node.value() == 4 ); + + ins = c.insert(std::move(node)); + VERIFY( !node ); + VERIFY( node.empty() ); + VERIFY( c.size() == 3 ); + VERIFY( ins.inserted ); + VERIFY( !ins.node ); + VERIFY( ins.position != c.end() ); + VERIFY( *ins.position == 4 ); + VERIFY( c.count(1) == 0 ); + VERIFY( c.count(4) == 1 ); + VERIFY( std::is_sorted(c.begin(), c.end()) ); + + pos = c.insert(c.begin(), std::move(node)); + VERIFY( !node ); + VERIFY( node.empty() ); + VERIFY( c.size() == 3 ); + VERIFY( pos == c.end() ); + + node = c.extract(2); + pos = c.insert(c.begin(), std::move(node)); + VERIFY( c.size() == 3 ); + VERIFY( pos != c.end() ); + VERIFY( *pos == 2 ); + + test_type c2 = c; + node = c2.extract(3); + ins = c.insert(std::move(node)); + VERIFY( node.empty() ); + VERIFY( ins.position != c.end() ); + VERIFY( !ins.inserted ); + VERIFY( !ins.node.empty() ); + VERIFY( ins.node.value() == 3 ); + VERIFY( *ins.position == ins.node.value() ); +} + +void +test02() +{ + bool test __attribute__((unused)) = true; + + test_type c{ 1, 2, 3 }; + test_type::node_type node; + test_type::insert_return_type ins; + + node = c.extract(c.begin()); + VERIFY( (bool)node ); + VERIFY( !node.empty() ); + VERIFY( c.size() == 2 ); + VERIFY( node.get_allocator() == c.get_allocator() ); + VERIFY( node.value() == 1 ); + + ins = c.insert(std::move(node)); + VERIFY( node.empty() ); + VERIFY( c.size() == 3 ); + VERIFY( ins.inserted ); + VERIFY( !ins.node ); + VERIFY( ins.position != c.end() ); + VERIFY( *ins.position == 1 ); +} + +void +test03() +{ + struct less : std::less { }; + using std::is_same_v; + using compat_type1 = std::set; + static_assert( is_same_v ); + using compat_type2 = std::multiset; + static_assert( is_same_v ); + using compat_type3 = std::multiset; + static_assert( is_same_v ); +} + +int +main() +{ + test01(); + test02(); + test03(); +} diff --git a/libstdc++-v3/testsuite/23_containers/set/modifiers/merge.cc b/libstdc++-v3/testsuite/23_containers/set/modifiers/merge.cc new file mode 100644 index 00000000000..b1e06937b64 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/set/modifiers/merge.cc @@ -0,0 +1,143 @@ +// Copyright (C) 2016 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-options "-std=gnu++17" } + +#include +#include +#include + +using test_type = std::set; + +void +test01() +{ + bool test __attribute__((unused)) = true; + + const test_type c0{ 1, 2, 3 }; + test_type c1 = c0, c2 = c0; + c1.merge(c2); + VERIFY( c1 == c0 ); + VERIFY( c2 == c0 ); + + c1.clear(); + c1.merge(c2); + VERIFY( c1 == c0 ); + VERIFY( c2.empty() ); + + c2.merge(std::move(c1)); + VERIFY( c1.empty() ); + VERIFY( c2 == c0 ); +} + +void +test02() +{ + bool test __attribute__((unused)) = true; + + const test_type c0{ 1, 2, 3 }; + test_type c1 = c0; + std::set> c2( c0.begin(), c0.end() ); + c1.merge(c2); + VERIFY( c1 == c0 ); + VERIFY( std::equal(c2.begin(), c2.end(), c0.begin(), c0.end()) ); + + c1.clear(); + c1.merge(c2); + VERIFY( c1 == c0 ); + VERIFY( c2.empty() ); + + c2.merge(std::move(c1)); + VERIFY( c1.empty() ); + VERIFY( std::equal(c2.begin(), c2.end(), c0.begin(), c0.end()) ); +} + +void +test03() +{ + bool test __attribute__((unused)) = true; + + const test_type c0{ 1, 2, 3 }; + test_type c1 = c0; + std::set> c2( c0.begin(), c0.end() ); + c1.merge(c2); + VERIFY( c1 == c0 ); + VERIFY( std::equal(c2.rbegin(), c2.rend(), c0.begin(), c0.end()) ); + + c1.clear(); + c1.merge(c2); + VERIFY( c1 == c0 ); + VERIFY( c2.empty() ); + + c2.merge(c1); + VERIFY( c1.empty() ); + VERIFY( std::equal(c2.rbegin(), c2.rend(), c0.begin(), c0.end()) ); + + c1.merge(std::move(c2)); + VERIFY( c1 == c0 ); + VERIFY( c2.empty() ); +} + +void +test04() +{ + bool test __attribute__((unused)) = true; + + const test_type c0{ 1, 2, 3 }; + test_type c1 = c0; + std::multiset> c2( c0.begin(), c0.end() ); + c1.merge(c2); + VERIFY( c1 == c0 ); + VERIFY( std::equal(c2.rbegin(), c2.rend(), c0.begin(), c0.end()) ); + + c1.clear(); + c1.merge(c2); + VERIFY( c1 == c0 ); + VERIFY( c2.empty() ); + + c2.merge(c1); + VERIFY( c1.empty() ); + VERIFY( std::equal(c2.rbegin(), c2.rend(), c0.begin(), c0.end()) ); + + c1 = c0; + c2.merge(c1); + VERIFY( c1.empty() ); + VERIFY( c2.size() == (2 * c0.size()) ); + VERIFY( std::is_sorted(c2.begin(), c2.end(), c2.value_comp()) ); + + c1.merge(c2); + VERIFY( c1 == c0 ); + VERIFY( std::equal(c2.rbegin(), c2.rend(), c0.begin(), c0.end()) ); + + c1.merge(std::move(c2)); + VERIFY( c1 == c0 ); + VERIFY( std::equal(c2.rbegin(), c2.rend(), c0.begin(), c0.end()) ); + + c1.clear(); + c1.merge(std::move(c2)); + VERIFY( c1 == c0 ); + VERIFY( c2.empty() ); +} + +int +main() +{ + test01(); + test02(); + test03(); + test04(); +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/extract.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/extract.cc new file mode 100644 index 00000000000..9d9c43ef905 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/extract.cc @@ -0,0 +1,148 @@ +// Copyright (C) 2016 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-options "-std=gnu++17" } + +#include +#include + +using test_type = std::unordered_map; + +void +test01() +{ + bool test __attribute__((unused)) = true; + + test_type c{ {1, 10}, {2, 20}, {3, 30} }; + test_type::node_type node; + test_type::insert_return_type ins; + test_type::iterator pos; + + node = c.extract(0); + VERIFY( !node ); + VERIFY( node.empty() ); + VERIFY( c.size() == 3 ); + + ins = c.insert(std::move(node)); + VERIFY( !node ); + VERIFY( node.empty() ); + VERIFY( c.size() == 3 ); + VERIFY( !ins.inserted ); + VERIFY( !ins.node ); + VERIFY( ins.position == c.end() ); + + node = c.extract(1); + VERIFY( (bool)node ); + VERIFY( !node.empty() ); + VERIFY( c.size() == 2 ); + VERIFY( node.get_allocator() == c.get_allocator() ); + VERIFY( node.key() == 1 ); + VERIFY( node.mapped() == 10 ); + + node.key() = 4; + node.mapped() = 40; + VERIFY( node.key() == 4 ); + VERIFY( node.mapped() == 40 ); + + ins = c.insert(std::move(node)); + VERIFY( !node ); + VERIFY( node.empty() ); + VERIFY( c.size() == 3 ); + VERIFY( ins.inserted ); + VERIFY( !ins.node ); + VERIFY( ins.position != c.end() ); + VERIFY( ins.position->first == 4 ); + VERIFY( ins.position->second == 40 ); + VERIFY( c.count(1) == 0 ); + VERIFY( c.count(4) == 1 ); + + pos = c.insert(c.begin(), std::move(node)); + VERIFY( !node ); + VERIFY( node.empty() ); + VERIFY( c.size() == 3 ); + VERIFY( pos == c.end() ); + + pos = c.insert(c.begin(), c.extract(2)); + VERIFY( c.size() == 3 ); + VERIFY( pos != c.end() ); + VERIFY( pos->first == 2 ); + VERIFY( pos->second == 20 ); + + test_type c2 = c; + node = c2.extract(3); + ins = c.insert(std::move(node)); + VERIFY( node.empty() ); + VERIFY( ins.position != c.end() ); + VERIFY( !ins.inserted ); + VERIFY( !ins.node.empty() ); + VERIFY( ins.node.key() == 3 ); + VERIFY( ins.node.mapped() == 30 ); + auto hasher = c.hash_function(); + VERIFY( hasher(ins.position->first) == hasher(ins.node.key()) ); + auto eq = c.key_eq(); + VERIFY( eq(ins.position->first, ins.node.key()) ); +} + +void +test02() +{ + bool test __attribute__((unused)) = true; + + test_type c{ {1, 10}, {2, 20}, {3, 30} }; + test_type::node_type node; + test_type::insert_return_type ins; + + const int key = c.begin()->first; + node = c.extract(c.begin()); + VERIFY( (bool)node ); + VERIFY( !node.empty() ); + VERIFY( c.size() == 2 ); + VERIFY( node.get_allocator() == c.get_allocator() ); + VERIFY( node.key() == key ); + VERIFY( node.mapped() == (key * 10) ); + + ins = c.insert(std::move(node)); + VERIFY( node.empty() ); + VERIFY( c.size() == 3 ); + VERIFY( ins.inserted ); + VERIFY( !ins.node ); + VERIFY( ins.position != c.end() ); + VERIFY( ins.position->first == key ); + VERIFY( ins.position->second == (key * 10) ); +} + +void +test03() +{ + struct hash : std::hash { }; + struct equal : std::equal_to { }; + using std::is_same_v; + using compat_type1 = std::unordered_map; + static_assert( is_same_v ); + using compat_type2 = std::unordered_multimap; + static_assert( is_same_v ); + using compat_type3 = std::unordered_multimap; + static_assert( is_same_v ); +} + +int +main() +{ + test01(); + test02(); + test03(); +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/merge.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/merge.cc new file mode 100644 index 00000000000..f0035d2eb84 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/merge.cc @@ -0,0 +1,140 @@ +// Copyright (C) 2016 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-options "-std=gnu++17" } + +#include +#include +#include + +using test_type = std::unordered_map; + +struct hash { + auto operator()(int i) const noexcept { return ~std::hash()(i); } +}; +struct equal : std::equal_to<> { }; + +template +bool equal_elements(const C1& c1, const C2& c2) +{ + if (c2.size() != c1.size()) + return false; + for (auto& i : c1) + if (c2.count(i.first) != c1.count(i.first)) + return false; + return true; +} + +void +test01() +{ + bool test __attribute__((unused)) = true; + + const test_type c0{ {1, 10}, {2, 20}, {3, 30} }; + test_type c1 = c0, c2 = c0; + + c1.merge(c2); + VERIFY( c1 == c0 ); + VERIFY( c2 == c0 ); + + c1.clear(); + c1.merge(c2); + VERIFY( c1 == c0 ); + VERIFY( c2.empty() ); + + c2.merge(std::move(c1)); + VERIFY( c1.empty() ); + VERIFY( c2 == c0 ); +} + +void +test02() +{ + bool test __attribute__((unused)) = true; + + const test_type c0{ {1, 10}, {2, 20}, {3, 30} }; + test_type c1 = c0; + std::unordered_map c2( c0.begin(), c0.end() ); + + c1.merge(c2); + VERIFY( c1 == c0 ); + VERIFY( equal_elements(c2, c0) ); + + c1.clear(); + c1.merge(c2); + VERIFY( c1 == c0 ); + VERIFY( c2.empty() ); + + c2.merge(c1); + VERIFY( c1.empty() ); + VERIFY( equal_elements(c2, c0) ); + + c1.merge(std::move(c2)); + VERIFY( c2.empty() ); + VERIFY( c1 == c0 ); +} + +void +test03() +{ + bool test __attribute__((unused)) = true; + + const test_type c0{ {1, 10}, {2, 20}, {3, 30} }; + test_type c1 = c0; + std::unordered_multimap c2( c0.begin(), c0.end() ); + c1.merge(c2); + VERIFY( c1 == c0 ); + VERIFY( equal_elements(c2, c0) ); + + c1.clear(); + c1.merge(c2); + VERIFY( c1 == c0 ); + VERIFY( c2.empty() ); + + c2.merge(c1); + VERIFY( c1.empty() ); + VERIFY( equal_elements(c2, c0) ); + + c1 = c0; + c2.merge(c1); + VERIFY( c1.empty() ); + VERIFY( c2.size() == (2 * c0.size()) ); + VERIFY( c2.count(1) == 2 ); + VERIFY( c2.count(2) == 2 ); + VERIFY( c2.count(3) == 2 ); + + c1.merge(c2); + VERIFY( c1 == c0 ); + VERIFY( equal_elements(c2, c0) ); + + c1.merge(std::move(c2)); + VERIFY( c1 == c0 ); + VERIFY( equal_elements(c2, c0) ); + + c1.clear(); + c1.merge(std::move(c2)); + VERIFY( c1 == c0 ); + VERIFY( c2.empty() ); +} + +int +main() +{ + test01(); + test02(); + test03(); +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/extract.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/extract.cc new file mode 100644 index 00000000000..635e7d0acd3 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/extract.cc @@ -0,0 +1,138 @@ +// Copyright (C) 2016 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-options "-std=gnu++17" } + +#include +#include + +using test_type = std::unordered_multimap; + +void +test01() +{ + bool test __attribute__((unused)) = true; + + test_type c{ {1, 10}, { 1, 11 }, {2, 20}, { 2, 21}, {3, 30}, { 3, 31 } }; + test_type::node_type node; + test_type::iterator pos; + + node = c.extract(0); + VERIFY( !node ); + VERIFY( node.empty() ); + VERIFY( c.size() == 6 ); + + pos = c.insert(std::move(node)); + VERIFY( !node ); + VERIFY( node.empty() ); + VERIFY( c.size() == 6 ); + VERIFY( pos == c.end() ); + + node = c.extract(1); + VERIFY( (bool)node ); + VERIFY( !node.empty() ); + VERIFY( c.size() == 5 ); + VERIFY( node.get_allocator() == c.get_allocator() ); + VERIFY( node.key() == 1 ); + int mapped = node.mapped(); + VERIFY( mapped == 10 || mapped == 11 ); + + node.key() = 4; + node.mapped() = 40; + VERIFY( node.key() == 4 ); + VERIFY( node.mapped() == 40 ); + + pos = c.insert(std::move(node)); + VERIFY( !node ); + VERIFY( node.empty() ); + VERIFY( c.size() == 6 ); + VERIFY( pos != c.end() ); + VERIFY( pos->first == 4 ); + VERIFY( pos->second == 40 ); + + pos = c.insert(c.begin(), std::move(node)); + VERIFY( !node ); + VERIFY( node.empty() ); + VERIFY( c.size() == 6 ); + VERIFY( pos == c.end() ); + + node = c.extract(1); + mapped = node.mapped(); + pos = c.insert(c.begin(), std::move(node)); + VERIFY( !node ); + VERIFY( c.size() == 6 ); + VERIFY( pos != c.end() ); + VERIFY( pos->first == 1 ); + VERIFY( pos->second == mapped ); + + test_type c2 = c; + node = c2.extract(1); + mapped = node.mapped(); + pos = c.insert(std::move(node)); + VERIFY( pos != c.end() ); + VERIFY( node.empty() ); + VERIFY( pos->first == 1 ); + VERIFY( pos->second == mapped ); +} + +void +test02() +{ + bool test __attribute__((unused)) = true; + + test_type c{ {1, 10}, { 1, 11 }, {2, 20}, { 2, 21}, {3, 30}, { 3, 31 } }; + test_type::node_type node; + test_type::iterator pos; + + const int key = c.begin()->first; + const int mapped = c.begin()->second; + node = c.extract(c.begin()); + VERIFY( !node.empty() ); + VERIFY( c.size() == 5 ); + VERIFY( node.get_allocator() == c.get_allocator() ); + VERIFY( node.key() == key ); + VERIFY( node.mapped() == mapped ); + + pos = c.insert(std::move(node)); + VERIFY( node.empty() ); + VERIFY( c.size() == 6 ); + VERIFY( pos != c.end() ); + VERIFY( pos->first == key ); + VERIFY( pos->second == mapped ); +} + +void +test03() +{ + struct hash : std::hash { }; + struct equal : std::equal_to { }; + using std::is_same_v; + using compat_type1 = std::unordered_multimap; + static_assert( is_same_v ); + using compat_type2 = std::unordered_map; + static_assert( is_same_v ); + using compat_type3 = std::unordered_map; + static_assert( is_same_v ); +} + +int +main() +{ + test01(); + test02(); + test03(); +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/merge.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/merge.cc new file mode 100644 index 00000000000..3c67e3c28da --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/merge.cc @@ -0,0 +1,123 @@ +// Copyright (C) 2016 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-options "-std=gnu++17" } + +#include +#include +#include + +using test_type = std::unordered_multimap; +struct hash { + auto operator()(int i) const noexcept { return ~std::hash()(i); } +}; +struct equal : std::equal_to<> { }; + +void +test01() +{ + bool test __attribute__((unused)) = true; + + const test_type c0{ {1, 10}, {1, 11}, {2, 20}, {2, 21}, {3, 30}, {3, 31} }; + test_type c1 = c0, c2 = c0; + + c1.merge(c2); + for (auto& i : c1) + VERIFY( c1.count(i.first) == (2 * c0.count(i.first)) ); + VERIFY( c2.empty() ); + + c1.clear(); + c2 = c0; + c1.merge(std::move(c2)); + VERIFY( c1 == c0 ); + VERIFY( c2.empty() ); +} + +void +test02() +{ + bool test __attribute__((unused)) = true; + + const test_type c0{ {1, 10}, {1, 11}, {2, 20}, {2, 21}, {3, 30}, {3, 31} }; + test_type c1 = c0; + std::unordered_multimap c2( c0.begin(), c0.end() ); + + c1.merge(c2); + VERIFY( c1.size() == (2 * c0.size()) ); + for (auto& i : c1) + VERIFY( c1.count(i.first) == (2 * c0.count(i.first)) ); + VERIFY( c2.empty() ); + + c1.clear(); + c2.insert( c0.begin(), c0.end() ); + c1.merge(std::move(c2)); + VERIFY( c1 == c0 ); + VERIFY( c2.empty() ); +} + +void +test03() +{ + bool test __attribute__((unused)) = true; + + const test_type c0{ {1, 10}, {1, 11}, {2, 20}, {2, 21}, {3, 30}, {3, 31} }; + test_type c1 = c0; + std::unordered_multimap c2( c0.begin(), c0.end() ); + + c1.merge(c2); + VERIFY( c1.size() == (2 * c0.size()) ); + for (auto& i : c1) + VERIFY( c1.count(i.first) == (2 * c0.count(i.first)) ); + VERIFY( c2.empty() ); + + c1.clear(); + c2.insert( c0.begin(), c0.end() ); + c1.merge(std::move(c2)); + VERIFY( c1 == c0 ); + VERIFY( c2.empty() ); +} + +void +test04() +{ + bool test __attribute__((unused)) = true; + + const test_type c0{ {1, 10}, {1, 11}, {2, 20}, {2, 21}, {3, 30}, {3, 31} }; + test_type c1 = c0; + std::unordered_map c2( c0.begin(), c0.end() ); + + c1.merge(c2); + VERIFY( c1.size() == (1.5 * c0.size()) ); + for (auto& i : c1) + VERIFY( c1.count(i.first) == (1.5 * c0.count(i.first)) ); + VERIFY( c2.empty() ); + + c1.clear(); + c2.insert( c0.begin(), c0.end() ); + c1.merge(std::move(c2)); + VERIFY( c1.size() == (0.5 * c0.size()) ); + VERIFY( c2.empty() ); +} + +int +main() +{ + test01(); + test02(); + test03(); + test04(); +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/extract.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/extract.cc new file mode 100644 index 00000000000..e703dc41ca0 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/extract.cc @@ -0,0 +1,128 @@ +// Copyright (C) 2016 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-options "-std=gnu++17" } + +#include +#include + +using test_type = std::unordered_multiset; + +void +test01() +{ + bool test __attribute__((unused)) = true; + + test_type c{ 1, 1, 2, 2, 3, 3 }; + test_type::node_type node; + test_type::iterator pos; + + node = c.extract(0); + VERIFY( !node ); + VERIFY( node.empty() ); + VERIFY( c.size() == 6 ); + + pos = c.insert(std::move(node)); + VERIFY( !node ); + VERIFY( node.empty() ); + VERIFY( c.size() == 6 ); + VERIFY( pos == c.end() ); + + node = c.extract(1); + VERIFY( (bool)node ); + VERIFY( !node.empty() ); + VERIFY( c.size() == 5 ); + VERIFY( node.get_allocator() == c.get_allocator() ); + VERIFY( node.value() == 1 ); + + node.value() = 4; + VERIFY( node.value() == 4 ); + + pos = c.insert(std::move(node)); + VERIFY( !node ); + VERIFY( node.empty() ); + VERIFY( c.size() == 6 ); + VERIFY( pos != c.end() ); + VERIFY( *pos == 4 ); + VERIFY( c.count(1) == 1 ); + VERIFY( c.count(4) == 1 ); + + pos = c.insert(c.begin(), std::move(node)); + VERIFY( !node ); + VERIFY( node.empty() ); + VERIFY( c.size() == 6 ); + VERIFY( pos == c.end() ); + + node = c.extract(1); + pos = c.insert(c.begin(), std::move(node)); + VERIFY( !node ); + VERIFY( c.size() == 6 ); + VERIFY( pos != c.end() ); + VERIFY( *pos == 1 ); + + test_type c2 = c; + node = c2.extract(1); + pos = c.insert(std::move(node)); + VERIFY( pos != c.end() ); + VERIFY( node.empty() ); + VERIFY( *pos == 1 ); +} + +void +test02() +{ + bool test __attribute__((unused)) = true; + + test_type c{ 1, 1, 2, 2, 3, 3 }; + test_type::node_type node; + test_type::iterator pos; + + const int val = *c.begin(); + node = c.extract(c.begin()); + VERIFY( !node.empty() ); + VERIFY( c.size() == 5 ); + VERIFY( node.get_allocator() == c.get_allocator() ); + VERIFY( node.value() == val ); + + pos = c.insert(std::move(node)); + VERIFY( node.empty() ); + VERIFY( c.size() == 6 ); + VERIFY( pos != c.end() ); + VERIFY( *pos == val ); +} + +void +test03() +{ + struct hash : std::hash { }; + struct equal : std::equal_to { }; + using std::is_same_v; + using compat_type1 = std::unordered_multiset; + static_assert( is_same_v ); + using compat_type2 = std::unordered_set; + static_assert( is_same_v ); + using compat_type3 = std::unordered_set; + static_assert( is_same_v ); +} + +int +main() +{ + test01(); + test02(); + test03(); +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/merge.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/merge.cc new file mode 100644 index 00000000000..4ce4b84d717 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/merge.cc @@ -0,0 +1,121 @@ +// Copyright (C) 2016 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-options "-std=gnu++17" } + +#include +#include +#include + +using test_type = std::unordered_multiset; +struct hash { + auto operator()(int i) const noexcept { return ~std::hash()(i); } +}; +struct equal : std::equal_to<> { }; + +void +test01() +{ + bool test __attribute__((unused)) = true; + + test_type c0{ 1, 1, 2, 2, 3, 3 }; + test_type c1 = c0, c2 = c0; + + c1.merge(c2); + for (auto i : c1) + VERIFY( c1.count(i) == (2 * c0.count(i)) ); + VERIFY( c2.empty() ); + + c1.clear(); + c2 = c0; + c1.merge(std::move(c2)); + VERIFY( c1 == c0 ); + VERIFY( c2.empty() ); +} + +void +test02() +{ + bool test __attribute__((unused)) = true; + + test_type c0{ 1, 1, 2, 2, 3, 3 }; + test_type c1 = c0; + std::unordered_multiset c2( c0.begin(), c0.end() ); + + c1.merge(c2); + VERIFY( c1.size() == (2 * c0.size()) ); + for (auto i : c1) + VERIFY( c1.count(i) == (2 * c0.count(i)) ); + VERIFY( c2.empty() ); + + c1.clear(); + c2.insert( c0.begin(), c0.end() ); + c1.merge(std::move(c2)); + VERIFY( c1 == c0 ); + VERIFY( c2.empty() ); +} + +void +test03() +{ + const test_type c0{ 1, 1, 2, 2, 3, 3 }; + test_type c1 = c0; + std::unordered_multiset c2( c0.begin(), c0.end() ); + + c1.merge(c2); + VERIFY( c1.size() == (2 * c0.size()) ); + for (auto i : c1) + VERIFY( c1.count(i) == (2 * c0.count(i)) ); + VERIFY( c2.empty() ); + + c1.clear(); + c2.insert( c0.begin(), c0.end() ); + c1.merge(std::move(c2)); + VERIFY( c1 == c0 ); + VERIFY( c2.empty() ); +} + +void +test04() +{ + bool test __attribute__((unused)) = true; + + const test_type c0{ 1, 1, 2, 2, 3, 3 }; + test_type c1 = c0; + std::unordered_set c2( c0.begin(), c0.end() ); + + c1.merge(c2); + VERIFY( c1.size() == (1.5 * c0.size()) ); + for (auto& i : c1) + VERIFY( c1.count(i) == (1.5 * c0.count(i)) ); + VERIFY( c2.empty() ); + + c1.clear(); + c2.insert( c0.begin(), c0.end() ); + c1.merge(std::move(c2)); + VERIFY( c1.size() == (0.5 * c0.size()) ); + VERIFY( c2.empty() ); +} + +int +main() +{ + test01(); + test02(); + test03(); + test04(); +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/instantiation_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/instantiation_neg.cc index cc572fc90ca..5e8de37c440 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_set/instantiation_neg.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/instantiation_neg.cc @@ -18,7 +18,7 @@ // with this library; see the file COPYING3. If not see // . -// { dg-error "with noexcept" "" { target *-*-* } 265 } +// { dg-error "with noexcept" "" { target *-*-* } 268 } #include diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/extract.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/extract.cc new file mode 100644 index 00000000000..cb48cbcef4e --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/extract.cc @@ -0,0 +1,140 @@ +// Copyright (C) 2016 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-options "-std=gnu++17" } + +#include +#include + +using test_type = std::unordered_set; + +void +test01() +{ + bool test __attribute__((unused)) = true; + + test_type c{ 1, 2, 3 }; + test_type::node_type node; + test_type::insert_return_type ins; + test_type::iterator pos; + + node = c.extract(0); + VERIFY( !node ); + VERIFY( node.empty() ); + VERIFY( c.size() == 3 ); + + ins = c.insert(std::move(node)); + VERIFY( !node ); + VERIFY( node.empty() ); + VERIFY( c.size() == 3 ); + VERIFY( !ins.inserted ); + VERIFY( !ins.node ); + VERIFY( ins.position == c.end() ); + + node = c.extract(1); + VERIFY( (bool)node ); + VERIFY( !node.empty() ); + VERIFY( c.size() == 2 ); + VERIFY( node.get_allocator() == c.get_allocator() ); + VERIFY( node.value() == 1 ); + + node.value() = 4; + VERIFY( node.value() == 4 ); + + ins = c.insert(std::move(node)); + VERIFY( !node ); + VERIFY( node.empty() ); + VERIFY( c.size() == 3 ); + VERIFY( ins.inserted ); + VERIFY( !ins.node ); + VERIFY( ins.position != c.end() ); + VERIFY( *ins.position == 4 ); + VERIFY( c.count(1) == 0 ); + VERIFY( c.count(4) == 1 ); + + pos = c.insert(c.begin(), std::move(node)); + VERIFY( !node ); + VERIFY( node.empty() ); + VERIFY( c.size() == 3 ); + VERIFY( pos == c.end() ); + + pos = c.insert(c.begin(), c.extract(2)); + VERIFY( c.size() == 3 ); + VERIFY( pos != c.end() ); + VERIFY( *pos == 2 ); + + test_type c2 = c; + node = c2.extract(3); + ins = c.insert(std::move(node)); + VERIFY( node.empty() ); + VERIFY( ins.position != c.end() ); + VERIFY( !ins.inserted ); + VERIFY( !ins.node.empty() ); + VERIFY( ins.node.value() == 3 ); + auto hasher = c.hash_function(); + VERIFY( hasher(*ins.position) == hasher(ins.node.value()) ); + auto eq = c.key_eq(); + VERIFY( eq(*ins.position, ins.node.value()) ); +} + +void +test02() +{ + bool test __attribute__((unused)) = true; + + test_type c{ 1, 2, 3 }; + test_type::node_type node; + test_type::insert_return_type ins; + + const int val = *c.begin(); + node = c.extract(c.begin()); + VERIFY( (bool)node ); + VERIFY( !node.empty() ); + VERIFY( c.size() == 2 ); + VERIFY( node.get_allocator() == c.get_allocator() ); + VERIFY( node.value() == val ); + + ins = c.insert(std::move(node)); + VERIFY( node.empty() ); + VERIFY( c.size() == 3 ); + VERIFY( ins.inserted ); + VERIFY( !ins.node ); + VERIFY( ins.position != c.end() ); + VERIFY( *ins.position == val ); +} + +void +test03() +{ + struct hash : std::hash { }; + struct equal : std::equal_to { }; + using std::is_same_v; + using compat_type1 = std::unordered_set; + static_assert( is_same_v ); + using compat_type2 = std::unordered_multiset; + static_assert( is_same_v ); + using compat_type3 = std::unordered_multiset; + static_assert( is_same_v ); +} + +int +main() +{ + test01(); + test02(); + test03(); +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/merge.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/merge.cc new file mode 100644 index 00000000000..29387dd21f6 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/merge.cc @@ -0,0 +1,140 @@ +// Copyright (C) 2016 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-options "-std=gnu++17" } + +#include +#include +#include + +using test_type = std::unordered_set; + +struct hash { + auto operator()(int i) const noexcept { return ~std::hash()(i); } +}; +struct equal : std::equal_to<> { }; + +template +bool equal_elements(const C1& c1, const C2& c2) +{ + if (c2.size() != c1.size()) + return false; + for (auto& i : c1) + if (c2.count(i) != c1.count(i)) + return false; + return true; +} + +void +test01() +{ + bool test __attribute__((unused)) = true; + + const test_type c0{ 1, 2, 3, }; + test_type c1 = c0, c2 = c0; + + c1.merge(c2); + VERIFY( c1 == c0 ); + VERIFY( c2 == c0 ); + + c1.clear(); + c1.merge(c2); + VERIFY( c1 == c0 ); + VERIFY( c2.empty() ); + + c2.merge(std::move(c1)); + VERIFY( c1.empty() ); + VERIFY( c2 == c0 ); +} + +void +test02() +{ + bool test __attribute__((unused)) = true; + + const test_type c0{ 1, 2, 3, }; + test_type c1 = c0; + std::unordered_set c2( c0.begin(), c0.end() ); + + c1.merge(c2); + VERIFY( c1 == c0 ); + VERIFY( equal_elements(c2, c0) ); + + c1.clear(); + c1.merge(c2); + VERIFY( c1 == c0 ); + VERIFY( c2.empty() ); + + c2.merge(c1); + VERIFY( c1.empty() ); + VERIFY( equal_elements(c2, c0) ); + + c1.merge(std::move(c2)); + VERIFY( c2.empty() ); + VERIFY( c1 == c0 ); +} + +void +test03() +{ + bool test __attribute__((unused)) = true; + + const test_type c0{ 1, 2, 3, }; + test_type c1 = c0; + std::unordered_multiset c2( c0.begin(), c0.end() ); + c1.merge(c2); + VERIFY( c1 == c0 ); + VERIFY( equal_elements(c2, c0) ); + + c1.clear(); + c1.merge(c2); + VERIFY( c1 == c0 ); + VERIFY( c2.empty() ); + + c2.merge(c1); + VERIFY( c1.empty() ); + VERIFY( equal_elements(c2, c0) ); + + c1 = c0; + c2.merge(c1); + VERIFY( c1.empty() ); + VERIFY( c2.size() == (2 * c0.size()) ); + VERIFY( c2.count(1) == 2 ); + VERIFY( c2.count(2) == 2 ); + VERIFY( c2.count(3) == 2 ); + + c1.merge(c2); + VERIFY( c1 == c0 ); + VERIFY( equal_elements(c2, c0) ); + + c1.merge(std::move(c2)); + VERIFY( c1 == c0 ); + VERIFY( equal_elements(c2, c0) ); + + c1.clear(); + c1.merge(std::move(c2)); + VERIFY( c1 == c0 ); + VERIFY( c2.empty() ); +} + +int +main() +{ + test01(); + test02(); + test03(); +} diff --git a/libstdc++-v3/testsuite/libstdc++-prettyprinters/cxx17.cc b/libstdc++-v3/testsuite/libstdc++-prettyprinters/cxx17.cc index 09d79e9e59d..bc9b26a74f9 100644 --- a/libstdc++-v3/testsuite/libstdc++-prettyprinters/cxx17.cc +++ b/libstdc++-v3/testsuite/libstdc++-prettyprinters/cxx17.cc @@ -27,12 +27,15 @@ #include #include #include +#include #include using std::any; using std::optional; using std::variant; using std::string_view; +using std::map; +using std::unordered_set; int main() @@ -83,10 +86,21 @@ main() // { dg-final { note-test v3 {std::variant [index 1] = {3}} } } variant v4{ str }; // { dg-final { note-test v4 {std::variant [index 2] = {"string"}} } } - variant vref{str}; // { dg-final { note-test vref {std::variant > &> [index 0] = {"string"}} } } + map m{ {1, "one"} }; + map::node_type n0; +// { dg-final { note-test n0 {empty node handle for map}}} + map::node_type n1 = m.extract(1); +// { dg-final { note-test n1 {node handle for map with element = {{first = 1, second = "two"}}}}} + + unordered_set s{ 3, 4 }; + unordered_set::node_type n2; +// { dg-final { note-test n2 {empty node handle for unordered set}}} + unordered_set::node_type n3 = s.extract(3); +// { dg-final { note-test n1 {node handle for unordered set with element = {3}}}} + std::cout << "\n"; return 0; // Mark SPOT } -- 2.30.2