Make associative container operators inline friend

François Dumont frs.dumont@gmail.com
Tue Oct 2 20:55:00 GMT 2018 

On 09/28/2018 01:51 PM, Jonathan Wakely wrote:
> Please remember to CC the gcc-patches list for all patches.
>
> On 27/09/18 22:38 +0200, François Dumont wrote:
>> Hi
>>
>>     Here is a patch to make all associative containers operators 
>> inline friends. This is for both container operators themselves and 
>> their associated iterators.
>>
>>     Note that I also remove iterator/const_iterator == and != 
>> operators. They are useless as iterator can be implicitly converted 
>> into const_iterator so as soon as there is a mix the conversion will 
>> take place (and is cheap). Do you see an ABI issue ?
>
> There's no ABI issue, and as these are only internal types I don't see
> any problems that can arise when trying to compare types that are
> convertible to these iterators. So this seems OK.
>
>>     I also wonder if Doxygen will properly manage doc on operators I 
>> kept when moving those inline.
>
> Yes it should be OK.
>
>>     Before I came to this result I faced some problems which make me 
>> introduce the _Rb_tree cbegin and cend and use it to avoid sometimes 
>> iterator/const_iterator comparisons or conversions. Even if 
>> eventually useless I propose to keep it.
>>
>>     I also benefit from C++11 syntax simplifications in 
>> _GLIBCXX_DEBUG associatives containers implementations.
>
> Those changes to use C++11 syntax in the debug containers are OK, but
> they can be a separate commit from the changes to make operators
> inline friends (and need to be mentioned in the changelog).

Ok I'll commit those soon with proper ChangeLog.

>
>
>>     * include/bits/stl_tree.h
>>     (_Rb_tree_iterator<>::operator==): Make inline friend.
>>     (_Rb_tree_iterator<>::operator!=): Make inline friend.
>>     (_Rb_tree_const_iterator<>::operator==): Make inline friend.
>>     (_Rb_tree_const_iterator<>::operator!=): Make inline friend.
>>     (operator==(const _Rb_tree_iterator<>&,
>>     const _Rb_tree_const_iterator&)): Remove.
>>     (operator!=(const _Rb_tree_iterator<>&,
>>     const _Rb_tree_const_iterator&)): Remove.
>
> These are OK, but ...
>
>>     (_Rb_tree<>::cbegin()): New.
>>     (_Rb_tree<>::cend()): New.
>
> In C++98/C++03 the names "cbegin" and "cend" are not reserved, so this
> change breaks this valid C++98 program:
>
> #define cbegin 1
> #define cend 1
> #include <set>
> int main() { }
Ok, I reverted this part.
>
>>     (operator==(const _Rb_tree<>&, const _Rb_tree<>&)): Make inline 
>> friend.
>>     (operator!=(const _Rb_tree<>&, const _Rb_tree<>&)): Likewise.
>>     (operator<(const _Rb_tree<>&, const _Rb_tree<>&)): Likewise.
>>     (operator>(const _Rb_tree<>&, const _Rb_tree<>&)): Likewise.
>>     (operator<=(const _Rb_tree<>&, const _Rb_tree<>&)): Likewise.
>>     (operator>=(const _Rb_tree<>&, const _Rb_tree<>&)): Likewise.
>
> These changes to _Rb_tree operators are OK, but ...
>
>>     * include/bits/stl_map.h
>>     (operator==(const map<>&, const map<>&)): Make inline friend.
>>     (operator!=(const map<>&, const map<>&)): Likewise.
>>     (operator<(const map<>&, const map<>&)): Likewise.
>>     (operator>(const map<>&, const map<>&)): Likewise.
>>     (operator<=(const map<>&, const map<>&)): Likewise.
>>     (operator>=(const map<>&, const map<>&)): Likewise.
>
> These are not. The operators are declared at namespace scope in the
> standard, so we need to also declare them at namespace scope. They
> cannot be hidden friends (this is unfortunate, but it's what the
> standard says).

I consider the Table 83 - Container requirements where it is only saying 
that a == b should be well defined without namespace consideration. But 
I won't argue on Standard details with you, I'll revert that part.

>
> And it looks like these are missing from the patch anyway:
>
>>     * include/bits/stl_set.h
>>     (operator==(const set<>&, const set<>&)): Make inline friend.
>>     (operator!=(const set<>&, const set<>&)): Likewise.
>>     (operator<(const set<>&, const set<>&)): Likewise.
>>     (operator>(const set<>&, const set<>&)): Likewise.
>>     (operator<=(const set<>&, const set<>&)): Likewise.
>>     (operator>=(const set<>&, const set<>&)): Likewise.
>>     * include/bits/stl_multiset.h
>>     (operator==(const multiset<>&, const multiset<>&)): Make inline 
>> friend.
>>     (operator!=(const multiset<>&, const multiset<>&)): Likewise.
>>     (operator<(const multiset<>&, const multiset<>&)): Likewise.
>>     (operator>(const multiset<>&, const multiset<>&)): Likewise.
>>     (operator<=(const multiset<>&, const multiset<>&)): Likewise.
>>     (operator>=(const multiset<>&, const multiset<>&)): Likewise.
>
>
>> When building attached test case the compiler is proposing 73 
>> operator== candidates before the patch and 69 after, respectively 69 
>> and 63 in Debug mode.
>
> Wow, that number of overloads is so horrible. Unfortunately, I think
> we can only reduce that number by one  :-(
>
>> Ok to commit ?
>
> No, sorry.
>
> The changes to the operators for _Rb_tree and its iterators are OK,
> but see the question below.
>
> The changes to use C++11 syntax in the debug containers are OK.
>
Ok, I'll go with those parts as soon I've completed the cleanup.
>
>
>>
>> François
>>
>
>> diff --git a/libstdc++-v3/include/bits/stl_tree.h 
>> b/libstdc++-v3/include/bits/stl_tree.h
>> index 70d7483c7b1..5a0b5b8e9f6 100644
>> --- a/libstdc++-v3/include/bits/stl_tree.h
>> +++ b/libstdc++-v3/include/bits/stl_tree.h
>> @@ -1616,55 +1612,37 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>>         }
>>     }
>> #endif // C++17
>> -    };
>>
>> -  template<typename _Key, typename _Val, typename _KeyOfValue,
>> -       typename _Compare, typename _Alloc>
>> -    inline bool
>> -    operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, 
>> _Alloc>& __x,
>> -           const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, 
>> _Alloc>& __y)
>> +      friend bool
>> +      operator==(const _Rb_tree& __x, const _Rb_tree& __y)
>>       {
>>     return __x.size() == __y.size()
>>       && std::equal(__x.begin(), __x.end(), __y.begin());
>>       }
>>
>> -  template<typename _Key, typename _Val, typename _KeyOfValue,
>> -       typename _Compare, typename _Alloc>
>> -    inline bool
>> -    operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, 
>> _Alloc>& __x,
>> -          const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& 
>> __y)
>> +      friend bool
>> +      operator<(const _Rb_tree& __x, const _Rb_tree& __y)
>>       {
>>     return std::lexicographical_compare(__x.begin(), __x.end(),
>>                         __y.begin(), __y.end());
>>       }
>
> Why do we even have the operators below?
>
> As far as I can tell, we only every use __x._M_t < __y._M_t and
> __x._M_t == __y._M_t, so don't need anything else.

For sure we don't use those for associative containers operators. I 
guess they have been added for consistency with Standard containers. 
There are here for a long time, do you want to remove them now ? I can 
add this cleanup in my patch if you want.

François

More information about the Libstdc++ mailing list