Smart- oder Raw-Pointer beim Implementieren von Datenstrukturen?

Question

Ich habe gelesen und experimentiert mit den Smart-Pointer der Standard-Bibliothek, unique_ptr und shared_ptr und obwohl sie offensichtlich große Ersatz für viele Fälle sind, in denen rohe Zeiger als gefährlich angesehen werden, bin ich unsicher bei der Verwendung von Datenstrukturen.

Um zu experimentieren, habe ich ein Beispiel für eine Hash-Map geschrieben, die shared_ptr verwendet - die nach Meyers Effective Modern C++ etwa doppelt so groß wie eine unique_ptr sind. Aus diesem Grund würde ich gerne unique_ptr verwenden, aber ich bin ziemlich ratlos wegen dem, was ich in der Add-Funktion, Aktualisierung und Kopieren ausführe.

Hat jemand irgendwelche Vorschläge für dieses Problem? Sollen Datenstrukturen mit rohen Zeigern geschrieben werden?

#pragma once 
#include "core.h" 

const int TABLE_SIZE = 256; 

template<typename K> 
class HashKey { 
public: 
    unsigned long operator()(const K& p_key) const { 
     return (p_key) % TABLE_SIZE; 
    } 
}; 

template<typename K, typename T> 
class HashNode { 
public: 
    K m_key; 
    T m_value; 
    std::shared_ptr<HashNode> next = nullptr; 
}; 


template<typename K, typename T, typename F = HashKey<K>> 
class HashMap { 
public: 
    std::array< std::shared_ptr< HashNode<K, T> >, 128 > m_table; 
    F m_hash_function; 
    int m_elem_count{ 0 }; 

    void Add(K p_key, T p_value); 
}; 

template<typename K, typename T, typename F = HashKey<K>> 
void HashMap<K, T, F>::Add(K p_key, T p_value) 
{ 
    unsigned long key = m_hash_function(p_key); 

    std::shared_ptr<HashNode<K, T>> new_node = std::make_shared<HashNode<K, T>>(); 
    new_node->m_key = p_key; 
    new_node->m_value = p_value; 


    if (m_table[key] == nullptr) { 
     /* only item in the bucket */ 
     m_table[key] = std::move(new_node); 
     m_elem_count++; 
    } 
    else { 
     /* check if item exists so it is replaced */ 
     std::shared_ptr< HashNode<K, T> > current = m_table[key]; 
     std::shared_ptr< HashNode<K, T> > previous = m_table[key]; 
     while (current != nullptr && p_key != current->m_key) { 
      previous = current; 
      current = current->next; 
     } 
     if (current == nullptr) { 
      previous->next = new_node; 
      //current = new_node; 
      m_elem_count++; 
     } 
     else { 
      current->m_value = p_value; 
     } 

    } 
} 

void TestHashMap() { 

    HashMap<int, std::string> hash_map; 

    hash_map.Add(1, "one"); 
    hash_map.Add(2, "does"); 
    hash_map.Add(3, "not"); 
    hash_map.Add(50, "simply"); 
    hash_map.Add(11, "waltz"); 
    hash_map.Add(11, "into"); 
    hash_map.Add(191, "mordor"); 

    std::cout << hash_map.m_elem_count << std::endl; 
} 

Answer 1

Die Wahl des Smart Pointer hängt davon ab, wie Sie Ihre Datenstruktur „besitzt“ die Halde zugewiesenen Objekte.

Wenn Sie müssen einfach beobachten und besitzen nicht ein Objekt (unabhängig davon, ob es Haufen zugeteilt oder nicht), ein roh Zeiger, eine Referenz oder std::reference_wrapper ist die richtige Wahl .

Wenn Sie einzigartige Besitz (höchstens ein Besitzer des Haufens zugewiesene Objekt) benötigen, dann std::unique_ptr verwenden. Es hat keinen zusätzlichen Zeit-/Speicheraufwand.

Wenn Sie geteilt Eigentum (eine beliebige Anzahl von Besitzern des Haufens zugewiesene Objekt), dann std::shared_ptr verwenden. Dies führt zu zusätzlichem Zeit-/Speicher-Overhead, da ein zusätzlicher Zeiger (zu den Metadaten der Referenzzählung) gespeichert werden muss und der Zugriff darauf garantiert Thread-sicher ist.

Es gibt keine Notwendigkeit std::unique_ptr(anstelle eines Rohzeiger) zu verwenden, es sei denn, Sie brauchen eigentlich eigenen das Objekt.

Angenommen, Sie müssen das Objekt besitzen, gibt es keine Notwendigkeit std::shared_ptr(anstelle eines std::unique_ptr) zu verwenden, wenn Sie tatsächlich gemeinsame Verantwortung Semantik müssen.

---

In Ihrem Fall sieht es aus wie Sie ein Maximum von Heap-Knoten in Ihrem HashMap haben. Daher nehme ich an , dass Sie möchten die HashMap Instanz der eindeutige Besitzer der Knoten sein.

Welchen Typ sollten Sie verwenden?

template<typename K, typename T, typename F = HashKey<K>> 
class HashMap { 
public: 
    std::array</* ? */, 128 > m_table; 
    // ... 
}; 

Sie haben zwei Möglichkeiten:

1. Wenn Sie die Objekte mit einem Haufen indirection speichern möchten, verwenden Sie std::unique_ptr, als einzigartige Besitzer dieser heap-Objekt zugewiesen ist und wird immer Sei die HashMap Instanz.

2. Wenn Sie die Objekte direkt in HashMap ohne Heap-Indirection speichern möchten, dann verwenden Sie überhaupt keinen Zeiger. Dies könnte zu sehr großen HashMap Instanzen führen. Die Schnittstelle für den Zugriff auf die next Knoten wird umständlich.

---

Option 1 (Speicher Knoten in der Halde):

Dies ist die häufigste und wahrscheinlich die beste Wahl.

template<typename K, typename T, typename F = HashKey<K>> 
class HashMap { 
public: 
    std::array<std::unique_ptr<HashNode<K, T>>, 128 > m_table; 
    // ... 
}; 

in leichten (in Bezug auf Speicherbedarf)HashMap Instanzen führt Dies wird.

Hinweis: ein std::vector anstelle ein std::array verwendet, wird die Größe von HashMap deutlich zu reduzieren, aber ein zusätzlichen Haufen indirection einzuführen. Dies ist der übliche Weg, eine ähnliche Datenstruktur zu implementieren. Normalerweise möchten Sie, dass die HashMap Instanz so leicht wie möglich ist, damit sie effizient kopiert/verschoben/gespeichert werden kann.

Es ist nicht erforderlich, Smartpointer zu verwenden, um die Knoten untereinander zu verbinden, da die Knoten ausschließlich von HashMap verwaltet werden. Ein roher Zeiger ist ausreichend.

template<typename K, typename T> 
class HashNode { 
public: 
    // ... 
    HashNode* next_ptr = nullptr; 
    auto& next() 
    { 
     assert(next_ptr != nullptr); 
     return *next_ptr; 
    } 
}; 

Der obige Code wird gut funktionieren, vorausgesetzt, dass die HashMap noch am Leben ist, wenn next erreichbar.

---

Option 2 (Speicherknoten in der Instanz):

template<typename K, typename T, typename F = HashKey<K>> 
class HashMap { 
public: 
    std::array<HashNode<K, T>, 128 > m_table; 
    // ... 
}; 

HashMap Instanzen enorm sein kann, abhängig von der Größe des HashNode<K, T>.

Wenn Sie die Knoten direkt in den HashMap ohne Heap indirection zu speichern, sehen Sie einen Index für den Zugriff auf das interne Array, das Verschieben/Kopieren der HashMap um wird Adresse der Knoten verwenden, um den Speicher zu ändern.

template<typename K, typename T> 
class HashNode { 
public: 
    // ... 
    int next_index = -1; 
    auto& next(HashMap& map) 
    { 
     assert(next_index != -1); 
     return map.m_table[next_index]; 
    } 
};