Anzahl der shared_ptrs in persistenter Datenstruktur reduzieren

Question

Ich stehe vor einer Design-Entscheidung für eine einfach verknüpfte Listenklasse. Die grobe Idee:

template<typename T> 
class List { 
public: 
    ... 

private: 
    struct Node { 
     std::shared_ptr<const T> value; 
     std::shared_ptr<const Node> next; 
    }; 

    std::shared_ptr<const Node> node_; 
}; 

Ja, ich kenne eine Menge shared_ptr s gibt es umher, aber das ist, weil List eine funktionelle persistente Datenstruktur, die so viel strukturelle Teilung wie möglich benötigt. In dieser Implementierung müssen zum Beispiel beim Umkehren einer Liste keine Elemente kopiert werden, und mehrere Listen können eine gemeinsame Unterliste teilen (indem sie auf denselben shared_ptr Endabschnitt verweisen).

Das gesagt, ich fühle immer noch, es gibt vielleicht zu viele shared_ptr s. Gibt es trotzdem die Möglichkeit, die Anzahl der verwendeten zu reduzieren, während strukturelles Teilen weiterhin möglich ist? Etwas wie die Kombination der beiden shared_ptr s innerhalb einer Node, um den Overhead von Kontrollblöcken zu reduzieren ... Ich weiß nicht, vielleicht gibt es keinen Weg, oder vielleicht gibt es. Jede Idee ist willkommen, sogar über die Neugestaltung der List Klasse insgesamt.

Answer 1

Sie möchten Daten ohne Struktur teilen (der umgekehrte Fall).

Sie möchten Struktur teilen.

Beide erfordern gemeinsame Zeiger. Wenn Sie den Steuerblock-Overhead jedoch reduzieren möchten, können Sie dies tun, solange Sie die Lebensdauer verschränken.

Sie können die Lebensdauer des T an seinen Knoten binden. Der umgekehrte Knoten muss dann auch den ursprünglichen Knoten persistieren lassen. Dies kann dazu führen, dass die Struktur ihre Bedürfnisse überlebt, macht den reinen Vorwärtsfall jedoch weniger teuer.

Machen Sie den Pointer-to-T zu einem rohen Pointer.

Erstellen Sie eine kombinierte Struktur mit einem T und einem Knoten darin.

Verwenden Sie make_shared, um es zu erstellen.

Jetzt machen Sie den Pointer-to-T Punkt am T in der kombinierten Struktur.

Als nächstes verwenden Sie den Aliasing-Ctor, um ein Shared-Ptr zu dem Knoten zu erstellen, der den Steuerblock der kombinierten Struktur teilt.

Um umzukehren, erstellen Sie eine Helper-Struktur mit einem Knoten und einem freigegebenen Ptr zu Node. Machen Sie den Helfer freigegeben. Richten Sie den freigegebenen Knoten ptr auf den Forward-Knoten, T ptr auf den T ptr im Forward-Knoten und verwenden Sie dann den Aliasing-Ctor von shared ptr, um ein gemeinsam genutztes ptr an Node zu erhalten.

Ich glaube nicht, dass es das wert ist.