CppCon 2015

STL has a big history. Due to class paradigm of C++, many STL containers have a flat layout in memory, i.e. containers naturally store objects and address objects rather than their indexing entities such as smart pointers (which are, strictly speaking, objects too). This model has a benefit of lower memory fragmentation, that causes better CPU cache performance. However, many tasks in real life require reordering of objects, that requires compexity of O(n*q), where q is a size of an object and n is a compexity measured in operations. Thus, some imlementations of operations with reordering objects in some containers are much slower that they could be. This problem could sometimes be solved by storing “pointers” as index entities in containers instead of the objects by themselves, what improves performance by q times, but causes memory fragmentation and worse cache performance. Algorithmically, the solution with pointers is obviously better, but it is still not the most efficient one. In the presentation I will show myimplementations of containers using both approaches and having the best of two worlds. I will compare these methods with classical and modern approaches and draw some conclusion, encouraging everybody to use the power of algorithms with C++.