Google Abseil Btree

В C++ библиотеку Google Abseil https://github.com/abseil/abseil-cpp/tree/master/absl/container, о которой я уже писал (https://t.me/seaplusplus/69), добавили четыре новых STL-like Btree контейнера: absl::btreemap, absl::btreemultimap, absl::btreeset и absl::btreemultiset. Данные хранятся в памяти, но под капотом алгоритм, который пришел из баз данных. Btree хранит несколько элементов в одном блоке памяти, что уменьшает количество аллокаций, а также за счет более эффективного использования кэша работает быстрее в большинстве случаев.

Это практически drop-in замена std::map и std::set. Однако при вставке и удалении происходит инвалидация итераторов. Поэтому надо быть осторожным.

English version: https://telegra.ph/Google-Abseil-Btree-10-20