Wie kann ich das verschwenderische Kopieren von Schlüsseln in einer B-Tree-basierten STL-ähnlichen Karte vermeiden? ⇐ C++

[Anonymous]

Ich ersetze eine Verwendung von std::map in einem Hot Path durch cpp-btrees btree_map. Aber wenn die Optimierung aktiviert ist, beschweren sich GCC und Clang über einen strikten Aliasing-Verstoß. Das Problem läuft auf folgendes hinaus:

Code: Select all

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;
// ...
}
};

Das brachte mich zum Nachdenken: Gibt es eine Möglichkeit, dies so effizient zu machen, dass es nicht auf undefiniertem Verhalten beruht? Die Schlüssel, die ich verwende, sind effizient beweglich, aber ziemlich langsam zu kopieren, daher würde ich gerne vermeiden, bei jedem Einfügen viele Schlüssel zu kopieren. Ich habe darüber nachgedacht

• Verwenden Sie value_type-Werte[N] und dann const_cast(values.first) = std::move(key), um den Schlüssel zu verschieben, aber ich bin mir ziemlich sicher, dass das immer noch undefiniert ist
• Zurückgeben von std::pair statt std::pair&, wenn zutreffend, aber ich bin mir nicht sicher, ob dies immer noch die Containeranforderungen erfüllen würde (ich habe gehört, dass ...::reference eigentlich ein Referenztyp sein soll)
• Das ist mir egal. Der Code funktioniert so wie er ist, aber ich bin gespannt, ob er auf standardkonforme Weise umgesetzt werden kann. Es besteht auch die Möglichkeit, dass zukünftige Compiler andere Dinge mit dem UB machen, und ich kenne keine Möglichkeit, -fno-strict-aliasing nur auf eine einzelne Klasse anzuwenden.

Irgendwelche anderen Ideen?