*Summary*
I am proposing the addition of this:
    struct contiguous_iterator_tag : public random_iterator_tag { };



*Detail*
The following iterator category hierarchy exists:

struct input_iterator_tag { };
struct output_iterator_tag { };
struct forward_iterator_tag       : public input_iterator_tag { };
struct bidirectional_iterator_tag : public forward_iterator_tag { };
struct random_access_iterator_tag : public bidirectional_iterator_tag { };

However, there seems to me to be an iterator category beyond random
access iterators: contiguous memory iterators (i.e. pointers, arrays).
Note that both vector::iterator and deque::iterator are random access
iterators, yet there are optimizations that can be made on vector
iterators which cannot be made on deque iterators. In looking at various
STL implementations' attempts to optimize algorithms, I see them go
through various type_traits contortions in order to tell the difference
between a random access iterator and one that is simply a pointer. In
fact, these attempts are often blowing my GCC template depth limit(!)

So how about adding something like this to <iterator>:
    struct contiguous_iterator_tag : public random_iterator_tag { };

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Paul Pedriana wrote:
> *Summary*
> I am proposing the addition of this:
>     struct contiguous_iterator_tag : public random_iterator_tag { };
>

<snip>

> Note that both vector::iterator and deque::iterator are random access
> iterators, yet there are optimizations that can be made on vector
> iterators which cannot be made on deque iterators. In looking at various
> STL implementations' attempts to optimize algorithms, I see them go
> through various type_traits contortions in order to tell the difference
> between a random access iterator and one that is simply a pointer. In
> fact, these attempts are often blowing my GCC template depth limit(!)
>

I like the idea, but have one question:

Do these attempts also require that the value_type be POD (Plain Old
Data - no constructors/destructors/copy/etc)?  ie what are the
optimizations.  I'm trying to imagine cases where, ***just using the
iterator**, I could make use of the difference between contiguous and
non-contiguous.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Paul Pedriana wrote:
> <snip> In looking at various
> STL implementations' attempts to optimize algorithms, I see them go
> through various type_traits contortions in order to tell the difference
> between a random access iterator and one that is simply a pointer. In
> fact, these attempts are often blowing my GCC template depth limit(!)

That strikes me, because in order to tell the difference between an
iterator (of whatever class) and a pointer, you just need to partially
specialize the template and rely on partial ordering, without using
traits. For example:

template <class It>
void my_algorithm(It first, It end)
{ /* generic implementation */ }

template <class T>
void my_algorithm(T* first, T* end)
{ /* specialization for pointers */ }


> So how about adding something like this to <iterator>:
>    struct contiguous_iterator_tag : public random_iterator_tag { };

I don't think that's needed. As seen in the previous example, a pointer
can very easily be detected without introducing an additional tag. BTW,
TR1 is going to include all-purposes type traits like tr1::is_pointer,
which might also help addressing this issue.

Just my opinion,

Ganesh

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

In article <1129817997.855596.61500@g43g2000cwa.googlegroups.com>,
frege <gottlobfrege@gmail.com> wrote:

> Paul Pedriana wrote:
> > *Summary*
> > I am proposing the addition of this:
> >     struct contiguous_iterator_tag : public random_iterator_tag { };
> >
>
> <snip>
>
> > Note that both vector::iterator and deque::iterator are random access
> > iterators, yet there are optimizations that can be made on vector
> > iterators which cannot be made on deque iterators. In looking at various
> > STL implementations' attempts to optimize algorithms, I see them go
> > through various type_traits contortions in order to tell the difference
> > between a random access iterator and one that is simply a pointer. In
> > fact, these attempts are often blowing my GCC template depth limit(!)
> >
>
> I like the idea, but have one question:
>
> Do these attempts also require that the value_type be POD (Plain Old
> Data - no constructors/destructors/copy/etc)?  ie what are the
> optimizations.  I'm trying to imagine cases where, ***just using the
> iterator**, I could make use of the difference between contiguous and
> non-contiguous.
>
>
   to Paul
      template <class T> struct is_raw_ptr
      {
         static const bool value = false;
      };

      template <class T> struct is_raw_ptr<T *>
      {
         static const bool value = true;
      };
      should not blow up  gcc 3.x :)

   to frege
      most optimizations requested seem to want more than just
contiguous iterators, but most of the rest of the requirements are
implimented in boost and or tr1.  using boost mpl library or equivalent
it is possible to test if all of the conditions hold.

   It is possible to find something that only a contiguos iterator trait
can be used for but can't think of useful one offhand.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

On 2005-10-21 15:48, Carl Barron wrote:
>> Paul Pedriana wrote:
>> > *Summary*
>> > I am proposing the addition of this:
>> >     struct contiguous_iterator_tag : public random_iterator_tag { };
:
>    It is possible to find something that only a contiguos iterator
> trait can be used for but can't think of useful one offhand.

An iterator does not need to be a pointer to represent a sequence that
is contiguous in memory. For a possible use case see the current thread
"Passing strings to APIs" in comp.lang.c++.moderated (in particular
the subthread starting at news:<IoA7DM.1s94@beaver.cs.washington.edu>).

-- Niklas Matthies

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

I think for many cases contiguous_iterator_tag wouldn't be strictly
needed, though it would make implementations clearer and reduce the
template load on the compiler. Like I said, I regularly run into the GCC
  template depth limit because of the libstdc++ copy algorithm's usage
of type traits such as is_pointer.

It seems like a natural extension of random_access_iterator to me, and
the effort to add it to the standard library would be pretty minimal.

Also, is is_pointer alone sufficient, given that it doesn't apply to
member pointers? Have to think about that...

Paul

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

> An iterator does not need to be a pointer to represent a sequence that
> is contiguous in memory. For a possible use case see the current thread
> "Passing strings to APIs" in comp.lang.c++.moderated (in particular
> the subthread starting at news:<IoA7DM.1s94@beaver.cs.washington.edu>).

Your idea there isn't entirely crazy, as one of the things we sometimes
do on the wintel platform is intentionally allocate blocks of memory so
that the end of them at the end of a page and we intentionally allocate
a second read-only page after that which is normally unused. This is
done in order to trap memory writes by the user beyond the allocated
region and assists in debugging. Well, there's no reason this space
can't be put to some good use, such as holding the c_str value.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Paul Pedriana wrote:
> I think for many cases contiguous_iterator_tag wouldn't be strictly
> needed, though it would make implementations clearer and reduce the
> template load on the compiler. Like I said, I regularly run into the GCC
>  template depth limit because of the libstdc++ copy algorithm's usage of
> type traits such as is_pointer.

That's a gcc problem, not something that the standard should take care
of, in my opinion.

> It seems like a natural extension of random_access_iterator to me, and
> the effort to add it to the standard library would be pretty minimal.

Our opinions differ, clearly. Anyway, there is a proposal that would
replace the whole iterator concept system with something more functional
(see http://www.boost.org/libs/iterator/doc/new-iter-concepts.html), so
it doesn't make sense to try to patch what is probably going to be ditched.

> Also, is is_pointer alone sufficient, given that it doesn't apply to
> member pointers? Have to think about that...
>

Strictly speaking, pointer to non-static members are *not* pointers
(such claim may strike you, but that's basically what the standard says
in 3.9.2/3). Moreover, you can't perform arithmetic operations on
pointer to members and they can't be used to describe ranges, so how can
you even think about using them as iterators?

Just my opinion,

Ganesh

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

pedriana@remove_this.pacbell.net (Paul Pedriana) writes:

> I think for many cases contiguous_iterator_tag wouldn't be strictly
> needed, though it would make implementations clearer and reduce the
> template load on the compiler. Like I said, I regularly run into the GCC
>  template depth limit because of the libstdc++ copy algorithm's usage
> of type traits such as is_pointer.

Did you know that there's a -ftemplate-depth command-line option for
GCC?  The default of 17 is too low for serious work with modern
templates.  I usually use -ftemplate-depth-255.  That said, it's hard
to believe that is_pointer is responsible for the effects you're
seeing.  It's an unbelievably simple template with very ordinary
characteristics; there's not much reason to think that it, more than
any other template the system might use, is to blame for going beyond
17 levels of instantiation.

--
Dave Abrahams
Boost Consulting
www.boost-consulting.com

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

David Abrahams wrote:
> Did you know that there's a -ftemplate-depth command-line option for
> GCC?  The default of 17 is too low for serious work with modern
> templates.  I usually use -ftemplate-depth-255.  That said, it's hard
> to believe that is_pointer is responsible for the effects you're
> seeing.  It's an unbelievably simple template with very ordinary
> characteristics; there's not much reason to think that it, more than
> any other template the system might use, is to blame for going beyond
> 17 levels of instantiation.

I agree.

By the way, the "current" (since 2002-01-10 ;) default is 500.

Paolo.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]