A stack container that can pop multiple types

[Frederick Gotham]

I'm writing a class called "MultiStack". It is a stack container in
which the elements can be of different types, for example you can push
an 'int' onto the stack, and then push a 'std::string' onto the stack.

This class shall have an interface as close as possible to "std::stack"
while accommodating new features. The following 7 public member
functions shall be implemented:

empty - Test whether container is empty
size - Return quanity of elements
pop - Remove top element
swap - Swap contents with another Multistack
push - Insert element
emplace - Construct and insert element
top - Access top element

Specifically the following four member functions will have the same
signature and behave exactly as they do for "std::stack":

empty, size, pop, swap

However, whereas the standard library container "std::stack" contains
elements of only one type, for example:

std::stack<int > my_multistack_of_ints ;
std::stack<float > my_multistack_of_floats ;
std::stack<std::string> my_multistack_of_strings;

The MultiStack container can have a unique type for each element,
for example:

int my_int = 5;
double my_double = 67.45;
std::string my_str("I like green monkeys");

MultiStack my_multistack;
my_multistack.push(my_int );
my_multistack.push(my_double);
my_multistack.push(my_str );
my_multistack.emplace<int>(65535);
my_multistack.emplace<std::string>(20u, 'a');

I'm sure you can guess how I implemented the "push" and "emplace" member
functions, quite simply as templates:

template<class T>
void MultiStack::push(T const &arg)
{
/* Push an object onto the stack */
}

template <class T, class... Args>
void MultiStack::emplace(Args&&... args)
{
/* Construct an object and push it onto the stack */
}

So now the only member function left to implement is "top". At first
glance, you might think that the way to implement "top" would be to have
multiple overloads of the member function "top", but C++ doesn't allow
function overloads that only differ by return type. The following is
disallowed:

class MultiStack {
public:
int top(void) { /* implementation */ }
float top(void) { /* implementation */ }
std::string top(void) { /* implementation */ }
};

Nor did I go with the following tactic of a template function to which
you would explicitly specify the type:

class MultiStack {
public:
template<class T>
T &top(void) { /* implementation */ }
};

int some_value = my_multistack.top<int>();

What C++ does allow though, is to throw an exception of any type -- and
so exception handling can be used as a more elaborate form of return
value.

And so I've written the "top" member function as a non-template function
to return void as follows:

void MultiStack::top(void)
{
/* Throw an exception from here in order
to return an object of any type */
}

In the event that a runtime error occurs in the "top" member function,
an exception of type "Stack::exception_top_error" will be thrown.
NOTE: It is permitted to push an "std::exception" (or any of its
derivatives such as "runtime_error") onto the stack -- and for this
reason "Stack::exception_top_error" does not derive from std::exception.

And so then a programmer could use the MultiStack class as follows.
First lets create an object of type 'MultiStack', and push (or emplace)
13 objects onto it:

MultiStack my_multistack;

my_multistack.push( int() );
my_multistack.push( double() );
my_multistack.push( int() );
my_multistack.push( std::pair<int,int>() );
my_multistack.push( int() );
my_multistack.push( int() );
my_multistack.push( float() );
my_multistack.push( int() );
my_multistack.push( double() );
my_multistack.push( std::runtime_error("Something went wrong!") );
my_multistack.push( std::pair<int,int>() );
my_multistack.emplace<int>(5);
my_multistack.emplace<std::string>(20, 'a');

Next let's run a loop to pop elements off the stack until it's empty:

for ( ; ! my_multistack.empty(); my_multistack.pop() )
{
try
{
my_multistack.top();
}
catch(int const &e)
{
cout << "Just got an int!" << endl;
}
catch(double const &e)
{
cout << "Just got a double!" << endl;
}
catch(std::pair<int,int> const &e)
{
cout << "Just got a pair<int,int>!" << endl;
}
catch(std::string const &str)
{
cout << "Just got a std::string, contents = '" << str << "'"
<< endl;
}
catch(std::exception const &e)
{
cout << "Just got a std::exception, what = '" << e.what() <<
"'" << endl;
}
catch(MultiStack::exception_top_error const &e)
{
/* something went wrong when popping */
cout << e.what() << endl;
}
catch(...)
{
cout << "Just got something unexpected! -- not necessarily
an error" << endl;
}
}

I have tested this and it's working as I intended it. I have a few more
things to tweak, such as the ability to stack objects that don't have
a copy-constructor, but I have the beef of the code written. See all my
code here:

#include <cassert> // assert
#include <cstddef> // size_t
#include <utility> // pair
#include <stack> // stack
#include <exception> // exception
#include <typeinfo> // typeid
#include <type_traits> // is_base_of, is_array
#include <string> // string

// Next 5 lines just for debugging
#include <stdexcept> // runtime_error
#include <cstring> // memcpy
#include <iostream>
using std::cout;
using std::endl;

class MultiStack {
public:

typedef std::size_t size_type;

MultiStack(void) = default;

MultiStack(MultiStack const &) = delete;
MultiStack(MultiStack &&) = delete;
MultiStack &operator=(MultiStack const &) = delete;
MultiStack &operator=(MultiStack&&) = delete;

class exception_top_error { /* important not to derive from
std::exception */
protected:
std::string str;

public:
exception_top_error(std::exception const &arg)
{
str = "ERROR: Exception thrown when calling
MultiStack::top(), type : '";
str += typeid(arg).name();
str += "', what() == '";
str += arg.what();
str += "'";
}

char const *what(void) const noexcept
{
return str.c_str();
}
};

protected:

template<class T>
static void Delete_Or_Throw(void *const arg_p, bool const
arg_to_throw_or_not_to_throw = true)
{
if ( ! arg_to_throw_or_not_to_throw )
{
if ( std::is_array<T>::value ) /* C++11 doesn't have 'if
constexpr' */
{
delete [] static_cast< typename
std::remove_extent<T>::type * >(arg_p);
}
else
{
delete static_cast<T*>(arg_p);
}

return;
}

// If control reaches here, we're not deleting -- instead we're
throwing

try
{
// Since the type T could be 'std::exception' or one of its
// derivations (e.g. 'std::runtime_error'), we need to make
// a distinction here when throwing, because the 'throw'
// command itself might throw an exception such as
// "bad_alloc", and so we throw an object of type:
// T[1u]
// instead of:
// T
throw *static_cast<T (*)[1u]>( static_cast<void*>(arg_p) );
}
catch(T const (&e)[1u])
{
//cout << "Got to Line " << __LINE__ << endl;
throw e[0u];
}
catch(std::exception const &e) /* To handle the likes of
"bad_alloc" */
{
//cout << "Got to Line " << __LINE__ << endl;
throw exception_top_error(e);
}
catch(...)
{
//cout << "Got to Line " << __LINE__ << " -- exception
thrown of unknown type (not derived from std::exception) -- calling
std::abort()" << endl;
std::abort();
}
}

std::stack< std::pair<void (*)(void*,bool), void*> > _stack;

public:

bool empty(void) const { return _stack.empty(); }
std::size_t size(void) const { return _stack.size (); }

void swap(MultiStack &rhs)
{
_stack.swap(rhs._stack);
}

void pop(void)
{
assert( ! _stack.empty() );

assert( nullptr != _stack.top().first );
assert( nullptr != _stack.top().second );

_stack.top().first( _stack.top().second, false /* just delete */
);
_stack.pop();
}

template<class T>
void push(T const &arg)
{
try
{
_stack.push( { &Delete_Or_Throw<T>, new T(arg) } ); //
This might throw bad_alloc
}
catch(std::exception const &e)
{
#ifndef NDEBUG
std::cout << "Exception thrown from " << __func__ << endl;
#endif
throw;
}
}

template <class T, class... Args>
void emplace(Args&&... args)
{
try
{
_stack.push( { &Delete_Or_Throw<T>, new
T(std::forward<Args>(args)...) } ); // This might throw bad_alloc
}
catch(std::exception const &e)
{
#ifndef NDEBUG
std::cout << "Exception thrown from " << __func__ << endl;
#endif
throw;
}
}

void top(void)
{
assert( ! _stack.empty() );

decltype(_stack)::value_type *p_top = nullptr;

try
{
p_top = &_stack.top();
//throw std::runtime_error("_stack.top() threw an
exception"); /* just for debugging */
}
catch (std::exception const &e)
{
throw exception_top_error(e);
}

assert( nullptr != p_top );
assert( nullptr != p_top->first ); /* p->first is a pointer
to a function that throws an exception */
assert( nullptr != p_top->second ); /* p->second is a pointer
to an object on the heap */

p_top->first( p_top->second, true /* throws exception */ ); /*
This line could throw an exception of any type as its "return value" */
}

virtual ~MultiStack(void)
{
while ( ! _stack.empty() )
{
pop();
}
}
};

auto main(void) -> int
{
MultiStack my_multistack;

my_multistack.push( int() );
my_multistack.push( double() );
my_multistack.push( int() );
my_multistack.push( std::pair<int,int>() );
my_multistack.push( int() );
my_multistack.push( int() );
my_multistack.push( float() );
my_multistack.push( int() );
my_multistack.push( double() );
my_multistack.push( std::runtime_error("monkey") );
my_multistack.push( std::pair<int,int>() );
my_multistack.emplace<int>(5);
my_multistack.emplace<std::string>(20, 'a');

MultiStack another_multistack;

another_multistack.swap(my_multistack);

for ( ; ! another_multistack.empty(); another_multistack.pop() )
{
try
{
another_multistack.top();
}
catch(int const &e)
{
cout << "Just got an int!" << endl;
}
catch(double const &e)
{
cout << "Just got a double!" << endl;
}
catch(std::pair<int,int> const &e)
{
cout << "Just got a pair<int,int>!" << endl;
}
catch(std::string const &str)
{
cout << "Just got a std::string, contents = '" << str << "'"
<< endl;
}
catch(std::exception const &e)
{
cout << "Just got a std::exception, what = '" << e.what() <<
"'" << endl;
}
catch(MultiStack::exception_top_error const &e)
{
/* something went wrong when popping */
cout << e.what() << endl;
}
catch(...)
{
cout << "Just got something unexpected! -- not necessarily
an error" << endl;
}
}
}

[David Brown]

How does it compare to:

std::stack<std::variant<int, float, std::string>> my_stack;


The idea of a MultiStack doesn't sound bad, but abusing exceptions for
the return of top() strikes me as horrible. It will be messy and
non-standard in use, unnecessarily dynamic, and seriously inefficient
(exception implementations are designed to be as low cost as possible
when there are no exceptions, at the price of being slow when thrown).

If you want to "overload on return type", you can do it by returning a
proxy object that has conversion operators for the various types you
want to use.

[Öö Tiib]

On Thursday, 4 November 2021 at 23:05:59 UTC+2, David Brown wrote:
> On 04/11/2021 12:45, Frederick Gotham wrote:
> > I'm writing a class called "MultiStack". It is a stack container in

...

> How does it compare to:
>
> std::stack<std::variant<int, float, std::string>> my_stack;

His idea seems closer to std::stack<std::any> .

[red floyd]

Yeah, I was wondering about that as well.

[David Brown]

Yes, that occurred to me too. But I think it is more common to have
need of a type that could be one of a few different things, than to be
writing code where you have no idea what types you are dealing with.

But it will also be interesting to hear how Frederick sees his container
compare to std::stack<std::any>.

[Paavo Helde]

04.11.2021 13:45 Frederick Gotham kirjutas:
> I'm writing a class called "MultiStack". It is a stack container in
> which the elements can be of different types, for example you can push
> an 'int' onto the stack, and then push a 'std::string' onto the stack.
>

As others have commented, the abstraction is in the wrong place here.
The stack should not concern itself about such details about its
elements. Instead, one adds an abstraction layer like std::variant or
std::any, and keeps the stack implementation unchanged. Otherwise you
will soon find yourself reimplementing also vector, list, map, etc.

A major point about C++ is that adding such abstraction layers does not
cause any extra performance penalties.

> So now the only member function left to implement is "top". At first
> glance, you might think that the way to implement "top" would be to have
> multiple overloads of the member function "top", but C++ doesn't allow
> function overloads that only differ by return type. The following is
> disallowed:
>
> class MultiStack {
> public:
> int top(void) { /* implementation */ }
> float top(void) { /* implementation */ }
> std::string top(void) { /* implementation */ }
> };

Sure, but you can have template member functions:

class MultiStack {
public:
template<typename T> T top();
template<typename T> bool top_is();
};

For using this I also added a type check function top_is(). A basic
usage example:

MultiStack stack = ...;

if (stack.top_is<int>()) {
int x = stack.top<int>();

} else if (stack.top_is<float>()) {
float f = stack.top<float>();

} else if (stack.top_is<std::string>()) {
std::string s = stack.top<std::string>();
}

This usage would be about at least hundreds of times faster than abusing
the exception throw/catch mechanism.

Of course, this would still be abstraction in wrong place, and this all
would be resolved better by using std::stack<std::any> or similar.

[Bonita Montero]

Any allocates its items usually on the heap because there is
no maximum storage requirement of the items, whereas variant
is internally usually sth. like a union and a type tag, which
might consume more memory, but is significantly faster.

[Tony Oliver]

I assume you’re talking about std::variant. It is not internally using south, whatever you think.

[red floyd]

In Bonita's defense, "sth" = "something". I've seen that usage elsewhere.

[Bonita Montero]

std:: can be omitted.