How does an allocator create and destroy an array?

Question

How does an allocator create and destroy and array, for example

int* someInt = someAllocator(3);

Where without the allocator it would just be

int* someInt = new int[3];

Where the allocator is responsible for create each element and ensuring the constructor will be called.

How is the internals for an allocator written without the use of new? Could someone provide and example of the function?

I do not want to just use std::vector as I am trying to learn how an allocator will create an array.

Isn't this about the same as your previous question http://stackoverflow.com/questions/10220846/how-to-create-an-array-while-potentially-using-placement-new — Mark B, Apr 19 '12 at 18:55
@MarkB: I thought they might done differently and I wanted to be sure as I was curious — mmurphy, Apr 19 '12 at 21:28

score 2 · Accepted Answer · edited May 23 '17 at 12:18

2

The problem of general memory allocation is a surprisingly tricky one. Some consider it solved and some unsolvable ;) If you are interested in internals, start by taking a look at Doug Lea's malloc.

The specialized memory allocators are typically much simpler - they trade the generality (e.g. by making the size fixed) for simplicity and performance. Be careful though, using general memory allocation is usually better than a hodge-podge of special allocators in realistic programs.

Once a block of memory is allocated through the "magic" of the memory allocator, it can be initialized at container's pleasure using placement new.

--- EDIT ---

The placement new is not useful for "normal" programming - you'd only need it when implementing your own container to separate memory allocation from object construction. That being said, here is a slightly contrived example for using placement new:

#include <new> // For placement new.
#include <cassert>
#include <iostream>

class A {
public:
    A(int x) : X(x) {
        std::cout << "A" << std::endl;
    }
    ~A() {
        std::cout << "~A" << std::endl;
    }
    int X;
};

int main() {

    // Allocate a "dummy" block of memory large enough for A.
    // Here, we simply use stack, but this could be returned from some allocator.
    char memory_block[sizeof(A)];

    // Construct A in that memory using placement new.
    A* a = new(memory_block) A(33);

    // Yup, it really is constructed!
    assert(a->X == 33);

    // Destroy the object, wihout freeing the underlying memory
    // (which would be disaster in this case, since it is on stack).
    a->~A();

    return 0;

}

This prints:

A
~A

--- EDIT 2 ---

OK, here is how you do it for the array:

int main() {

    // Number of objects in the array.
    const size_t count = 3;

    // Block of memory big enough to fit 'count' objects.
    char memory_block[sizeof(A) * count];

    // To make pointer arithmetic slightly easier.
    A* arr = reinterpret_cast<A*>(memory_block);

    // Construct all 3 elements, each with different parameter.
    // We could have just as easily skipped some elements (e.g. if we
    // allocated more memory than is needed to fit the actual objects).
    for (int i = 0; i < count; ++i)
        new(arr + i) A(i * 10);

    // Yup, all of them are constructed!
    for (int i = 0; i < count; ++i) {       
        assert(arr[i].X == i * 10);
    }

    // Destroy them all, without freeing the memory.
    for (int i = 0; i < count; ++i)
        arr[i].~A();

    return 0;

}

BTW, if A had a default constructor, you could try call it on all elements like this...

new(arr) A[count];

...but this would open a can of worms you really wouldn't want to deal with.

edited May 23 '17 at 12:18

Community

1
1

answered Apr 19 '12 at 18:28

Branko Dimitrijevic

50,809
10
93
167

Could you please provide an example of how to create and initialze the array with placement new? I read there may be some dangerous with using placement new on the creation of arrays, though I might have misunderstood. – mmurphy Apr 19 '12 at 18:31
@mmurphy Ahh... I just realized you want an array and not just a single object. This should be easy enough following the same idea, but let me know if you need help on that too... – Branko Dimitrijevic Apr 19 '12 at 18:48
@mmurphy The danger is in being able to shot yourself in the foot very easily if you're not careful. For example, there is nothing preventing you from calling the constructor (or destructor) twice on the same block of memory or not calling it at all. This can lead to various forms of data corruption, which if you are unlucky will not fail immediately, but later in seemingly unrelated piece of code, making these kinds of problems hard to diagnose. Only do this if absolutely necessary, the normal constructor/destructor behavior should be plenty enough in most cases. – Branko Dimitrijevic Apr 19 '12 at 18:57
Hmm, I understand how it can be done for a single object. How would it be done for an array? – mmurphy Apr 19 '12 at 21:47
@mmurphy Simple: just **repeat** the process! Look at the edit. – Branko Dimitrijevic Apr 19 '12 at 23:32
Wouldn't `new(arr + i) A(i * 10);` call the constructor for the elements, so what would the point of `new(arr) A[count];` be? – mmurphy Apr 19 '12 at 23:58
@mmurphy `new(arr + i) A(i * 10)` calls the (non-default) constructor on a single (`i`th) element. `new(arr) A[count]` calls default constructor on multiple elements. – Branko Dimitrijevic Apr 20 '12 at 00:11
Couldn't I just call default constructor with `new(arr + i) A();` on a single (`i`th) element rather than `new(arr) A[count]`. – mmurphy Apr 20 '12 at 00:25
@mmurphy Sure, why not? I simply demonstrated that you can call a non-default constructor as well, if you wish. – Branko Dimitrijevic Apr 20 '12 at 00:35
Ah ok, I suppose since you mentioned both that it confused me. I was not sure if there was a difference between the two, other than the second seems to have a disadvantage, – mmurphy Apr 20 '12 at 02:51
I was doing one last look to make sure I understand everything, and it turns out there was something I don't. After `arr[i].~A();` why don't you do free(arr[i]). It would seem that that the memory should be freed somewhere. If not `arr[i]`, then at least `arr`. – mmurphy Apr 20 '12 at 05:36
@mmurphy Because I didn't use `malloc` to allocate it. I could have, but I chose not to for simplicity, and to make it more clear that the whole point of this exercise is to **separate** object construction and destruction from memory allocation. This is useful for a container such as `vector`, which needs to grow faster than the number of objects it contains - it will allocate a big block of memory up-front, and then construct objects **in that block** on as-needed basis. This avoids having to reallocate memory and copy all elements on each and every added element (a disaster for perf). – Branko Dimitrijevic Apr 20 '12 at 10:18

score 0 · Answer 2 · edited May 23 '17 at 10:24

0

I've written about it in my second example here:

How to create an array while potentially using placement new

The difference is that the t_allocator::t_array_record would be managed by the allocator rather than the client.

edited May 23 '17 at 10:24

Community

1
1

answered Apr 19 '12 at 18:55

justin

104,054
14
179
226

How does an allocator create and destroy an array?

2 Answers2

--- EDIT ---

--- EDIT 2 ---