Re: How to push a stack on a stack without passing by value?

On May 18, 4:09 am, "Siegfried Heintze" <siegfr...@heintze.com> wrote:


It took the C++ community YEARS to figure out how to make a properly
working stack template. This was an interesting debate to follow,
which I wont cover here, but the end game is that Herb Sutter more or
less made his reputation by being the first guy to explain clearly how
to do it, and the "Exceptional C++" books were started from that.
So instead of designing your own stack class that uses C arrays, your
best bet is to make a C array wrapper that works with the stack
adapter. Here is one:
template<class T, std::size_t N>
struct ArrayStack{
    typedef T value_type;
    typedef typename std::size_t size_type;
    typedef T& reference;
    typedef T const& const_reference;
    ArrayStack():m_len(0){}
    void push_back(T const&_a){
        if(m_len!=(N)){
            m_data[m_len]=_a;//may throw
            m_len++;
        }else
           throw std::overflow_error("Too much stuff!!!");
    }
    void pop_back(){
        if(!empty()){
            m_data[m_len-1]=T();//may throw
            --m_len;
        }
    }
    bool empty()const{
        return m_len==0;
    }
           size_type size()const{
        return m_len;
    }
          reference back()
          {
                  return m_data[m_len-1];
          }
          const_reference back() const
          {
                return m_data[m_len-1];
          }
//default copy Constructor,Destructor are fine
private:
     size_type m_len;
     T m_data[N];
};

And here is a short tester to demonstrate:
typedef std::stack<int,ArrayStack<int,8> > mystack;
mystack ms;
assert(ms.empty());
ms.push(1);
ms.push(2);
assert(ms.size()==2);
assert(ms.top()==2);
ms.push(3);
ms.push(4);
ms.push(5);
ms.push(6);
ms.push(7);
ms.push(8);
assert(ms.size()==8);
assert(ms.top()==8);
assert(!ms.empty());
try{
ms.push(9);
assert(false);
}catch(...){}
ms.pop();
ms.pop();
ms.pop();
ms.pop();
ms.pop();
ms.pop();
ms.pop();
assert(ms.top()==1);
assert(ms.size()==1);
ms.pop();
assert(ms.empty());

This is easy enough for T of int. But this concoction will work
correctly for *any* T that is Default and CopyConstructible. For
example it will work for this guy too:
struct Touchy{
    Touchy(){
       if(rand()%2==0)throw 1;
    }
    Touchy(Touchy const&){
       if(rand()%2==0)throw 1;
    }
  //destructor cannot throw, cant be THAT Touchy
};


I would recommend a free function:
template<class T,class U, class W>
void move(std::stack<T,U>&_r,std::stack<T,W>&_l)
{
    while(!_l.empty()){
       _r.push(_l.top());
       _l.pop();
    }
}

And here is a demo:
typedef std::stack<int,ArrayStack<int,8> > mystack;
mystack ms;
for(int i=0;i<8;++i){
   ms.push(i+1000);
}
assert(ms.size()==8);
std::stack<int> other;
move(other,ms);
assert(ms.size()==0);
assert(other.size()==8);

Note that the Stack implementations do not have to be the same, just
the T has to be the same.
So if you want to do a nondestructive "push", do this:

mystack ms2(ms);//make a copy
move(other,ms2);//then move

How can this be optimized? I can tell you that this works correctly
with no surprises, and the first rule of optimization is "It is far
easier to make a correct program fast, than it is to make a fast
program correct." So now that we have correctly behaving stacks that
use C arrays, we can work on this part.

So how can we trim the fat? After running this though our profiler, we
may discover a few places: I can speculate (and that is all it is)
that for fundamental types, I can make a few enhancements--these do no
throw, and I can perhaps make a specialization that takes this into
account:
typedef <std::size_t N>struct ArrayStack<int>{/*something special*/};
but your compiler is likely to have already figured this one out.
Note that the designers of std::stack already chose the best overall
container, namely std::deque, as the default. I would use that until
proven I needed something else otherwise.

Hope this helps,
Lance

--
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated. First time posters: Do this! ]