Using the class allocate for implementing a vector

[Frank14]

Hello,

The case belongs to the chapter 19 of the book "Programming Principles And Practice Using C++ 2nd Edition May 2014", section 19.3.7. Here is three parts of that section (1, 2, 3): https://postimg.org/gallery/2tkekelie/

And here is also the code for that allocator class that I'd previously used in the vector:

#include <iostream>
#define vector Vector
using namespace std;

template <class T> class My_allocator {
public:

	T* allocate(int n);  // allocate space for n objects of type T
	void deallocate(T* p, int n);  // deallocate n objects of type T starting at p

	void construct(T* p, const T& v);  // construct a T with the value v in p
	void destroy(T* p);  //  destroy the T in p
};

//-------------------------------------------------

template<class T>
T* My_allocator<T>::allocate(int n)
{
	T* p = (T*)malloc(sizeof(T)*n);
	return p;

}

//------------------------------

template<class T>
void My_allocator<T>::deallocate(T* p, int n)
{
	free(p);
}

//------------------------------

template<class T>
void My_allocator<T>::construct(T* p, const T& v)
{
	p = new (p) T(v);
}

//------------------------------

template<class T>
void My_allocator<T>::destroy(T* p)
{
	p->~T();
}

This is the function reserve that uses that allocator:

template <class T, class A>
void pvector<T, A>::reserve(int newalloc)
{
	if (newalloc <= space) return;
	T* p = alloc.allocate(newalloc);
	for (int i = 0; i < sz; ++i) alloc.construct(&p[i], elem[i]);
	for (int i = 0; i < sz; ++i) alloc.destroy(&elem[i]);
	alloc.deallocate(elem, space);
	elem = p;
	space = newalloc;
}

I read the section 19.3.7 three times but couldn't understand it the way I liked and have questions in mind:

1- Why do we need that allocator class? I know it's for types that haven't a default value but Why can't we just use new instead of that allocator class? Both new and malloc get an amount of memory from the main memory.

2- What are those types that haven't a default value?

3- In the function allocate(int n) the code T* p = (T*)malloc(sizeof(T)*n); I think means: Get an amount of memory of size T, multiplied by n, and convert it to a "pointer to T" then assign it to p. Right?
Then what is the meaning of the line below in the construct(T* p, const T& v); function?

p = new (p) T(v);

[Duthomhas]

1. Sometimes you have special memory requirements, where you want to keep something in a special place, or you want to do something like keep track of how memory is used, etc. Allocators allow you to hook the memory management for that particular class:

    typedef std::vector <int, myallocator> super_special_vector;

2. It is not clear what you are asking. Are you asking about a specific piece of the code above? Or about how default values are generated?

3. Yes. The allocate/deallocate handle memory for use by the object. The construct/destroy handle using that memory for the object.

In other words, there are two parts to creating a dynamic object: getting memory for it, then constructing it over that memory space. Likewise, when you delete an object, it must first be destroyed (destructed) and then the memory gets released back into the memory pool.

Hope this helps.

[coder777]

I know it's for types that haven't a default value but Why can't we just use new instead of that allocator class?

No, it doesn't have anything to do with default values. new allocates memory and calls the constructor. For a container it is desirable to allocate the memory for several objects beforehand. Later, when the user actually want to create the object, only the constructor is called on the precreated memory.

[Frank14]

Thank you both. I understood most of your answers but still can't figure the stuff out well!

Sometimes you have special memory requirements, where you want to keep something in a special place, or you want to do something like keep track of how memory is used, etc. Allocators allow you to hook the memory management for that particular class

What special memory requirements? What place? We just need some memory (some bytes of the memory which is free/raw) for using.
I think both malloc and new hook memory from heap.
new, too, gives us some bytes of that memory for us to use it the way we like.

By 2, I meant types like, int, double, char and so on. These seems to have default values, I meant, so what other types don't have default values?

By 3 I meant: What does this code do:
p = new (p) T(v);
I know it tries to construct a T with the value v in p. I meant you to explain the syntax or the code.


And the final question, why can't we use new rather than malloc? Doesn't new have any advantages? I think of memory as a store of raw places.

[mbozzi]

What special memory requirements?

Maybe you want to allocate from a memory pool - i.e., out of a 1GiB pre-allocated block, like many games, or dynamically from the stack. Maybe you must place a object at exactly a particular memory location (i.e., overlaying a MMIO register in an embedded processor). Maybe you're allocating memory from external storage, for lack of space in main memory.

For each of those cases, plain new or malloc won't suffice.

what other types don't have default values?

Any type which is not default-constructible, e.g. class A { A(int) {} };. Try declaring an array of those. But you can create a vector of those, because of allocators.

p = new (p) T(v);
Besides what you already know,
"Constructs a new T, initialized with the value v, at the location referred to by p"
I don't know what else to say - the feature is called placement new.
http://en.cppreference.com/w/cpp/language/new

Doesn't new have any advantages?

It calls the constructor. If you wanted, you could allocate an array of unsigned char, and use the result similarly to the result of std::malloc.

[JLBorges]

> What special memory requirements? What place?
> We just need some memory (some bytes of the memory which is free/raw) for using.

The default memory allocation in C++ is allocation of memory from the heap via operator new ...
Conceivable non-default memory management schemes include use of pre-allocated memory pools, thread-specific memory, memory shared among processes, garbage-collected memory, persistent stores, etc.
https://www.angelikalanger.com/Articles/C++Report/Allocators/Allocators.html

A example of a simple allocator (which does not use alternative pointer/reference types):
http://www.boost.org/doc/libs/1_65_0/libs/pool/doc/html/boost_pool/pool/interfaces.html#boost_pool.pool.interfaces.interfaces.pool_allocator


> so what other types don't have default values?

Any type that is not DefaultConstructible; for example a class type which has a user-defined constructor which requires one or more arguments, but does not have a user-declared default constructor.


> What does this code do: p = new (p) T(v);

See: https://en.wikipedia.org/wiki/Placement_syntax


> why can't we use new rather than malloc?

In addition to allocating memory, new T would construct an object of type T in the allocated storage.
See: 'What is the difference between new and malloc()?' https://isocpp.org/wiki/faq/freestore-mgmt

Note: we could use ptr = std::operator new (sz) and std::operator delete (ptr) instead of malloc/free to allocate and release raw uninitialised memory.

[Frank14]

Maybe you want to allocate from a memory pool - i.e., out of a 1GiB pre-allocated block, like many games, or dynamically from the stack. Maybe you must place a object at exactly a particular memory location (i.e., overlaying a MMIO register in an embedded processor). Maybe you're allocating memory from external storage, for lack of space in main memory.

Good info, thanks.

For each of those cases, plain new or malloc won't suffice.

Well, here, you toy with the both as some thing with the same level of efficiency or capability that won't suffice for those specific requirements.
So here both result in the same, so I can use new instead of malloc!!
What possibilities malloc can give us, in this case (the program), while new can't?

I don't know what else to say

Thanks. It's fine, I got it. :-)


Incidentally, I'm thinking of them as if: new can get/hook some part of "a memory" and also it can initialize it, but malloc can only get/hook that some part of memory and needs new for initializing. I'm not sure whether it's correct.

It calls the constructor

The constructor of the type T?

[mbozzi]

The constructor of the type T?

Yes.

So here both result in the same, so I can use new instead of malloc!!

In your case, the point of the exercise is to understand allocators. So in this case, you're right -- you could very well use new instead of malloc, as long as you were careful to not cause any inappropriate side effects (calling constructors, e.g.).

For the purposes of obtaining a block of memory from the free store with size n bytes, both

void* p1 = std::malloc(n); // and
void* p2 = new unsigned char[n];

are probably acceptable. At a high level, they both do mostly the same thing, except that new can throw an exception (if you don't also pass std::nothrow).

This is okay because unsigned char is trivially constructible: no constructor runs because unsigned char is not a class type. Further, each char (whether char, signed char or unsigned char) is exactly one byte in size.

You could then proceed to construct a new T at p1 or p2 using the placement-new syntax, assuming that sizeof (T) <= n.

[Frank14]

JLBorges (10038)

In addition to allocating memory, new T would construct an object of type T in the allocated storage.

1- We have allocation and initialization. I think initialization has the same meaning as construction.

2- The only difference is that I see is that, new is a typed way of allocating memory while malloc is non-typed. new also gets memory based on its type and malloc based on the number of bytes. So malloc is really raw, simple and free compared to new.

3- And in my code the class My_allocator is useless and I could use new perfectly and easily instead of that and the result would have no difference with using malloc. So I think by this code sniped, the author has just wanted us to be familiar with malloc.
I also would like to be familiar with make_unique and use it instead of the both in the code.

4- In the reserve(int newalloc) function in line 5 above, we have: T* p = alloc.allocate(newalloc);. Here the memory is hooked. In line 6, there is: alloc.construct(&p[i], elem[i]);. And in the alloc.construct we have new that "again hooks memory" of that size (T) which was hooked by malloc beforehand!! Couldn't it use *p = v; ?

Disagree with any of 1, 2 or 3?

[JLBorges]

> 1- We have allocation and initialization. I think initialization has the same meaning as construction.

Yes.


> 2- The only difference is that I see is that, new is a typed way of allocating memory while malloc is non-typed.

It is best if we recognise the distinction between:
a. create an object with dynamic storage duration - new expression: A* p = new A( /* ... */ )
b. allocate raw storage which can be used later - malloc, operator new: void* p = ::operator new( sizeof(A) ) ;


> So I think by this code sniped, the author has just wanted us to be familiar with malloc.

The author wanted us to be familiar with the concept of first allocating raw storage and subsequently constructing objects in the storage which was allocated earlier.


> Couldn't it use *p = v;

After T* p = alloc.allocate(newalloc);, the pointer p points to uninitialised raw storage. That its type is 'pointer to T' is merely for convenience; because we know that we will eventually construct an object of type T there.

*p = v; without constructing the object first is wrong, because we are trying to assign to an object which does not exist. Think of:
construction: initialise raw storage so that there is an object (create an object)
assignment: modify the state of an already existing object (the object must have been constructed earlier).

[Frank14]

construction: initialise raw storage so that there is an object (create an object)

If you mean new by that, well, we will have an extra memory hooking by new, here.

assignment: modify the state of an already existing object (the object must have been constructed earlier).

What if we have meant (or interpret it) the copy constructor for this and not copy assignment?

T* p = alloc.allocate(newalloc); creates a pointer, p, to an object of type T. Consider we have declared an int or double vector, so p will be a pointer to an int/double.
Afterwards, we initilise that pointer with a value. It looks straightforward.


It seems that initialisation of an object is the same as construction of that object only if that initialisation/construction is done by new.

[JLBorges]

> If you mean new by that, well, we will have an extra memory hooking by new, here.

Not necessarily. Constructing an object without also allocating memory for it is the raison d'être for placement new.


> What if we have meant (or interpret it) the copy constructor for this and not copy assignment?

To copy construct or move construct an object into already allocated storage, where pmem points to the raw memory: A* pa = new (pmem) A( A_to_be_copied ) ;


> It seems that initialisation of an object is the same as construction of that object
> only if that initialisation/construction is done by new.

This is true only for objects with dynamic storage duration.

#include <iostream>
#include <string>
#include <cstring>
#include <new>

struct A
{
    A( std::string name ) { str += name ; std::cout << "A::constructor\n" ; }

    A( const A& that ) : str(that.str) { std::cout << "A::copy_constructor\n" ; }
    A( A&& that ) noexcept : str( std::move(that.str) )
    { std::cout << "A::move_constructor\n" ; }

    A& operator= ( const A& that )
    { str = that.str ; std::cout << "A::copy_assignment\n" ; return *this ; }
    A& operator= ( A&& that ) noexcept
    { str = std::move(that.str) ; std::cout << "A::move_assignment\n" ; return *this ; }

    ~A() noexcept { std::cout << "A::destructor\n" ; }

    std::string str = "the name of this object is: " ;
};

int main()
{
    // raw uninitialised memory
    void* buffer = ::operator new( sizeof(A) ) ;
    std::memset( buffer, 255, sizeof(A) ) ; // fill the buffer with junk

    A* pa = static_cast<A*>(buffer) ; // at this point, pa does not point to an object of type A
                                      // no object has been constructed

    // what we now have is raw memory sufficient to hold an object of type A.
    // uncomment either of the following lines to engender undefined behaviour
    // *pa = A( "yet another" ) ; // *** undefined behaviour (assign to non-existent object)
    // std::cout << pa->str << '\n' ; // *** undefined behaviour (access member of non-existent object)

    // construct an A in the memory already available
    pa = new (pa) A( "abcdefgh" ) ;

    std::cout << pa->str << '\n' ; // access the object

    pa->~A() ; // destroy the object

    // ------------------------------------

    {
        A other( "other" ) ; // construct an object with automatic storage duration

        // copy construct an A in the memory already available
        pa = new (pa) A(other) ;

        // construct an anonymous temporary and
        *pa = A( "yet another" ) ; // move assign to the already constructed object
        // lime time of the anonymous temporary is over, destroy it

        pa->~A() ; // destroy the object

        // life-time of 'other' is over; destroy that too
    }

    // what we now have left is raw memory sufficient to hold an object of type A.
    // uncomment either of the following lines to engender undefined behaviour
    // *pa = A( "yet another" ) ; // *** undefined behaviour (assign to non-existent object)
    // std::cout << pa->str << '\n' ; // *** undefined behaviour (access member of non-existent object)

    ::operator delete(pa) ; // release the raw memory
}

[Frank14]

Thank you.