Heterogenous container using only static polymorphism

Question

My goal is to implement a container (here a set of stacks, one for each type) that accepts many different types of objects simultaneously. This would be trivial to do at runtime, using void pointers (or a common base class for all stored types) and runtime type indentification (RTTI). Since all types the container is going to hold are known at compile time, it may (or may not) be possible to make such a class using templates. I am aware that boost::variant already provides similar functionality, but it requires that the stored types are listed as template arguments, as in boost::variant< int, std::string > v;.

What I'm really looking for is a class that transparently adds a matching (internal) data strucure to itself each time a new template specialization of the equivalent of push() is created. The usage of the class would look like this:

int main()
{
    MultiTypeStack foo;
    //add a double to the container (in this case, a stack). The class would
    //..create a matching std::stack<double>, and push the value to the top.
    foo.push<double>(0.1);
    //add an int to the container. In this case, the argument type is deduced.
    //..The class would create a std::stack<int>, and push the value to the top.
    foo.push(123);
    //push a second double to the internal std::stack<double>.
    foo.push<double>(3.14159);
    std::cout << "int: " << foo.top<int>() << "\n";      //"int: 123"
    std::cout << "double: " << foo.top<double>() << "\n";//"double: 3.14159"
    return 0;
}

A naïve implementation as an example:

template<typename T> struct TypeIndex;
template<> struct TypeIndex<int>{enum{i = 0};};
template<> struct TypeIndex<double>{enum{i = 1};};

class MultiTypeStack
{
public:
    template<typename T>
    void push(const T &val){std::get<TypeIndex<T>::i>(stacks_).push(val);}

    template<typename T>
    void pop(){std::get<TypeIndex<T>::i>(stacks_).pop();}

    template<typename T>
    T top(){return std::get<TypeIndex<T>::i>(stacks_).top();}
private:
    std::tuple<std::stack<int>, std::stack<double>> stacks_;
};

Answer 1

The problem with trying to use static polymorphism to implement a heterogeneous container of the kind you describe is that while "all types the container is going to hold are known at compile time," this information is not available until very late in the compilation process. In fact, thanks to C++'s translation unit model of compilation, you can only really depend on that type information being available at link time, which just screams virtual dispatch.

Realistically, I'd say the best way of accomplishing most of what you want without invoking Greenspun's Tenth Rule of Programming outright is to use the method of ad-hoc dynamic polymorphism (dynamically dispatching on a type without requiring that it inherit from a particular base class) outlined by Sean Parent in his GoingNative 2013 talk. It does rely internally on full-blown inheritance-based dynamic typing, but it hides it all away and allows for stratifying the elements according to type with a little work. Expanding on @Yakk's suggestion:

#include <stack>
#include <unordered_map>
#include <typeindex>

class MultiStack
{
    class MultiStackBase
    {
    public:
        virtual ~MultiStackBase () = default;
    };

    template <typename T>
    class MultiStackImpl
        : public MultiStackBase
    {
        std::stack <T> _stack;

    public:
        virtual ~MultiStackImpl () = default;

        template <typename U>
        void push (U&& new_element)
        { _stack.push (std::forward <U> (new_element)); }

        void pop ()
        { _stack.pop (); }

        T& top ()
        { return _stack.top (); }

        const T& top () const
        { return _stack.top (); }
    };

    mutable std::unordered_map <std::type_index, std::unique_ptr <MultiStackBase>> stacks;

protected:
    template <typename T>
    static std::type_index index ()
    { return std::type_index {typeid (T)}; }

    template <typename T>
    MultiStackImpl <T>& stack_cast ()
    {
        if (stacks.count (index <T> ()) == 0)
            stacks [index <T> ()] = std::make_unique <MultiStackImpl <T>> ();
        return dynamic_cast <MultiStackImpl <T>&> (*stacks [index <T> ()]);
    }

    template <typename T>
    const MultiStackImpl <T>& stack_cast () const
    {
        if (stacks.count (index <T> ()) == 0)
            stacks [index <T> ()] = std::make_unique <MultiStackImpl <T>> ();
        return dynamic_cast <const MultiStackImpl <T>&> (*stacks [index <T> ()]);
    }

public:
    template <typename T, typename U>
    void push (U&& new_element)
    { stack_cast <T> ().push (std::forward <U> (new_element)); }

    template <typename T>
    void pop ()
    { stack_cast <T> ().pop (); }

    template <typename T>
    T& top ()
    { return stack_cast <T> ().top (); }

    template <typename T>
    const T& top () const
    { return stack_cast <T> ().top (); }
};


#include <iostream>

int main ()
{
    MultiStack m;

    m.push <int> (42);
    m.push <float> (3.14);

    std::cout << m.top <int> () << std::endl
              << m.top <float> () << std::endl;
}

we get the following output:

42
3.14

So unfortunately we did resort to dynamic typing and don't have template argument deduction as we'd like (you could have a deducing push, but I suspect it would be prone to subtle programmer errors; better to make it explicit), but we got the desired behaviour: a multi-type stack without enumerating types, letting instead the compiler determine them for us.

EDIT: I should point out that this approach has one potentially massive benefit over a statically typed implementation (if such a thing is even possible): with a purely static implementation, every object of type MultiStack would have a stack for every type used; for example, if you used a std::string in a MultiStack in one function, a MultiStack living in another would also have a std::string stack, and vice versa. Doing it this way, any given MultiStack object only allocates stacks for the types it uses.

Answer 2

Create an std::unordered_map<std::type_index, std::unique_ptr<unknown>>. Your typed access code takes the type and finds the appropiate entry. Then static_cast the unknown to a type dependent on T that holds your stack.

Make sure unknown is a base of stack_holder<T>, and that unknown has a virtual destructor.

This is probably not exactly what you want, but the C++ type system is pure: later expressions cannot change 'earlier' types.

If you chained the type you could construct a more complex type, but this is just listing the types while concealing them.

If the object is a singleton some hackery using static locals could work.

Answer 3

I have an implementation that is slightly different from what you requested, but maybe it will work for you. I made a list-like structure that when you try to add a new type of element into it either copies or moves itself into an enveloping container (of a different type) that can contain that new element type. (Like a persistent data structure in the copy case).

Here is the code. It is pretty ugly and I wasn't going to post it but no has answered at the time of writing so I can only hope someone can help make it better.

//Checks if list (or element) S has element of type T
template<class L, class T> struct HasElem : std::is_same<L,T>{};

template<template<class,class> class Node, class T, class NodeT, class Next>
struct HasElem<Node<NodeT,Next>,T>{
  static constexpr bool value = std::is_same<NodeT,T>::value || HasElem<Next,T>::value;
};
template<template<class> class Leaf, class S, class T> struct HasElem<Leaf<S>,T> :  std::is_same<S,T>{};

//Push type transform
template<class N, class T> struct Push{};
template<template<class,class> class Node, class T, class Next, class U> struct Push<Node<T,Next>,U>{
    typedef Node<U,Node<T,Next>> type;
};

//Node type
template<class T, class Next>
struct Node{
    Node(Next&& nxt) : next(nxt){}
    Node(const Next& nxt) : next(nxt){}

    std::stack<T> st;
    Next next; 

    //Pushing a new type onto the stack
    template<class U> typename std::enable_if<!HasElem<Node,U>::value,typename Push<Node,U>::type>::type
        push(const U& u) &&{ //disallow pushing new types on lvalues
            return typename Push<Node,U>::type(std::move(*this)).push(u);
        }
    //Pushing a new type onto the stack as an lvalue and return a copy
    template<class U> typename std::enable_if<!HasElem<Node,U>::value,typename Push<Node,U>::type>::type
        push_new(const U& u) const{ //cannot overload on && qualifier. Make the name uglier to warn of the cost
            return typename Push<Node,U>::type(*this).push(u);
        }

    //Regular old push
    Node& push(const T& t){ st.push(t); return *this; }
    //Push onto another node in the list
    template<class U> typename std::enable_if<HasElem<Node,U>::value,Node>::type
        push(const U& u){ next.push(u); return *this; }

    template<class U> typename std::enable_if<std::is_same<T,U>::value,U>::type&
        top(){ return st.top(); }
    template<class U> typename std::enable_if<!std::is_same<T,U>::value && HasElem<Node,U>::value,U>::type&
        top(){ return next.top<U>(); } 

};

//The last node. I made it hold data but it doesn't need to
template<class T> struct Leaf{
  std::stack<T> st;

  Leaf& push(const T& t){ st.push(t); return *this; }
  template<class U> Node<U,Leaf> push(const U& u){ 
      return Node<U,Leaf>(std::move(*this)).push(u);
  }

  template<class U> void top(){}
  T& top(){ return st.top(); }
  void pop(){ st.pop(); }
};

Here is an example of how to use it and hide away the difference between push and push_new.

template<class T, class Next, class U> auto push(Node<T,Next>&& n, const U& u) 
 -> decltype(n.push(u)){
    return n.push(u);
}
template<class T, class Next, class U> auto push(const Node<T,Next>& n, const U& u)
 -> decltype(n.push_new(u)){
    return n.push_new(u);
}

int main(){
    auto b = Leaf<int>().push<int>(42).push<double>(3.14).push<char>('a');
    auto a = push(b,(char*)"Hello"); //Make a copy of b but with "Hello"

    cout << a.top<int>() << " " << a.top<double>() << " " <<
        a.top<char>() << " " << a.top<char*>() << endl;

    cout << b.top<char>() << endl; //The earlier version b still exists
}

The major downside is that it will be inefficient if you save the intermediate states (i.e. into variables) but if you chain operations together like b in the example you can avoid it.