Heterogeneous container using only static polymorphism

Question

My goal is to implement a container (here is a set of stacks, one for each type) that accepts many different types of objects at the same time. This would be trivial to do at runtime using void pointers (or a common base class for all stored types) and runtime type indexing (RTTI). Since all the types that 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 know that boost::variant already provides similar functions, but requires that the stored types be specified 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 structure to itself every time a new specialized specialization of the push() equivalent is created. Using the class will 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; } 

An example naive implementation:

 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

Create std::unordered_map<std::type_index, std::unique_ptr<unknown>> . Your entered passcode accepts the type and finds the corresponding entry. Then static_cast unknown to the type dependent on T which your stack contains.

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

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

If you bound the type, you could build a more complex type, but it's just an enumeration of the types when hiding them.

If the object is a singleton hacker using static , local residents can work.

Answer 2

The problem with trying to use static polymorphism to implement a heterogeneous container of the type you are describing is that, although "all types that 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 the compilation model with translation into C ++, you can only really depend on what information is available at the time of the link, which just screams virtual sending.

Actually, I would say that the best way to accomplish most of what you want without urging the Greenspun Tenth Rule of Programming to directly use the ad-hoc dynamic polymorphism method (dynamic dispatch by type that does not require its inheritance from a specific base class) described Sean Parent in his discussion of GoingNative 2013 . It relies internally on full-scale dynamic typing of inheritance, but it hides all this and allows you to stratify elements by type with little work. Extension to @ 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 result:

 42 3.14 

So, unfortunately, we resorted to dynamic typing and do not have the output of the template arguments as we would like (you could output the output, but I suspect that it will be prone to subtle programmer errors, it is better to make it explicit), but we got the desired behavior: a multi-type stack without enumerating types, allowing the compiler to define them for us instead.

EDIT: I have to point out that this approach has one potentially huge advantage 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 std::string in MultiStack in one function, a MultiStack living in another would also have a std::string stack and vice versa. Thus, any given MultiStack object allocates only stacks for the types it uses.

Answer 3

I have an implementation that is slightly different from what you requested, but maybe this will work for you. I created a structure that looks like a list, which when you try to add an element of a new type to it, either copies or moves to an envelope container (of another type) that may contain this new type of element. (As a permanent data structure in case of copying).

Here is the code. This is pretty ugly, and I was not going to publish it, but no one answered at the time of writing, so I can only hope that 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 using and hiding 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 main disadvantage is that it will be ineffective if you save intermediate states (i.e. in variables), but if you combine operations together, for example b , in the example, you can avoid this.

Answer 4

There were several presentations in C ++ Now 2013 that describe how to implement dynamic containers in a static language such as C ++. These were:

1) Dynamic, recursive, heterogeneous types in statically typed languages: paper and presentation

2) Dynamic C ++ presentation

The two people also collaborated in a Dynamic C ++ article for an online article for ACCU: Dynamic C ++

There is a lot of information on how to create dynamic constructs for a static language such as C ++.