Constant iterator of Single Pass Range

Jan Hudec

5 May 2014 5 May '14

10:03 a.m.

Hello All, The documentation of [Single Pass Range][1] in Boost.Range says that there should be both `iterator` and `const_iterator` associated types and both const and non-const overloads for `begin` and `end`. However if it is really a single-pass range, I don't see a way to implement a `const_iterator` that would work on `const` reference to the range, because the `operator++` of the iterator involves calling a non-const method of the range. For example the `std::istream_iterator::operator++` calls `std::istream::operator>>`, which is non-const and so there is no `const_istream_iterator`. The `istream_range` cheats around this a little, because the range is a wrapper around the stream, not the stream itself. But when I have similarly behaving class that I can make itself be a range, do I really have to work around this using a wrapper, or can the requirement be relaxed in practice? [1]: http://www.boost.org/libs/range/doc/html/range/concepts/single_pass_range.ht... -- Jan Hudec

Show replies by date

Neil Groves

5 May 5 May

11:40 a.m.

On Mon, May 5, 2014 at 11:03 AM, Jan Hudec wrote:

...

Hello All,

The documentation of [Single Pass Range][1] in Boost.Range says that there should be both `iterator` and `const_iterator` associated types and both const and non-const overloads for `begin` and `end`. However if it is really a single-pass range, I don't see a way to implement a `const_iterator` that would work on `const` reference to the range, because the `operator++` of the iterator involves calling a non-const method of the range.

I think that your statements indicate that you have a misunderstanding about implementing iterators. The word "const" does not refer to the iterator type itself but to the reference type. It is not possible without resort to very perverse use of the "mutable" keyword to implement a const_iterator to refer to any type. Of course, const_iterator is part of every standard container so this is not an idiom that is specific to Boost.Range.

...

For example the `std::istream_iterator::operator++` calls `std::istream::operator>>`, which is non-const and so there is no `const_istream_iterator`. The `istream_range` cheats around this a little, because the range is a wrapper around the stream, not the stream itself. But when I have similarly behaving class that I can make itself be a range, do I really have to work around this using a wrapper, or can the requirement be relaxed in practice?

I believe that you don't have a problem! A const_iterator can be implemented with non-const member functions. There are examples within the Boost.Range unit test code that show the use of extending Boost.Range for user defined types. These show the various methods for implementing this. There is also documentation that has an example extending via the const and mutable meta-functions here: http://www.boost.org/doc/libs/1_55_0/libs/range/doc/html/range/reference/ext... In the above example the type returned from the meta-function is the same for both the const and mutable versions. If the iterators are acting upon a container then you often don't need to provide either of the range meta-functions for obtaining the iterator since the member typedefs will be sufficient. I typically implement my own container types to simply have the member typedefs and avoid the need to specialise the meta-functions. One would typically extend the meta-functions when the custom range or container does not model standard container Concepts. It might therefore be worth reviewing the rest of the Boost.Range reference section on extending the library.

...

-- Jan Hudec

If I have misunderstood your problem, or you require any additional help please let me know. Regards, Neil Groves

Jan Hudec

4:08 p.m.

Dne 05.05.2014 13:40, Neil Groves napsal:

...

On Mon, May 5, 2014 at 11:03 AM, Jan Hudec wrote:

...
Hello All,

The documentation of [Single Pass Range][1] in Boost.Range says that there should be both `iterator` and `const_iterator` associated types and both const and non-const overloads for `begin` and `end`. However if it is really a single-pass range, I don't see a way to implement a `const_iterator` that would work on `const` reference to the range, because the `operator++` of the iterator involves calling a non-const method of the range.

I think that your statements indicate that you have a misunderstanding about implementing iterators. The word "const" does not refer to the iterator type itself but to the reference type. It is not possible without resort to very perverse use of the "mutable" keyword to implement a const_iterator to refer to any type. Of course, const_iterator is part of every standard container so this is not an idiom that is specific to Boost.Range.

All containers are at least forward ranges, not merely single pass ones. Since iterating a forward range does not change it, there is no problem for it to have a `const` `begin()` and `end()` methods (returning const iterators). What I had issue with is single pass range. Consider something that behaves like `std::istream`. The `std::istream_iterator` can be only constructed from non-const reference to `std::istream`, because the `std::istream_iterator::operator++` (and the constructor itself) call the `std::istream::operator>>`, which is non-const. Of course for `std::istream` a wrapper is needed anyway, because the stream can return various types, so the wrapper has to specify which one is desired. But if I have a class that behaves similarly, but returns a specific type, I still can't make it a range, because I still can't give it a `begin` that would accept const reference (I _can_ usually give it `end`, because for this kind of objects the end iterator is dummy, but that won't help).

...

...
For example the `std::istream_iterator::operator++` calls `std::istream::operator>>`, which is non-const and so there is no `const_istream_iterator`. The `istream_range` cheats around this a little, because the range is a wrapper around the stream, not the stream itself. But when I have similarly behaving class that I can make itself be a range, do I really have to work around this using a wrapper, or can the requirement be relaxed in practice?

I believe that you don't have a problem! A const_iterator can be implemented with non-const member functions. There are examples within the Boost.Range unit test code that show the use of extending Boost.Range for user defined types. These show the various methods for implementing this. There is also documentation that has an example extending via the const and mutable meta-functions here:

http://www.boost.org/doc/libs/1_55_0/libs/range/doc/html/range/reference/ext...

Well, it can't be implemented using non-const methods of the _range_ _itself_. If I have a stream-like object class int_reader { ... int get_next(); // NOT const }; than I can create iterators for it. But the iterators will look like class int_reader_iterator : boost::iterator_facade { int_reader *reader; // NOT const ... void advance() { value = reader->get_next(); } // must NOT be const HERE ... int_reader_iterator(int_reader &reader) : reader(&reader) { } // can't be const here }; And therefore I can't provide int_reader_iterator range_begin(int_reader_iterator const &); And therefore I can't make `int_reader` a range. I can make a range adapter for it, that will break the const chain like `boost::istream_range` does. Now why I wanted that was that I wanted to work with temporaries and was concerned that I would get dangling reference, because BOOST_FOREACH will extend life of the passed range by binding it to a reference, but that does not extend to arguments of the expression. Basically I thought of writing something like BOOST_FOREACH(int i, boost::input_range<int>(std::ifstream("file.txt"))) ... Now this won't extend the life of the ifstream, but fortunately it won't compile either, because input_range requires a non-const reference. And if I had my object that would directly be range, but didn't have const begin, well, then BOOST_FOREACH wouldn't accept a temporary either, because temporary only binds to const reference. So the object that needs to be modified can't be a temporary whatever I do and I can wrap it and don't need to bother. What is still a problem is wrapper of a wrapper, but it's enough to simplify that to one level of wrapper. -- Jan Hudec

Neil Groves

5:38 p.m.

...

All containers are at least forward ranges, not merely single pass ones. Since iterating a forward range does not change it, there is no problem for it to have a `const` `begin()` and `end()` methods (returning const iterators).

What I had issue with is single pass range. Consider something that behaves like `std::istream`. The `std::istream_iterator` can be only constructed from non-const reference to `std::istream`, because the `std::istream_iterator::operator++` (and the constructor itself) call the `std::istream::operator>>`, which is non-const.

I apologise for misunderstanding your original post. In this scenario the range_const_iterator meta-function may validly return a mutable iterator. The purpose of the range_const_iterator meta-function is to define the iterator type for functions that use the const Range& overloads. The range_const_iterator does not have to return a type that is a constant iterator. The separate mechanism is necessary (pre C++11) since there are many examples where the type of iterator needs to be determined differently for the const and non-const function overloads. In most cases, of course, the range_const_iterator does return a const_iterator. You have correctly highlighted that sometimes you need to do something else. I believe that, if I have understood your example correctly, that you can do this by simply defining range_const_iterator to return a mutable iterator. The example I linked to previously does just this. It returns the iterator type from a pair. It returns the same type whether or not the range is passed as a const or mutable reference.

...

Well, it can't be implemented using non-const methods of the _range_ _itself_.

If I have a stream-like object

class int_reader { ... int get_next(); // NOT const };

than I can create iterators for it. But the iterators will look like

class int_reader_iterator : boost::iterator_facade { int_reader *reader; // NOT const ... void advance() { value = reader->get_next(); } // must NOT be const HERE ... int_reader_iterator(int_reader &reader) : reader(&reader) { } // can't be const here };

As mentioned above, you don't need to create a const_iterator that isn't a const iterator. You can just return the mutable iterator from range_const_iterator. It seems to me that this type doesn't really have a const_iterator. It isn't sensible for me to make a special case for single_pass_traversal versions of range_const_iterator since this is merely one of a number of reasons one might wish to return a mutable iterator from range_const_iterator. Any change for single_pass_traversal would be insufficient while adding complexity to the rules of extension.

...

And therefore I can't provide

int_reader_iterator range_begin(int_reader_iterator const &);

And therefore I can't make `int_reader` a range. I can make a range adapter for it, that will break the const chain like `boost::istream_range` does.

Now why I wanted that was that I wanted to work with temporaries and was concerned that I would get dangling reference, because BOOST_FOREACH will extend life of the passed range by binding it to a reference, but that does not extend to arguments of the expression. Basically I thought of writing something like

BOOST_FOREACH(int i, boost::input_range<int>(std:: ifstream("file.txt"))) ...

Now this won't extend the life of the ifstream, but fortunately it won't compile either, because input_range requires a non-const reference.

The potential for lifetime issues when combining temporaries with BOOST_FOREACH is a known problem without a good solution with broad compatibility with C++03. In many cases while the range lifetime may end, the underlying iterators live on. The BOOST_FOREACH library then behaves correctly in many cases where it might look like undefined behaviour ought to occur. There are however some lifetime issues for example applying range adaptors to a container returned by value. The solution, for now at least, is to create a temporary variable before the BOOST_FOREACH statement. I did consider the use of a slightly naughty const range to try and extend the lifetime, but it is rather odd and doesn't work in the general case.

...

And if I had my object that would directly be range, but didn't have const begin, well, then BOOST_FOREACH wouldn't accept a temporary either, because temporary only binds to const reference. So the object that needs to be modified can't be a temporary whatever I do and I can wrap it and don't need to bother.

I didn't write BOOST_FOREACH, but I believe that it isn't accepting the temporary rather deliberately to avoid lifetime issues.

...

What is still a problem is wrapper of a wrapper, but it's enough to simplify that to one level of wrapper.

I believe I understand your aim. I rejected this direction of design since it only helps in a small number of cases. I would love to have a complete solution and have spent considerable time to no avail. In my production code I resort to one of: 1. Use one of the Boost.Range algorithms such as boost::push_back or boost::transform (works with versions of C++ prior to C++11) 2. Add a temporary (works with versions of C++ prior to C++11) 3. Replace BOOST_FOREACH with the C++11 range-base for loop 4. Replace BOOST_FOREACH with boost::for_each

...

-- Jan Hudec

I hope I've understood the issue properly this time around. If you are using C++11 then simply not using BOOST_FOREACH is probably the best solution. The other alternatives I listed above lack elegance in some cases, but do work reliably. Regards, Neil Groves

Jan Hudec

6 May 6 May

7:48 p.m.

Dne 05.05.2014 19:38, Neil Groves napsal:

...

I apologise for misunderstanding your original post. In this scenario the range_const_iterator meta-function may validly return a mutable iterator. The purpose of the range_const_iterator meta-function is to define the iterator type for functions that use the const Range& overloads.

Well, the point is not the metafunction, but the `const Range&` overloads. Single-pass iterators usually modify the "generator" (otherwise they could be forward iterators easily). So if they are needed, the "generator" can't be a range itself, but instead needs a wrapper. When it is a wrapper, all is fine and the const and non-const overloads both return the same iterator as is the case of pair of iterators.

...

...
And therefore I can't provide

int_reader_iterator range_begin(int_reader_iterator const &);

And therefore I can't make `int_reader` a range. I can make a range adapter for it, that will break the const chain like `boost::istream_range` does.

This is the key bit.

...

The potential for lifetime issues when combining temporaries with BOOST_FOREACH is a known problem without a good solution with broad compatibility with C++03. In many cases while the range lifetime may end, the underlying iterators live on. The BOOST_FOREACH library then behaves correctly in many cases where it might look like undefined behaviour ought to occur. There are however some lifetime issues for example applying range adaptors to a container returned by value. The solution, for now at least, is to create a temporary variable before the BOOST_FOREACH statement.

... and fortunately the range constructor accepting non-const reference only enforces that, so a wrapper ends up being fine in this case.

...

I didn't write BOOST_FOREACH, but I believe that it isn't accepting the temporary rather deliberately to avoid lifetime issues.

It does. And then it binds it const and properly extends it's lifetime, so it also only uses const iterators with it. The problem is wrappers. Because other temporaries in the expression don't get their lifetime extended. And it boils down to following rule: * If the actual object can be iterated using const access (like containers), the object itself has to be adapted to be a range. Wrapping it would cause life-cycle issues with foreach. * If the actual object can *not* be iterated using const access (like std::istream), than the object *must* be wrapped and the fact that the wrapper will take non-const reference will prevent using temporary and avoid life-cycle issues with foreach. * The actual object that can not be iterated using const access (like std::istream) could be made a

...

...
What is still a problem is wrapper of a wrapper, but it's enough to simplify that to one level of wrapper.

I believe I understand your aim. I rejected this direction of design since it only helps in a small number of cases. I would love to have a complete solution and have spent considerable time to no avail. In my production code I resort to one of: 1. Use one of the Boost.Range algorithms such as boost::push_back or boost::transform (works with versions of C++ prior to C++11) 2. Add a temporary (works with versions of C++ prior to C++11) 3. Replace BOOST_FOREACH with the C++11 range-base for loop 4. Replace BOOST_FOREACH with boost::for_each

I hope I've understood the issue properly this time around.

Well, fortunately I now do. I was rather confused at the beginning. BOOST_FOREACH is perfectly fine, provided the right combination of const and non-const references are used to avoid getting dangling reference by accident. -- Jan Hudec

Karsten Ahnert

7:59 p.m.

...

All containers are at least forward ranges, not merely single pass ones. Since iterating a forward range does not change it, there is no problem for it to have a `const` `begin()` and `end()` methods (returning const iterators).

What I had issue with is single pass range. Consider something that behaves like `std::istream`. The `std::istream_iterator` can be only constructed from non-const reference to `std::istream`, because the `std::istream_iterator::operator++` (and the constructor itself) call the `std::istream::operator>>`, which is non-const.

I have exactly the same problem. The iterator approach to treat the range as a pair of iterators is not sufficient for me, since it bloats the last iterator. I would like to store all informations in the range and just pass pointers to the range to the iterators, like Erik Niebler explains in his posts single pass ranges.

Neil Groves

8:33 p.m.

On Tue, May 6, 2014 at 8:59 PM, Karsten Ahnert < karsten.ahnert@googlemail.com> wrote:

...

...
All containers are at least forward ranges, not merely single pass ones. Since iterating a forward range does not change it, there is no problem for it to have a `const` `begin()` and `end()` methods (returning const iterators).

What I had issue with is single pass range. Consider something that behaves like `std::istream`. The `std::istream_iterator` can be only constructed from non-const reference to `std::istream`, because the `std::istream_iterator::operator++` (and the constructor itself) call the `std::istream::operator>>`, which is non-const.

I have exactly the same problem. The iterator approach to treat the range as a pair of iterators is not sufficient for me, since it bloats the last iterator. I would like to store all informations in the range and just pass pointers to the range to the iterators, like Erik Niebler explains in his posts single pass ranges.

There is much merit in having state in a range rather than in bloated iterators. It is much more general than just the "last" iterator. It is always horrible to see the predicates and functors held in iterators. It is not a panacea however for the lifetime issues. If applied universally state in the ranges would introduce a lot more lifetime issues. Currently many scenarios work with ranges that die before the end of an expression because the iterators are copied outside of the adaptor expressions therefore the iterators are copied into a new range. It is possible to imagine various mechanisms for passing ownership of ranges or mandating shallow copying, but these all work less consistently with standard containers. It is not the case that one solution is obviously always better than the other. I have done extensive performance measurements upon various arrangements of having data in iterators versus ranges. I have been surprised how many times a bloated iterator outperforms the indirection to a separate range object. The performance impact varies between processor architectures and of course the size of the iterator and range. I am not allowed to publish my results due to this being under an NDA. I therefore don't expect my assertion to be taken as fact. I encourage experimentation. I am working on Range primitives that are as interoperable as possible with existing code. I completely agree that the bloat is suboptimal, but the solution is nothing like as simple as simple having iterators point to ranges.

...

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Karsten Ahnert

9:08 p.m.

...

...
I have exactly the same problem. The iterator approach to treat the range as a pair of iterators is not sufficient for me, since it bloats the last iterator. I would like to store all informations in the range and just pass pointers to the range to the iterators, like Erik Niebler explains in his posts single pass ranges.

There is much merit in having state in a range rather than in bloated iterators. It is much more general than just the "last" iterator. It is always horrible to see the predicates and functors held in iterators. It is not a panacea however for the lifetime issues. If applied universally state in the ranges would introduce a lot more lifetime issues. Currently many scenarios work with ranges that die before the end of an expression because the iterators are copied outside of the adaptor expressions therefore the iterators are copied into a new range. It is possible to imagine various mechanisms for passing ownership of ranges or mandating shallow copying, but these all work less consistently with standard containers. It is not the case that one solution is obviously always better than the other.

I have done extensive performance measurements upon various arrangements of having data in iterators versus ranges. I have been surprised how many times a bloated iterator outperforms the indirection to a separate range object. The performance impact varies between processor architectures and of course the size of the iterator and range. I am not allowed to publish my results due to this being under an NDA. I therefore don't expect my assertion to be taken as fact. I encourage experimentation.

What kind of algorithms have you used for your experiments? Most of the algorithms for single pass ranges are quite easy. I am experimenting with odeint, where the range abstracts a mathematical algorithm which solves an ODE iteratively. Using pairs of iterators immediately means that the end iterator needs to know the algorithms and the ode. Even if this does not influence the performance negatively it induces a very unintuitive interface, since your end iterator must be instantiated with these types. I think I can provide some performance measures in the next weeks. Nevertheless, I think that the requirement of obtaining a iterator from const single pass range could be relaxed.

Eric Niebler

7 May 7 May

1:56 a.m.

On 5/6/2014 1:33 PM, Neil Groves wrote:

...

I have done extensive performance measurements upon various arrangements of having data in iterators versus ranges. I have been surprised how many times a bloated iterator outperforms the indirection to a separate range object.

In my (admittedly limited) testing, I agree. In some places in my code, I've re-bloated iterators I had previously un-bloated simply for performance reasons. But I've also noticed that at least in some situations, the optimizer can see through the pointer-to-range stored in the iterator. That happens when the use of the iterator is not far from where the iterator was created. \e

4013

Age (days ago)

4015

Last active (days ago)

List overview

Download

8 comments

4 participants

participants (4)

Eric Niebler
Jan Hudec
Karsten Ahnert
Neil Groves