Одна из причин, по которой std::map может быть менее эффективной, чем некоторые реализации дерева в C, заключается в том, что она не является "навязчивой".
В навязчивом контейнере бухгалтерская информация хранится непосредственно в значениях. Например, двоичное дерево в C может быть основано на этом типе:
struct node {
node *left, *right;
int key;
int value;
};
Тогда как в C ++ это будет:
std::map<int, int>
Разница в том, что когда вы вставляете пару ключ / значение в карту C ++, карта выделяет память для хранения узла, а затем копирует в него пару ключ / значение. В C узел может быть выделен один раз, а затем вставлен в дерево без дальнейшего выделения или копирования.
Boost Intrusive реализует несколько навязчивых контейнеров в C ++, основной целью которых является обеспечение паритета производительности со структурами данных "стиль C". map нет, но есть boost::intrusive::set, который можно использовать вместо этого (заставив value_type удерживать ключ и значение на карте).
C ++ 17 добавлено std::map::insert(node_type&&), что позволяет вставить узел без копирования ключа и значения. Но единственный способ получить значение node_type - использовать std::map::extract(key). Вы не можете выделить узел вне контейнера (с помощью C или Boost Intrusive вы можете).