Back to Basics: Iterators in C++ - Nicolai Josuttis - CppCon 2023
Вставка
- Опубліковано 1 січ 2024
- cppcon.org/
---
Back to Basics: Iterators in C++ - Nicolai Josuttis - CppCon 2023
github.com/CppCon/CppCon2023
One key success factor of C++ was the introduction of the Standard Template Library (STL) bringing together containers/ranges and algorithms using iterators as glue API to iterate over elements of collections.
This talk will present the basics of the design of iterators, the various consequences, remarkable corner cases, and what this means when using ranges and views as introduced with C++20.
---
Nicolai Josuttis
Nicolai Josuttis (www.josuttis.com) is well-known in the community for his authoritative books and talks. For more than 20 years he has been a member of the C++ Standard Committee. He is the author of several worldwide best-sellers, including:
- C++20: The Complete Guide
- C++17: The Complete Guide
- C++ Move Semantics: The Complete Guide
- The C++ Standard Library: A tutorial and Reference
- C++ Templates: The Complete Guide (w/ David Vandevoorde & Doug Gregor)
---
Videos Filmed & Edited by Bash Films: www.BashFilms.com
UA-cam Channel Managed by Digital Medium Ltd: events.digital-medium.co.uk
---
Registration for CppCon: cppcon.org/registration/
#cppcon #cppprogramming #cpp #iterator - Наука та технологія
This is an amazing talk. Thank you for this Nicolai Josuttis.
I struggle with why the committee included caching of the first match. Wouldn't it be sufficient with a special function for the rare cases it is desired or needed?
// e.g. something like
template
auto cached_filter(Iter start, Iter end, const auto& pred) {
start = std::find_if(start, end, pred);
return std::ranges::subrange(start, end) | std::views::filter(pred);
}
I'm sure someone thought of std::views::cached during the standardization, I can't see why that wasn't chosen over the internal caching nonsense.
Where std::views::cached saves begin() and any other data required for ad-hoc "amortized-constant time" requirements.
For real, whatever happened to "if you don't need it, you don't pay for it"? Surely in a pipeline like this vec | cached_begin | filter(greater_than(40)) would have been perfectly reasonable?
Since C++20 the committee has delivered more and more ivory-tower broken changes (there were a few in 17 already).
Now with the proposals in 26 it is becoming just absurd.
Great talk. I’m not sure but I think that the fact that the committee chose to make some scenario “undefined behavior” gives them the opportunity of changing (defining) that scenario in subsequent standard versions. Of course in the case of std::views::filter_view it will be hard to ‘fix’ the situation without relaxing the requirement of begin() taking amortized constant-time (but potentially such relaxation could be made (there’s also a potential problem keeping ABI if we eliminate the caching in filter_view)
I think the question of undefined behaviour as is often the case is to allow optimisations rather than leaving it open to change. Most of the explicitly mentioned UB is either because it can't be known at compile time or to allow optimisations by the library or compiler.
Relaxing time complexity has been done before; e.g. since c++11 std::list can return its size in constant time (whereas before it was in linear time, apparently because of the splice member function). I suppose if real-world practice shows the views thing causes too many issues, they might change it later; the ranges stuff isn’t too widely used yet.
Believe it when I tell you that the committee can change any behavior and it won't matter if it was undefined before or not. They may dislike breaking backwards compatibility, and avoid it whenever possible and then some, but they have done so in the past and could for any revision. Even the C committee has done so and has again with C23.
Great talk from Nicolai Josuttis. 点赞。👍
Some say the juniors say "yes, chef" after scrum with Nicolai.
48:00 std::ranges::remove already returns the (valid) subrange with elements removed.
I am not sure if I get this right. If we have the requirement of amortised constant time in begin(), why does the standard say "This is undefined behaviour if the resulting value doesn't satisfy the filter predicate"? The statement of standard is a more strong statement than the consequence of prefetching. It could be like: "Running same filter again on container is undefined behaviour, if the elements of underlying container are changed"
Thanks for the great talk. I also have a question: why does set/map support bidirectional iterators ? Shouldn't that be an implementation detail ?
They are sorted, so there should be one logical direction
why they did not "simply" implemented two different version of std::view::filters, one for const iterator that can be optimized like now, and one for non const iterator that can change values, so we can have the best of both world, speed on first case and coherence in second case...
Perhaps interesting to no one, but the "solution" I came up with in my own language is to allow for warning against the use of certain functions. For instance, I provide a list class as part of my standard library, but I have a preprocessor directive that warns against using it in its entirety, and for multiple element iteration and indexing it gives a second warning that the operation will be computationally expensive. I'm sure that people who love lists will find it childish and insulting, but for years I've told people to use arrays for everything they can because it's a superior data structure in nearly every way and apparently so have others. Of course, I still provide the functionality to do random access of a list, or to increment iterators more than once at a time, such as it += 5; and I even provide a slice operation for lists. I really don't get why C++ restricts so much in the name of speed, when warning against use of something would be more useful. Annoying, yes, but apparently people these days want annoying compilers.
Great talk. That whole std::view caching situation is very concerning. A mandatory optimization that induces semantic errors and promotes undefined behavior. With all due respect, it is unnecessarily patronizing and it makes the committee seem much less resourceful and discerning than it once was.
Yeah we should be taking foot guns out of C++ instead of adding them
@@StrikeEagleIII This is not possible, I'm afraid. All C++ constructs must adhere to the std::Footgunnable Concept.
from the way I understood it, caching as an optimization was not the goal. nico kinda shows it from a wrong side. what really happened is that there is no sensible way to define multipass filter view with mutation, and whether you cache or not, does not make a difference. it is not a c++ pitfall but a pitfall of all languages where you can mutate multipass lazy filter, even rust has this footgun.
so comittee decided since they cannot define this behaviour, they won't, and since they won't define this behaviour then caching will not bring any more problems.
and while I do understand why they did this, I'd prefer version with no caching.
What's going on behind the scenes?
slide 19, second loop:
If the vector has an odd number of elements, the very last pos+=2 will jump over the end iterator and invoke UB.
Yeah, that's a bug in the slide.
"will jump over the end iterator and invoke UB."
Who says that this is UB? I can't find anything in the standard saying that this would be UB. Random-access iterators make no mentioning of not being allowed to increment the end-iterator. Other iterator-traits do have that restriction.
Did you mean the second loop on the slide? Can you explain why do you consider it as UB? In case of odd number of elements, on the last step `pos` will be behind the .end() - that is right, but it will not be used, am I right?
Great talk !! but i didn't get how remove algorithm replaces ... anyone help here
If I understanding what you’re asking correctly, the remove was just moving the elements down, and left the last 2 elements where they were. I think what he didn’t mention was that the size reduces by 2. So if you iterate over the new range, it’ll ignore the 2 values at the end as they’re no longer within size, even if they’re technically still there in memory. But if you ignored that new range and continued to use the old range (IIRC that’s what the example was showing), it would still see the 2 removed elements (as you’re now using an incorrect range.
I know that Iterators give a standard way to access containers, like a glue he said, but I just don't like them, when possible, I much rather use the integer indexes, but I do see their utility.
Congratulations Nico! Top must watched recent tech talk of the week.
techtalksweekly.substack.com/p/tech-talks-weekly-2-where-web-tech
"Contiguous iterator" seems like a concept failure to me:
having a contiguous memory layout does not in any way depend on the elements being randomly accessible. You can very well have say a container that guarantees it has contiguous memory but that does not allow backwards iteration.
I have seen libraries that had compiletime sized lists with contiguous memory. They were memcopyable, contiguous, and not random accessible.
it's related to cache locality mate
Indeed, it's a linguistic error. I would think ranged iterator might make for a better name as it applies specifically to a range.
all C++ above the 17 standard in one phrase
"is syntactic sugar"😂
CppCon is a blessing 🫶 Thanks to all of you and Happy New Year.
59:00 Imo, that's not just a Gotcha anymore, that's just actively user-hostile...
"We use c++, b'cause we dont like bad performance" ...interesting
I think this is a really good and important talk, especially for new C++ programmers. But I am kind of frustrated, that Nicolai talks about "we" all the time. To my understanding this is the work of Alex Stepanov and Paul McJones. Here's a link where Alex tells the story and even explains why iterator is kind of a bad naming and how that happend: ua-cam.com/video/84gHZgPCf1s/v-deo.htmlsi=73xPLaJhP-9IJicy&t=1199
56:45 "we have intentionally designed the filter view in a way that one of the major use cases we use a filter for (which is fix the broken elements) has undefined behavior". Worse is better. "The group that standardized this behaviour does not think this is a bug." There should be a law prohibiting the use of C++ for any new software.
but this is indeed not a bug. you shouldn't mutate through a filter view while multipassing not only in c++ but pretty much in every language where said thing is possible. there is no way to define such behavior even without caching .begin(). single pass should be fine and it is more of a wording issue, not a fundamental design flaw. if you are willing, you are always welcome to propose the wording which would allow single pass with mutation.
.end() name has been a bad idea from the start. They should have named it "endex".
Guys you stick in past. Today we need short fast information. Not day long talks about simple standards!
Write our own views then. Because if you’re looking through a stained glass window, you wouldn’t go buy a new stained glass window after painting the bench and planting a tree outside?
Are you talking about iterators in 2023 as something new in C++ ? No wonder people use Python.