Как я могу избежать расточительного копирования ключей в STL-подобной карте на основе B-дерева? ⇐ C++

[Anonymous]

Я заменяю использование std::map в горячем пути на btree_map cpp-btree. Но при включенной оптимизации GCC и Clang жалуются на строгое нарушение псевдонимов. Проблема сводится к следующему:

Код: Выделить всё

template 
class btree_map {
public:
// In order to match the standard library's container interfaces
using value_type = std::pair;

private:
using mutable_value_type = std::pair;

struct node_type {
mutable_value_type values[N];
// ...
};

public:
class iterator {
// ...

value_type& operator*() {
// Here we cast from const std::pair&
// to const std::pair&
return reinterpret_cast(node->values[i]);
}
};

std::pair insert(const value_type& value) {
// ...
// At this point, we have to insert into the middle of a node.
// Here we rely on nodes containing mutable_value_type, because
// value_type isn't assignable due to the const Key member
std::move_backward(node->values + i, node->values + j,
node->values + j + 1);
node->values[i] = value;
// ...
}
};

Это заставило меня задуматься: есть ли способ сделать это так же эффективно, не полагаясь на неопределенное поведение? Ключи, которые я использую, легко перемещаются, но копируются довольно медленно, поэтому мне бы хотелось избегать копирования большого количества ключей при каждой вставке. Я рассмотрел

• использование значений value_type[N], а затем const_cast(values.first) = std::move(key) для перемещения ключа, но я почти уверен, что это все еще неопределенно
• Возврат std::pair вместо std::pair&, когда это необходимо, но я не уверен, что это по-прежнему будет удовлетворять требованиям контейнера (я слышал, что ...::reference действительно должен быть ссылочным типом)
• Неважно. Код работает как есть, но мне интересно, можно ли его реализовать в соответствии со стандартами. Также есть вероятность, что будущие компиляторы будут делать с UB разные вещи, и я не знаю, как применить -fno-strict-aliasing только к одному классу.

Есть еще идеи?

Подробнее здесь: https://stackoverflow.com/questions/280 ... l-like-map