c++ - 实现数据结构时使用智能指针还是原始指针？

Question

我一直在阅读和试验标准库的智能指针，unique_ptr 和 shared_ptr，尽管在​​很多情况下它们显然是很好的替代品，其中原始指针可能是被认为是危险的我不确定在实现数据结构时它们的用途。

为了进行实验，我编写了一个使用 shared_ptr 的 HashMap 示例 - 根据 Meyer 的 Effective Modern C++，它的大小大约是 unique_ptr 的两倍。出于这个原因，我想使用 unique_ptr，但由于我在 Add 函数中执行的操作、更新和复制，我有点难过。

有人对这个问题有什么建议吗？数据结构是否仍应使用原始指针编写？

#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实例成为节点的唯一所有者。

你应该使用什么类型？

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

你有两个选择:

1. 如果要使用堆间接存储对象，请使用 std::unique_ptr ，因为这些堆分配对象的唯一所有者是并且将永远是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::vector代替 std::array将减小 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(在 map 实例中存储节点):

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 around 会改变节点的内存地址。

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