Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Writing a custom iterator in modern C++

internalpointers.com

Post reply on HN
Print view View original

41–50 of 79 posts

Re: Writing a custom iterator in modern C++

#41

Post by arcticbull »

millstone wrote: post #37
arcticbull wrote: post #24

Earlier quoted context omitted.

Right but why should this matter at the type level? All you need to implement is next() and annotate it with documentation of the performance characteristics.

Yeah, this is a good question. Scott Myers has a talk where he pokes fun at the "guaranteed O(N log N)" sort of a linked list, where the guarantee is in number of comparisons and not the (very large) number of pointer chases. Why describe at the type level the difference between a backwards pointer chase and a pointer decrement? The hope is: if you know at compile time that your iterator is efficient in this way, you…

Thanks, that was helpful. I suspect the reason it ends up being dead weight is that it doesn't make much sense to prevent an API customer from using an iterator with certain performance characteristics with certain algorithms. Ultimately, the onus is on the developer to know something about the data; for instance, why wouldn't I be allowed to use any iteration algorithm on my slow-to-increment iterator if I know the length is 1?

So long as it's safe I think it's on the designer to make sure it's efficient, and I suspect that's where the API has gravitated to.

Re: Writing a custom iterator in modern C++

#42

Post by mehrdadn »

stkdump wrote: post #38
mehrdadn wrote: post #32

Earlier quoted context omitted.

Yeah. That actually sucks; often iterators doesn't fit the iteration model of some sequences, but ranges would fit right in if they didn't require separability into two iterators.

Since C++20, the end iterator doesn't have to be the same type. Instead it can be something like a tag with no own runtime data, and comparing with it can be implemented as asking the other iterator if it is 'out of data'.

Yeah that's definitely an improvement in some respects, but (a) generic code still has to deal with 2 iterators, (b) generic code now has to allow them to be different types (so old code will have to be rewritten), (c) it doesn't change the fact that iterators are still treated like cheap objects (generalized pointers) and hence the begin iterator is still potentially expensive to store and copy around regardless of what you do with the end iterator, and (d) it's still a fundamental model mismatch relative to the actual problem, just not quite as unpalatable as before. Ranges fundamentally change the calculus around iteration.

P.S. (e) Is this sentinel-based approach even composable? If your iterator needs to use other iterators underneath, what do you do? You have to store a 'full' iterator anyway... or now you waste even more space and time storing a discriminated union. The fact that a range represents the whole sequence in one object instead of two makes composition intuitive and trivial.

Re: Writing a custom iterator in modern C++

#43

Post by cma »

mehrdadn wrote: post #42
stkdump wrote: post #38

Earlier quoted context omitted.

Since C++20, the end iterator doesn't have to be the same type. Instead it can be something like a tag with no own runtime data, and comparing with it can be implemented as asking the other iterator if it is 'out of data'.

Yeah that's definitely an improvement in some respects, but (a) generic code still has to deal with 2 iterators, (b) generic code now has to allow them to be different types (so old code will have to be rewritten), (c) it doesn't change the fact that iterators are still treated like cheap objects (generalized pointers) and hence the begin iterator is still potentially expensive to store and copy around regardless of…

It isn't a sentinel is it? He said no runtime data, so it sounds like some kind of empty tag for the type system. I'm not sure if it is related to what he is describing, but C++20 also added [[no_unique_address]] for something to do with truly empty members.

Re: Writing a custom iterator in modern C++

#44

Post by mehrdadn »

cma wrote: post #43
mehrdadn wrote: post #42

Earlier quoted context omitted.

Yeah that's definitely an improvement in some respects, but (a) generic code still has to deal with 2 iterators, (b) generic code now has to allow them to be different types (so old code will have to be rewritten), (c) it doesn't change the fact that iterators are still treated like cheap objects (generalized pointers) and hence the begin iterator is still potentially expensive to store and copy around regardless of…

It isn't a sentinel is it? He said no runtime data, so it sounds like some kind of empty tag for the type system. I'm not sure if it is related to what he is describing, but C++20 also added [[no_unique_address]] for something to do with truly empty members.

Distinguishing two members of a union with... 0 bytes of extra data? Sounds like magic.

Not 100% sure about the terminology. Pick whatever word might fit it better. I just called it a sentinel.

Re: Writing a custom iterator in modern C++

#45

Post by vardump »

robscallsign wrote: post #8
arcticbull wrote: post #2

There's six different kinds of iterator?! Off hand, is it just me or... - Isn't an iterator that outputs data to its recipient container not an iterator, but rather some type of filling API? - Isn't a random access iterator not an iterator but rather a slice view? - Isn't a contiguous iterator a leaky abstraction in that an iterator is just an interface that shouldn't expose how the data backing it is stored? This it…

Keep in mind that most of the details you mentioned are for the developer of the library, not the end user/consumer of the library. Ultimately most consumers of the library care if they can call std::sort(YourSpecialContainer.begin(), YourSpecialContainer.end()); in a consistent manner with some semblance that the use of templates and interfaces result in nearly zero overhead of the abstraction.

"nearly zero overhead"

I can't call anything "nearly zero overhead" that can generate large amounts of code. Not at least with a pure conscience.

I've seen enough many cases of better performance with more "overhead" but drastically smaller code size.

Re: Writing a custom iterator in modern C++

#46

Post by pumpkinpal »

mehrdadn wrote: post #42
stkdump wrote: post #38

Earlier quoted context omitted.

Since C++20, the end iterator doesn't have to be the same type. Instead it can be something like a tag with no own runtime data, and comparing with it can be implemented as asking the other iterator if it is 'out of data'.

Yeah that's definitely an improvement in some respects, but (a) generic code still has to deal with 2 iterators, (b) generic code now has to allow them to be different types (so old code will have to be rewritten), (c) it doesn't change the fact that iterators are still treated like cheap objects (generalized pointers) and hence the begin iterator is still potentially expensive to store and copy around regardless of…

The iterator and sentinel do not need to be the same type, they just need to be equality comparable. If you wanted to represent a infinite range you could implement it in terms of a regular iterator and an empty sentinel type to which the regular iterator compares false to.

Re: Writing a custom iterator in modern C++

#47

Post by mehrdadn »

pumpkinpal wrote: post #46
mehrdadn wrote: post #42

Earlier quoted context omitted.

Yeah that's definitely an improvement in some respects, but (a) generic code still has to deal with 2 iterators, (b) generic code now has to allow them to be different types (so old code will have to be rewritten), (c) it doesn't change the fact that iterators are still treated like cheap objects (generalized pointers) and hence the begin iterator is still potentially expensive to store and copy around regardless of…

The iterator and sentinel do not need to be the same type, they just need to be equality comparable. If you wanted to represent a infinite range you could implement it in terms of a regular iterator and an empty sentinel type to which the regular iterator compares false to.

I'm not sure why you're repeating the comment I replied to, but this is exactly what I replied to in my comment.

Re: Writing a custom iterator in modern C++

#48

Post by pumpkinpal »

mehrdadn wrote: post #40
tlb wrote: post #36

Earlier quoted context omitted.

Can you give an example of such a sequence?

Any kind of generator is basically like this. Imagine one for listing the contents of a directory... maybe it looks like this: class DirectoryChildren { void *dir; void *buffer; size_t buffer_size; size_t buffer_offset; ... public: bool next(FileInfo *info); }; Bear in mind the buffer only represents a chunk of intermediate results fetched from the OS; when we reach its end, we have to request more data from the OS.…

This functionality already exists in the C++ standard library as std::filesystem::(recursive_)directory_iterator with the default constructor creating a sentinel value. This is solution (1) and this is due to the restriction that prior to C++20 iterators were required to be the same type. C++20 relaxes this restriction and allows the sentinel to be any type as long as it is equality comparable with the other iterator. Since on *nix systems readdir is used under the hood, the sentinel can simply be an empty type that is only equal when the actual iterator's last cached dirent pointer is equal to NULL. The sentinel itself can be an empty type.

Re: Writing a custom iterator in modern C++

#49

Post by fjfaase »

Iterators are a very powerful concept, however, it is very cumbersome and often impossible, to implement some interesting iterator based on the standard iterators. This stems from the idea that any iterator can based on a single pointer and use pointer comparison for indicating the start and the end of the contents.

The most common case, are forward output iterators, for which I usually define a class that defines the methods more and next, that can be used as:

for (MyIterator it(data); it.more(); it.next())

Re: Writing a custom iterator in modern C++

#50

Post by rualca »

quietbritishjim wrote: post #15

The classic iterator categories (input, output, ...) discussed in this article have been deprecated in C++20, and replaced with new concepts. I would expect a post from 2020 claiming to be about iterators "in modern C++" to be specifically about that change, but actually it's just about the legacy categories, so this is a pretty worthless article.

> I would expect a post from 2020 claiming to be about iterators "in modern C++" to be specifically about that change (...)

...and yet here I am, still struggling to get some of my employer's C++ projects to build with C++14.

Post reply on HN