Implement the debug versions of new overloads from P2077.
Also, make existing unordered_set<>::erase perform the same
bucket check as erase on unordered_multimap.
libstdc++-v3/ChangeLog:
PR libstdc++/117402
* include/debug/map.h (extract, erase): Define overloads.
* include/debug/multimap.h: Same.
* include/debug/multiset.h: Same.
* include/debug/set.h: Same.
* include/debug/unordered_map: Same (2x).
* include/debug/unordered_set: Same (2x).
---
libstdc++-v3/include/debug/map.h | 30 ++++++++++++
libstdc++-v3/include/debug/multimap.h | 27 +++++++++++
libstdc++-v3/include/debug/multiset.h | 27 +++++++++++
libstdc++-v3/include/debug/set.h | 30 ++++++++++++
libstdc++-v3/include/debug/unordered_map | 49 +++++++++++++++++++
libstdc++-v3/include/debug/unordered_set | 62 +++++++++++++++++++++---
6 files changed, 219 insertions(+), 6 deletions(-)
diff --git a/libstdc++-v3/include/debug/map.h b/libstdc++-v3/include/debug/map.h
index 0fc7afae385..29363a08d4d 100644
--- a/libstdc++-v3/include/debug/map.h
+++ b/libstdc++-v3/include/debug/map.h
@@ -476,6 +476,16 @@ namespace __debug
return {};
}
+# ifdef __glibcxx_heterogeneous_container_erasure
+ template <__heterogeneous_tree_key<map> _Kt>
+ node_type
+ extract(_Kt&& __key)
+ {
+ const auto __position = _Base::find<_Kt>(__key);
+ return __position != end() ? extract(__position) : {};
+ }
+# endif
+
insert_return_type
insert(node_type&& __nh)
{
@@ -538,6 +548,26 @@ namespace __debug
}
}
+# ifdef __glibcxx_heterogeneous_container_erasure
+ // Note that for some types _Kt this may erase more than
+ // one element, such as if _Kt::operator< checks only part
+ // of the key.
+ template <__heterogeneous_tree_key<map> _Kt>
+ size_type
+ erase(_Kt&& __x)
+ {
+ auto __victims = _Base::equal_range<_Kt>(__x);
+ size_type __count = 0;
+ for (auto __victim = __victims.first; __victim != __victims.second;)
+ {
+ this->_M_invalidate_if(_Equal(__victim));
+ _Base::erase(__victim++);
+ ++__count;
+ }
+ return __count;
+ }
+# endif
+
#if __cplusplus >= 201103L
iterator
erase(const_iterator __first, const_iterator __last)
diff --git a/libstdc++-v3/include/debug/multimap.h
b/libstdc++-v3/include/debug/multimap.h
index 4137186c527..ba6e9498710 100644
--- a/libstdc++-v3/include/debug/multimap.h
+++ b/libstdc++-v3/include/debug/multimap.h
@@ -360,6 +360,16 @@ namespace __debug
return {};
}
+# ifdef __glibcxx_heterogeneous_container_erasure
+ template <__heterogeneous_tree_key<multimap> _Kt>
+ node_type
+ extract(_Kt&& __key)
+ {
+ const auto __position = _Base::find<_Kt>(__key);
+ return __position != end() ? extract(__position) : {};
+ }
+# endif
+
iterator
insert(node_type&& __nh)
{ return { _Base::insert(std::move(__nh)), this }; }
@@ -420,6 +430,23 @@ namespace __debug
return __count;
}
+# ifdef __glibcxx_heterogeneous_container_erasure
+ template <__heterogeneous_tree_key<multimap> _Kt>
+ size_type
+ erase(_Kt&& __x)
+ {
+ auto __victims = _Base::equal_range<_Kt>(__x);
+ size_type __count = 0;
+ for (auto __victim = __victims.first; __victim != __victims.second;)
+ {
+ this->_M_invalidate_if(_Equal(__victim));
+ _Base::erase(__victim++);
+ ++__count;
+ }
+ return __count;
+ }
+# endif
+
#if __cplusplus >= 201103L
iterator
erase(const_iterator __first, const_iterator __last)
diff --git a/libstdc++-v3/include/debug/multiset.h
b/libstdc++-v3/include/debug/multiset.h
index 6fa499228f5..c8e34f704b4 100644
--- a/libstdc++-v3/include/debug/multiset.h
+++ b/libstdc++-v3/include/debug/multiset.h
@@ -331,6 +331,16 @@ namespace __debug
return {};
}
+# ifdef __glibcxx_heterogeneous_container_erasure
+ template <__heterogeneous_tree_key<multiset> _Kt>
+ node_type
+ extract(_Kt&& __key)
+ {
+ const auto __position = _Base::find<_Kt>(__key);
+ return __position != end() ? extract(__position) : {};
+ }
+#endif
+
iterator
insert(node_type&& __nh)
{ return { _Base::insert(std::move(__nh)), this }; }
@@ -387,6 +397,23 @@ namespace __debug
return __count;
}
+# ifdef __glibcxx_heterogeneous_container_erasure
+ template <__heterogeneous_tree_key<multiset> _Kt>
+ size_type
+ erase(_Kt&& __x)
+ {
+ auto __victims = _Base::equal_range<_Kt>(__x);
+ size_type __count = 0;
+ for (auto __victim = __victims.first; __victim != __victims.second;)
+ {
+ this->_M_invalidate_if(_Equal(__victim));
+ _Base::erase(__victim++);
+ ++__count;
+ }
+ return __count;
+ }
+# endif
+
#if __cplusplus >= 201103L
_GLIBCXX_ABI_TAG_CXX11
iterator
diff --git a/libstdc++-v3/include/debug/set.h b/libstdc++-v3/include/debug/set.h
index 99701d4a6d7..9a3bcce41fa 100644
--- a/libstdc++-v3/include/debug/set.h
+++ b/libstdc++-v3/include/debug/set.h
@@ -340,6 +340,16 @@ namespace __debug
return {};
}
+# ifdef __glibcxx_heterogeneous_container_erasure
+ template <__heterogeneous_tree_key<set> _Kt>
+ node_type
+ extract(_Kt&& __key)
+ {
+ const auto __position = _Base::find<_Kt>(__key);
+ return __position != end() ? extract(__position) : {};
+ }
+#endif
+
insert_return_type
insert(node_type&& __nh)
{
@@ -398,6 +408,26 @@ namespace __debug
}
}
+# ifdef __glibcxx_heterogeneous_container_erasure
+ // Note that for some types _Kt this may erase more than
+ // one element, such as if _Kt::operator< checks only part
+ // of the key.
+ template <__heterogeneous_tree_key<set> _Kt>
+ size_type
+ erase(_Kt&& __x)
+ {
+ auto __victims = _Base::equal_range<_Kt>(__x);
+ size_type __count = 0;
+ for (auto __victim = __victims.first; __victim != __victims.second;)
+ {
+ this->_M_invalidate_if(_Equal(__victim));
+ _Base::erase(__victim++);
+ ++__count;
+ }
+ return __count;
+ }
+#endif
+
#if __cplusplus >= 201103L
_GLIBCXX_ABI_TAG_CXX11
iterator
diff --git a/libstdc++-v3/include/debug/unordered_map
b/libstdc++-v3/include/debug/unordered_map
index 4bde18c917b..e90d1078241 100644
--- a/libstdc++-v3/include/debug/unordered_map
+++ b/libstdc++-v3/include/debug/unordered_map
@@ -581,6 +581,16 @@ namespace __debug
return {};
}
+# ifdef __glibcxx_heterogeneous_container_erasure
+ template <__heterogeneous_tree_key<unordered_map> _Kt>
+ node_type
+ extract(_Kt&& __key)
+ {
+ const auto __position = _Base::find<_Kt>(__key);
+ return __position != _Base::end() ? _M_extract(__position) : {};
+ }
+#endif
+
insert_return_type
insert(node_type&& __nh)
{
@@ -713,6 +723,16 @@ namespace __debug
return __ret;
}
+# ifdef __glibcxx_heterogeneous_container_erasure
+ template <__heterogeneous_tree_key<unordered_map> _Kt>
+ size_type
+ erase(_Kt&& __key)
+ {
+ auto __victim = _Base::find<_Kt>(__key);
+ return __victim != _Base::end() ? _M_erase(__victim), 1 : 0;
+ }
+#endif
+
iterator
erase(const_iterator __it)
{
@@ -1381,6 +1401,16 @@ namespace __debug
return {};
}
+# ifdef __glibcxx_heterogeneous_container_erasure
+ template <__heterogeneous_tree_key<unordered_multimap> _Kt>
+ node_type
+ extract(_Kt&& __key)
+ {
+ const auto __position = _Base::find<_Kt>(__key);
+ return __position != _Base::end() ? _M_extract(__position) : {};
+ }
+#endif
+
iterator
insert(node_type&& __nh)
{ return { _Base::insert(std::move(__nh)), this }; }
@@ -1510,6 +1540,25 @@ namespace __debug
return __ret;
}
+# ifdef __glibcxx_heterogeneous_container_erasure
+ template <__heterogeneous_tree_key<unordered_multimap> _Kt>
+ size_type
+ erase(_Kt&& __key)
+ {
+ size_type __count(0);
+ size_type __bucket_count = this->bucket_count();
+ auto __victims = _Base::equal_range<_Kt>(__key);
+ for (auto __victim = __victims.first; __victim != __victims.second;)
+ {
+ _M_invalidate(__victim);
+ __victim = _Base::erase(__victim);
+ ++__count;
+ }
+ _M_check_rehashed(__bucket_count);
+ return __count;
+ }
+#endif
+
iterator
erase(const_iterator __it)
{
diff --git a/libstdc++-v3/include/debug/unordered_set
b/libstdc++-v3/include/debug/unordered_set
index de999a76890..6f4f4ae8f96 100644
--- a/libstdc++-v3/include/debug/unordered_set
+++ b/libstdc++-v3/include/debug/unordered_set
@@ -468,6 +468,16 @@ namespace __debug
return {};
}
+# ifdef __glibcxx_heterogeneous_container_erasure
+ template <__heterogeneous_tree_key<unordered_set> _Kt>
+ node_type
+ extract(_Kt&& __key)
+ {
+ const auto __position = _Base::find<_Kt>(__key);
+ return __position != _Base::end() ? _M_extract(__position) : {};
+ }
+#endif
+
insert_return_type
insert(node_type&& __nh)
{
@@ -598,6 +608,16 @@ namespace __debug
return __ret;
}
+# ifdef __glibcxx_heterogeneous_container_erasure
+ template <__heterogeneous_tree_key<unordered_set> _Kt>
+ size_type
+ erase(_Kt&& __x)
+ {
+ auto __victim = _Base::find<_Kt>(__key);
+ return __victim != _Base::end() ? _M_erase(__victim), 1 : 0;
+ }
+#endif
+
iterator
erase(const_iterator __it)
{
@@ -1202,6 +1222,16 @@ namespace __debug
return {};
}
+# ifdef __glibcxx_heterogeneous_container_erasure
+ template <__heterogeneous_tree_key<unordered_multiset> _Kt>
+ node_type
+ extract(const _Kt& __key)
+ {
+ const auto __position = _Base::find<_Kt>(__key);
+ return __position != _Base::end() ? _M_extract(__position) : {};
+ }
+#endif
+
iterator
insert(node_type&& __nh)
{ return { _Base::insert(std::move(__nh)), this }; }
@@ -1318,18 +1348,38 @@ namespace __debug
size_type
erase(const key_type& __key)
{
- size_type __ret(0);
- auto __pair = _Base::equal_range(__key);
- for (auto __victim = __pair.first; __victim != __pair.second;)
+ size_type __count(0);
+ size_type __bucket_count = this->bucket_count();
+ auto __victims = _Base::equal_range(__key);
+ for (auto __victim = __victims.first; __victim != __victims.second;)
{
_M_invalidate(__victim);
__victim = _Base::erase(__victim);
- ++__ret;
+ ++__count;
}
-
- return __ret;
+ _M_check_rehashed(__bucket_count);
+ return __count;
}
+# ifdef __glibcxx_heterogeneous_container_erasure
+ template <__heterogeneous_tree_key<unordered_multiset> _Kt>
+ size_type
+ erase(_Kt&& __key)
+ {
+ size_type __count(0);
+ size_type __bucket_count = this->bucket_count();
+ auto __victims = _Base::equal_range<_Kt>(__key);
+ for (auto __victim = __victims.first; __victim != __victims.second;)
+ {
+ _M_invalidate(__victim);
+ __victim = _Base::erase(__victim);
+ ++__count;
+ }
+ _M_check_rehashed(__bucket_count);
+ return __count;
+ }
+#endif
+
iterator
erase(const_iterator __it)
{
--
2.52.0
