Using malloc and free in C++

Pages: 12
Hello all,

I'm working on an exercise that says I should using the following My_allocator class design my own vector.
It's this:

1
2
3
4
5
6
7
8
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
};


I know what T* allocate(int n) and void construct(T* p, const T& v) mean but I don't know what void destroy(T* p) and void deallocate(T* p, int n) should do exactly.

According to what I understood by reading their comments (the // parts) I wrote the following code named test:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <iostream>
#include <vector>
#include <stdlib.h>
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)
{
	for (int i = 0; i < n; ++i) 
		free(&p[i]);
}

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

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

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

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

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

class Range_error : out_of_range {
public:
	int index;
	Range_error(int i) :out_of_range("Range error"), index(i) {}
};

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

template <class T, class A = My_allocator<T> >
class Vector : public vector<T> {
	A alloc;
	int sz, space;
	T* elem;
public:
	Vector(int n) :vector<T>(n), sz(n), space(n) { elem = alloc.allocate(n); }

	int  my_size() { return sz; } 
	void my_push_back(const T&);
	void my_reserve(int);

	T& operator[](unsigned int n) // rather than return at(i);
	{
		if (n < 0 || this->sz <= n) throw Range_error(n);
		return elem[n];
	}
};

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

template <class T, class A>
void Vector<T, A>::my_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;
}

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

template <class T, class A>
void Vector<T, A>::my_push_back(const T& val)
{
	if (space == 0) my_reserve(8);
	else if (sz == space) my_reserve(2 * space);
	alloc.construct(&elem[sz], val);
	++sz;
}

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


int main() {
	Vector<int> v1(4);
	for (int i = 0; i < v1.my_size(); ++i)
		v1[i] = i + 3;

	v1.my_push_back(12);
	return 0;
}


But when running, I get the error below in free(&p[i]); (line 30).
test.exe has triggered a breakpoint.

Would anybody please guide me?
Last edited on
Please edit your post and use code tags to make it more readable. You have 240+ posts, you should not this already - http://www.cplusplus.com/articles/jEywvCM9/

Using malloc and free in C++
malloc and free is C, not c++. new and delete is c++ - http://www.cplusplus.com/doc/tutorial/dynamic/

Althought it is very much recommended to not use them, and instead use smart pointers, but for exercise it's perfectly fine :)
Last edited on
Thank you TarikNeaj.
There is a problem with the website on using tags when creating a new topic. So I write the comment (Please wait for a min so that I put some tags!) at the top of the posts I create. Then I edit the post and add some good tags!
This routine was exactly what I did for this thread too!
Last edited on
It looks like deallocate should just free the space that allocate() created. So it's simply free(p); construct() needs to call the copy constructor using placement new:
http://stackoverflow.com/questions/222557/what-uses-are-there-for-placement-new destroy() needs to call the destructor on the items. This can be called directory:
p->~T(); // explicitly destroy p.
Last edited on
Thank you very much for your reply.

On using malloc and free, I had to use them because it was an exercise! When I read the chapter and looked at the exercise, I couldn't completely figure out what the exercise really wants me to do. But I tried my best to do the wanted work! I made some screenshots of the related pages from that book which is of the issue and combine them into a single PDF file uploaded on the link below:
PS: The book is Programming Principle and Practice Using C++ by Stroustrup, first edition, first printing.
http://www.4shared.com/folder/psJrUYkm/_online.html

What you said (in the above post) is right, I agree. Thanks again. And I tried to look up for "replacement new" and "explicit destroying". I obtained some info. :-)

Then I made changes in my code. The changed part is only on the class My_allocator, which is as follows:
I also added ~Vector<T, A>() { delete[] elem; } to the class Vector : public vector<T>.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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)
{
	if (T* p = (T*)malloc(sizeof(T)*n))
		return p;
	else throw Range_error(n);
}

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

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);  //My assumption on applying "new replacement" here
}

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

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

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


Now I have two questions:
1- Have I correctly understood the exercise (exercise #8 in the PDF file) please?
2- Have I correctly done it please?

PS: Now the code runs successfully.
> I also added ~Vector<T, A>() { delete[] elem; }
that's the allocator job.
Also
new -> delete

new[] -> delete[]

malloc() -> free()
don't mix them


> class Vector : public vector<T>
That's a terrible idea.
The operations of std::vector would not work with your member variables and will likely break invariances.
Last edited on
Thank you very much for your reply.

> I also added ~Vector<T, A>() { delete[] elem; }
that's the allocator job.
I don't understand you. Do you mean I should have added ~My_allocator<T>() inside the class My_allocator please?


Also
new -> delete

new[] -> delete[]

malloc() -> free()
don't mix them
And by this, I think you meant that I should use the code ~My_allocator<T>() { free(this); }, yes?

> class Vector : public vector<T>
That's a terrible idea.
Maybe, but it's the author that has set such a class in his book and I have to solve the exercise.


The operations of std::vector would not work with your member variables and will likely break invariances.
But public functions of std::vector are accessible for the members and objects of the class Vector, because they have been inherited.
Last edited on
The allocator is responsible for the memory management. So the allocator should destroy the elements and deallocate the space.

> free(this);
don't kill yourself (yet)
You wrote delete[] elem;. `elem' is not pointing to memory allocated with new[], but with malloc().

> it's the author that has set such a class in his book
in the pdf that you linked, `Vector' doesn't add a data buffer.

> But public functions of std::vector are accessible
and those functions are useless for you.
they do not refer to you `elem' pointer, but to another data buffer (_M_start)
¿what benefit do you think you get from that inheritance?
Thank you for your explanations. I know that you are trying to help me and I appreciate you because of that, but I'm confused.
Please just answer this question: What code would you wrote for the exercise 8 please?
Let's take a step back. Why do we need an allocator in the first place? If you want to make a vector with space for 10 items, why not just define the constructor list this?
1
2
3
4
5
Vector(int n) :
   sz(0),   // zero items in the vector
   space(n),   // room for n elements
   elem(new T[n]) // allocate space for n elements
   {}

The reason is that this code will actually construct 10 element (because we initialized elem with new T[n]. We want to reserve space for 10 elements but we don't want to construct any in that space (yet).

So what does this mean? It means that at any given time:
- elem points to memory that room to hold space elements
- The first sz*sizeof(T) bytes in that space contain sz valid, constructed T's.
- the remaining bytes contain nothing.

Managing this memory is whole purpose of the allocator. It lets you allocate and deallocate space independently of constructing and destroying the elements.

Now let's return to the destructor. When you destroy the Vector you need to do 2 things:
- destroy (i.e., call the destructor on) the first sz items in elem.
- deallocate the entire elem block of memory.

Class Vector : public vector<T> {
Your Vector template is meant to mimic std::vector, not to extend it. As ne555 pointed out, if you access the members of std::vector, you won't get what you expect because those members will be using the internal data (vector space, size, capacity etc) of std::vector, not your data.
And by this, I think you meant that I should use the code ~My_allocator<T>() { free(this); }, yes?

No. Since My_allocator doesn't have any data members, there's no need for the destructor to do anything. ne555 just means to allocate and deallocate memory with matching functions. In this case, I think you have it right. You are allocating/deallocating memory with malloc/free. You are using new to construct objects, not to allocate memory.
void Vector<T, A>::my_reserve(int newalloc)
newalloc should be unsigned since it makes no sense to allocate negative space. Also, what if the newalloc is smaller than the current number of items? You should handle this case.

I hope this helps.
OK dear dhayden, so let's have a total overview:

1- There is an exercise for which I'm trying to write a correct code. That exercise (#8) exists in the uploaded PDF by the link.
As it wanted us, we should implement an allocator (19.3.6) using the basic allocation functions malloc() and free(). And as you already pointed out correctly, the author meant using "replacement new" and "explicit destroying" to be used in solving that exercise. So I implemented an allocator named My_allocator and used malloc() and free() there. Just like my above (My_allocator class) code. So I have to use My_allocator and malloc() and free() because it is an exercise not an arbitrarily program.

2- I agree that using the the std::vector may not have a useful outcome. Because of that, I haven't used them. I added a My_ prefix to the used functions (like My_size() and etc) to use my own functions in Vector<T, A>.

3- And about the exercise: to me, it's vague, at least for me. And also it's somewhat absurd (to use a, for example, Vector class that inherits from std::vector but doesn't use any of the std::vector's public members). But it was up to the author what exercise he offer. Look at the 19.4 please.

By now, I think if I replace the My_allocator class in my first post of this thread with the one I offered later (after your pointing to the replacement new and explicit destruction) the code is fine and acceptable. Do you disagree?


> I added a My_ prefix to the used functions
> for example, Vector class that inherits from std::vector but doesn't use any
> of the std::vector's public members
you have defined those functions
you weren't supposed to modify vector. Simply define it as vector<T, My_allocator<T> > and test it.


It is weird that a bad allocation throws a `Range_error', other than that it looks fine. Test it.
Thank you very much.
I appreciate all helps of all of you guys.
Please post your latest code (both for My_allocator and Vector) so we can look it over.

By the way, I think it's great that you're doing this assignment. I've seen lots of "implement a vector" assignments on this forum and this is the only one time someone has handled the construction/destruction properly.
Thank you for your interest.
This code is is assigned for the exercise 8 of that book. If the intention was to implement one better, we could.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include <iostream>
#include <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();
}

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

class Range_error : out_of_range {
public:
	int index;
	Range_error(int i) :out_of_range("Range error"), index(i) {}
};

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

template <class T, class A = My_allocator<T> >
class Vector : public vector<T> {
	A alloc;
	int sz, space;
	T* elem;
public:
	Vector() :vector<T>(), sz(0), space(0), elem(nullptr) {}
	Vector(int n) :vector<T>(n), sz(n), space(n) { elem = alloc.allocate(n); }
	Vector(int n, const T& v) :vector<T>(n, v) sz(n), space(n) { elem = alloc.allocate(n); }

	int my_size() const { return sz; }
	int my_capacity() const { return space; }
	T get_elem(int i) { return elem[i]; }

	void my_resize(int, T);
	void my_push_back(const T&);
	void my_reserve(int);

	T& operator[](unsigned int n) // rather than return at(i);
	{
		if (n < 0 || this->sz <= n) throw Range_error(n);
		return elem[n];
	}

	const T& operator[](unsigned int n) const
	{
		if (n < 0 || this->sz <= n) throw Range_error(n);
		return elem[n];
	}
};

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

template <class T, class A>
void Vector<T, A>::my_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;
}

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

template <class T, class A>
void Vector<T, A>::my_push_back(const T& val)
{
	if (space == 0) my_reserve(8);
	else if (sz == space) my_reserve(2 * space);
	alloc.construct(&elem[sz], val);
	++sz;
}

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

template <class T, class A>
void Vector<T, A>::my_resize(int newsize, T val = T())
{
	my_reserve(newsize);
	for (int i = sz; i < newsize; ++i) alloc.construct(&elem[i], val);  // construct
	for (int i = newsize; i < sz; ++i) alloc.destroy(&elem[i]);  // destroy
	sz = newsize;
}

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

int main() {
	Vector<int> v(4);
	for (int i = 0; i < v.my_size(); ++i)
		v[i] = i + 3;

	v.my_push_back(12);
	
	for (int i = 0; i < v.my_size(); ++i)
		cout << "'" << v[i] << "'" << "  ";

	v.my_reserve(10);
	
	for (int i = 0; i < v.my_size(); ++i)
		cout << "'" << v[i] << "'" << "  ";
	
	v.my_resize(12, 5);
	
	for (int i = 0; i < v.my_size(); ++i)
		cout << "'" << v[i] << "'" << "  ";

	
	return 0;
}
Thanks for posting it.

You're still deriving Vector from std::vector. You should not do that. When removing this, change the my_XYZ method names to XYZ. E.g., change my_reserve() to reserve()

Other than that, the code looks great. I particularly like your implementation of resize() which is short and elegant.
Thank you dear dhayden for your kind words. I appreciate you.


You're still deriving Vector from std::vector. You should not do that. When removing this, change the my_XYZ method names to XYZ. E.g., change my_reserve() to reserve()

Yes, you are right. But please bear in mind that, this code is an answer to the exercise and I should obey the conditions told in the context of the exercise. :-)
It says I should derive from std::vector, otherwise I'd write that code in a more simple and nice way. :-)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template <class T, class A = My_allocator<T> >
class Vector : public vector<T, A> {
private:
   /* nothing */
public:
//constructors (simply forwarding)
	Vector() :{}
	Vector(int n) :vector<T>(n) {}
	Vector(int n, const T& v) :vector<T>(n, v){}
//accesor
   T& operator[](unsigned int n){
      if( n<0 or this->size()<=n ) throw Range_error(n);
      return vector<T>::operator[](n);
   }
   const T& operator[](unsigned int n) const{
      if( n<0 or this->size()<=n ) throw Range_error(n);
      return vector<T>::operator[](n);
   }
/* done, don't add anything else */
};
¿does this work for you?
Last edited on
It says I should derive from std::vector,

I can't seem to find that stated anywhere.

The question that I read said only,
8. Implement an allocator (§19.3.6) using the basic allocation functions malloc() and free() ( §B.10.4 ). Get vector as defined by the end of §19.4 to work for a few simple test cases.


19.4 refers to an ongoing vector class being developed during the course of the previous sections. None of the code I looked at is deriving from std::vector. In 19.3.6 it refers to mirroring the standard library vector, but that is something quite different.

I suppose the context is set at the beginning of chapter 17,
In this and the following two chapters, we show how to build vector from the basic language facilities available to every programmer. Doing so allows us to illustrate useful concepts and programming techniques, and to see how they are expressed using C++ language features. The language facilities and programming techniques we encounter in the vector implementation are generally useful and very widely used.



Last edited on
ne555 wrote:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template <class T, class A = My_allocator<T> >
class Vector : public vector<T, A> {
private:
   /* nothing */
public:
//constructors (simply forwarding)
	Vector() :{}
	Vector(int n) :vector<T>(n) {}
	Vector(int n, const T& v) :vector<T>(n, v){}
//accesor
   T& operator[](unsigned int n){
      if( n<0 or this->size()<=n ) throw Range_error(n);
      return vector<T>::operator[](n);
   }
   const T& operator[](unsigned int n) const{
      if( n<0 or this->size()<=n ) throw Range_error(n);
      return vector<T>::operator[](n);
   }
/* done, don't add anything else */
};

¿does this work for you?




Honestly, I'd thought about it before.
We need some functions to change the values of sz and space in the std::vector, in this way. (because we are using std::vector's operator[])
I searched the web much for finding functions that have access to the private members of the std::vector, but couldn't find.




Pages: 12