I've been looking through the new iterator concepts in the current C+
+0x working paper [n2857] and am slightly worried that, if I'm
understanding things correctly, operator-> is not terribly useful on
the new iterator concepts.

As an example, let's consider a simple C++03 template that calls uses
operator->:

   template <class InputIterator>
   void algo( InputIterator first, InputIterator last ) {
     for ( ; first != last; ++first )
       first->fn();
   }

Let's try to convert this to use C++0x's concepts:

   concept Foo<typename T> {
     void fn( const T& );
   };

   template <std::InputIterator Iterator>
     requires Foo<Iterator::value_type>
   void algo( Iterator first, Iterator last ) {
     for ( ; first != last; ++first )
       first->fn();
   }

Whilst this accurately reflects what we think the requirements should
be, it isn't good enough.  The InputIterator concept defines
[24.2.2/1]:

   typename pointer = typename X::pointer;
   requires Convertible<pointer, const value_type*>;
   pointer operator->( const X& );

And the meaning of an expression x->m in a constrained template is
defined by [13.5.6/2]:

| If declared in a concept or concept map, operator-> shall be a
| non-member associated function taking exactly one parameter.
| It implements class member access using ->
|
|   postfix-expression -> id-expression
|
| An expression x->m is interpreted as (operator->(x))->m for an
| object x of type T if operator->(T) exists and if the operator is
| selected as the best match function by the overload resolution
| mechanism (13.3).

So within the constrained template we're interested in the expression
first->fn.  The type of 'first' is an archetype of InputIterator and
so operator->(Iterator) exists and returns an InputIterator::pointer.
But pointer isn't a raw pointer: it's merely convertible to one, so
the outer -> in the expression (operator->(first))->fn makes no sense.

Adding an additional requirement to our template would seem to fix
this:

   template <std::InputIterator Iterator>
     requires Foo<Iterator::value_type>
       && SameType<const Iterator::value_type*, Iterator::pointer>
   void algo( Iterator first, Iterator last );

And now, as I understand it, the template should compile.  But let's
try instantiating it:

   struct foo { void fn() const; };
   std::vector<foo> foos = get_foos();
   algo( foos.begin(), foos.end() );

The thing to notice here is that we are passing algo() a pair of (non-
const_)iterators, and the pointer type of a (non-const_)iterator is
value_type*, not const value_type*.  Although I haven't yet managed to
find the exact wording in clause 23, I'm something has to define a
RandomAccessIterator concept_map for std::vector<T,A>::iterator and
this cannot possibly define pointer as anything other than T*.  This
means that the requirement clause doesn't hold for the (non-const_)
iterator, and so no overload of algo() will be found.

Replace begin() and end() with cbegin() and cend() and the code will
work fine.

But this strikes me as a fairly big problem.  It means we cannot write
constrained-template algorithms that use operator-> and that will work
on both const_iterators and (non-const_)iterators.

The problems goes deeper.  In the current C++03 standard, it's quite
common to have iterators that have operator* return by value.  In such
cases, operator-> is conventionally defined to return a proxy pointer
type:

   typedef value_type reference;
   reference operator*() const { /* ... */ }
   struct pointer {
     pointer( value_type v ) : v(v) {}
     value_type* operator->() const { return &v; }
     operator value_type*() const { return &v; }
   private:
     value_type v;
   };
   pointer operator->() const { return **this; }

In our unconstrained C++0x code, we can use such an iterator without
problem; and such an iterator conforms to the various C++0x iterator
concepts as pointer is convertible to value_type const* and reference
to value_type const&.  However, in my constrained template algo(), we
cannot use this because pointer is not a raw pointer.

The latter case -- of supporting iterators that return by value and
use proxy pointers -- is probably salvageable.  We could introduce a
helper concept:

   auto concept IteratorProxyPointer<typename P, typename V> {
     V const* operator->(P const&);
   };

and then add a requirement to the InputIterator concept:

   requires IteratorProxyPointer<pointer, value_type>;

Under the current wording of the working draft, I think this probably
needs a explicit concept_map for the normal case of a non-proxy
pointer:

   template <typename T>
   concept_map IteratorProxyPointer<T const*, T> {
     T const* operator->(T const* p) { return p; }
   };

It's not completely clear that this is needed because the paragraph
describing how associated functions requirements are satisified
[14.10.2.1/4] doesn't really cope with the case of operator-> (or
operator[]) because of it (they) are not ordinary binary infix
operators.

With this helper concept in place, I think this fixes the proxy case,
but it does nothing for earlier the const/non-const issues.  Nor does
rewriting the code to write (*i).m instead of i->m help as precisely
the same issues exist regarding reference's convertibility to const
value_type&.

Any thoughts?

Richard Smith

--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On May 10, 11:49 pm, Richard Smith <rich...@ex-parrot.com> wrote:

> And the meaning of an expression x->m in a constrained template is
> defined by [13.5.6/2]:
>
> | If declared in a concept or concept map, operator-> shall be a
> | non-member associated function taking exactly one parameter.
> | It implements class member access using ->
> |
> |   postfix-expression -> id-expression
> |
> | An expression x->m is interpreted as (operator->(x))->m for an
> | object x of type T if operator->(T) exists and if the operator is
> | selected as the best match function by the overload resolution
> | mechanism (13.3).
>
> So within the constrained template we're interested in the expression
> first->fn.  The type of 'first' is an archetype of InputIterator and
> so operator->(Iterator) exists and returns an InputIterator::pointer.
> But pointer isn't a raw pointer: it's merely convertible to one, so
> the outer -> in the expression (operator->(first))->fn makes no sense.

The outer -> makes perfect sense - because even if the first call to
operator->() does not return a pointer - then the compiler invokes the
-> operator on the object that is returned - and once again on the
object that that object returns. In fact, the compiler will keep
invoking the operator -> recursively on each successive object
returned - until the compiler obtains a pointer to the expected object
(the one that has the specified member being accessed).

Greg


--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On May 10, 11:49 pm, Richard Smith <rich...@ex-parrot.com> wrote:
>
>    template <std::InputIterator Iterator>
>      requires Foo<Iterator::value_type>
>        && SameType<const Iterator::value_type*, Iterator::pointer>
>    void algo( Iterator first, Iterator last );
>
> And now, as I understand it, the template should compile.

The above function template will work only with Iterators whose
value_types are const (that is, for const_iterator types). Otherwise,
(for ordinary iterator types) the SameType comparison will fail (due
to left-hand type's added const qualification). Therefore, to have algo
() support both const_ and non-const_iterators, all that is needed is
to remove the const qualification from "value_type".

> try instantiating it:
>
>    struct foo { void fn() const; };
>    std::vector<foo> foos = get_foos();
>    algo( foos.begin(), foos.end() );
>
> The thing to notice here is that we are passing algo() a pair of (non-
> const_)iterators, and the pointer type of a (non-const_)iterator is
> value_type*, not const value_type*.

The pointer type of a const_iterator is also value_type* (not const
value_type*) because value_type will incorporate any necessary const
or volatile qualification.

> But this strikes me as a fairly big problem.  It means we cannot write
> constrained-template algorithms that use operator-> and that will work
> on both const_iterators and (non-const_)iterators.

In fact, it takes more work to write a constraint that distinguishes
between const_ and non_const iterators than it is to write one that
treats the two indiscriminately.

> The problems goes deeper.  In the current C++03 standard, it's quite
> common to have iterators that have operator* return by value.  In such
> cases, operator-> is conventionally defined to return a proxy pointer
> type:
>
>    typedef value_type reference;
>    reference operator*() const { /* ... */ }
>    struct pointer {
>      pointer( value_type v ) : v(v) {}
>      value_type* operator->() const { return &v; }
>      operator value_type*() const { return &v; }
>    private:
>      value_type v;
>    };
>    pointer operator->() const { return **this; }
>
> In our unconstrained C++0x code, we can use such an iterator without
> problem; and such an iterator conforms to the various C++0x iterator
> concepts as pointer is convertible to value_type const* and reference
> to value_type const&.  However, in my constrained template algo(), we
> cannot use this because pointer is not a raw pointer.

As I pointed out in an earlier post, invoking operator->() on an
object eventually has to return a real pointer to something.
Therefore, applying the * operator to this returned pointer type -
will work as expected.

Greg


--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On May 11, 8:21 pm, Greg Herlihy <gre...@mac.com> wrote:
> On May 10, 11:49 pm, Richard Smith <rich...@ex-parrot.com> wrote:

>
> > And the meaning of an expression x->m in a constrained template is
> > defined by [13.5.6/2]:
>
> > | If declared in a concept or concept map, operator-> shall be a
> > | non-member associated function taking exactly one parameter.
> > | It implements class member access using ->
> > |
> > |   postfix-expression -> id-expression
> > |
> > | An expression x->m is interpreted as (operator->(x))->m for an
> > | object x of type T if operator->(T) exists and if the operator is
> > | selected as the best match function by the overload resolution
> > | mechanism (13.3).
>
> > So within the constrained template we're interested in the expression
> > first->fn.  The type of 'first' is an archetype of InputIterator and
> > so operator->(Iterator) exists and returns an InputIterator::pointer.
> > But pointer isn't a raw pointer: it's merely convertible to one, so
> > the outer -> in the expression (operator->(first))->fn makes no sense.
>
> The outer -> makes perfect sense - because even if the first call to
> operator->() does not return a pointer - then the compiler invokes the
> -> operator on the object that is returned

Yes, I'm aware of the recursive nature of operator->.  In this case it
tries to invoke operator-> again on the return type which is an
archetype of Iterator::pointer.  But it can't as there is no operator-
> that takes the Iterator::pointer archetype.  So perhaps I shouldn't
have said it makes no sense, but it doesn't compile either.

In a unconstrained template this would be fine because
Iterator::pointer would almost certainly turn out to be a raw pointer
(or if not, to have an operator->) but the archetype is not a raw
pointer and does not have an operator-> and so, in a constrained
template, the code does not compile.

In any case, this point was incidental to my argument.

Richard


--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On May 12, 5:49 am, Greg Herlihy <gre...@mac.com> wrote:
> On May 10, 11:49 pm, Richard Smith <rich...@ex-parrot.com> wrote:
>
> > try instantiating it:
>
> >    struct foo { void fn() const; };
> >    std::vector<foo> foos = get_foos();
> >    algo( foos.begin(), foos.end() );
>
> > The thing to notice here is that we are passing algo() a pair of (non-
> > const_)iterators, and the pointer type of a (non-const_)iterator is
> > value_type*, not const value_type*.
>
> The pointer type of a const_iterator is also value_type* (not const
> value_type*) because value_type will incorporate any necessary const
> or volatile qualification.

That might be a good solution to this problem, but it is not what the
working draft [N2857] currently says.  For example, in 24.2.6/11 it
defines a concept map for raw pointers:

   template<ObjectType T>
   concept_map RandomAccessIterator<const T*> {
     typedef T value_type;
     typedef ptrdiff_t difference_type;
     typedef const T& reference;
     typedef const T* pointer;
   }

If what you say is true, the latter should have a const-qualified
value_type, which it doesn't.  Similarly in 23.2.6, the Container
concept has (truncating heavily):

   concept Container<typename C> {
     ObjectType value_type = typename C::value_type;

     requires SameType<ForwardIterator<iterator>::value_type,
value_type>
       && SameType<ForwardIterator<const_iterator>::value_type,
value_type>;
   }

So here a Container whose const_iterator::value_type is const-
qualified will fail to match the Container concept.  I could have
believed one of these might have been a typo; but two seems a bit
improbable.

Can you find any evidence in the working draft that
Iterator::value_type ought to be const-qualified?

I would also be worried that requiring const_iterators to have a const-
qualified value_type would be error-prone with existing code.  Without
a concept_map that explicitly does something to contrary, the
concept_map's value_type is taken from iterator, and existing practice
is generally not to const-qualify value_type on a const_iterator.

> > But this strikes me as a fairly big problem.  It means we cannot write
> > constrained-template algorithms that use operator-> and that will work
> > on both const_iterators and (non-const_)iterators.
>
> In fact, it takes more work to write a constraint that distinguishes
> between const_ and non_const iterators than it is to write one that
> treats the two indiscriminately.

If it were true, that would be good.

> > The problems goes deeper.  In the current C++03 standard, it's quite
> > common to have iterators that have operator* return by value.  In such
> > cases, operator-> is conventionally defined to return a proxy pointer
> > type:
>
> >    typedef value_type reference;
> >    reference operator*() const { /* ... */ }
> >    struct pointer {
> >      pointer( value_type v ) : v(v) {}
> >      value_type* operator->() const { return &v; }
> >      operator value_type*() const { return &v; }
> >    private:
> >      value_type v;
> >    };
> >    pointer operator->() const { return **this; }
>
> > In our unconstrained C++0x code, we can use such an iterator without
> > problem; and such an iterator conforms to the various C++0x iterator
> > concepts as pointer is convertible to value_type const* and reference
> > to value_type const&.  However, in my constrained template algo(), we
> > cannot use this because pointer is not a raw pointer.
>
> As I pointed out in an earlier post, invoking operator->() on an
> object eventually has to return a real pointer to something.

As I pointed out in an earlier post (assuming it finally makes it to
comp.std.c++), it doesn't.  When the template is being instantiated,
there is no operator-> that takes an Iterator::pointer archetype and
so it doesn't compile without a SameType requirement to say that
Iterator::pointer is a raw pointer; and with the SameType requirement,
it doesn't instantiate because the proxy pointer type isn't a raw
pointer.  Hence the need for some more complicated concept that
supports proxy pointers, like the IteratorProxyPointer I gave.

> Therefore, applying the * operator to this returned pointer type -
> will work as expected.

I assume you're not advocating writing code like (*i.operator->()).m
()?

Actually, (*i).m() has just as many problems as i->m().  Again, you
need a SameType requirement that says something about
Iterator::reference.  Either you write

   SameType<Iterator::reference, value_type&>

(with or without const-qualfication), in which case the case when
operator* returns by value fails to match it; or you write

   SameType<Iterator::reference, value_type>

in which case the usual case of operator* returning by reference fails
to match it.  And unlike the case of operator->, you can't use a
helper concept like IteratorProxyPointer to save you because operator*
isn't invoked recursively (and for good reason).

So right at the moment, I'm sticking by all of the points I've made.

Richard Smith


--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]