Глубокая копия std :: stack <boost :: shared_ptr <T>>

Question

Я хотел бы реализовать копию std::stack< boost::shared_ptr<T> >. Есть ли способ сделать это без 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

Если вы хотите сохранить порядок, вы немного застряли, так как в стеке нет итераторов. Если вы не хотите использовать deque, вы можете, по крайней мере, сделать код более понятным (и более эффективным при определенных обстоятельствах ), передавая исходный стек значением:

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