C++ Educational Content Creator | 20 years of Software Engineering experience distilled into digestible daily posts
std::vector is the quintessential C++ data structure. It offers random access, low memory overhead and, due to the linear layout, is cache and branch-predictor friendly. This makes it often outperform more complex data structures. Whenever picking a storage container, std::vector should be your first choice. Compiler Explorer link: https://lnkd.in/djzu_5aQ #cpp #cplusplus #coding #programming #dailybiteofcpp
👍👍 I would add: if keeping iterators or references/ pointers valid for stored data is important, std::deque is a better choice without the problem of iterator invalidation due to vector grow and reallocations... 😃
The missing part is a good method to handle dynamic classes. Using vector<smartpointer> means loosing the continuous memory advantage. I wrote an in_place_ptr that uses a fixed size byte array as storage and could store any class up to that size. Adding something larger results in a compile time error. The result is that vector::resize/reserve allocates memory for the objects. It’s obviously a bit wasteful but so is the smart pointer it replaces. It’s not a solution that fits every scenario.
Šimon Tóth Indeed array-like data-structures are interesting and super useful. Reach for std::vector first, and consider whether the size can be reserved up-front. Also consider absl::InlinedVector (https://github.com/abseil/abseil-cpp/blob/master/absl/container/inlined_vector.h) where the length is known to good probability, size of the contained data is reasonably small and locality is important. Finally something like absl::FixedArray (https://github.com/abseil/abseil-cpp/blob/master/absl/container/fixed_array.h) is occasionally useful where the size is known at runtime and does not need to change.
I can probably count on one hand the cases where I’ve ever needed another sequential container besides a vector, and when I did, it was a deque, for cases where I’d need to pop off the 1st element. I can’t think of a single time I’ve ever needed a list, except when a particular external library required it.
what about std::array?
I agree with what you say except for branch-prediction friendly. Can we really say branch-prediction friendly if the data of the std::vector structure takes up space in contiguous memory? Considering branch-prediction is a instruction-based situation, I think that having contiguous data in memory will not have any effect on branch-prediction.