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?

score 2 · Accepted Answer · answered Mar 06 '12 at 20:35

2

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;
    };
};

answered Mar 06 '12 at 20:35

kennytm

510,854
105
1,084
1,005

nice solution - it helps give an insight of how a lot boost MPL could be re-written / replaced with variadic templates. – mark Mar 06 '12 at 21:05
In the meantime I also came to the conclusion that I have to write a `push_front` function - however, I did not realize that it has to be inside the vector itself! I think it is impossible to write push_front outside the vector class, right? – cschwan Mar 07 '12 at 09:47
1

@cschwan: Of course you *can* (example: http://ideone.com/3F4UQ). I just don't bother to do that. – kennytm Mar 07 '12 at 10:08
Thanks for the link. When I tried to write `push_front` outside of the class I ran into "invalid use of incomplete type" errors. Searching for a solution, I found http://stackoverflow.com/questions/652155/invalid-use-of-incomplete-type in which the solution suggested to put it inside the class. This only as a reference for people who also try to do that. – cschwan Mar 07 '12 at 12:22

score 1 · Answer 2 · answered Mar 06 '12 at 20:00

if you want MPL to return a vector_c after an insert, you have to covnert it into a vector_c usign as_vector.

You're dealing with a semi-functionnal language here so if you want toinsert, you need to rebuild a new vector_c out of the old and the index/position. What MPL does, as such a reconstruction is very tedious is return a type which acts as a vector (aka follow the Static Sequence concept) and have an overload get<> that knows that when position N is required, checks the insert values to see what to return.

Thanks for the explanation - where do I find `as_vector`? – cschwan Mar 07 '12 at 09:48 — cschwan, Mar 07 '12 at 09:48

MPL-like vector with variadic templates: Insertion

2 Answers2