Contiguous memory allocation for several small std::vectors?

Question

I would like to find a way to store several std::vectors, each of a different but known and reasonably small size, in contiguous memory. I realize I could write my own class, say with a very large array and with pointers to the start of each subsection of the array within the larger array treated like a separate entity, but it seems like there should be a smarter way to do this.

Is there a way to use allocators, for example, to create contiguous std::vectors? I'd like not to reinvent the wheel just because I want this memory-locality of otherwise normal std::vectors

I don't know how to even begin coding. I need to create an allocator that takes a pointer to memory, allocates a vector there, and then somehow passes back the address of the end of that vector, so the next std::vector's allocator could grab that and do it again. How can an allocator return a value?

Bub

Yes, you can use allocators to do this. What have you tried? Show your working :) – Wait

@Wait I added something in my question, but I don't know where to begin. I haven't worked with allocators, and so far all I've done is read Josuttis's sections in his STL reference. – Bub

By any chance, are sizes known at compile time? – Dodd

@dasblinkenlight yes type and vector size are both known. I know everything about these vectors. Now I need to figure out how to write and use an allocator that could return a memory address. – Bub

@Bub If sizes stay the same and known at compile time, do you think you could use std::array<T,N> instead? It is much easier to place them in memory, and since you are not growing your vectors, the unnecessary member functions, such as push_back(...), would be gone. Of course if you are on pre-C++11, this wouldn't be an option. – Dodd

@dasblinkenlight There are many (and some unknown to me) dependencies on an std::vector implementation for these objects, so that is not an option. I am on C++11 – Bub

Have a look at https://mcmap.net/q/1268026/-algorithm-to-unify-contiguous-chunks-in-a-collection-of-chunks – Lolalolande

See also codereview.stackexchange.com/questions/31528/… – Shiah

@sunny: are those by any chance dependencies on the usual std::vector<T, std::allocator<T>> ? Because using a custom allocator affects the vector type. – Yoko

@Yoko my understanding is that nowadays the compiler ignores the allocator type for purposes of determining template type (saw that somewhere in this presentation: youtube.com/watch?v=YkiYOP3d64E)...but even if this were not that case, I'm ok with that...if I can find a solution. What Chris Drew pointed to seems the most likely, except I want to allocate contiguous memory on the heap. – Bub

The compiler cannot ignore it (it's library-unaware). However, the library provides conversions. But you can't have conversions on a std::vector<int>& argument. – Yoko

@Yoko I see your point, but I don't see how that's a problem? – Bub

Answer 1

The solution is @HowardHinnant's short_alloc. I want to allocate on the heap so have to use new,*** but otherwise Howard's posted code does exactly what I want.

template <std::size_t N>
class arena
{...
char* buf_ = new char[N] 
// still need to align this but not sure of the syntax 
// to do that with a new statement
...

The missing piece from my perspective when I asked the question was that allocators can have constructors that take arguments:

constexpr int N = 1000*sizeof(int);
arena<N> myArena;
std::vector<int, short_alloc<int, N>> x(MyArena);

I found the code reference in another SO post: Questions about Hinnant's stack allocator which was referenced from the CodeReview post Chris Drew suggested in his comment above. Thank you all.

***The code does use new in the allocate method, leaving me unsure of whether this is allocated on the stack (as it appears from the declaration of buf_*) or on the heap (use of new)...

Bub

Answer 2

For your requirement, I would implement custom allocator that extends std::allocator and overrides allocate, deallocate method that grabs chunks from a memory pool. If you already know the maximum size required, selecting memory pool size shouldn't be a problem.

Yurt

Yes I agree, that's the strategy I stated in my original question, but I was not clear on how to execute it with an allocator. The solution I posted below does what I wanted. – Bub

If you want to allocate on the stack, have a look at grabbing memory with builtin alloca. Your custom allocator has choice where to grab memory pool from. Hope it helps. Since this allocates on the stack, it would be automatically discarded upon return. – Yurt