Re: Make associative container operators inline friend

[François Dumont <frs dot dumont at gmail dot com>]

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