As I recall, the standard library will let me implement stacks with 
vectors,
deques or lists but not C arrays. Is this true?

Assumming it is:  I'm implementing my own stack class.

How can I optimize this member function that pushes a stack on a stack?

class STACK {
   int data[8], len;
public:
   STACK(): len(0){}
   void push(int x) { data[ii++] = x; }
   int getLength() { return len; }

   void push(STACK x) // Uggh! I'm passing by value! How can I avoid this?
   {
      for(int ii = x.getLength(); ii > 0; --ii)
         push(x.pop());
   }
}



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

On May 18, 11:09 am, "Siegfried Heintze" <siegfr...@heintze.com>
wrote:
> As I recall, the standard library will let me implement stacks with
> vectors,
> deques or lists but not C arrays. Is this true?
>
> Assumming it is:  I'm implementing my own stack class.
>
> How can I optimize this member function that pushes a stack on a stack?

Hardly I can say that implementation below 'pushes a stack on a
stack', but lets go on :-)

> class STACK {
>    int data[8], len;
> public:
>    STACK(): len(0){}
>    void push(int x) { data[ii++] = x; }
>    int getLength() { return len; }
>
>    void push(STACK x) // Uggh! I'm passing by value! How can I avoid this?
>    {
>       for(int ii = x.getLength(); ii > 0; --ii)
>          push(x.pop());
>    }
>
> }

Pass `x' by non-const reference: void push(STACK& x);  The function
will empty the passed object tough.

Anyway is there any harm of passing such an object by value?  Is there
a performance issue?

--
Alex Shulgin


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

On May 18, 1:55 pm, Alex Shulgin <alex.shul...@gmail.com> wrote:

> Anyway is there any harm of passing such an object by value?  Is there
> a performance issue?

Why pass by value when you can pass by reference?
Passing by reference is only less efficient than by value if the
object is very small and the function isn't inlined. However, that can
be solved by link-time optimization.

Here, it is quite obvious that the type is quite big since it's a
container that stores its content on the stack.


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

On May 18, 2:09 am, "Siegfried Heintze" <siegfr...@heintze.com> wrote:
> As I recall, the standard library will let me implement stacks with
> vectors,
> deques or lists but not C arrays. Is this true?

The underlying container must support push_back, pop_back and back.

>
> class STACK {
>    int data[8], len;
> public:
>    STACK(): len(0){}
>    void push(int x) { data[ii++] = x; }
>    int getLength() { return len; }
>
>    void push(STACK x) // Uggh! I'm passing by value! How can I avoid this?
>    {
>       for(int ii = x.getLength(); ii > 0; --ii)
>          push(x.pop());
>    }
>
> }
>

If you wish for the contents of incoming stack to remain unchanged,
this is the way to do it. Passing it by reference will change the
incoming stack.

I would redo your for-loop, however. This is equivalent (but easier to
read):

while (x.getLength())
{
     push(x.pop()); // pop must decrement x's len
     ++len; // or ii, whichever you stick with
}

Mind telling us why vector is not an option? Reallocation on 8
elements is minimal. With larger stacks you will probably save
yourself from wasted memory. In addition, you have less to worry about
if someone 'push'es more than 8 times - right now your code would
result in undefined behavior. I would rewrite your class above by
wrapping it around the standard stack class. I wouldn't worry so much
about efficiency in this case - you're not buying much reinventing the
wheel.

Best of luck!


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

I don't like new and delete because
(1) it requires several thousand times longer to allocate memory from the
stack than it does from the heap with my compilers (I've done the bench
marks myself)
(2) you have to store the pointer and the data, not just the data so it
takes more room (which becomes an issue if you are storing many, many tiny
stacks and I don't know if it is an issue for this application I am
presently working on)
(3) you are prone to memory leaks (I'm trying to refactor the code to 
remove
memory leaks)
(4) you are prone to heap fragmentation on apps that run 24x7x356 (like
mine)
(5) marching orders from the client say to reduce heap usage
(6) examining the contents of a std::list, std::deque or even a std::vector
in the Microsoft debugger is tedious. Examining fixed length arrays is much
nicer since the debugger knows the length of the array.

I hard coded 8 just as an example.

The existing code works and it uses CString to implement a stack of strings
where each stack element is separated from the next with a "|" and a pop is
implemented by searching backwards from the end of the string for the first
"|" and extracting the resulting substring. I'm replacing these pseudo
stacks with stacks of enums.

Why don't I pass by reference and destroy the argument?
Because the existing implementation does not do this -- it leaves the
original intact. I don't want to perturb the logic.

This is really a silly constraint C++ is putting on me: I must make a copy
(pass by value) so I can make a copy (push the elements of one stack on to
another).

The only work around that I can see is a lot of casting and using memcpy 
--
ughhh!

Thanks!

Siegfried



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

On May 18, 4:09 am, "Siegfried Heintze" <siegfr...@heintze.com> wrote:
> As I recall, the standard library will let me implement stacks with
> vectors,
> deques or lists but not C arrays. Is this true?
>
> Assumming it is:  I'm implementing my own stack class.
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
};

> How can I optimize this member function that pushes a stack on a stack?
>
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! ]

On 19 Mai, 15:41, "Siegfried Heintze" <siegfr...@heintze.com> wrote:
> I don't like new and delete because
> (3) you are prone to memory leaks (I'm trying to refactor the code to
> remove
> memory leaks)

IMO, this argument is not a "real one". Proper use
of some RAII class, responsible for the resource
management, does prevent all these problems. Smart
pointers (and similar class) are your friend!

> (6) examining the contents of a std::list, std::deque or even a std::vector
> in the Microsoft debugger is tedious. Examining fixed length arrays is much
> nicer since the debugger knows the length of the array.

Similarily this one. Basing on these arguments,
any from of software development would not have
taken place prior to 10 years ago.
Additionally, any modern compiler has reasonable
debugging capabilities to support even these cases.
(In another posting you mentioned VC6 - This indeed
is *not* a compiler that can be compared with
state-of-the art compilers concerning standard
conformity or extraordinary debugging support).

> This is really a silly constraint C++ is putting on me: I must make a copy
> (pass by value) so I can make a copy (push the elements of one stack on to
> another).
>
> The only work around that I can see is a lot of casting and using memcpy

I cannot follow your argumentation here. You are
arguing that you pass by-value, because

"existing implementation does not do this --
it leaves the original intact"

This is all fine, but you are not enforced by
the language to use arguments by-value, a
*const* reference argument would suffice in
combination with reasonable (non-modifying)
member functions.
Your limits exists, because you use the wrong
member function (pop) here, instead of a missing,
but very reasonable one - namely the top()
function, which simply returns the top element
(without "popping" it) and a proper iterator,
which allows element traversal without
modification.[1] With an (internally known) iterator
- the member 'data'+'len' already is one - and
std::reverse_copy from <algorithm> you could
simply solve the mentioned problem.

Greetings from Bremen,

Daniel Kr�gler

[1]: To prevent a misunderstanding: The proposed
top() function is practical as is, but not necessary
to solve the above problem, which only needs the
discussed data vector and std::reverse_copy as
explained in the text.



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

On May 19, 7:41 am, "Siegfried Heintze" <siegfr...@heintze.com> wrote:
> I don't like new and delete because
> (1) it requires several thousand times longer to allocate memory from the
> stack than it does from the heap with my compilers (I've done the bench
> marks myself)

I think Lance Diduck had an excellent suggestion. Using his ArrayStack
class you can get the best of both worlds. In addition, you could make
the size of the array part of your template.

> (2) you have to store the pointer and the data, not just the data so it
> takes more room (which becomes an issue if you are storing many, many tiny
> stacks and I don't know if it is an issue for this application I am
> presently working on)

That's a valid argument. We don't know enough about your platform.

> (3) you are prone to memory leaks (I'm trying to refactor the code to
> remove
> memory leaks)

Leaks? The pointers belonging to the vector/deque/list would be on the
stack. They would automatically clean themselves up when an exception
was thrown. If your stack has pointers, use a shared_ptr. But, if
arrays are the way to go, go for it.

> (5) marching orders from the client say to reduce heap usage

Ah, here we go!

> Why don't I pass by reference and destroy the argument?
> Because the existing implementation does not do this -- it leaves the
> original intact. I don't want to perturb the logic.

Perfectly legit!

> This is really a silly constraint C++ is putting on me: I must make a copy
> (pass by value) so I can make a copy (push the elements of one stack on to
> another).

Yes, silly. However there are plenty options. The best option would be
to simply create a member function that took the stack. It would of
course have access to the other stacks members. Now, instead of
calling a function, call a method:

inline void push(STACK const& x) // Uggh! I'm passing by value! How
can I avoid this? -- NOT ANYMORE!!!
 {
     // assert x.len + this.len < sizeof(data)
     for (int i = 0, past = x.len; i != past; ++i)
     {
          data[len++] = x.data[i];
     }

     //copy(&x.data[0], &x.data[0] + x.len, data + len);
 }

Here, you avoid an extra copy. You don't get to use your push/pop
methods, but oh well. Since you are passing the stack by const& you
are not changing the incoming stack. Make it inline if you wish. Mix
this with Lance's code and your well on your way.

Best of luck!


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

On May 18, 7:21 pm, Mathias Gaunard <loufo...@gmail.com> wrote:
> On May 18, 1:55 pm, Alex Shulgin <alex.shul...@gmail.com> wrote:
>
> > Anyway is there any harm of passing such an object by value?  Is there
> > a performance issue?
>
> Why pass by value when you can pass by reference?
> Passing by reference is only less efficient than by value if the
> object is very small and the function isn't inlined. However, that can
> be solved by link-time optimization.

OK.  I just was not clear enough--I was asking about the precise case
of OP's function, which is inlined.  The proposed variant with passing
by reference modifies the passed object, so the functions are not
completely equivalent.  Thus I was trying to suggest the OP to examine
if there is any _real_ harm of passing that object by value.

--
Alex Shulgin


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

Siegfried Heintze <siegfried@heintze.com> wrote:

> The existing code works and it uses CString to implement a stack of strings
> where each stack element is separated from the next with a "|" and a pop is
> implemented by searching backwards from the end of the string for the first
> "|" and extracting the resulting substring. I'm replacing these pseudo
> stacks with stacks of enums.
> 
> Why don't I pass by reference and destroy the argument?
> Because the existing implementation does not do this -- it leaves the
> original intact. I don't want to perturb the logic.
> 
> This is really a silly constraint C++ is putting on me: I must make a copy
> (pass by value) so I can make a copy (push the elements of one stack on to
> another).
> 
> The only work around that I can see is a lot of casting and using memcpy
>

  You can reduce allocations to reserves, if store the 'strings' as null
terminated char arrays one after the other in a vector of char. If you
are given the old format with '|' separators you can copy them replacing
'|' with '\0' and storing a ptr to the last such 'string' makes top()
trivial, push() might allocate but if capacity() would be exceeded.
pop is lookbackward for '\0' before the terminiating '\0' of the
previous 'string', if the result is just before this then the stack is
empty.

class string_stack
{
     std::vector<char> data_;
     const char *top_;
     const char *data () {return data_.size() ? &data[0]:0;}
     void append(const char *s);
  public:
      string_stack():data_(2,'\0') {top_= &data[2];}
      void push(const char *s);
      const char *top() const {return top_;}
      void pop();
      bool empty() const {return *top_ == '\0';}
};

implementation:
    void string_stack::push(const char *s)
    {
        append(s);
    }

    void string_stack::pop()
    {
       for(--top_;*top_;--top_)
       {
         // no body
       }
       ++top_;
    }

    void string_stack.append(const char *s)
    {
        std::size_t len = std::strlen(s);
        if(data_.size() + len > data_.capacity())
        {
           data_.reserve(data_.size()+len);
        }
        std::replace_copy(s,s+len,'|','\0',std::back_inserter(data_));
        top_ = data()+data_.size() + 1;
        pop();
    }

off the cuff thia should work without any allocations outside of the
ctor's, and append() function.   This will also take the old stacks
as a single push operation as well as plain C strings not containing
'|'.
  was not that easy? :)




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

Carl Barron <cbarron3@ix.netcom.com> wrote:


> class string_stack
> {
>      std::vector<char> data_;
>      const char *top_;
>      const char *data () {return data_.size() ? &data[0]:0;}
>      void append(const char *s);
>   public:
>       string_stack():data_(2,'\0') {top_= &data[2];}
>       void push(const char *s);
>       const char *top() const {return top_;}
>       void pop();
>       bool empty() const {return *top_ == '\0';}
> };
> 
> implementation:
>  [snip]
>     void string_stack::pop()
>     {
>        for(--top_;*top_;--top_)
>        {
>          // no body
>        }
>        ++top_;
//  adjust the vector missing from original code
          std::vector<char>::iterator it(data_.begin());
          std::advance(it,top-data());
          data_.erase(it,data_.end());
>     }
> 

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