Confused by <bits/predefined_ops.h>

[Jonathan Wakely <jwakely at redhat dot com>]

I've been trying to re-read the six (!) different threads about the
patch that introduced the <bits/predefined_ops.h> header because I
find the header confusing and have some questions about it.

At the time I thought removing code from <bits/stl_algo.h> was good,
but now 3-4 years later I can't figure out what any of the algos are
doing, because of all the __ops::__iter_comp_val calls to create
mysterious function objects.

The naming of the function objects seems rather arbitrary. We have
_Iter_equal_to_iter and _Iter_equals_iter. One of them is stateless
and binary, one is stateful and unary (and stores the iterator's
reference type, which causes PR78346). Can you guess which is which by
the names? I can't. Shouldn't the names indicate whether they are
unary or binary function objects? Then we have a function __pred_iter
that returns an _Iter_pred ... why are the names reversed?

When you're in a long list of things called iter_comp_iter and
iter_comp_to_val and iter_less_iter and iter_that_iter_this_iter_val
the names are *really* important to understand what the code does.

We have three helper functions called __iter_comp_iter but one is
unary and two are binary. The unary one is used to wrap an arbitrary
binary comparison function (usually coming from user code) to produce
another binary function object, but the binary ones are only used with
our own internal __ops function objects and they bind an iterator to
the function object to produce a unary function object. Why do they
have the same name? The unary one should be called something like
"make indirect", because it transforms bool(T1,T2) into bool(T1*,T2*),
and the binary ones should be "bind second" because they combine
bool(T1*,T2*) and T2* to produce bool(T1*) (i.e. partial application).

If there's logic to the names then there should be a comment in the
file explaining it. Or we should just give them better names.

As for PR78346, I can fix it by making the relevant function object
types take their constructor arguments by reference, so that the
reference we store in _M_ref is bound to some iterator in the caller's
scope, not the constructor argument that goes out of scope immediately
(see patch below). But why do those objects store a reference anyway?
Why don't they just store the iterator passed to the constructor and
dereference it as needed? Is this to avoid dereferencing multiple
times?  Because that might be slow?

The Ranges TS removes the requirement that two equal ForwardIterators
must return references bound to the same object, i.e. in the future
ForwardIterators will be allowed to be "stashing iterators". So we're
going to need to handle this case eventually, even if it's undefined
in C++ today. It seems that storing the iterator and dereferencing it
as needed would solve the problem.


--- a/libstdc++-v3/include/bits/predefined_ops.h
+++ b/libstdc++-v3/include/bits/predefined_ops.h
@@ -210,7 +210,7 @@ namespace __ops
      typename std::iterator_traits<_Iterator1>::reference _M_ref;

      explicit
-      _Iter_equals_iter(_Iterator1 __it1)
+      _Iter_equals_iter(_Iterator1& __it1)
       : _M_ref(*__it1)
      { }

@@ -222,7 +222,7 @@ namespace __ops

  template<typename _Iterator>
    inline _Iter_equals_iter<_Iterator>
-    __iter_comp_iter(_Iter_equal_to_iter, _Iterator __it)
+    __iter_comp_iter(_Iter_equal_to_iter, _Iterator& __it)
    { return _Iter_equals_iter<_Iterator>(__it); }

  template<typename _Predicate>
@@ -275,7 +275,7 @@ namespace __ops
      _Compare _M_comp;
      typename std::iterator_traits<_Iterator1>::reference _M_ref;

-      _Iter_comp_to_iter(_Compare __comp, _Iterator1 __it1)
+      _Iter_comp_to_iter(_Compare __comp, _Iterator1& __it1)
       : _M_comp(_GLIBCXX_MOVE(__comp)), _M_ref(*__it1)
      { }

@@ -287,7 +287,7 @@ namespace __ops

  template<typename _Compare, typename _Iterator>
    inline _Iter_comp_to_iter<_Compare, _Iterator>
-    __iter_comp_iter(_Iter_comp_iter<_Compare> __comp, _Iterator __it)
+    __iter_comp_iter(_Iter_comp_iter<_Compare> __comp, _Iterator& __it)
    {
      return _Iter_comp_to_iter<_Compare, _Iterator>(
         _GLIBCXX_MOVE(__comp._M_comp), __it);