C++指针树模板问题

Question

我刚刚发现了一个由 Kasper Peeters 编写的类似 STL 的树容器类:

http://tree.phi-sci.com/

但是，因为它类似于 STL，所以它适合在树中拥有单一类类型；即 template <class T> .问题是，就像 STL 列表一样，如果它遇到多态类问题，树中指向基于堆的对象的指针(如指向基类的指针)的对象在删除节点时不会被销毁。

所以，我的选择:

1:使用 boost::shared_ptr 树，虽然这比我想要的更昂贵/矫枉过正。

2: 像我在下面写的那样写一个小的指针包装器。这个想法是它包装了一个指针，当它超出范围时，删除它的指针。它不是引用计数，它只是保证指针销毁。

template<class T>
class TWSafeDeletePtr
{
private:
    T *_ptr;
public:
    TWSafeDeletePtr() : _ptr(NULL) {}
    TWSafeDeletePtr(T *ptr) : _ptr(ptr) {}
    ~TWSafeDeletePtr()
    { 
        delete _ptr;
    }
    T &operator=(T *ptr)
    {
        assert(!_ptr);
        delete _ptr;
        _ptr=ptr;
        return *ptr;
    }
    void set(T *ptr)
    {
        *this=ptr;
    }

    T &operator*() const { return *_ptr; }
    T *operator->() const { return _ptr; }
};

3: 编写我自己的分配器，它在 allocate() 中从池中分配节点对象，并在 deallocate() 中删除指向内存的指针。

4: 专门编写指针树的代码，避免初始分配和复制构造，加上天生就知道如何删除指向的数据。

我已经可以使用选项 2，但我对它不是很满意，因为我实际上必须先插入一个空 ptr，然后在插入返回迭代器时设置 () 指针。这是因为树使用复制构造，因此在堆栈上传递的临时对象将在超出范围时最终删除指针。所以我在返回时设置了指针。它有效，它是隐藏的，但我不喜欢它。

选项 3 看起来是最佳选择，但我想我会问是否有其他人已经这样做过，或者有任何其他建议？

好的，我决定采用选项 1(shared_ptrs 树)，主要是因为它使用标准库，而且还因为每个节点的额外引用计数不会耗尽资金。感谢大家的回复:)

干杯，

谢恩

Answer 1

我不喜欢分配器版本，因为分配器应该分配内存，而不是构造对象。所以不能保证请求分配给分配器的数量与要构造的对象数量相匹配；这将取决于您是否能够摆脱它的实现。

在分配器为其分配内存后，树会在插入或追加的值上调用复制构造函数，因此您很难编写与多态对象一起工作的东西 - alloc_.allocate 不知道运行时类型调用构造函数之前的 x(第 886 行):

tree_node* tmp = alloc_.allocate(1,0);
kp::constructor(&tmp->data, x);

同时查看代码，它似乎根本没有使用赋值，而且你的包装器只提供默认的复制构造函数，所以我看不到你建议的任何机制起作用——当一个节点被分配给相同的此代码已包含的值(第 1000 行):

template <class T, class tree_node_allocator>
template <class iter>
iter tree<T, tree_node_allocator>::replace(iter position, const T& x)
    {
    kp::destructor(&position.node->data);
    kp::constructor(&position.node->data, x);
    return position;
    }

当他们的析构函数在这里被调用时，你的智能指针会破坏他们的指称；你可以通过传递一个引用计数的指针来摆脱它(所以 x 在它超出范围之前不会破坏它的引用，而不是 position.node->data 析构函数破坏它)。

如果您想使用这棵树，那么我要么将其用作其他地方拥有的数据的索引，而不是将其用作拥有数据的树，要么坚持使用 shared_ptr 方法。