代码之家 › 专栏 › 技术社区 › tibur

std::stack的深度拷贝

containers stack stl boost c++

tibur · 技术社区 · 14 年前

我想实现 std::stack< boost::shared_ptr<T> >

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

4 回复 | 直到 14 年前

Steve M 14 年前

如果你想保持顺序,你就有点卡住了,因为stack没有提供任何迭代器。如果不想使用deque,至少可以使代码更清晰(并且更高效 under certain circumstances

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

尽管如此,我还是怀疑是否抄袭了共享资源所指的价值观。如果要复制所有内容,为什么还要动态分配呢?

Mark B 14 年前

在这种情况下,您最好的选择可能是使用 deque 而不是 stack 和改变 top 到 back

或者找出为什么需要深层副本,并尝试从源位置删除该需求。

Billy ONeal IS4 14 年前

不,你所拥有的就是你所能得到的效率。但是,如果您发现自己这样做了,您可能只需要使用 std::vector 或 std::deque std::stack 只是其中一个容器的包装(通常 标准::德克 )如果使用这两个容器中的任何一个,则可以通过使用反向迭代器有效地反转序列,并且如果使用 ,甚至可以使用 push_front .

旁注:你也应该 copyStackContent

-1

Nim 14 年前

我的第一个答案是愚蠢的,没有阅读完整的问题,这里是一个干净的克隆操作的栈实现,将上面讨论的想法结合在一起,但只使用栈。。。

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