Re: How to push a stack on a stack without passing by value?
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! ]