Array of contiguous new objects

Question

I am currently filling an vector array of elements like so:

  std::vector<T*> elemArray;

  for (size_t i = 0; i < elemArray.size(); ++i)
  {
    elemArray = new T();
  }

The code has obviously been simplified. Now after asking another question (unrelated to this problem but related to the program) I realized I need an array that has new'd objects (can't be on the stack, will overflow, too many elements) but are contiguous. That is, if I were to receive an element, without the array index, I should be able to find the array index by doing returnedElement - elemArray[0] to get the index of the element in the array.

I hope I have explained the problem, if not, please let me know which parts and I will attempt to clarify.

EDIT: I am not sure why the highest voted answer is not being looked into. I have tried this many times. If I try allocating a vector like that with more than 100,000 (approximately) elements, it always gives me a memory error. Secondly, I require pointers, as is clear from my example. Changing it suddenly to not be pointers will require a large amount of code re-write (although I am willing to do that, but it still does not address the issue that allocating vectors like that with a few million elements does not work.

Answer 1

A std::vector<> stores its elements in a heap allocated array, it won't store the elements on the stack. So you won't get any stack overflow even if you do it the simple way:

std::vector<T> elemArray;
for (size_t i = 0; i < elemCount; ++i) {
   elemArray.push_back(T(i));
}

&elemArray[0] will be a pointer to a (continuous) array of T objects.

Answer 2

If you need the elements to be contiguous, not the pointers, you can just do:

std::vector<T> elemArray(numberOfElements);

The elements themselves won't be on the stack, vector manages the dynamic allocation of memory and as in your example the elements will be value-initialized. (Strictly, copy-initialized from a value-initialized temporary but this should work out the same for objects that it is valid to store in a vector.)

I believe that your index calculation should be: &returnedElement - &elemArray[0] and this will work with a vector. Provided that returnedElement is actually stored in elemArray.

Answer 3

While I also have the same requirements but for a different reason, mainly for being cache hot...(for small number of objects)

    int maxelements = 100000;

    T *obj = new T [100000];        

    vector<T *> vectorofptr;

    for (int i = 0; i < maxelements; i++)
    {
        vectorofptr.push_back(&obj[i]);
    }

or

    int sz = sizeof(T);
    int maxelements = 100000;

    void *base = calloc(maxelements, sz); //need to save base for free()

    vector<T *> vectorofptr;
    int offset = 0;

    for (int i = 0; i < maxelements; i++)
    {
        vectorofptr.push_back((T *) base + offset);
        offset += sz;
    }

Answer 4

Your original loop should look something like this: (though it doesn't create objects in contiguous memory).

for (size_t i = 0; i < someSize ; ++i)
{
    elemArray.push_back(new T());
}

And then you should know two basic things here:

• elemArray.size() returns the number of elements elemArray currently holds. That means, if you use it in the for loop's condition, then your for loop would become an infinite loop, because you're adding elements to it, and so the vector's size would keep on increasing.
• elemArray is a vector of T*, so you can store only T*, and to populate it, you've to use push_back function.

Answer 5

Considering your old code caused a stack overflow I think it probably looked like this:

Item items[2000000]; // stack overflow

If that is the case, then you can use the following syntax:

std::vector<Item> items(2000000);

This will allocate (and construct) the items contiguously on the heap.

Answer 6

I know this is an old post but it might be useful intel for any who might need it at some point. Storing pointers in a sequence container is perfectly fine only if you have in mind a few important caveats:

• the objects your stored pointers point to won't be contiguously aligned in memory since they were allocated (dynamically or not) elsewhere in your program, you will end up with a contiguous array of pointers pointing to data likely scattered across memory.

• since STL containers work with value copy and not reference copy, your container won't take ownership of allocated data and thus will only delete the pointer objects on destruction and not the objects they point to. This is fine when those objects were not dynamically allocated, otherwise you will need to provide a release mechanism elsewhere on the pointed objects like simply looping through your pointers and delete them individually or using shared pointers which will do the job for you when required ;-)

• one last but very important thing to remember is that if your container is to be used in a dynamic environment with possible insertions and deletions at random places, you need to make sure to use a stable container so your iterators/pointers to stored elements remain valid after such operations otherwise you will end up with undesirable side effects... This is the case with std::vector which will release and reallocate extra space when inserting new elements and then perform a copy of the shifted elements (unless you insert at the end), thus invalidating element pointers/iterators (some implementations provide stability though, like boost::stable_vector, but the penalty here is that you lose the contiguous property of the container, magic does not exist when programming, life is unfair right? ;-))

Regards

Answer 7

Allocate a large chunk of memory and use placement new to construct your vector elements in it:

elemArray[i] = new (GetNextContinuousAddress()) T(); 

(assuming that you really need pointer to indidually new'ed objects in your array and are aware of the reasons why this is not recommended ..)