在实现数据结构时，智能指针还是原始指针更好？

Question

我一直在阅读和尝试使用标准库的智能指针`unique_ptr`和`shared_ptr`，虽然它们显然是替代原始指针的好选择，但当实现数据结构时，我不确定它们的使用方法。

为了进行实验，我编写了一个使用`shared_ptr`的哈希表示例，根据Meyer's Effective Modern C ++，其大约是`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;
}

- dgouder

---

一般而言，您应该从所有权的角度考虑新的智能指针，而不是简单地自动删除指针。一个“资源”是否可以有多个同时所有者（std::shared_ptr），还是一次只能有一个所有者（std::unique_ptr）取决于具体情况。 - Some programmer dude

我不确定你为什么觉得这里需要指针，或者 std::array。 为什么不用 std::vector<HashNode<K, T>> 来实现哈希映射呢？通常，这个问题让我有些困惑：你应该做的大部分工作是编写数据结构（以及它们的算法）。因此，你当然会为数据结构使用智能指针，而不是笨重的指针 - 否则你还会用智能指针来做什么？没有其他用途了。 - Konrad Rudolph

在编写树形数据结构中的旋转等代码时，我倾向于微调优化，通常包括在指针放弃概念所有权后几个指令使用它们。只要我使用原始指针并且理解代码的所有权语义，我就可以在安全和高效的地方弯曲所有权规则。对于智能指针，优化器永远无法将生成的代码恢复到我使用原始指针编写的那么高效。一个技能较低的程序员会发现更少的受益机会，并冒更多的错误风险。 - JSF

@JSF 我觉得这是一个谬论。当然，有些情况下你可以进行优化（例如，std::unique_ptr目前无法传递到寄存器内的函数中，而原始指针可以）。但总的来说，很难做出这样的断言，因为编译器中的优化器变得越来越好，并且在手动实现中所做的许多假设会因平台而异。特别是，我甚至不确定你所说的“放弃概念所有权后使用...”是什么意思。那听起来像是未定义行为。 - Konrad Rudolph

独特的“概念”所有权意味着一次只有一个指针“拥有”对象，并且程序员知道哪个指针，而编译器不知道。交出概念所有权后，您仍然拥有指向有效对象的指针，直到/除非新所有者删除它。因此，在所有权移交和新所有者可能已经删除对象的某个较晚时间之间，裸指针可以访问该对象，而std::unique_ptr则不能（假设在代码的那部分不需要异常安全）。 - JSF

@JSF 你能给出一个具体的例子吗？这似乎是一个非常特殊的情况。一般来说，我会使用普通的unique_ptr来管理所有权（转移），并使用原始指针来维护对同一对象的传递性、非拥有引用。 - Konrad Rudolph

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

假设在访问next时，HashMap仍然存在，上述代码将正常工作。

---

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

- Vittorio Romeo

---

选项1正是我想到的替代方案，只是我不确定这是否是正确的方法，非常感谢！您可以详细说明一下“堆间接”这个术语吗？ - dgouder

@dgouder：这不是“官方”术语 - 我用它来描述当您通过指针访问在堆上分配的对象时发生的间接引用。 SomeClass x; x.some_method(); <- 这里没有间接引用。 std::unique_ptr<SomeClass>(x); x->some_method(); <- 间接引用：您必须获取由 x 指向的堆上的对象。这可能不利于缓存，因为您必须在内存中跳转。 - Vittorio Romeo