डेटा संरचनाओं को लागू करते समय स्मार्ट या कच्चे पॉइंटर्स?

Question

मैं मानक पुस्तकालय के स्मार्ट पॉइंटर्स, unique_ptr और shared_ptr के साथ पढ़ रहा हूं और प्रयोग कर रहा हूं और हालांकि वे बहुत से मामलों के लिए स्पष्ट रूप से महान प्रतिस्थापन हैं जहां कच्चे पॉइंटर्स को खतरनाक समझा जा सकता है, मैं डेटा संरचनाओं को लागू करते समय उनके उपयोग से अनिश्चित हूं।

प्रयोग करने के लिए, मैंने एक हैश मानचित्र का एक उदाहरण लिखा है जो shared_ptr का उपयोग करता है - जो मेयर के प्रभावी आधुनिक सी ++ के अनुसार लगभग unique_ptr के आकार को दोगुना कर देता है। इस कारण से मैं unique_ptr का उपयोग करना चाहता हूं लेकिन मैं फंक्शन, अपडेटिंग और कॉपी करने में जो कर रहा हूं उसके कारण मैं स्टंप हूं।

क्या किसी को इस समस्या के लिए कोई सुझाव है? कच्चे पॉइंटर्स का उपयोग कर डेटा संरचनाओं को लिखा जाना चाहिए?

#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

स्मार्ट सूचक का चुनाव कैसे अपने डेटा संरचना "मालिक" ढेर-आवंटित वस्तुओं पर निर्भर करता है।

आप बस निरीक्षण करने के लिए, और नहीं ही एक वस्तु , एक कच्चे सूचक, एक संदर्भ (चाहे वह है ढेर-आवंटित या नहीं की स्वतंत्र रूप से) की जरूरत है या एक std::reference_wrapper उचित विकल्प है ।

अगर आप की जरूरत अद्वितीय स्वामित्व (ढेर-आवंटित वस्तु के सबसे एक मालिक पर), तो std::unique_ptr का उपयोग करें। इसमें कोई अतिरिक्त समय/मेमोरी ओवरहेड नहीं है।

आप स्वामित्व (ढेर-आवंटित वस्तु के मालिकों के किसी भी संख्या) साझा की जरूरत है, तो std::shared_ptr का उपयोग करें। इसके परिणामस्वरूप अतिरिक्त समय/मेमोरी ओवरहेड होता है क्योंकि एक अतिरिक्त पॉइंटर (संदर्भ गणना मेटाडाटा में) को संग्रहीत किया जाना चाहिए, और क्योंकि इसे एक्सेस करने से थ्रेड-सुरक्षित होने की गारंटी है।

std::unique_ptr(एक कच्चे सूचक के स्थान पर) उपयोग करने के लिए जब तक आप वास्तव में खुद वस्तु की जरूरत है कोई ज़रूरत नहीं है।

मान लिया जाये कि आप वस्तु के मालिक हैं की जरूरत है, std::shared_ptr (एक std::unique_ptr के स्थान पर) का उपयोग करने के लिए जब तक आप वास्तव में साझा स्वामित्व अर्थ विज्ञान की जरूरत की आवश्यकता नहीं है।

---

आपके मामले में, यह है कि आप अपने HashMap में ढेर नोड्स की एक अधिकतम राशि लग रहा है। इसलिए, मैं मान रहा हूं कि आप HashMap उदाहरण नोड्स के अद्वितीय मालिक होने के लिए उदाहरण चाहते हैं।

आप किस प्रकार का उपयोग करना चाहिए?यदि आप एक ढेर अविवेक के साथ वस्तुओं की दुकान std::unique_ptr उपयोग करना चाहते हैं

1. , इन ढेर-आवंटित वस्तु की अद्वितीय मालिक के रूप में है और हमेशा करेंगे:

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

   आपके पास दो विकल्प HashMap उदाहरण हो।

2. यदि आप वस्तुओं को सीधे HashMap में स्टोर करना चाहते हैं, तो कोई ढेर संकेत नहीं है, तो किसी भी पॉइंटर का उपयोग न करें। इससे बहुत बड़े HashMap उदाहरण हो सकते हैं। next नोड्स तक पहुंचने के लिए इंटरफ़ेस बोझिल हो जाता है।

---

विकल्प 1 (दुकान ढेर में नोड्स):

यह सबसे सामान्य है, और शायद सबसे अच्छा विकल्प है।

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

यह लाइटर HashMap उदाहरणों (स्मृति पदचिह्न के संदर्भ में) का परिणाम देगा।

नोट: एक std::array के स्थान पर एक std::vector का उपयोग कर HashMap काफी का आकार कम हो जाएगा, लेकिन एक अतिरिक्त ढेर अविवेक का परिचय देंगे। इसी तरह की डेटा संरचना को लागू करने का यह एक आम तरीका है। आप आमतौर पर HashMap उदाहरण जितना संभव हो उतना हल्का वजन चाहते हैं, ताकि इसे कुशलतापूर्वक कॉपी/स्थानांतरित/संग्रहित किया जा सके।

नोड्स को एक दूसरे के बीच जोड़ने के लिए स्मार्ट पॉइंटर्स का उपयोग करने की आवश्यकता नहीं है, क्योंकि नोड्स का स्वामित्व विशेष रूप से HashMap द्वारा किया जाता है। कच्चा सूचक पर्याप्त होगा।

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

कोड ऊपर से कार्य करेंगे, यह सोचते हैं कि HashMap जब next तक पहुँचने अभी भी जीवित है।

---

विकल्प 2 (नक्शा उदाहरण में दुकान नोड्स):

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

HashMap उदाहरणों HashNode<K, T> के आकार के आधार पर भारी हो सकता है।

आप नोड्स सीधे कोई ढेर अविवेक के साथ HashMap में स्टोर करने के लिए चुनते हैं, तो आप, आंतरिक सरणी तक पहुँचने के लिए आगे बढ़/कॉपी करने HashMap चारों ओर नोड्स की स्मृति पता बदल जाएगा के रूप में एक सूचकांक का उपयोग करना होगा।

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]; 
    } 
};