Alan Talbot “How to Choose the Right Standard Library Container, and Why You Should Want Some More”

CppCon.org
-
Discussion & Comments: / cpp
-
Presentation Slides, PDFs, Source Code and other presenter materials are available at: github.com/CppCon/CppCon2019
-
Containers are at the heart of the Standard Library and are used in almost all non-trivial C++ programs, but a misunderstanding of the relationship between their algorithmic complexity and actual behavior can dramatically affect program performance. One of the most compelling advantages of C++ is that it allows programs to be precisely crafted so as to take full advantage of the hardware while still providing sophisticated high-level abstractions that represent the domain in elegant, expressive and natural ways. Knowing how to choose the correct container for each task and how to use that container most effectively is a vital part of that craft, and can have a profound impact on the behavior of a program.
From a user’s perspective many popular computer programs are no faster today than they were 30 years ago despite the enormous increase in measured performance of the hardware. I believe that this is due in part to a misconception that efficiency does not matter in most situations because processors are so fast and numerous, and memory is so large. This talk will proceed with the assumption that performance almost always matters, and so attention to efficiency is an essential aspect of good programming. We will examine the Standard Library containers and consider both the abstractions they are meant to express and the practical limitations they impose. We will then explore some containers that are not yet in the Standard Library which promise efficiency improvements in various situations. Finally we will look at a number of common cases and compare the naïve implementation with one that considers the actual behavior of containers on modern processors.
-
Alan Talbot
LTK Engineering Services
Manager - Software Engineering
Lebanon, NH
Alan Talbot started programming in 1972, in BASIC on a DEC PDP-8. He began his professional programming career in 1979 and started using C++ in 1989. For 20 years he was a pioneer in music typography software, then spent 8 years writing digital mapping software, and has spent the last 9 years writing railroad simulation software. He has been a member of the C++ Standards Committee since 2005, and most of his Committee work has focused on improvements in efficiency. His contributions include container emplace, extract and merge of associative container nodes, and the emancipation of unions.
-
Videos Filmed & Edited by Bash Films: www.BashFilms.com
*-----*
Register Now For CppCon 2022: cppcon.org/registration/
*-----*

[@Dave_thenerd]

I really, really want boost's static_vector in the standard.

[@alexeysubbota]

Real experience of the real programmer

[@dirtbikersteve]

19:15 it is necessary front is reset. You're taking a pointer to memory that may be reallocated when the push back occurs. This gives you a dangling pointer if it's not reset

[@zeropointer125]

In my suggestions, it only showed "how to pick the right stl container and why" and I genuinely thought the ret of the title would be "a why it will be vector"

[@robbie_]

Haha my thought exactly. 99% of the time it's vector, and the rest of the time it's unordered_map.

[@alexeydmitriev1681]

You don't need to shift anything if you consider the first element to be right after the last one.
aka cyclic buffer

[@jgreitemann]

That would however give up the contiguous storage guarantee given by vector. This may or may not be acceptable, but it doesn't make for a true drop-in replacement of vector. The storage will certainly still be cache-efficient. Iterators can no longer be completely dumb (like vector's which are just incrementing pointers) -- hard to say how detrimental that might be to performance. But if you iterate often and push/pop only occasionally, the shift operation (which is still amortized constant) might be cheaper than having to account for a possible cyclic wrap-around upon each and every increment.

[@CarrotCakeMake]

I was wondering about this too, why not a circular buffer? Rust uses a circular buffer for deque.

[@Astfresser]

Branch overhead yes. Would be interesting to test

[@pazdziochowaty]

Is this recycle bin sort of colony? Like elements marked deleted but not actually deleted

[@kiffeeify]

on slide 61, would'nt the pop_back call the destructor on an invalid (becaused moved) element? Obviously that doesnt matter for ints, but in a general case?

[@kaiserprinz6472]

That is no problem, the destructor of an moved object is always called when it goes out of scope. Here is an example: gcc.godbolt.org/z/h7nh39

[@childhood1888]

33:27

[@jeanblaguin5830]

39:04 so he just skipped 7 hours by reusing the same capacity, i might look back to some of my code to try this.

[@robbie_]

I didn't watch the video but I'm guessing the answer is always vector.

[@destiny_02]

For sake of consistany atleast they should have added operator [] to lists and push_front to vectors

[@Astfresser]

No that would only encourage misuse of the container. If you want to random access a list something is wrong with your code

[@childhood1888]

28:40