8

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?

sunny
  • 3,853
  • 5
  • 32
  • 62
  • 2
    Yes, you can use allocators to do this. What have you tried? Show your working :) – Andrew Jul 30 '15 at 15:25
  • @Andrew 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. – sunny Jul 30 '15 at 15:29
  • 1
    By any chance, are sizes known at compile time? – Sergey Kalinichenko Jul 30 '15 at 15:30
  • @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. – sunny Jul 30 '15 at 15:33
  • 8
    @sunny If sizes stay the same and known at compile time, do you think you could use `std::array` 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. – Sergey Kalinichenko Jul 30 '15 at 15:35
  • @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 – sunny Jul 30 '15 at 15:40
  • Have a look at http://stackoverflow.com/a/18518258/2249683 –  Jul 30 '15 at 17:03
  • 1
    See also http://codereview.stackexchange.com/questions/31528/a-working-stack-allocator – Chris Drew Jul 30 '15 at 19:10
  • @sunny: are those by any chance dependencies on the usual `std::vector>` ? Because using a custom allocator affects the vector type. – MSalters Jul 30 '15 at 21:25
  • @MSalters my understanding is that nowadays the compiler ignores the allocator type for purposes of determining template type (saw that somewhere in this presentation: https://www.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. – sunny Jul 30 '15 at 21:29
  • The compiler cannot ignore it (it's library-unaware). However, the library provides conversions. But you can't have conversions on a `std::vector&` argument. – MSalters Jul 30 '15 at 21:35
  • @MSalters I see your point, but I don't see how that's a problem? – sunny Jul 30 '15 at 21:41

2 Answers2

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)...

Community
  • 1
  • 1
sunny
  • 3,853
  • 5
  • 32
  • 62
0

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.

kchoi
  • 473
  • 1
  • 4
  • 11
  • 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. – sunny Jul 31 '15 at 14:56
  • 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. – kchoi Jul 31 '15 at 14:59