5 ms·
Somewhat related but C++20 ranges do not replace iterators and instead build a higher level of abstraction upon iterators. Ranges are implemented in terms of it
by pumpkinpal 6y ago
Somewhat related but C++20 ranges do not replace iterators and instead build a higher level of abstraction upon iterators. Ranges are implemented in terms of iterator pairs.
- mehrdadn 6y agoYeah. 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.
- tlb 6y agoCan you give an example of such a sequence?
- mehrdadn 6y agoAny 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. If you had to make an iterator for this, what would you do? You'd basically need to either (a) create iterators that at least duplicate the entire state of DirectoryChildren on the stack, or (b) make iterators allocate on the heap. Both of these suck, because (1) iterators are passed around and copied all over the place on the assumption that these are fundamentally cheap operations, which is an assumption that easily breaks (like here), and (2) the iterators fundamentally do not have any meaning or utility as separate entities from the range itself.
- pumpkinpal 6y agoThis 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.
- mehrdadn 6y agoWhy do you keep repeating the same comment? Are you reading my replies? I already addressed exactly what you're talking about: https://news.ycombinator.com/item?id=25492756 https://news.ycombinator.com/item?id=25492756
- stkdump 6y agoSince 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'.
- mehrdadn 6y agoYeah 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.
- cma 6y agoIt 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.