c++ - Smart or raw pointers when implementing data structures? -

i have been reading , experimenting standard library's smart pointers, unique_ptr , shared_ptr , although great replacements lot of cases raw pointers might deemed dangerous unsure of use when implementing data structures.

to experiment, have written example of hash map uses shared_ptr - according meyer's effective modern c++ double size of unique_ptr. reason use unique_ptr kind of stumped due performing in add function, updating , copying.

does have suggestions problem? should data structures remain written using raw pointers?

#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) {         /* item in bucket */         m_table[key] = std::move(new_node);         m_elem_count++;     }     else {         /* check if item exists 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; } 

the choice of smart pointer depends on how data structure "owns" heap-allocated objects.

if need observe, , not own object (independently of whether heap-allocated or not), raw pointer, reference or std::reference_wrapper appropriate choice.

if need unique ownership (at 1 owner of heap-allocated object), use std::unique_ptr. has no additional time/memory overhead.

if need shared ownership (any number of owners of heap-allocated object), use std::shared_ptr. results in additional time/memory overhead because additional pointer (to reference count metadata) has stored, , because accessing guaranteed thread-safe.

there's no need use std::unique_ptr (in place of raw pointer) unless need own object.

assuming need own object, there's no need use std::shared_ptr (in place of std::unique_ptr) unless need shared ownership semantics.

---

in case, looks have maximum of heap nodes in hashmap. therefore, i'm assuming want the hashmap instance unique owner of nodes.

what type should use?

template<typename k, typename t, typename f = hashkey<k>> class hashmap { public:     std::array</* ? */, 128 > m_table;     // ... }; 

you have 2 options:

1. if want store objects heap indirection, use std::unique_ptr, unique owner of these heap-allocated object , hashmap instance.

2. if want store objects directly hashmap, no heap indirection, not use pointer @ all. lead big hashmap instances. interface accessing next nodes becomes cumbersome.

---

option 1 (store nodes in heap):

this common, , best option.

template<typename k, typename t, typename f = hashkey<k>> class hashmap { public:     std::array<std::unique_ptr<hashnode<k, t>>, 128 > m_table;     // ... }; 

this result in lighter (in terms of memory footprint) hashmap instances.

note: using std::vector in place of std::array reduce size of hashmap significantly, introduce additional heap indirection. this common way of implementing similar data structure. want hashmap instance lightweight possible, can copied/moved/stored efficiently.

there's no need use smart pointers connect nodes between each other, nodes owned exclusively hashmap. raw pointer sufficient.

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

the code above work fine, assuming hashmap still alive when accessing next.

---

option 2 (store nodes in map instance):

template<typename k, typename t, typename f = hashkey<k>> class hashmap { public:     std::array<hashnode<k, t>, 128 > m_table;     // ... }; 

hashmap instances may enormous, depending on size of hashnode<k, t>.

if choose store nodes directly hashmap no heap indirection, have use index access internal array, moving/copying hashmap around change memory address of nodes.

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