std::stack< 的深拷贝boost::shared_ptr; >

Question

我想实现 std::stack 的副本boost::shared_ptr; >。有没有办法不用3份就可以呢？这是代码：

template<typename T>
void copyStackContent(std::stack< boost::shared_ptr<T> > & dst,
                      std::stack< boost::shared_ptr<T> > const & src){

    //// Copy stack to temporary stack so we can unroll it
    std::stack< boost::shared_ptr<T> > tempStack(src);

    /// Copy stack to array
    std::vector< boost::shared_ptr<T> > tempArray;
    while(!tempStack.empty()){
        tempArray.push_back(tempStack.top());
        tempStack.pop();
    }

    /// Clear destination stack
    while(!dst.empty()){
        dst.pop();
    }

    /// Create destination stack
    for(std::vector< boost::shared_ptr<T> >::reverse_iterator it =
        tempArray.rbegin(); it != tempArray.rend(); ++it){
        dst.push( boost::shared_ptr<T>(new T(**it)) );
    }
}

和一个示例测试：

void test(){
    // filling stack source
    std::stack< boost::shared_ptr<int> > intStack1;
    intStack1.push( boost::shared_ptr<int>(new int(0)) );
    intStack1.push( boost::shared_ptr<int>(new int(1)) );
    intStack1.push( boost::shared_ptr<int>(new int(2)) );
    intStack1.push( boost::shared_ptr<int>(new int(3)) );
    intStack1.push( boost::shared_ptr<int>(new int(4)) );

    // filling stack dest
    std::stack< boost::shared_ptr<int> > intStack2;
    copyStackContent(intStack2, intStack1);

    assert(intStack1.size() == intStack2.size());         // same size
    while(!intStack1.empty()){
        assert(intStack1.top() != intStack2.top());       // != pointers
        assert((*intStack1.top()) == (*intStack2.top())); // same content
        intStack1.pop();
        intStack2.pop();
    }
}

Answer 1

如果你想维持顺序，你就会陷入困境，因为堆栈不提供任何迭代器。如果你不想使用双端队列，至少可以让代码更清晰（并且更高效在某些情况下）通过按值传递源堆栈：

template<typename T>
void copyStackContent(std::stack< boost::shared_ptr<T> > & dst,
                      std::stack< boost::shared_ptr<T> > src){

    // Copy stack to array
    std::vector< boost::shared_ptr<T> > tempArray;
    while(!tempStack.empty()){
        tempArray.push_back(tempStack.top());
        tempStack.pop();
    }

    // Clear destination stack
    while(!dst.empty()){
        dst.pop();
    }

    // Create destination stack
    for(std::vector< boost::shared_ptr<T> >::reverse_iterator it =
        tempArray.rbegin(); it != tempArray.rend(); ++it){
        dst.push( boost::shared_ptr<T>(new T(**it)) );
    }
}

不过，我对复制shared_ptrs指向的值持怀疑态度。如果您无论如何都要复制所有内容，为什么还要动态分配呢？

Answer 2

在这种情况下，您最好的选择可能是只使用 deque 而不是 stack 并将 top 更改为 back等根据需要。然后您可以迭代并一次完成深复制。

或者找出为什么需要深层复制并尝试从源头上消除这种需求。

Answer 3

不，您所拥有的与您将获得的一样高效。但是，如果您发现自己这样做，您可能应该简单地使用 std::vector 或 std::deque 而不是堆栈。 std::stack 只是这些容器之一的包装器（通常是 std::deque）如果您使用这些容器中的任何一个，您可以通过使用来有效地反转顺序反向迭代器，如果您使用 std::deque，您甚至可以使用 push_front 在另一侧高效插入。

旁注：您可能还应该让 copyStackContent 返回一个新堆栈，而不是通过引用获取目标堆栈。它更具可读性，并且分配一个新堆栈并简单地释放旧堆栈比删除现有堆栈中的所有元素更便宜。

Answer 4

我的第一个答案很愚蠢，没有阅读整个问题，这是堆栈克隆操作的干净实现，汇集了上面讨论的想法，但仅使用堆栈......

template <typename T, typename _CT = boost::shared_ptr<T>, typename _ST = std::stack<_CT> >
struct cloner
{
  inline _CT copy(_CT t)
  {
    return _CT(new T(*t));
  }

  _ST operator()(_ST src)
  {
    _ST temp;

    while(!src.empty())
    {
      temp.push(copy(src.top()));
      src.pop();
    }

    while(!temp.empty())
    {
      src.push(temp.top());
      temp.pop();
    }
    return src;
  }
};