Writing a custom iterator in modern C++
internalpointers.com
internalpointers.com
"The first thing to do is to assign the iterator some properties. Until C++17 this is done by tagging it with the tag dispatch mechanism, while C++20 uses concepts: in this article I will follow the traditional approach."
Normative for the current edition of the Standard, but having been identified as a candidate for removal from future revisions
This is a very blunt tool. In practice, a feature may be deprecated if it is:
1. Legacy inherited from C that serves no modern purpose. The register keyword.
2. Features hardly anybody implemented. Exported templates is the only example I am aware of. Like falling off the edge of the map.
3. Features that proved to be a bad idea, like incrementing a bool.
4. Features that proved to be wholly inadequate, like codecvt for dealing with Unicode.
5. Features that are reasonably new in C++ but obviated by new stuff. You don't need std::bind if you have lambdas.
This is my outsider's perspective; please chime in if you have standards committee insight.
strstream has not been removed, yet, because spanstream is not in yet. Until that is in, there are certain things only strstream can do: specifically, attach to an existing buffer you need to parse things out of, or to format things into.
An article using C++20 will just lead to frustration, as there are still rough edges using concepts, with a standard that was just published last week.
The title is misleading marketing: It gives the impression you need this nice new blog post instead of all the old out of date ones, and that it's all you'll need to know for the foreseeable future.
Apparently too many people still keep using C++ compilers to compile C code, not surprising when there are schools still using Turbo C++ for MS-DOS as teaching tool, as per one of Bjarne talks.
Back to C++20, C++ is no longer my main tool, but I still follow up on it and one of my hobbies is checking new standard features, hardly everything works at is supposed to be and I expect the usual three years for stabilization, so when C++23 will be around the corner, is when I expect all major compilers to fully support C++20 without triggering some kind of compiler error.
That's not surprising as modern C++ predates C++11. Newer standards "merely" make it more convenient to practice it.
At the end of the day, modern c++ is really about emphasizing value types, RAII and parametric polymorphism as opposed to OOP.
Anyway, these days we have it good conformance to new standards comes relatively quickly. It took forever for most compilers to be C+98 conformant (and technically most never reached it).
...and yet here I am, still struggling to get some of my employer's C++ projects to build with C++14.
class DirectoryChildren
{
void *dir;
void *buffer;
size_t buffer_size;
size_t buffer_offset;
...
public:
bool next(FileInfo *info);
};
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.
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.
Not 100% sure about the terminology. Pick whatever word might fit it better. I just called it a sentinel.
edit: looking at this it maybe covers it:
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.
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.
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.
`RandomAccessIterator` implements the `+=` and `-=` operations that `BidirectionalIterator` does not. Algorithms that accept `RandomAccessIterator` can then assume that calling += is possible.
If you want indexed access why wouldn't you just, you know, use anything that implements operator[]?
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).
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 can pick a more specialized algorithm, say, quicksort instead of mergesort. C++ really does enable this at the type level through template specialization. In practice the STL collections haven't lived up to this, and I think the iterator tags are mostly deadweight.
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.
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.
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.
Zero overhead cult is pretty strong. People should profile instead. Sigh.
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.
Even assuming you actually have multiple specializations in the same binary, which is not a given, only the one being in use or that it will be used very soon will be in L1. Instruction cache prefetching is extremely effective.
It's very easy to forget things like memory bandwidth, inter-core/CPU links, etc. are all limited resources. And that on real systems resources are shared.
* 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.
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.
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.
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.
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())
How it decides to compare equal to the .end() instance is also your call. Your example is not a compliant iterator (as in, wouldn't work in a range-based for loop) - yet the same behaviour would be achievable through your own operator++() and operator bool(),
A DSL could codify rules like the ones described in this article and generate at least a rough first pass to be hand-tuned later.
https://www.boost.org/doc/libs/1_75_0/doc/html/stl_interface...
This is not the primary purpose of an iterator. Does anyone want to hazard a guess as to what an iterator’s primary purpose is? You? You? Bueller?
Sometimes C pointers are used for iteration, but I would not say that is their primary purpose.
I really wonder why people put up with something named this way then. "That fool thinks iterators are for iteration!"
Clarity of abstraction and good naming are important, unless the practitioners are masochists.
Take `std::copy_n` for example. You _could_ use this to copy from one vector to another:
std::vector<int> a = {1,2,3}, b = {0,0,0};
std::copy_n(a.begin(), a.size(), b.begin());
std::vector<int> a = {1,2,3};
std::array<int,3> b;
std::copy_n(a.begin(), a.size(), b.begin());
std::vector<int> a = {1,2,3};
std::copy_n(a.begin(), a.size(), std::ostream_iterator<int>(std::cout, " "));A forward iterator doesn't have a difference_type. A random access iterator does.