Modern C++: What You Need to Know
Why Stack Overflow recommends it
Stack Overflow users link it when answering container-choice and cache-performance questions, citing its argument that std::vector usually beats lists, maps and other pointer-heavy structures.
Recommended by 5 people across 6 different months, 2014 to 2024.
What it is
Herb Sutter's keynote at Microsoft Build 2014 giving an overview of where C++ stood and where it was heading, covering performance-minded native programming on modern hardware. A well-known section explains why contiguous arrays and std::vector beat node-based containers because of caches and prefetching.
What people said
Recommends Richard Critten · 2014-04 · Stack Overflow · on “Ordered versus unordered containers in C++”
Herb Sutter covered this in his talk Modern C++: What You Need to Know [this video] In summary use std::vector, test and profile. But std::vector usually wins by a few orders of magnitude.
Recommends Jack Deeth · 2016-12 · Stack Overflow · on “Automatically resize array after popping any element in C++”
Regarding the performance of `std::vector` - here's Herb Sutter at Build 2014 talking about prefetching and how amazingly quick it is to iterate over vectors: [this video]
Recommends Jack Deeth · 2016-12 · Stack Overflow · on “How does object size impact array perfomance in C++?”
Have a look at Herb Sutter's talk [this video] at the 2014 `//build/` conference. Talks about array performance and caches at 23:30.
Recommends arboreal84 · 2017-05 · Stack Overflow · on “Linux perf reporting cache misses for unexpected instruction”
When you read a memory location, the processor will try to prefetch the adjacent memory locations and cache them. That works well if you are reading an array of objects which are all allocated in memory in contiguous blocks. However, if for example you have an array of pointers which live in the heap, it is less likely that you will be iterating over contiguous portions of memory unless you are using some sort of custom allocator specifically designed for this. Because of this, dereferencing should be seen as some sort of cost. An array of structs can be more efficient to an array of pointers to structs. Herb Sutter (member of C++ commitee) speaks about this in this talk [this video]
Recommends Stephen Newell · 2019-06 · Stack Overflow · on “Are linked lists better than arrays for adding/removing elements at any position in the list?”
Your mileage will vary, but bear in mind arrays are much friendlier to the cache than linked lists. Herb Sutter did a fantastic talk where he covered this: [this video] (skip to about 29:27 if you want to get to the good stuff).
Recommends einpoklum · 2020-07 · Stack Overflow · on “An array of pairs instead of an STL map - possible? What are the pros and cons?”
Several points to note/consider: While Jejo's answer is true in terms of asymptotic complexity, in many practical scenarios - a pair of vectors (or a vector of pairs) may actually be faster than using a map - even for insertion or erasure. See this presentation-fraction [this video] by Herb Sutter extols the virtues, in practice, of using arrays ( std::vector 's) over other structures in various scenarios. It's a fun listen if you haven't had that drilled into you before... There are a lot more than two options for you to choose from - depending on your actual needs: Do you need the map elements to be iterable in increasing order of the keys? i.e. do you need your data to be sorted? If not, then
Recommends Richard Critten · 2023-06 · Stack Overflow · on “Efficient storage for time-based actions”
For up to a few thousand `timer_key`s just use `std::vector` and linear search. The memory pre-fetcher and cache locality beat any other data structure. If you wish to check measure it. Also see Modern C++: What You Need to Know [this video] at 45:50
Cites simon · 2017-05 · Stack Overflow · on “Linked List vs Vector”
I don't like the number one answer here so I figured I'd share some actual research into this conducted by Herb Sutter from Microsoft. The results of the test was with up to 100k items in a container, but also claimed that it would continue to out perform a linked list at even half a million entities. Unless you plan on your container having millions of entities, your default container for a dynamic container should be the vector. I summarized more or less what he says, but will also link the reference at the bottom: "[Even if] you preallocate the nodes within a linked list, that gives you half the performance back, but it's still worse [than a vector]. Why? First of all it's more space -- T
Cites J. Coenen · 2024-02 · Stack Overflow · on “Java 8: performance of Streams vs Collections”
@searchengine27 ArrayLists are a lot faster even for sequential access (because of contiguous memory storage an therefore better cache usage). Bjarne Stroustrup (the inventor of C++) about why you should avoid linked lists with modern hardware: [LINK] ; here are some direct performance comparisons: [this video]