Can a contiguous allocation boundary be forced in a C++ template?

Question

Simple example:

template <class P> class MyT
{
    struct Item
    {
    public:
        Item() {}
        P *pData;
        Item *next;
    };
    Item *head;
public:
    ...adding etc..
    P* operator [](int index)
    {
       See question below:
    }
};

Can I somehow make sure that the 'Item's are allocated in such a way that I can calculate the offset as follows: (@Steve:) Maybe not so clear here; what I need is a quick & easy way to get to the item without iterating through 10000 next's.

Item *pi = head + (sizeof(Item) * (index - 1));

A (clearer?) explanation of what I mean

Answer 1

Item* pi = (head + (index - 1));

does the job. Btw, are you sure you want to do this? struct Item looks like linked-list structure (contains next).

Answer 2

I guess what you need is a std::list or std::vector.

However what you are trying would work if you have allocated sequential memory for Items and head is pointing to the start along with the modification suggested by Yossarian.

You can pre-allocate while initializing if this limit is crossed, allocate more and copy your contents to that area, freeing the existing.

Note: All these things are wrapped for you in the std containers.

Answer 3

Depends what you mean by "etc", in "adding, etc".

If "etc" includes, "removing", then you have the obvious problem that if you remove something in the middle of your list, then to maintain the indexing you have to shift everything after it downwards, which means updating all the next pointers.

I think perhaps you have simplified your example too far. If you require contiguous storage, use a vector (either of P, or of Item if there's something useful in Item that you've removed). If you have contiguous storage, then there's no benefit in having a next pointer, since you could just calculate it in Item, by adding 1 to this (then checking a bound to make sure you haven't reached the end).

If you absolutely need the public next pointer field, because it's part of some interface you're implementing that you can't change, then you could update it in the copy constructor and operator= for Item, and the interface had better forbid clients from writing to it.

There's no way to tell the memory allocator to allocate contiguous storage for separate allocations, if that's what you're asking. How would that even work? What if when you come to allocate, the "next" address is already occupied? What if the allocator imposes some overhead, for its own control structures (as almost all general-purpose allocators do), so that allocating an Item requires more than sizeof(Item) bytes? You can get the behaviour you want for a while with a fixed-size allocator, but eventually it needs a new block, or you delete something, and the relationship no longer holds.

Answer 4

"Memory Boundaries" can be forced through special gcc keywords

http://gcc.gnu.org/onlinedocs/gcc/Variable-Attributes.html#Variable-Attributes

look at "alignment"

Answer 5

If I understand your question correctly you need to override operator new for Item and have the allocator pre-allocate enough memory to store all the Items you will ever need (which isn't possible in the general case but may be possible in your specific scenario). Then whenever an Item is newed up the allocator will return the next slot in the pre-allocated block.

All this looks un-realistic and the simple solution would be to use std::vector.