MPL-like vector with variadic templates: Insertion

Question

I am wondering how one would write a Boost MPL-like vector_c using variadic templates. I already wrote the following snippet of code:

template <std::size_t element, std::size_t ... E>
struct vector
{
    typedef vector<E ...> next;

    static constexpr std::size_t size()
    {
        return sizeof... (E);
    }

    static constexpr std::size_t value()
    {
        return element;
    }
};

template <std::size_t element>
struct vector<element>
{
    // no need to define 'next' here

    static constexpr std::size_t size()
    {
        return 1;
    }

    static constexpr std::size_t value()
    {
        return element;
    }
};

You may notice that vector must have at least one element in it, but that is not really a restriction for me. With the definitions above, it is very easy to write "functions" for accessing the elements for a given index:

template <std::size_t index, typename T>
struct get
{
    typedef typename get<index - 1, typename T::next>::type type;
};

template <typename T>
struct get<0, T>
{
    typedef T type;
};

For example, get<1, vector<1, 2, 3>> returns the correct result 2. Now my question: How would one implement an insert function? The reason I am not using MPL is that when I tried its insert<>, it did not return a vector_c. In particular, an insertion should be applied like this:

insert<vector<1, 3, 4>, 1, 2>::type
//     ^                ^  ^
//     type            at  element

which must yield vector<1, 2, 3, 4>. It that possible?

Answer 1

In terms of Haskell,

insert list 0 element = element : list
insert list at element = (head list) : insert (tail list) (at-1) element 

and translating this to C++ templates:

// insert list at element =
template <typename List, size_t at, size_t element>
struct Insert
{
    typedef typename
        // insert (tail list) (at-1) element
        Insert<typename List::next, at-1, element>::type::
        // (head list) : …
        template push_front<List::value()>::type
    type;
};

// insert list 0 element = 
template <typename List, size_t element>
struct Insert<List, 0, element>
{
    // element : list
    typedef typename List::template push_front<element>::type type;
};

Note that you need to define the primitive push_front in both vector's:

template <std::size_t element, std::size_t ... E>
struct vector<element, E...>
{
    template <size_t x>
    struct push_front
    {
        typedef vector<x, element, E...> type;
    };
};