Interest in updated, standalone iterator_facade library?
I write a lot of iterators, and I'm getting sick of doing it by hand. I can't use Boost.Iterator's iterator_facade in library code, since it knows nothing about constexpr and noexcept. The design of Boost.Iterator's iterator_facade does not lend itself very well to being modified in a direction that is standardization-friendly (reasons why are outlined in the online docs). So, here is one take on this problem: GitHub: https://github.com/tzlaine/iterator_facade Online Docs: https://tzlaine.github.io/iterator_facade For those unfamiliar with the problem, iterators are very simple, at the highest level of abstraction. An iterator's implementation does not reflect this -- it is highly repetitive and easy to get subtly wrong. This library fixes that. The library is forward-looking, since I intend to write WG21 papers to standardize iterator_facade; there is good support for upcoming C++20 library features. In particular, the iterators created with iterator_facade model the C++20 iterator concepts, and therefore do not necessarily match the requirements of the C++17-and-earlier requirement tables. I have not found this to affect the usability of iterator-facade-based iterators with pre-C++20 code. Something to note: there was a recent-ish attempt to stanrdize iterator_facade, which is now abandoned, P0186 (http://wg21.link/P0186). This was very different from what I'm proposing for Boost. I talked to Eric Niebler about this, and he favors a return to the CRTP-based approach of my lib and the original Boost.Iterator iterator_facade library. Zach
On Sat, Aug 10, 2019 at 9:21 PM Zach Laine via Boost <boost@lists.boost.org> wrote:
I write a lot of iterators, and I'm getting sick of doing it by hand. I can't use Boost.Iterator's iterator_facade in library code, since it knows nothing about constexpr and noexcept.
The design of Boost.Iterator's iterator_facade does not lend itself very well to being modified in a direction that is standardization-friendly (reasons why are outlined in the online docs).
So, here is one take on this problem:
GitHub: https://github.com/tzlaine/iterator_facade
Online Docs: https://tzlaine.github.io/iterator_facade
For those unfamiliar with the problem, iterators are very simple, at the highest level of abstraction. An iterator's implementation does not reflect this -- it is highly repetitive and easy to get subtly wrong.
This
library fixes that.
The library is forward-looking, since I intend to write WG21 papers to standardize iterator_facade; there is good support for upcoming C++20 library features. In particular, the iterators created with iterator_facade model the C++20 iterator concepts, and therefore do not necessarily match the requirements of the C++17-and-earlier requirement tables. I have not found this to affect the usability of iterator-facade-based iterators with pre-C++20 code.
Something to note: there was a recent-ish attempt to stanrdize iterator_facade, which is now abandoned, P0186 (http://wg21.link/P0186). This was very different from what I'm proposing for Boost. I talked to Eric Niebler about this, and he favors a return to the CRTP-based approach of my lib and the original Boost.Iterator iterator_facade library.
Zach
I would definitely use this, and I'd be thrilled to see it in boost. My sole suggestion would be to consider choosing a name other than iterator_facade to prevent confusion with the old one. Some potential candidates, some better than others: * iterator_veneer * iterator_face * iterator_guise * iterator_disguise * iterator_outfit * iterator_costume * iterator_hat * iterator_sugar * iterator_porcelain * enable_iterator_from_this
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
I for one would be very happy to see this utility in boost. Just wondering: Would it be possible to extend this lib with a range_facade CRTP? Not sure if/how this could work in the general case, but for containers / views that represent a contiguous range of elements (array, vector, span, string, string_view) it has saved me a ton of typing, testing and probably also bugs over the years. However, if I had to choose, I'd prefer a simple iterator_facade library as proposed by you over a big, complex solution that tries to solve everything for everyone (that could be a separate library). Best Mike
On Sun, Aug 11, 2019 at 5:28 AM Mike via Boost <boost@lists.boost.org> wrote:
I for one would be very happy to see this utility in boost.
Just wondering: Would it be possible to extend this lib with a range_facade CRTP? Not sure if/how this could work in the general case, but for containers / views that represent a contiguous range of elements (array, vector, span, string, string_view) it has saved me a ton of typing, testing and probably also bugs over the years.
This is a reasonable request, and one that I had already considered. It would require maintaining a whole second header, so I'm not sure it's worth it. :) I don't think this would grow the library too much, but I do want to carefully consider what a range_facade could and should do. I already know the answer for iterator_facade. IOW, I'll probably get to it, if/when that consideration is fruitful.
However, if I had to choose, I'd prefer a simple iterator_facade library as proposed by you over a big, complex solution that tries to solve everything for everyone (that could be a separate library).
Agreed! Zach
Zach Laine wrote:
`reference` being `char const` in the introductory example doesn't feel correct. `char const` can't be returned from a function (such as `operator*`), top-level qualifiers aren't meaningful for `char`.
On Sun, Aug 11, 2019 at 5:43 AM Peter Dimov via Boost <boost@lists.boost.org> wrote:
Zach Laine wrote:
`reference` being `char const` in the introductory example doesn't feel correct. `char const` can't be returned from a function (such as `operator*`), top-level qualifiers aren't meaningful for `char`.
It is correct, as of C++20. Proxy iterators are first-class citizens, as of the ranges concepts work. I used that reference type on purpose, and I refer to that later in the docs. Also, this is copy-paste from Boost.Text (proposed), which uses that exact iterator with a "char const" reference type. Zach
Zach Laine wrote:
On Sun, Aug 11, 2019 at 5:43 AM Peter Dimov via Boost <boost@lists.boost.org> wrote:
Zach Laine wrote:
`reference` being `char const` in the introductory example doesn't feel correct. `char const` can't be returned from a function (such as `operator*`), top-level qualifiers aren't meaningful for `char`.
It is correct, as of C++20. Proxy iterators are first-class citizens, as of the ranges concepts work. I used that reference type on purpose, and I refer to that later in the docs. Also, this is copy-paste from Boost.Text (proposed), which uses that exact iterator with a "char const" reference type.
Thanks. You should however be aware that both gcc and clang warn on functions returning `const char` with -Wextra. :-)
On Sun, Aug 11, 2019 at 10:52 AM Peter Dimov via Boost < boost@lists.boost.org> wrote:
Zach Laine wrote:
On Sun, Aug 11, 2019 at 5:43 AM Peter Dimov via Boost <boost@lists.boost.org> wrote:
Zach Laine wrote:
`reference` being `char const` in the introductory example doesn't feel correct. `char const` can't be returned from a function (such as `operator*`), top-level qualifiers aren't meaningful for `char`.
It is correct, as of C++20. Proxy iterators are first-class citizens, as of the ranges concepts work. I used that reference type on purpose, and I refer to that later in the docs. Also, this is copy-paste from Boost.Text (proposed), which uses that exact iterator with a "char const" reference type.
Thanks. You should however be aware that both gcc and clang warn on functions returning `const char` with -Wextra. :-)
Huh. Good to know. I guess I should change it to char then. Zach
Dear Zach, Dear Zach,
On 11. Aug 2019, at 18:00, Zach Laine via Boost <boost@lists.boost.org> wrote:
On Sun, Aug 11, 2019 at 10:52 AM Peter Dimov via Boost < boost@lists.boost.org> wrote:
Zach Laine wrote:
On Sun, Aug 11, 2019 at 5:43 AM Peter Dimov via Boost <boost@lists.boost.org> wrote:
Zach Laine wrote:
`reference` being `char const` in the introductory example doesn't feel correct. `char const` can't be returned from a function (such as `operator*`), top-level qualifiers aren't meaningful for `char`.
It is correct, as of C++20. Proxy iterators are first-class citizens, as of the ranges concepts work. I used that reference type on purpose, and I refer to that later in the docs. Also, this is copy-paste from Boost.Text (proposed), which uses that exact iterator with a "char const" reference type.
Thanks. You should however be aware that both gcc and clang warn on functions returning `const char` with -Wextra. :-)
Huh. Good to know. I guess I should change it to char then.
+1 for the proposal to have a modern iterator_fascade. I use a private implementation of iterator_fascade in Boost.Histogram for a couple of reasons, but mostly because the old boost iterator library pulls in a lot of boost dependencies which I want to avoid. But code duplication is bad, so I am looking forward to switch to your library which only depends on the stdlib. I object to change the name of iterator_fascade. The established convention in Boost is to call a updated library X with the same purpose X2, see variant and variant2, coroutine and coroutine2, signal and signal2, etc. This library should follow this route and be called iterator2. I am by no means an expert of the iterator_fascade, but I spend some time to figure out how the old iterator_fascade works, and it has some subtle solutions to corner case situations. Therefore, I would recommended that you port the iterator test suite to your project (if you haven't done so already). Also, please add a modern iterator_adaptor. iterator_adaptors are awesome, because you need to implemented even less. Best regards, Hans
PS:
On 12. Aug 2019, at 10:26, Hans Dembinski <hans.dembinski@gmail.com> wrote:
+1 for the proposal to have a modern iterator_fascade. I use a private implementation of iterator_fascade in Boost.Histogram for a couple of reasons, but mostly because the old boost iterator library pulls in a lot of boost dependencies which I want to avoid. But code duplication is bad, so I am looking forward to switch to your library which only depends on the stdlib.
I object to change the name of iterator_fascade. The established convention in Boost is to call a updated library X with the same purpose X2, see variant and variant2, coroutine and coroutine2, signal and signal2, etc. This library should follow this route and be called iterator2.
I am by no means an expert of the iterator_fascade, but I spend some time to figure out how the old iterator_fascade works, and it has some subtle solutions to corner case situations. Therefore, I would recommended that you port the iterator test suite to your project (if you haven't done so already).
Also, please add a modern iterator_adaptor. iterator_adaptors are awesome, because you need to implemented even less.
You should switch from gtest to lightweight_test in Boost.Core. lightweight_test is lovely and pulling in a third-party dependency for testing will surely be rejected in a Boost review.
Some more thoughts from a first glance at the library: In https://tzlaine.github.io/iterator_facade/doc/html/boost_iteratorfacade__pro... you list the user supplied operations. The method names should exactly correspond to the existing ones used by boost.iterator, see https://www.boost.org/doc/libs/1_71_0/libs/iterator/doc/iterator_facade.html compare vs. distance_to equals vs. equal next vs. increment prev vs. decrement The reason is that the old names were likely already "optimised" by previous reviews and you should make it easy for people to port existing code to iterator2. Switching from iterator to iterator2 should be as easy changing the included header for simple cases. Best regards, Hans
Hans Dembinski wrote:
compare vs. distance_to
This reminds me of an issue that I've found with the existing iterator_facade: sometimes I can magnitude-compare the iterators, but not report a distance. For example, a simple filter iterator can quickly tell whether A is before or after B by comparing the underlying iterators, but it cannot find the distance without applying its filter predicate to all the intermediate elements. Currently, operator< etc. in the facade are implemented by calling the user's distance_to which is inefficient in this case. Your change of name to compare made me wonder if it is now expected only to return -1/0/+1, but that doesn't seem to be the case. The other thing that I've found tedious to do with the current iterator_facade is implementing both iterator and const_iterator. The pattern I tend to use is: template <bool is_const> class iterator_base: public boost::iterator_facade< ......... > ...... using iterator = iterator_base<false>; using const_iterator = iterator_base<true>; I don't know if there is anything that iterator_facade could do to make this easier. Regards, Phil.
On Mon, Aug 12, 2019 at 8:38 AM Phil Endecott via Boost < boost@lists.boost.org> wrote:
Hans Dembinski wrote:
compare vs. distance_to
This reminds me of an issue that I've found with the existing iterator_facade: sometimes I can magnitude-compare the iterators, but not report a distance.
For example, a simple filter iterator can quickly tell whether A is before or after B by comparing the underlying iterators, but it cannot find the distance without applying its filter predicate to all the intermediate elements.
Currently, operator< etc. in the facade are implemented by calling the user's distance_to which is inefficient in this case. Your change of name to compare made me wonder if it is now expected only to return -1/0/+1, but that doesn't seem to be the case.
I think this is out of scope for the library, simply because the library is for making models of the C++20 iterator concepts. An iterator like you describe is not one of those -- an iterator that is not random access and yet has operator<() may be useful to you in some situations, but it is not useful for communicating capabilities to standard algorithms. Also, it's easy for you to bolt this on yourself if it's useful to you.
The other thing that I've found tedious to do with the current iterator_facade is implementing both iterator and const_iterator. The pattern I tend to use is:
template <bool is_const> class iterator_base: public boost::iterator_facade< ......... > ......
using iterator = iterator_base<false>; using const_iterator = iterator_base<true>;
I don't know if there is anything that iterator_facade could do to make this easier.
I've struggled with this too. I have not found a good way to deal with this. I think the best we can do is something like what you show above. One day reflection and/or "metaclass"-style source generation may be the way to do this. Zach
Zach Laine wrote:
On Mon, Aug 12, 2019 at 8:38 AM Phil Endecott via Boost < boost@lists.boost.org> wrote:
Hans Dembinski wrote:
compare vs. distance_to
This reminds me of an issue that I've found with the existing iterator_facade: sometimes I can magnitude-compare the iterators, but not report a distance.
For example, a simple filter iterator can quickly tell whether A is before or after B by comparing the underlying iterators, but it cannot find the distance without applying its filter predicate to all the intermediate elements.
Currently, operator< etc. in the facade are implemented by calling the user's distance_to which is inefficient in this case. Your change of name to compare made me wonder if it is now expected only to return -1/0/+1, but that doesn't seem to be the case.
I think this is out of scope for the library, simply because the library is for making models of the C++20 iterator concepts. An iterator like you describe is not one of those -- an iterator that is not random access and yet has operator<() may be useful to you in some situations, but it is not useful for communicating capabilities to standard algorithms.
I disagree. If I try to use std::sort() or std::map<> with these iterators, they don't (IIUC) check the iterator category, but rather they just need operator< (or std::less?) to be defined. Yes I can add them myself, but adding all of <, <=, >, >= is, pre-spaceship, tedious and a little error-prone - exactly the sort of boilerplate code that iterator_facade is trying to help eliminate. Regards, Phil.
On Tue, Aug 13, 2019 at 7:18 AM Phil Endecott via Boost < boost@lists.boost.org> wrote:
Zach Laine wrote:
On Mon, Aug 12, 2019 at 8:38 AM Phil Endecott via Boost < boost@lists.boost.org> wrote:
Hans Dembinski wrote:
compare vs. distance_to
This reminds me of an issue that I've found with the existing iterator_facade: sometimes I can magnitude-compare the iterators, but not report a distance.
For example, a simple filter iterator can quickly tell whether A is before or after B by comparing the underlying iterators, but it cannot find the distance without applying its filter predicate to all the intermediate elements.
Currently, operator< etc. in the facade are implemented by calling the user's distance_to which is inefficient in this case. Your change of name to compare made me wonder if it is now expected only to return -1/0/+1, but that doesn't seem to be the case.
I think this is out of scope for the library, simply because the library is for making models of the C++20 iterator concepts. An iterator like you describe is not one of those -- an iterator that is not random access and yet has operator<() may be useful to you in some situations, but it is not useful for communicating capabilities to standard algorithms.
I disagree. If I try to use std::sort() or std::map<> with these iterators, they don't (IIUC) check the iterator category, but rather they just need operator< (or std::less?) to be defined.
std::map is a read herring. It does not need operator< on iterators, only on keys. As for std::sort, the existence of operator< on iterators is not enough to make this work. For instance, sort is allowed to use offsets and operator[] on your iterator, and yet there's no such thing. These concepts exist for a reason, and I'm not interested in subverting them.
Yes I can add them myself, but adding all of <, <=, >, >= is, pre-spaceship, tedious and a little error-prone - exactly the sort of boilerplate code that iterator_facade is trying to help eliminate.
Right, but in the cases you mention you only need operator<, right? Moreover, all the requirements on each concept are actually checked in the std::ranges algorithms. Only having operator< does not help you use algorithms that require a random_access_iterator does not work if the algorithm only uses operator<; the concept-checking machinery will still error out if you don't meet the full concept. Zach
On Tue, Aug 13, 2019 at 2:01 PM Zach Laine via Boost <boost@lists.boost.org> wrote:
On Tue, Aug 13, 2019 at 7:18 AM Phil Endecott via Boost < boost@lists.boost.org> wrote:
Zach Laine wrote:
On Mon, Aug 12, 2019 at 8:38 AM Phil Endecott via Boost < boost@lists.boost.org> wrote:
Hans Dembinski wrote:
compare vs. distance_to
This reminds me of an issue that I've found with the existing iterator_facade: sometimes I can magnitude-compare the iterators, but not report a distance.
For example, a simple filter iterator can quickly tell whether A is before or after B by comparing the underlying iterators, but it cannot find the distance without applying its filter predicate to all the intermediate elements.
Currently, operator< etc. in the facade are implemented by calling the user's distance_to which is inefficient in this case. Your change of name to compare made me wonder if it is now expected only to return -1/0/+1, but that doesn't seem to be the case.
I think this is out of scope for the library, simply because the library is for making models of the C++20 iterator concepts. An iterator like you describe is not one of those -- an iterator that is not random access and yet has operator<() may be useful to you in some situations, but it is not useful for communicating capabilities to standard algorithms.
I disagree. If I try to use std::sort() or std::map<> with these iterators, they don't (IIUC) check the iterator category, but rather they just need operator< (or std::less?) to be defined.
std::map is a read herring. It does not need operator< on iterators, only on keys.
I assume they want to use an iterator (from some container) as a key in a map? Tony
Hi, just to express my interest in this. I already have a legacy project where this could be useful and if it were to land in boost (or in the standard) it would be great. Thanks for doing this. Do you think that the code is already useable, or is there something "big" left to do? I hope to give it a try in some days and of course will report back to you if there is anything relevant or useful. Francesco Il dom 11 ago 2019, 04:21 Zach Laine via Boost <boost@lists.boost.org> ha scritto:
I write a lot of iterators, and I'm getting sick of doing it by hand. I can't use Boost.Iterator's iterator_facade in library code, since it knows nothing about constexpr and noexcept.
The design of Boost.Iterator's iterator_facade does not lend itself very well to being modified in a direction that is standardization-friendly (reasons why are outlined in the online docs).
So, here is one take on this problem:
GitHub: https://github.com/tzlaine/iterator_facade
Online Docs: https://tzlaine.github.io/iterator_facade
For those unfamiliar with the problem, iterators are very simple, at the highest level of abstraction. An iterator's implementation does not reflect this -- it is highly repetitive and easy to get subtly wrong. This library fixes that.
The library is forward-looking, since I intend to write WG21 papers to standardize iterator_facade; there is good support for upcoming C++20 library features. In particular, the iterators created with iterator_facade model the C++20 iterator concepts, and therefore do not necessarily match the requirements of the C++17-and-earlier requirement tables. I have not found this to affect the usability of iterator-facade-based iterators with pre-C++20 code.
Something to note: there was a recent-ish attempt to stanrdize iterator_facade, which is now abandoned, P0186 (http://wg21.link/P0186). This was very different from what I'm proposing for Boost. I talked to Eric Niebler about this, and he favors a return to the CRTP-based approach of my lib and the original Boost.Iterator iterator_facade library.
Zach
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Sun, Aug 11, 2019 at 9:54 AM Francesco Guerrieri via Boost < boost@lists.boost.org> wrote:
Hi, just to express my interest in this. I already have a legacy project where this could be useful and if it were to land in boost (or in the standard) it would be great. Thanks for doing this.
Do you think that the code is already useable, or is there something "big" left to do? I hope to give it a try in some days and of course will report back to you if there is anything relevant or useful.
I consider it to be ready, as-is. There may be bugs lurking that need to be fixed, but I don't know of any. I can write every kind of iterator I've ever needed to write (which is a lot). This includes all the iterator categories, plus proxy versions of each, and even weird stuff like back_insert_iterator. Zach
On Sun, Aug 11, 2019 at 10:22 AM Zach Laine <whatwasthataddress@gmail.com> wrote:
On Sun, Aug 11, 2019 at 9:54 AM Francesco Guerrieri via Boost < boost@lists.boost.org> wrote:
Hi, just to express my interest in this. I already have a legacy project where this could be useful and if it were to land in boost (or in the standard) it would be great. Thanks for doing this.
Do you think that the code is already useable, or is there something "big" left to do? I hope to give it a try in some days and of course will report back to you if there is anything relevant or useful.
I consider it to be ready, as-is. There may be bugs lurking that need to be fixed, but I don't know of any. I can write every kind of iterator I've ever needed to write (which is a lot). This includes all the iterator categories, plus proxy versions of each, and even weird stuff like back_insert_iterator.
Yeah, about this statement. I meant it yesterday when I made it. Then I started investigating what it would take to make something like a range_facade, as was suggested earlier in this thread. That lead me to discover std::view_interface, which I previously had never even heard of: http://eel.is/c++draft/view.interface It's pretty similar in concept to what iterator_facade does, but it does it using concept-based SFINAE on the members of std::view_interface, which leads to a small, easy-to-understand library interface, and a lot less library code. It also allows the user to specify operations with their usual spellings, like operator*() instead of dereference(). It also does not require the access type, because you don't have to make functions with odd names that you want to hide. I like this a lot better. In fact, I like it so much better that I implemented something like it yesterday on a branch, renaming iterator_facade to iterator_interface: https://github.com/tzlaine/iterator_facade/tree/interface_alternative The one downside to this approach is that when you define operator++(), the iterator_interface cannot define operator++(int) for you automatically, because it gets hidden by the operator++() you just defined! Oh, C++, I wish I could quit you. Anyway, I worked around this for now by just keeping next() and prev(), and using operator*(), operator==(), operator+=() and operator-() for the other operations. I'm not super pleased with that, and I'm considering just using operator++() and operator--() instead of next() and prev(), and requiring the user to add "using operator++;" and/or "using operator--;". This has the nice property that if they forget, they'll get a compilation failure if anyone tries to use post-incr-/decrement. It has the bad property that it is one more thing for the user to remember. I'm certainly open to input here. So, there's your very large change. You might give both approaches a try and indicate which one feels more natural and why. Zach
On Mon, Aug 12, 2019 at 5:45 PM Zach Laine via Boost <boost@lists.boost.org> wrote:
On Sun, Aug 11, 2019 at 10:22 AM Zach Laine <whatwasthataddress@gmail.com> wrote:
On Sun, Aug 11, 2019 at 9:54 AM Francesco Guerrieri via Boost < boost@lists.boost.org> wrote:
Do you think that the code is already useable, or is there something "big" left to do? I hope to give it a try in some days and of course will report back to you if there is anything relevant or useful.
I consider it to be ready, as-is. There may be bugs lurking that need to be fixed, but I don't know of any. I can write every kind of iterator I've ever needed to write (which is a lot). This includes all the iterator categories, plus proxy versions of each, and even weird stuff like back_insert_iterator.
Yeah, about this statement. I meant it yesterday when I made it. Then I started investigating what it would take to make something like a range_facade, as was suggested earlier in this thread. That lead me to discover std::view_interface, which I previously had never even heard of:
http://eel.is/c++draft/view.interface
It's pretty similar in concept to what iterator_facade does, but it does it using concept-based SFINAE on the members of std::view_interface, which leads to a small, easy-to-understand library interface, and a lot less library code. It also allows the user to specify operations with their usual spellings, like operator*() instead of dereference(). It also does not require the access type, because you don't have to make functions with odd names that you want to hide.
I like this a lot better. In fact, I like it so much better that I implemented something like it yesterday on a branch, renaming iterator_facade to iterator_interface:
It is a large change but it is for the better, I like it a lot. The "using operator++;" requirement is not too bad, it becomes mostly a matter of documentation. Thanks, Francesco
On Aug 12, 2019, at 9:46 AM, Zach Laine via Boost <boost@lists.boost.org> wrote:
On Sun, Aug 11, 2019 at 10:22 AM Zach Laine <whatwasthataddress@gmail.com> wrote:
I consider it to be ready, as-is. There may be bugs lurking that need to be fixed, but I don't know of any. I can write every kind of iterator I've ever needed to write (which is a lot). This includes all the iterator categories, plus proxy versions of each, and even weird stuff like back_insert_iterator.
Have you considered an analogy of the Boost iterator_adaptor? That might reduce boilerplate in some useful cases. Cheers, Brook
participants (9)
-
Barrett Adair -
Brook Milligan -
Francesco Guerrieri -
Gottlob Frege -
Hans Dembinski -
Mike -
Peter Dimov -
Phil Endecott -
Zach Laine