[PATCH 1/2] libstdc++: Add _M_key_compare helper to associative containers
Jonathan Wakely
jwakely@redhat.com
Thu Apr 24 22:14:03 GMT 2025
In r10-452-ge625ccc21a91f3 I noted that we don't have an accessor for
invoking _M_impl._M_key_compare in the associative containers. That
meant that the static assertions to check for valid comparison functions
were squirrelled away in _Rb_tree::_S_key instead. As Jason noted in
https://gcc.gnu.org/pipermail/gcc-patches/2025-April/681436.html this
means that the static assertions fail later than we'd like.
This change adds a new _Rb_tree::_M_key_compare member function which
invokes the _M_impl._M_key_compare function object, and then moves the
static_assert from _S_key into _M_key_compare.
Because the new function is const-qualified, we now treat LWG 2542 as a
DR for older standards, requiring the comparison function to be const
invocable. Previously we only enforced the LWG 2542 rule for C++17 and
later.
I did consider deprecating support for comparisons which aren't const
invocable, something like this:
// Before LWG 2542 it wasn't strictly necessary for _Compare to be
// const invocable, if you only used non-const container members.
// Define a non-const overload for pre-C++17, deprecated for C++11/14.
#if __cplusplus < 201103L
bool
_M_key_compare(const _Key& __k1, const _Key& __k2)
{ return _M_impl._M_key_compare(__k1, __k2); }
#elif __cplusplus < 201703L
template<typename _Key1, typename _Key2>
[[__deprecated__("support for comparison functions that are not "
"const invocable is deprecated")]]
__enable_if_t<
__and_<__is_invocable<_Compare&, const _Key1&, const _Key2&>,
__not_<__is_invocable<const _Compare&, const _Key1&, const _Key2&>>>::value,
bool>
_M_key_compare(const _Key1& __k1, const _Key2& __k2)
{
static_assert(
__is_invocable<_Compare&, const _Key&, const _Key&>::value,
"comparison object must be invocable with two arguments of key type"
);
return _M_impl._M_key_compare(__k1, __k2);
}
#endif // < C++17
But I decided that this isn't necessary, because we've been enforcing
the C++17 rule since GCC 8.4 and 9.2, and C++17 has been the default
since GCC 11.1. Users have had plenty of time to fix their invalid
comparison functions.
libstdc++-v3/ChangeLog:
* include/bits/stl_tree.h (_Rb_tree::_M_key_compare): New member
function to invoke comparison function.
(_Rb_tree): Use new member function instead of accessing the
comparison function directly.
---
Tested x86_64-linux.
libstdc++-v3/include/bits/stl_tree.h | 108 +++++++++++++--------------
1 file changed, 50 insertions(+), 58 deletions(-)
diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h
index 6b35f99a25a..c7352093933 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -1390,27 +1390,25 @@ namespace __rb_tree
_M_end() const _GLIBCXX_NOEXCEPT
{ return this->_M_impl._M_header._M_base_ptr(); }
+ // _GLIBCXX_RESOLVE_LIB_DEFECTS
+ // 2542. Missing const requirements for associative containers
+ template<typename _Key1, typename _Key2>
+ bool
+ _M_key_compare(const _Key1& __k1, const _Key2& __k2) const
+ {
+#if __cplusplus >= 201103L
+ // Enforce this here with a user-friendly message.
+ static_assert(
+ __is_invocable<const _Compare&, const _Key&, const _Key&>::value,
+ "comparison object must be invocable with two arguments of key type"
+ );
+# endif // C++17
+ return _M_impl._M_key_compare(__k1, __k2);
+ }
+
static const _Key&
_S_key(const _Node& __node)
- {
-#if __cplusplus >= 201103L
- // If we're asking for the key we're presumably using the comparison
- // object, and so this is a good place to sanity check it.
- static_assert(__is_invocable<_Compare&, const _Key&, const _Key&>{},
- "comparison object must be invocable "
- "with two arguments of key type");
-# if __cplusplus >= 201703L
- // _GLIBCXX_RESOLVE_LIB_DEFECTS
- // 2542. Missing const requirements for associative containers
- if constexpr (__is_invocable<_Compare&, const _Key&, const _Key&>{})
- static_assert(
- is_invocable_v<const _Compare&, const _Key&, const _Key&>,
- "comparison object must be invocable as const");
-# endif // C++17
-#endif // C++11
-
- return _KeyOfValue()(*__node._M_valptr());
- }
+ { return _KeyOfValue()(*__node._M_valptr()); }
static const _Key&
_S_key(_Base_ptr __x)
@@ -1933,7 +1931,7 @@ namespace __rb_tree
_M_find_tr(const _Kt& __k) const
{
const_iterator __j(_M_lower_bound_tr(__k));
- if (__j != end() && _M_impl._M_key_compare(__k, _S_key(__j._M_node)))
+ if (__j != end() && _M_key_compare(__k, _S_key(__j._M_node)))
__j = end();
return __j;
}
@@ -1955,7 +1953,7 @@ namespace __rb_tree
auto __x = _M_begin();
auto __y = _M_end();
while (__x)
- if (!_M_impl._M_key_compare(_S_key(__x), __k))
+ if (!_M_key_compare(_S_key(__x), __k))
{
__y = __x;
__x = _S_left(__x);
@@ -1973,7 +1971,7 @@ namespace __rb_tree
auto __x = _M_begin();
auto __y = _M_end();
while (__x)
- if (_M_impl._M_key_compare(__k, _S_key(__x)))
+ if (_M_key_compare(__k, _S_key(__x)))
{
__y = __x;
__x = _S_left(__x);
@@ -2474,8 +2472,8 @@ namespace __rb_tree
_NodeGen& __node_gen)
{
bool __insert_left = (__x || __p == _M_end()
- || _M_impl._M_key_compare(_KeyOfValue()(__v),
- _S_key(__p)));
+ || _M_key_compare(_KeyOfValue()(__v),
+ _S_key(__p)));
_Base_ptr __z =
__node_gen(_GLIBCXX_FORWARD(_Arg, __v))->_M_base_ptr();
@@ -2500,8 +2498,8 @@ namespace __rb_tree
#endif
{
bool __insert_left = (__p == _M_end()
- || !_M_impl._M_key_compare(_S_key(__p),
- _KeyOfValue()(__v)));
+ || !_M_key_compare(_S_key(__p),
+ _KeyOfValue()(__v)));
_Base_ptr __z =
_M_create_node(_GLIBCXX_FORWARD(_Arg, __v))->_M_base_ptr();
@@ -2529,7 +2527,7 @@ namespace __rb_tree
while (__x)
{
__y = __x;
- __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
+ __x = !_M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
_S_left(__x) : _S_right(__x);
}
return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v));
@@ -2601,7 +2599,7 @@ namespace __rb_tree
const _Key& __k) const
{
while (__x)
- if (!_M_impl._M_key_compare(_S_key(__x), __k))
+ if (!_M_key_compare(_S_key(__x), __k))
__y = __x, __x = _S_left(__x);
else
__x = _S_right(__x);
@@ -2617,7 +2615,7 @@ namespace __rb_tree
const _Key& __k) const
{
while (__x)
- if (_M_impl._M_key_compare(__k, _S_key(__x)))
+ if (_M_key_compare(__k, _S_key(__x)))
__y = __x, __x = _S_left(__x);
else
__x = _S_right(__x);
@@ -2639,9 +2637,9 @@ namespace __rb_tree
_Base_ptr __y = _M_end();
while (__x)
{
- if (_M_impl._M_key_compare(_S_key(__x), __k))
+ if (_M_key_compare(_S_key(__x), __k))
__x = _S_right(__x);
- else if (_M_impl._M_key_compare(__k, _S_key(__x)))
+ else if (_M_key_compare(__k, _S_key(__x)))
__y = __x, __x = _S_left(__x);
else
{
@@ -2671,9 +2669,9 @@ namespace __rb_tree
_Base_ptr __y = _M_end();
while (__x)
{
- if (_M_impl._M_key_compare(_S_key(__x), __k))
+ if (_M_key_compare(_S_key(__x), __k))
__x = _S_right(__x);
- else if (_M_impl._M_key_compare(__k, _S_key(__x)))
+ else if (_M_key_compare(__k, _S_key(__x)))
__y = __x, __x = _S_left(__x);
else
{
@@ -2737,7 +2735,7 @@ namespace __rb_tree
while (__x)
{
__y = __x;
- __comp = _M_impl._M_key_compare(__k, _S_key(__x));
+ __comp = _M_key_compare(__k, _S_key(__x));
__x = __comp ? _S_left(__x) : _S_right(__x);
}
iterator __j = iterator(__y);
@@ -2748,7 +2746,7 @@ namespace __rb_tree
else
--__j;
}
- if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
+ if (_M_key_compare(_S_key(__j._M_node), __k))
return _Res(__x, __y);
return _Res(__j._M_node, _Base_ptr());
}
@@ -2768,8 +2766,7 @@ namespace __rb_tree
while (__x)
{
__y = __x;
- __x = _M_impl._M_key_compare(__k, _S_key(__x)) ?
- _S_left(__x) : _S_right(__x);
+ __x = _M_key_compare(__k, _S_key(__x)) ? _S_left(__x) : _S_right(__x);
}
return _Res(__x, __y);
}
@@ -2838,19 +2835,18 @@ namespace __rb_tree
// end()
if (__position._M_node == _M_end())
{
- if (size() > 0
- && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k))
+ if (size() > 0 && _M_key_compare(_S_key(_M_rightmost()), __k))
return _Res(_Base_ptr(), _M_rightmost());
else
return _M_get_insert_unique_pos(__k);
}
- else if (_M_impl._M_key_compare(__k, _S_key(__position._M_node)))
+ else if (_M_key_compare(__k, _S_key(__position._M_node)))
{
// First, try before...
iterator __before(__position._M_node);
if (__position._M_node == _M_leftmost()) // begin()
return _Res(_M_leftmost(), _M_leftmost());
- else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k))
+ else if (_M_key_compare(_S_key((--__before)._M_node), __k))
{
if (!_S_right(__before._M_node))
return _Res(_Base_ptr(), __before._M_node);
@@ -2860,13 +2856,13 @@ namespace __rb_tree
else
return _M_get_insert_unique_pos(__k);
}
- else if (_M_impl._M_key_compare(_S_key(__position._M_node), __k))
+ else if (_M_key_compare(_S_key(__position._M_node), __k))
{
// ... then try after.
iterator __after(__position._M_node);
if (__position._M_node == _M_rightmost())
return _Res(_Base_ptr(), _M_rightmost());
- else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node)))
+ else if (_M_key_compare(__k, _S_key((++__after)._M_node)))
{
if (!_S_right(__position._M_node))
return _Res(_Base_ptr(), __position._M_node);
@@ -2923,18 +2919,18 @@ namespace __rb_tree
if (__position._M_node == _M_end())
{
if (size() > 0
- && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost())))
+ && !_M_key_compare(__k, _S_key(_M_rightmost())))
return _Res(_Base_ptr(), _M_rightmost());
else
return _M_get_insert_equal_pos(__k);
}
- else if (!_M_impl._M_key_compare(_S_key(__position._M_node), __k))
+ else if (!_M_key_compare(_S_key(__position._M_node), __k))
{
// First, try before...
iterator __before(__position._M_node);
if (__position._M_node == _M_leftmost()) // begin()
return _Res(_M_leftmost(), _M_leftmost());
- else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node)))
+ else if (!_M_key_compare(__k, _S_key((--__before)._M_node)))
{
if (!_S_right(__before._M_node))
return _Res(_Base_ptr(), __before._M_node);
@@ -2950,7 +2946,7 @@ namespace __rb_tree
iterator __after(__position._M_node);
if (__position._M_node == _M_rightmost())
return _Res(_Base_ptr(), _M_rightmost());
- else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k))
+ else if (!_M_key_compare(_S_key((++__after)._M_node), __k))
{
if (!_S_right(__position._M_node))
return _Res(_Base_ptr(), __position._M_node);
@@ -2999,8 +2995,7 @@ namespace __rb_tree
-> iterator
{
bool __insert_left = (__x || __p == _M_end()
- || _M_impl._M_key_compare(_S_key(__z),
- _S_key(__p)));
+ || _M_key_compare(_S_key(__z), _S_key(__p)));
_Base_ptr __base_z = __z->_M_base_ptr();
_Node_traits::_S_insert_and_rebalance
@@ -3017,8 +3012,7 @@ namespace __rb_tree
-> iterator
{
bool __insert_left = (__p == _M_end()
- || !_M_impl._M_key_compare(_S_key(__p),
- _S_key(__z)));
+ || !_M_key_compare(_S_key(__p), _S_key(__z)));
_Base_ptr __base_z = __z->_M_base_ptr();
_Node_traits::_S_insert_and_rebalance
@@ -3039,7 +3033,7 @@ namespace __rb_tree
while (__x)
{
__y = __x;
- __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ?
+ __x = !_M_key_compare(_S_key(__x), _S_key(__z)) ?
_S_left(__x) : _S_right(__x);
}
return _M_insert_lower_node(__y, __z);
@@ -3151,8 +3145,7 @@ namespace __rb_tree
{
iterator __j(_M_lower_bound(_M_begin(), _M_end(), __k));
return (__j == end()
- || _M_impl._M_key_compare(__k,
- _S_key(__j._M_node))) ? end() : __j;
+ || _M_key_compare(__k, _S_key(__j._M_node))) ? end() : __j;
}
template<typename _Key, typename _Val, typename _KeyOfValue,
@@ -3164,8 +3157,7 @@ namespace __rb_tree
{
const_iterator __j(_M_lower_bound(_M_begin(), _M_end(), __k));
return (__j == end()
- || _M_impl._M_key_compare(__k,
- _S_key(__j._M_node))) ? end() : __j;
+ || _M_key_compare(__k, _S_key(__j._M_node))) ? end() : __j;
}
template<typename _Key, typename _Val, typename _KeyOfValue,
@@ -3205,9 +3197,9 @@ namespace __rb_tree
|| (__R && __R->_M_color == _S_red))
return false;
- if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
+ if (__L && _M_key_compare(_S_key(__x), _S_key(__L)))
return false;
- if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
+ if (__R && _M_key_compare(_S_key(__R), _S_key(__x)))
return false;
if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
--
2.49.0
More information about the Libstdc++
mailing list