Arrays

This is the old, vanilla, simple data structure—just a chunk of memory with consecutive objects stored in it. But this simplicity is also its biggest strength, because it guarantees a superior memory locality. When we iterate over an array, the processor hardware is at its happiest—automatic prefetching works, caches stay hot, and branch predictors are 100% correct.

So, no problems at all? Alas not. Arrays are not very malleable. If they are too small, a bigger chunk of memory has to be allocated (first performance sin) and the the old data has to be copied over (second performance sin). Even if we have enough space to insert an element, if we have to insert it in the middle of the array, all the consecutive elements have to be moved one position to the right (by copying, a performance sin as we know) to make a place for a new element. So, we'd like a better data structure please!

std::vector and QVector are examples of containers which use arrays internally and take care of their automatic resizing. std::array doesn't do that and is only a thin wrapper over the naked C++ array.

Strings could also be said to be disguised arrays, as internally they just hold an array of characters, as the std::string and QString classes do. As the strings are oftentimes very heavily used, extra care has to be applied here to avoid unnecessary copying and reallocating of their buffers. One generic technique which can be applied in that context is small string optimization (SSO). 

SSO always preallocates some storage to be used directly to accommodate small strings. Only when a string is too big will dynamic memory be allocated. This strategy has proved to provide consistent performance benefits and is now widely supported. The GCC compiler also switched to this implementation and replaced the previously used copy-on-write technique. Unfortunately, in some Linux distributions, the old implementation is still used due to backward compatibility reasons.

The same optimization can be applied to vectors, but GCC doesn't support it yet. However, Facebook's Folly library and Boost library's small_vector implement it already.

We can search for an item in an array in O(n) time, but if the array is sorted, we can speed it up with binary search to O(log n). However, sorting an array will take O(n log n) time, so we do not want to do it often.