Allocation of variable-sized class

Question

I have a variable length data structure, a multi-dimensional iterator:

class Iterator
{
public:
    static Iterator& init(int dim, int* sizes, void* mem)
    {
        return *(new (mem) Iterator(dim, sizes));
    }

    static size_t alloc_size(int dim)
    {
        return sizeof(Iterator) + sizeof(int) * 2 * dim;
    }

    void operator++()
    {
        // increment counters, update pos_ and done_
    }

    bool done() const { return done_; }
    bool pos()  const { return pos_; }

private:
    Iterator(int dim, int* sizes) : dim_(dim), pos_(0), done_(false)
    {
        for (int i=0; i<dim_; ++i) size(i) = sizes[i];
        for (int i=0; i<dim_; ++i) counter(i) = 0;
    }

    int  dim_;
    int  pos_;
    bool done_;
    int  size   (int i) { return reinterpret_cast<int*>(this+1)[i]; }
    int& counter(int i) { return reinterpret_cast<int*>(this+1)[dim_+i]; }
};

The dimensionality of the iterator is not known at compile time but probably small, so I allocate memory for the iterator with alloca:

void* mem = alloca(Iterator::alloc_size(dim));

for (Iterator& i = Iterator::create(dim, sizes, mem); !i.done(); ++i)
{
    // do something with i.pos()
}

Is there a more elegant way of allocating memory for the iterator? I am aware of the fact that upon returning from a function, its stack is unwound, thus alloca must be used in the caller's stack frame (see e.g. here). This answer suggests that the allocation be performed in a default parameter:

static Iterator& init(int dim, int* sizes, void* mem = alloca(alloc_size(dim)));

However elegant, this solution does not help me: Default argument references parameter 'dim'. Any suggestion for a nice solution?

Answer 1

I wouldn't recommend to use alloca at all. If dim value is small, then some fixed-size buffer inside a class would be sufficient. If dim is large then heap allocation cost would be neglectable comparing to complexity of other operations performed on your iterator (note that for very large dim values alloca may cause stack overflow). You may choose between fixed buffer and heap allocation at runtime, depending on dim size.

So I'd recomend approach similar to small string optimization in std::string.

Perhaps, some kind of COW (copy on write http://en.wikipedia.org/wiki/Copy-on-write) techique may be also useful for your iterators.

Note, that this technique cannot be used with alloca, only with heap allocation. Morever, it's almost impossible to copy or copy initialize your iterators if they use alloca (at least without more and more ugly macroses).

Alloca is evil :)

Answer 2

You could have the dimension parameter as a template argument.

Answer 3

My suggestion might not be what you are looking for but why not have a create|make_iterator function that does the alloca call?

Answer 4

Unfortunately, given that dim is a run-time value, there isn't any way to do this other than with a macro:

#define CREATE_ITERATOR(dim, sizes) \
    Iterator::init(dim, sizes, alloca(Iterator::alloc_size(dim)))