5 ms·
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
by arcticbull 6y ago
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 iterator kindedness feels very C++ in the worst way possible. IMO the only iterator type that makes any sense is an "Input Iterator" and everything else is some sort of hot mess of inconsistency and, uh, C++.
Even with enough time I'm not sure I could design a worse API.
- deleted 6y ago[deleted]
- shakna 6y ago> Isn't a random access iterator not an iterator? Why would it not be? It still allows you to iterate over an entire collection, however the order is left undefined so that certain performance characteristics can be exposed to the underlying implementation. This is the kind of tool you'd reach for if you don't care about the order of a collection, but you do care about performance, and probably care about the entire collection. For example _pairs_ from Lua, used to iterate over key/values in tables, is a random-access iterator. Traversal of the collection is still happening.
- arcticbull 6y agoThe way the random access iterator was described in the article is not that it allows iteration over an un-ordered collection but rather that it allows random access within the collection. This would not necessarily map well to an un-ordered collection. This appears to be born out by the API which supports arbitrary addition and subtraction to the iterator. I could of course be mistaken. What you're describing based on my experience with other languages is simply an "input iterator" over an un-ordered collection. An iterator does not guarantee deterministic/repeatable ordering, just defined ordering (as in, guarantees it won't visit the same element twice), in my experience.
- millstone 6y agoRandom access iterators mean you can efficiently advance or retreat an iterator by an arbitrary amount. So a vector (via pointer arithmetic) but not a linked list.
- arcticbull 6y agoRight 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.
- missblit 6y agoYou can think of it as implementing `seek`, not just `next`. `RandomAccessIterator` implements the `+=` and `-=` operations that `BidirectionalIterator` does not. Algorithms that accept `RandomAccessIterator` can then assume that calling += is possible.
- arcticbull 6y agoWhat's the advantage to using a random access iterator over a get() indexed? Like to me the point of an iterator is that it abstracts over access kind, and exposes the minimum viable view, which is sequential forward and possibly backward access. If you want indexed access why wouldn't you just, you know, use anything that implements operator[]?
- missblit 6y agoJust that iterators is the API that C++ settled on for doing this in a generic way (well concepts in C++20, but I haven't learned that yet). It's totally 100% kosher to write a function that calls `.at()` instead of `operator+=`. As long as it only needs to work on vectors, strings, or other stuff with a `.at()` method. But if the function works on iterators instead it can work on ANY data structure that also fulfills the requirements of RandomAccessIterator API. String Views, raw pointers, a 3rd party Cord library, etc. There's no inherent meaning to the iterator API requiring `operator+=` instead of something closer to `get()`, except that it means that the iterator itself doesn't need to know anything about container bounds (like I said above, raw pointers work as RandomAccessIterators).
- brighton36 6y agoC/C++ may be better understood as a template processing system around assembly.
- glouwbug 6y agoWell, I mean, iterating over a deque, map, vector, and list, in its own, already require the pointer to the next element to decide whether to increment by the type of its size, reference the `next` pointer, or the left/right pointer, or a combination of any of the above 3. It's not the language's fault, it's computer science
- robscallsign 6y agoKeep 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.
- vardump 6y ago"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.
- vardump 6y agoSorry for answering my own reply. Zero overhead cult is pretty strong. People should profile instead. Sigh.
- benibela 6y agoUsually people say std::sort is faster than qsort
- flqn 6y agoIt is, since the compiler can inline the comparator.
- vardump 6y agoIt's true whenever the function call overhead for the comparison operation dominates. Inlining a trivial operation (often just one instruction) is one extreme. At the other extreme L1C cache (typically just 32 kB) gets constantly trashed by numerous type specialized functions. Individually fast when microbenchmarked, but collectively slow. That's why profiling is a must when high performance is required. Microbenchmarks can be very misleading.
- creato 6y agoIt's funny how two of the most common bandwagon posts you can see on HN and other programming venues is: * C++ is a terrible bloated language that no one should use. * The power of modern computers is wasted on lazy software engineers writing software with too many layers of abstraction.
- david2ndaccount 6y agoTo many, these statements are saying the same thing. Your average C++ codebase is a bloated mess with too many layers of abstraction.
- mzsmyk 6y agoYou don't need to use a "terribly bloated language" to write efficient software.
- mehrdadn 6y agoI mean, C++ has lots of compile-time abstractions, but unlike with other languages, it can collapse a lot of them during compilation via its inlining and other optimizations. You don't get that with a language like Python...
- adwn 6y agoI don't see a contradiction between these two statements. There are more languages than C++ and Python. You could use Rust, or some of the languages targeting the JVM or the CLI.
- gpderetta 6y ago> Isn't an iterator that outputs data to its recipient container not an iterator, but rather some type of filling API? Sure, but it makes sense for this api to have the same interface as an iterator so that existing iterators can be used without an adapter. > Isn't a random access iterator not an iterator but rather a slice view? It is an iterator that supports additional functions. You can use a random access oterators with functions that take output iterators, forward iterators, multipass iterators etc. Of you had untelated concepts for each use case the system would be more complex. > 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? Seeing thought abstractions and specializing algorithms is what makes STL style generic code efficient. And it is not inconsistent at all. Stepanov has written in grat details about the theoretical fundations of his design.
- quietbritishjim 6y agoYou seem to have mixed up an objection to the API with an objection to the user of the word "iterator" for something a bit more general than the normal/original meaning. That conflation isn't terribly helpful. Words can have more than one meaning. So long as everyone's on the same page, that's OK.
- millstone 6y agoIterators are inconsistent, but this plays to the strengths of C++'s duck-typed generics. The same code can either copy or insert, depending on whether you use std::begin or std::back_inserter; this isn't principled but it's powerful. The "six types of iterators" overstates it. You don't need to sweat those details unless you are writing boost or something. Just add what you need. I miss C++ iterators in other languages. For example, in Rust it's hard to talk about "a position in a String" which may be advanced or retreated. Usually you give up, use an integer index, and this is much worse.
- Tyr42 6y agoBacking up a utf8 stream is nontrivial though.
- millstone 6y agoThis is an interesting point. Walking backwards through a UTF8 byte stream is easy: just look for the next non-continuation byte, and Rust really can do this, though the API is buried under `str.chars().rev()`. C++ is structured around iterators that point into; this enables e.g. writing into the guts of a std::map but not the guts of a std::string if you care about Unicode, since the write might change the string's byte length.