C++指针模板树问题

Question

C++指针模板树问题

3

我刚刚发现了一种由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: 编写自己的分配器，从池中分配节点对象并在deallocate()中删除指向的内存。

4: 专门设计代码以创建指针树，避免初始分配和复制构造，并且本质上知道如何删除指向的数据。

我已经让选项2起作用了，但我并不是很满意，因为我必须先插入一个空指针，然后在插入返回迭代器时设置指针。这是因为树使用复制构造函数，因此在堆栈上传递的临时对象最终会在其超出范围时删除指针。所以我在返回时设置了指针。它有效，而且隐藏得很好，但我不喜欢它。

选项3看起来是最佳选择，不过我想问一下是否有其他人已经做过这个，或者有其他建议？

好的，我决定选择选项1（共享指针树），主要是因为它使用标准库，而且每个节点的额外引用计数不会太高。谢谢大家的回复:)

致敬，

Shane

- Shane

也许明确销毁对象在从树中移除时是最佳选择？（我只是猜测）。有时候最好不要解决问题，而是应对一些劣势。 - adf88

查看 Boost 指针容器。 - sellibitze

7个回答

1

[编辑] Shane选择了使用boost::shared_ptr的解决方案，并指出他需要存储多态基类指针。如果在分析之后内存/处理效率成为关注点（当然），请考虑具有安全复制行为的基指针包装器（例如，通过克隆方法对指向对象进行深复制）和#5中所示的快速交换习语。这将类似于建议的解决方案＃2，但是安全且不会对所使用的数据类型做出假设（例如：尝试在容器中使用auto_ptr）。

我认为你应该考虑选项＃5。

1：使用boost::shared_ptr的树，尽管这比我想要的更昂贵/过度。

首先，您是否意识到像std::list，std::set，std::map这样的链接结构需要每个节点单独的内存分配/释放，但不需要复制节点以执行诸如重新平衡树等操作？仅在插入到树中时，引用计数器才会产生任何处理开销。

2：编写一个类似下面我写的指针包装器。它的作用是将指针封装起来，当它超出范围时，删除其指针。它不是引用计数的，只是保证了指针的销毁。

对于这个树，你可能可以使用它，因为你有树的实现，但这是一个很大的假设。考虑至少使指针包装器不可复制，这样如果您尝试将其用于复制节点元素的内容，就会得到编译器错误。

3：编写自己的分配器，从池中分配节点对象，并在释放内存时删除指向的内存。

如果它是符合STL的内存分配器，那么它不应该对deallocate中的内存内容做出这样的假设。然而，编写一个快速的内存分配器，它可以假定固定的分配大小，可以真正加速任何链接结构。然而，编写一个始终优于malloc/free的快速内存分配器是非常棘手的工作，需要考虑像内存对齐这样的问题。

4：专门编写代码以创建指针树，避免初始分配和复制构造，同时天生知道如何删除所指向的数据。

为树创建包装器可能是最可靠的解决方案。您将完全控制何时插入和删除元素（节点），并可以在此期间执行任何操作。

选项＃5：直接将元素存储在树中，并专注于使元素快速。

如果问我，这是您最好的选择。不要使用map<int, ExpensiveElement*>或map<int, shared_ptr<ExpensiveElement> >，而是考虑简单地使用map<int, ExpensiveElement>。

毕竟，您显然希望树成为内存管理器（删除节点会删除元素）。当我们避免指向元素的指针的间接性时，就会发生这种情况。

但是，您似乎担心插入的复制策略的开销（ExpensiveElement上的复制构造函数开销）。没问题！只需使用operator[]而不是insert：

map<int, ExpensiveElement> my_map;

// default constructs ExpensiveElement 
// and calls ExpensiveElement::do_something().
// No copies of ExpensiveElement are made!
my_map[7].do_something();

哒！无需复制，无需担心正确销毁，每个元素也不需要内存分配/释放开销。

如果默认构造ExpensiveElement不足够，请考虑使默认构造非常便宜（几乎免费）并实现交换方法。

map<int, ExpensiveElement> my_map;

// construct an ExpensiveElement and swap it into the map
// this avoids redundant work and copying and can be very 
// efficient if the default constructor of ExpensiveElement
// is cheap to call
ExpensiveElement element(...);
my_map[7].swap(element);

为了使默认构建变得非常便宜并允许进行交换方法，您可以在ExpensiveElement上实现一个快速的pimpl。您可以使默认ctor甚至不分配pimpl，使其成为空指针，而交换方法则交换ExpensiveElement的两个pimpls。现在，您具有超级便宜的默认构建和一种将正确构建的ExpensiveElements交换到映射中的方法，完全避免深度复制的冗余。 如果ExpensiveElement不能有默认ctor怎么办？ 那么请创建一个包装器来实现。这种方法与您提出的指针包装器类似，但它将是一个具有有效（安全）复制行为的完整类。例如，如果不希望使用引用计数，则复制ctor可以深度复制指示物。差异听起来可能微妙，但以这种方式，它是一种非常安全和完整的解决方案，不会对树是如何实现做出假设；像boost :: shared_ptr一样安全且通用，但没有引用计数。只需提供一个swap方法作为您唯一的手段，在不需要深度复制的情况下轻松交换数据，并使用它将事物交换到树中。 如果我们需要存储多态基础指针怎么办？ 请参见上面的答案并修改包装器以调用类似clone（原型模式）的内容来深层复制指示物。

- stinky472

如果ExpensiveElement不能有默认构造函数，那么选项5就无法工作。否则，这看起来很不错。 - Mike DeSimone

@Ben 确实如此，但考虑到选项#3的建议，我怀疑作者在这里并不需要多态性。 - stinky472

@Ben 和 @Mike：我修改了这篇文章，以解决关于多态性和缺乏默认构造的问题。 - stinky472

顺便说一下，我也不提倡懒构造。考虑 boost::shared_ptr，它在默认构造函数中存储空指针。它并没有使用懒构造，但支持交换惯用语，并具有安全的复制行为。在其上调用参数化构造函数会导致它存储一个有效指针（非空），并且可以将一个空 shared_ptr 与一个非空 shared_ptr 进行交换。这就是我所提出的，但根据这种情况下 ExpensiveElement 的具体情况，我们甚至可能根本不需要类似智能指针的包装器。 - stinky472

这里的重点是，我需要一个指针树，因为单个模板T不是多态的。我有一个指向基类的指针树。无论如何，我已经采取了第一种选项。无论如何感谢您的回复 :) - Shane

显示剩余3条评论

0

首先，如果您可以访问C++0x，您可以从移动语义中受益。

否则，Boost指针容器库通过重新编码解决了STL指针容器的问题。

您没有提到的另一个指针容器的问题是容器的副本。在您的情况下，原始容器及其副本都指向相同的对象，因此更改一个不会更改另一个。

当然，您可以通过编写包装指针并提供深度复制语义（在对象中包装的clone方法）的代理类来缓解这个问题。但是，如果容器具有指针感知，则需要更频繁地复制数据...虽然这样做的工作量较小。

/// Requirement: T is a model of Cloneable
template <class T>
class Proxy
{
  template <class> friend class Proxy;
public:
  // Constructor
  Proxy(): mPointer(0) {}
  explicit Proxy(T* t): mPointer(t) {}
  template <class U>
  explicit Proxy(std::auto_ptr<U> t): mPointer(t.release()) {}
  template <class U>
  explicit Proxy(std::unique_ptr<U> t): mPointer(t.release()) {}

  // Copy Constructor
  Proxy(Proxy const& rhs):
    mPointer(rhs.mPointer ? rhs.mPointer->clone() : 0) {}
  template <class U>
  Proxy(Proxy<U> const& rhs):
    mPointer(rhs.mPointer ? rhs.mPointer->clone() : 0) {}

  // Assignment Operator
  Proxy& operator=(Proxy const& rhs)
  {
    Proxy tmp(rhs);
    this->swap(tmp);
    return *this;
  }
  template <class U>
  Proxy& operator=(Proxy<U> const& rhs)
  {
    Proxy tmp(rhs);
    this->swap(tmp);
    return *this;
  }

  // Move Constructor
  Proxy(Proxy&& rhs): mPointer(rhs.release()) {}
  template <class U>
  Proxy(Proxy<U>&& rhs): mPointer(rhs.release()) {}

  // Move assignment
  Proxy& operator=(Proxy&& rhs)
  {
    Proxy tmp(rhs);
    this->swap(tmp);
    return *this;
  }
  template <class U>
  Proxy& operator=(Proxy&& rhs)
  {
    Proxy tmp(rhs);
    this->swap(tmp);
    return *this;
  }

  // Destructor
  ~Proxy() { delete mPointer; }

  void swap(Proxy& rhs)
  {
    T* tmp = rhs.mPointer;
    rhs.mPointer = mPointer;
    mPointer = tmp;
  }

  T& operator*() { return *mPointer; }
  T const& operator*() const { return *mPointer; }

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

  T* release() { T* tmp = mPointer; mPointer = 0; return tmp; }

private:
  T* mPointer;
};

// Free functions
template <class T>
void swap(Proxy<T>& lhs, Proxy<T>& rhs) { lhs.swap(rhs); }

请注意，除了提供深拷贝语义外，它还提供了深层次的const语义。这可能或可能不符合您的口味。

另外，提供等效于 static_cast 和 dynamic_cast 操作会更好，但这留给读者作为练习 ;)

- Matthieu M.

0

看起来最干净的解决方案是使用Boost Pointer Container风格的容器适配器。这将大大简化语法。然而，编写这样的适配器是繁琐和重复的，因为您必须“提升”typedef并重复要适配的类的每个成员函数。

- pmr

0

看起来选项1可能是最好的选择。shared_ptr非常常见，大多数人应该知道它的工作原理。使用map_obj[key].reset(new ValueType);语法有问题吗？

除非您有测量数据表明选项2的包装在使用方面比shared_ptr节省了很多，否则shared_ptr似乎更安全，因为人们会立即了解其语义。

选项3似乎对提供的内容过于复杂。您需要实现allocate/construct和deallocate/destruct对，并确保如果节点被复制，它不会出现删除问题。

选项4可能是第二好的选择。除非分析表明shared_ptr操作真的非常昂贵，否则我不建议使用它，因为这需要重新发明已经在标准库中编写和调试的代码。

- Mark B

0

我决定选择选项1（共享指针树），主要是因为它使用标准库，而且每个节点的额外引用计数也不会太高。感谢大家的回复 :)

- Shane

-1

1.

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

除非至少有一个相同的shared_ptr副本，否则指向的对象不会被销毁，因此您写的内容没有问题。

2.你的类是无意义的。使用shared_ptr。

3.分配器必须知道在请求一段字节时要创建什么类型的对象，这不是一个好的解决方案。

4.太多的复杂性。

我建议使用方案1。

- adf88

就像我在帖子中所说的那样，我不想要每个节点都有一个引用计数的开销，这是不必要的。我的类在没有引用计数的情况下也能达到相同的结果。实际上，它只是在超出范围时删除其指针的类。 - Shane

你假设一旦创建节点，树类内部不会复制它。基于这个假设，你的TWSafeDeletePtr类是正确的，但在这种情况下最好使用std::auto_ptr，它几乎可以完成相同的工作 - 此外，它还可以消除你所遇到的初始化问题。如果没有这个假设，引用计数是必须的。 - adf88

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Pete Kirkham · Accepted Answer

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

树在插入或追加值后调用复制构造函数，此时分配器已经为其分配了内存，因此很难编写适用于多态对象的代码 - 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方法。