Stefan Heinzmann wrote [abridged]...
> Given that the notion of an iterator range is rather fundamental in
> the standard library, I wonder why this wasn't turned into a class
> template in the STL. Something like this:
>
> template<typename Iter>
> struct iterator_range {
>     Iter begin, end;
>
>     size_t size() const { return std::distance(begin,end); }
>     bool empty() const { return begin == end; }
>     bool operator==(const Iter& rhs) const
>         { return (begin == rhs.begin) && (end == rhs.end); }
>     // ... potentially more methods here
> };

I've often wondered about this myself. A lot of algorithms inherently
run over a range, and a single range object more naturally and flexibly
represents the required concept than a pair of iterators. Consider, for
example, the typical loop implied by many standard algorithms:

   for (iterator_type it = begin_it; it != end_it; ++it) { ... }

How could we provide iterators over a circular data structure that
satisfied the usual equality operations, but also allowed us to run such
an algorithm over an entire circular container? What would
container_list::begin() and circular_list::end() mean in a context like
that anyway?

For a circular container, it makes more sense to define a single
bidirectional "anchor" iterator (logically both begin() and end() would
return this, if they were provided at all) and offer both a "whole"
range, and a "partial" range based on two iterators, either or both of
which might be the anchor.

In general, I think that supporting the concept of a range would allow
more natural extension of the standard library to support newer data
structures and algorithms, as well as offering a cleaner presentation of
what is already available. One could also see plenty of applications for
"filtered ranges", which again might be a more natural representation of
some concepts than we current have with "iterator adapters" and such.

It might also be useful to provide a make_range function template,
analogous to make_pair, to build a suitable range from begin and end
iterators if this makes sense and is unambiguous. Suitable data
structures could provide their own specialisations. In cases like
circular lists, where there is potential ambiguity, alternatives could
be offered for each possibility instead, and no specialisation provided.
Anyone mistakenly trying to use the ambiguous construction would receive
a compile-time error, so as well as gaining a more natural interface to
the algorithms, we also provide more robust checking than in an iterator
pair solution.

Regards,
Chris

---
[ 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                       ]

"Chris Newton" <chrisnewton@no.junk.please.btinternet.com> skrev i
meddelandet news:bh4192$fan$1@hercules.btinternet.com...
> Stefan Heinzmann wrote [abridged]...
> > Given that the notion of an iterator range is rather fundamental
in
> > the standard library, I wonder why this wasn't turned into a class
> > template in the STL.

Possibly becase it would rule out some kinds of iterators, making the
entire concept less powerful.

>> Something like this:
> >
> > template<typename Iter>
> > struct iterator_range {
> >     Iter begin, end;

This requires the range to be constant. Usually, nothing reqires
container.end() to remain constant in a  loop.

> >
> >     size_t size() const { return std::distance(begin,end); }

This rules out the use of input and output iterators. How would you
compute the distance() for some keyboard input?

> >     bool empty() const { return begin == end; }

This requires end() to be a constant.

> >     bool operator==(const Iter& rhs) const
> >         { return (begin == rhs.begin) && (end == rhs.end); }

This rules out not only input and output iterators, but also filtering
iterators. Just because begin() and end() compares equal, the
intermediate values does not have to be the same, or the same number.

> >     // ... potentially more methods here
> > };
>
> I've often wondered about this myself. A lot of algorithms
inherently
> run over a range, and a single range object more naturally and
flexibly
> represents the required concept than a pair of iterators. Consider,
for
> example, the typical loop implied by many standard algorithms:
>
>    for (iterator_type it = begin_it; it != end_it; ++it) { ... }

I would say that this would be typical for a for_each() call, where
the iterator values *are* captured at the point of call. An ordinary
for loop is much more powerful.

>
> How could we provide iterators over a circular data structure that
> satisfied the usual equality operations, but also allowed us to run
such
> an algorithm over an entire circular container? What would
> container_list::begin() and circular_list::end() mean in a context
like
> that anyway?

The end() function should return a value that is somehow recognized as
the end of the list. Works fine for std::list for example.

The container requirements are quite simple: begin() returns an
iterator that refers to the first element, if any. Otherwise it
returns end(). end() returns an iterator that is different from an
iterator to any of the elements in the container, using one-of-the-end
is just an implementation detail not a requirement.

>
> In general, I think that supporting the concept of a range would
allow
> more natural extension of the standard library to support newer data
> structures and algorithms, as well as offering a cleaner
presentation of
> what is already available.

But you would also need to keep at least some of the current library,
as it presents a more general interface. Then you will have some
algorithms for range types and some for iterators. I don't immediately
see how this makes it cleaner.


Bo Persson
bop2@telia.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                       ]

bop2@telia.com ("Bo Persson") wrote in message news:<c0pZa.19360$mU6.23558@newsb.telia.net>...
> "Chris Newton" <chrisnewton@no.junk.please.btinternet.com> skrev i
> meddelandet news:bh4192$fan$1@hercules.btinternet.com...
> > Stefan Heinzmann wrote [abridged]...
> > > Given that the notion of an iterator range is rather fundamental
>  in
> > > the standard library, I wonder why this wasn't turned into a class
> > > template in the STL.
>
> Possibly becase it would rule out some kinds of iterators, making the
> entire concept less powerful.

I don't see what kind of iterator would be ruled out. Could you give
an example?

> >> Something like this:
> > >
> > > template<typename Iter>
> > > struct iterator_range {
> > >     Iter begin, end;
>
> This requires the range to be constant. Usually, nothing reqires
> container.end() to remain constant in a  loop.

If it doesn't remain constant, you're in trouble. It means you can't
use most of the STL algorithms either, because they take a copy of the
iterators. You would have to use plain for loops and have the
container.end() expression evaluated in each loop iteration.

What difference is there between passing two separate iterators to an
algorithm and passing a range object containing two iterators?

> > >
> > >     size_t size() const { return std::distance(begin,end); }
>
> This rules out the use of input and output iterators. How would you
> compute the distance() for some keyboard input?

You don't. If distance isn't available for the underlying iterator
then size() isn't either. SFINAE.

[...]
> > >     bool operator==(const Iter& rhs) const
> > >         { return (begin == rhs.begin) && (end == rhs.end); }
>
> This rules out not only input and output iterators, but also filtering
> iterators. Just because begin() and end() compares equal, the
> intermediate values does not have to be the same, or the same number.

That begs the question what it means if two ranges of input iterators
are equal. Maybe equality is not that useful for an iterator range...

> > >     // ... potentially more methods here
> > > };
> >
> > I've often wondered about this myself. A lot of algorithms
>  inherently
> > run over a range, and a single range object more naturally and
>  flexibly
> > represents the required concept than a pair of iterators. Consider,
>  for
> > example, the typical loop implied by many standard algorithms:
> >
> >    for (iterator_type it = begin_it; it != end_it; ++it) { ... }
>
> I would say that this would be typical for a for_each() call, where
> the iterator values *are* captured at the point of call. An ordinary
> for loop is much more powerful.

Nothing prevents you from using for loops if you prefer. I was
interested in using the algorithms in the standard library (for_each
and a *lot* more) and my question was whether this can be made safer
and more convenient by a range class.

[...]
> > In general, I think that supporting the concept of a range would
>  allow
> > more natural extension of the standard library to support newer data
> > structures and algorithms, as well as offering a cleaner
>  presentation of
> > what is already available.
>
> But you would also need to keep at least some of the current library,
> as it presents a more general interface. Then you will have some
> algorithms for range types and some for iterators. I don't immediately
> see how this makes it cleaner.

Keeping the current stuff would for the very least be necessary for
backwards compatibility. I imagine I even would get the boot for
suggesting that the methods and algorithms taking separate iterators
be declared obsolete.

I don't see, however, why the current interface is more general. If
you've got a range type you can always get at the individual
iterators, and if you've got separate iterators you can easily combine
them to form a range object. The provision of a convenience function
template akin to std::make_pair has already been suggested. In my view
the two alternatives are equivalent, with the one based on the range
type being clearer and safer in my opinion.

Cheers
Stefan

---
[ 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                       ]

bop2@telia.com ("Bo Persson") wrote in message news:<c0pZa.19360$mU6.23558@newsb.telia.net>...
> "Chris Newton" <chrisnewton@no.junk.please.btinternet.com> skrev i
> meddelandet news:bh4192$fan$1@hercules.btinternet.com...
> > Stefan Heinzmann wrote [abridged]...
...
> >> Something like this:
> > >
> > > template<typename Iter>
> > > struct iterator_range {
> > >     Iter begin, end;
>
> This requires the range to be constant. Usually, nothing reqires
> container.end() to remain constant in a  loop.

Iterator ranges are usually passed by value to an algorithm. That's
the only context in which the standard even talks about the concept.
As such, fresh calls to end() will NOT occur during execution of the
algorithm. Therefore, this wouldn't be a new restriction.

> > >     size_t size() const { return std::distance(begin,end); }
>
> This rules out the use of input and output iterators. How would you
> compute the distance() for some keyboard input?

>From which it follows that size() could only usefully be called for
iterator ranges created from iterators that are at least forward
iterators. The iterator_range template wouldn't exactly be the first
standard template with such a restriction.

---
[ 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                       ]

"Stefan Heinzmann" <stefan_heinzmann@yahoo.com> wrote in message
news:95e0e5ef.0308060330.28aefaae@posting.google.com...
[snip]
> Wouldn't that make the usage of standard algorithms and standard
> containers both easier and safer? Ideally, each container wouldn't
> just define its iterator type but also its iterator range type through
> a typedef. Algorithms operating on a range would not take two separate
> iterator arguments but a single range argument instead.

As I see it, the container/iterator coorporation is very generic and useful,
but its sometimes a bit
tedious and it doesn't go well in hand with functional style programming.

At boost we have been working on some new "container" algortihms, algorithms
that take an iterator range
as a single argument. This enables us to pass containers, pairs of iterator,
arrays as a single argument
   to algortihms which underneith will (mostly) simply forward to the current
algortihm.

For mutating algorithms the full benefit will first come if/when
move-semantics are intriduced. It's been a while since I looked into it, but
I think mojo is cannot be applied here.

Anyway, you can see some implementation in the boost sandbox:. Look for
these files

boost/sequence_algo/container_traits.hpp
boost/sequence_algo/container_algo.hpp

container_traits<> is the tool you need to treat types as iterator ranges.

I now Alisdair Meredith is trying (or tried?) to get an iterator_range
concept into the standard together the
proposed iterator adapter lib.

We had a discussion back then where I briefly sketched this
http://www.cs.auc.dk/~nesotto/iterator_range.html.

regards

Thorsten





---
[ 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                       ]

stefan_heinzmann@yahoo.com (Stefan Heinzmann) wrote

> Given that the notion of an iterator range is rather fundamental in
> the standard library, I wonder why this wasn't turned into a class
> template in the STL.

Well, in a weak sense, it was: std::pair.  In the rare cases in which
an STL container member function actually returns a range (e.g.
std::multimap::equal_range()), a pair is what you get.

Why isn't std::pair<iter, iter> used more often to represent a range?
I suspect that the reasoning runs like this:

(1) Users of containers will sometimes want just the begin() or end()
iterator, and we don't want to ask them to pay the cost of obtaining
and returning both if they only want one.  So containers *must*
implement begin() and end().

(2) Users might sometimes want the complete contents of a container as
a range.  However, to add a range() member function, when we already
have begin() and end(), is a little redundant.  If users want an
iter-pair, they can just call std::make_pair(c.begin(), c.end())
(which is exactly what the library implementation of range() would
probably do).

(3) Algorithms operate on ranges, so perhaps they should take
iter-pairs.  However, to get an iter-pair from a container requires an
extra piece of work, either on the users part:

  std::copy(std::make_pair(v.begin(), v.end()), out_iter);

or on the library's part:

  std::pair<iterator, iterator> vector::range() {
     return make_pair(this->begin(), this->end());
  }

with little obvious benefit.  So, never mind.

Would using ranges or iter-pairs be safer than working with individual
iterators?  In theory, yes, I suppose so.  In practice, however, I
don't know that this has become a real problem.  I can't remember
running into an "invalid iterator range" error personally.  But
others' experience may be different.

---
[ 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                       ]

Hi,

> Anyway, you can see some implementation in the boost sandbox:. Look for
> these files
>
> boost/sequence_algo/container_traits.hpp
> boost/sequence_algo/container_algo.hpp
>
> container_traits<> is the tool you need to treat types as iterator ranges.

I have just been looking at this and I've got a question. It seems to
me that using these iterator ranges it should be possible to eliminate
the slightly annoying STL issue of e.g. std::set.find versus find(...)
  by specialising the container algorithms. do you agree? is it the
intention to do this in container_algo ?

Cheers,

David J. Pearce

> I now Alisdair Meredith is trying (or tried?) to get an iterator_range
> concept into the standard together the
> proposed iterator adapter lib.
>
> We had a discussion back then where I briefly sketched this
> http://www.cs.auc.dk/~nesotto/iterator_range.html.
>
> regards
>
> Thorsten
>
>
>
>
>
> ---
> [ 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                       ]
>

---
[ 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 Pearce" <djp1@doc.ic.ac.uk> wrote in message
news:bhctdv$sfh$1@harrier.doc.ic.ac.uk...
> Hi,
>
> > Anyway, you can see some implementation in the boost sandbox:. Look for
> > these files
> >
> > boost/sequence_algo/container_traits.hpp
> > boost/sequence_algo/container_algo.hpp
> >
> > container_traits<> is the tool you need to treat types as iterator
ranges.
>
> I have just been looking at this and I've got a question. It seems to
> me that using these iterator ranges it should be possible to eliminate
> the slightly annoying STL issue of e.g. std::set.find versus find(...)
>   by specialising the container algorithms. do you agree? is it the
> intention to do this in container_algo ?

yes. I agree that it would be a benefit and it ought to be done that way.

it hasn't been done like that yet since I was annoyed by the need to include
e.g <map>
to make the specialization. Had the standard only forward declared container
templates, it would have been
easy. When I asked Matt Austern about it, he instead recommended a <std>
header that includes everything
which could then be precompiled no most systems.

I guess the relative headers should just be included. Anyway, there is
plenty of time to
fix the issue since the working group will not consider new libs for
one-and-a-half year.

regards

Thorsten




---
[ 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                       ]

Hi all,

this may have surfaced in the past, but I don't know what the current
wisdom is, so please forgive me if I'm asking a FAQ and point me to
the relevant docs.

Given that the notion of an iterator range is rather fundamental in
the standard library, I wonder why this wasn't turned into a class
template in the STL. Something like this:

template<typename Iter>
struct iterator_range {
    Iter begin, end;

    size_t size() const { return std::distance(begin,end); }
    bool empty() const { return begin == end; }
    bool operator==(const Iter& rhs) const
        { return (begin == rhs.begin) && (end == rhs.end); }
    // ... potentially more methods here
};

template<typename Iter>
iterator_range<Iter> range(const Iter& b, const Iter& e)
{
    iterator_range<Iter> res = { b,e };
    return res;
}


Wouldn't that make the usage of standard algorithms and standard
containers both easier and safer? Ideally, each container wouldn't
just define its iterator type but also its iterator range type through
a typedef. Algorithms operating on a range would not take two separate
iterator arguments but a single range argument instead.

Is this omission the result of a deliberate decision of the standards
committee, and if so, what was the rationale? Or if not, is the
addition of such a definition under consideration for the next version
of the standard?

Cheers
Stefan

---
[ 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                       ]