Не такие уж стандартные контейнеры, или Улучшенные версии STL-контейнеров из библиотеки Boost

В любом учебном курсе по C++, даже начального уровня, обязательно изучают, как устроен std::vector. Детали внутреннего устройства std::vector в подробностях продолжают изучать в вузах, спрашивать на собеседованиях, обсуждать на конференциях. То же самое происходит с контейнерами std::list, std::deque, std::map и std::unordered_map: про их реализацию и особенности внутреннего устройства можно говорить бесконечно долго, про них все еще делают доклады, снимают лекции и пишут статьи. И их продолжают использовать в продакшен-коде даже в самых крупных и известных компаниях.

При этом в библиотеке Boost давным-давно есть альтернативные версии контейнеров, которые выигрывают у стандартных по многим показателям. Однако об этих версиях почти никто не знает, о них почти нет лекций, статей и докладов. Пора положить этому конец и разобраться в том, как еще могут быть устроены контейнеры, помимо тех версий из STL, о которых и так все знают.

В этом докладе мы обсудим внутреннее устройство не таких уж стандартных контейнеров: stable_vector, devector, bimap, circular_buffer, а также интрузивных версий list, map, unordered_map и их разновидностей.