实现数据结构时的智能或原始指针？

智能指针的选择取决于数据结构如何"拥有"堆分配的对象.

如果你需要简单地观察,而不是拥有一个对象(无论它是否是堆分配的),原始指针,引用或者std::reference_wrapper是一个合适的选择.

如果您需要唯一所有权(最多一个堆分配对象的所有者),则使用std::unique_ptr.它没有额外的时间/内存开销.

如果您需要共享所有权(堆分配对象的任意数量的所有者),则使用std::shared_ptr.这会导致额外的时间/内存开销,因为必须存储附加指针(指向引用计数元数据),并且因为访问它所保证是线程安全的.

除非您确实需要拥有该对象,否则无需使用std::unique_ptr (代替原始指针).

假设您需要拥有该对象,除非您确实需要共享所有权语义,否则无需使用std::shared_ptr (代替std::unique_ptr).

在您的情况下,看起来您的堆节点最多HashMap.因此,我假设你想要的HashMap实例是节点的唯一所有者.

你应该用什么类型的？

template>
class HashMap {
public:
    std::array m_table;
    // ...
};

您有两种选择:

如果要使用堆间接存储对象,请使用std::unique_ptr,因为这些堆分配对象的唯一所有者始终是HashMap实例.

如果要将对象直接存储到HashMap没有堆间接的情况下,则根本不要使用任何指针.这可能会导致非常大的HashMap情况.用于访问next节点的接口变得麻烦.

选项1(在堆中存储节点):

这是最常见,也可能是最佳选择.

template>
class HashMap {
public:
    std::array>, 128 > m_table;
    // ...
};

这将导致更轻(在内存占用方面) HashMap实例.

注意:使用a std::vector代替std::array将HashMap显着减小大小,但会引入额外的堆间接.这是实现类似数据结构的常用方法.您通常希望HashMap实例尽可能轻量级,以便可以有效地复制/移动/存储它.

没有必要使用智能指针来连接彼此之间的节点,因为节点完全由它们拥有HashMap.甲原始指针将是足够的.

template
class HashNode {
public:
    // ...
    HashNode* next_ptr = nullptr;
    auto& next() 
    { 
        assert(next_ptr != nullptr);
        return *next_ptr;
    }
};

假设HashMap访问时仍然存在,上面的代码将正常工作next.

选项2(在地图实例中存储节点):

template>
class HashMap {
public:
    std::array, 128 > m_table;
    // ...
};

HashMap实例可能是巨大的,取决于的大小HashNode.

如果选择将节点直接存储到HashMap没有堆间接的情况下,则必须使用索引来访问内部数组,因为移动/复制HashMap周围将更改节点的内存地址.

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