1

If I have a container:

std::vector<T*> elements;

can I use placement new to allocate my objects so that the objects are all allocated contiguously? So that I can do something like this:

size_t elementIndex = someRandomElement - elements[0];

Where someRandomeElement is a random element from elements and elementIndex will then store the correct index of someRandomElement so that elements[elementIndex] == someRandomElement

This is needed for my current implementation of a memory manager. I have an implementation that I was able to finish today, but it requires the elements (which can be a voxel, a triangle or anything else) to have GetIndex() and SetIndex() function so that when the element is returned as a pointer, I can find out the index of the element in the elements array, which means that any elements that I cannot change (let's say Ogre::Vector3) cannot use the manager (in my case, I need them to use it because they are fragmenting the memory).

My only other solution is to have a structure that acts as an accessor and has the index as well as the pointer to the element although this will result in an increased memory usage (considering I am working with 5 million elements right now).

NOTE: There is a similar question that I posted today, but the answers there are making some assumptions which go totally against my requirements. One of the requirement is that the vector must be filled with pointers to T otherwise a large portion of the code-base needs to change. Secondly, initializing more than 100,000 (approximately) elements results in a bad_alloc exception. Each element is 196 bytes in size (I have managed to reduce that to 132 bytes).

Community
  • 1
  • 1
Samaursa
  • 16,527
  • 21
  • 89
  • 160
  • Who is imposing this "requirement"? Is this homework? If not, it's a nonsensical requirement; if so, then tag your question as `homework`. – ildjarn Apr 22 '11 at 03:01
  • Similar? It's the same, except in this one you state your idea of a possible solution. – Lightness Races in Orbit Apr 22 '11 at 03:07
  • possible duplicate of [Array of contiguous new objects](http://stackoverflow.com/questions/5747455/array-of-contiguous-new-objects) – Lightness Races in Orbit Apr 22 '11 at 03:08
  • Nope, not homework. The other question has more details (in the comments) on the reason for this requirement. I don't know why there is so much opposition to a certain requirement? I do not wish to sound rude, but I am seeing that a lot of times people tend to enforce their _good practices_ too much and ask the OP to change one of their requirements. Anyway, the reason for it is that it gives me a bad alloc exception. It simply cannot allocate that many elements. I am following up on some suggestions to see how my program is using up the memory and why the allocation is failing. – Samaursa Apr 22 '11 at 03:08
  • @Tomalak Geret'kal: Not the same because I did not know about placement new which makes this an entirely different question although solving the same problem in my case. – Samaursa Apr 22 '11 at 03:10
  • @Samaursa: What you do or do not know does not change the fact that you're asking the same thing here. – Lightness Races in Orbit Apr 22 '11 at 03:11
  • 1
    @Samaursa : If your "requirement" had any fathomable rationale, people might be more amenable to working with it. But as it is, `std::vector<>`'s default behavior when working with *values* (as opposed to pointers to values) is **exactly** what you're asking for. – ildjarn Apr 22 '11 at 03:11
  • @Tomalak: Of course it does! If I didn't know about `std::vector` and I came in to say if there is any way to dynamically increase an array size and then sort through it and people answered with `use std::vector, iterators and sort algorithm`, would I not come back and ask for a good explanation on how iterators and algorithms work so that I can sort the dynamically changing array? (assuming none of these questions were asked before on SO). – Samaursa Apr 22 '11 at 03:15
  • @Samaursa : To clarify, the only rationale you've given for wanting to work with pointers rather than values is that it's "too much work" to change now. As for myself, I can only say that *I think* it's more work to sustain a bad design than to fix it. I.e., it'll be less work in the long run to fix your code than to come up with a custom allocator and continue to working with pointers. – ildjarn Apr 22 '11 at 03:16
  • @ildjarn: I have to change a LOT of code. Sometimes that is a good requirement I would say :) but the question remains. I wish to know about placement new and how to use it in a vector (which I am beginning to understand already uses it) regardless of whether it is a bad practice or not. If it cannot be done, then that is obviously an answer I am willing to accept. – Samaursa Apr 22 '11 at 03:17
  • 1
    @Samaursa : `std::vector<>` uses placement new internally; you cannot use placement new "with" `std::vector<>`. Whatever you reinvent to continue working with pointers will be a monstrosity to maintain compared to just changing your code to work with values. Guaranteed. – ildjarn Apr 22 '11 at 03:18
  • @ildjarn: (No sarcasm here) Warning completely understood! Currently I am at a point where I need to write code that works and then re-factor later simply because it will take too much time (I don't even know yet whether this whole thing will give me an advantage over my previous solution). It is like writing a function that does 3-4 things and then re-factoring it and making 4 functions out of the single function (just like the clean code book suggests). – Samaursa Apr 22 '11 at 03:20

2 Answers2

2

To make your pointed-to objects contiguous, you have two reasonable options:

  • use new[] to create a single array of elements big enough to hold them all, then assign new values into them and put their addresses into elements
  • use malloc() to create a big enough uninitialised memory area to hold them all (it will likely be sufficiently-strictly aligned, but you should be aware of the issue), then use placement new to construct your elements in that memory

Do not use new[] then placement new, as the default-constructed element won't be destructed before placement new overwrites their memory... consequently any resources their constructor takes, counters it maintains etc. can't be properly released/updated by the destructor.

If you don't have enough memory to allocate the big array, then obviously you can't do it... simple as that. 100,000 separate new Ts can be expected to need more memory than a single new T[100000] though... there's padding and heap management overheads associated with allocation.

Tony Delroy
  • 102,968
  • 15
  • 177
  • 252
1

The std::bad_alloc exception is likely because you are attempting to allocate too large a contiguous block of memory. So, consider using a std::deque<T> instead.

If you decide that you still need a std::vector<T*> for some reason, you can store pointers to the elements in the std::deque<T>. As long as you only add and remove elements from the beginning or end of the sequence, you don't need to worry about the pointers being invalidated.

James McNellis
  • 348,265
  • 75
  • 913
  • 977