Writing this is like a compulsive need to understand wht the heck is all about Allocators in c++. I see these whenever I check a process core dump with vectors, maps etc , and they make the complete stack look so scary. And also not to mention the compilation errors. You do some teeny weeny mistake in vector or map or some crazy stl declaration and bammm the compilation error scares the hell out of you, and you wonder where did I declare with those allocators n all.
Here I will try to get over my fears and try to understand properly what are these things. And not embarrass my self because of the fact that being a 3.5 years experienced c++ programmer c++ allocators have eluded me for a long, and will now make an attempt to do it along with explaining to you guys.
The definition as understood by me is that an allocator is a class that handles the allocation/de-allocation of various STL, especially containers. For example take vector, its just a linked list. Whenever we call push_back() on a vector object, it has to allocate some memory for the entry and attache it to the existing linked list. This allocation of memory is hidden to us and is handled by a class specifically designed for the purpose i.e the allocator.
Now what is the functionality that we are looking for in the Allocator class
1. Allocation/Deallocation
2. Hopefully Thats it...
Lets take it forward and try to implement an allocator.
#include <iostream>
#include <vector>
using namespace std;
template<typename T>
class Allocator
{
public:
typedef T value_type;
typedef value_type* pointer;
public:
inline explicit Allocator()
{
cout << "Constructor of Allocator\n";
}
inline ~Allocator()
{
cout << "destructor of Allocator\n";
}
inline explicit Allocator(Allocator const&) {}
};
int main()
{
vector<int, Allocator<int> > vec;
}
Guess what when I compiled I got a really long list of errors. Probably these compilation errors will help us understand Allocators better. So, here is the listing.
/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h: In instantiation of `std::vector<int, Allocator<int> >':
test_allocator.cxx:29: instantiated from here
/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:152: error: no type named `const_pointer' in `class Allocator<int>'
/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:153: error: no type named `reference' in `class Allocator<int>'
/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:154: error: no type named `const_reference' in `class Allocator<int>'
/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:157: error: no type named `const_pointer' in `class Allocator<int>'
/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:158: error: no type named `const_pointer' in `class Allocator<int>'
/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:322: error: no type named `const_pointer' in `class Allocator<int>'
/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:338: error: no type named `const_pointer' in `class Allocator<int>'
/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:354: error: no type named `const_pointer' in `class Allocator<int>'
/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:370: error: no type named `const_pointer' in `class Allocator<int>'
/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:462: error: no type named `reference' in `class Allocator<int>'
/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:476: error: no type named `const_reference' in `class Allocator<int>'
/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:500: error: no type named `reference' in `class Allocator<int>'
/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:514: error: no type named `const_reference' in `class Allocator<int>'
/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:521: error: no type named `reference' in `class Allocator<int>'
/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:528: error: no type named `const_reference' in `class Allocator<int>'
/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:535: error: no type named `reference' in `class Allocator<int>'
/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:542: error: no type named `const_reference' in `class Allocator<int>'
test_allocator.cxx: In function `int main()':
test_allocator.cxx:29: error: no matching function for call to `Allocator<int>::Allocator(Allocator<int>)'
/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:182: error: in passing argument 1 of `std::vector<_Tp, _Alloc>::vector(const typename std::_Vector_base<_Tp, _Alloc>::allocator_type&) [with _Tp = int, _Alloc = Allocator<int>]'
/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h: In member function `void std::_Vector_base<_Tp, _Alloc>::_M_deallocate(_Tp*, size_t) [with _Tp = int, _Alloc = Allocator<int>]':
/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:106: instantiated from `std::_Vector_base<_Tp, _Alloc>::~_Vector_base() [with _Tp = int, _Alloc = Allocator<int>]'
/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:182: instantiated from `std::vector<_Tp, _Alloc>::vector(const typename std::_Vector_base<_Tp, _Alloc>::allocator_type&) [with _Tp = int, _Alloc = Allocator<int>]'
test_allocator.cxx:29: instantiated from here
/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:117: error: 'struct std::_Vector_base<int, Allocator<int> >::_Vector_impl' has no member named 'deallocate'
So, you can see there are various declarations/definitions missing in the allocator class. I hate to tell this, but its a fact that allocators follow some C++ standards guideline as per how the class should look like.
(ISO C++ standard, section 20.4.1)
And it looks like the following. I have provided brief description next to each declaration.
//Template definition for allocator as it will be used to allocate
// any pointer type
template <class T> class allocator {
public:
//Set of typedefs to be used in various
//methods for allocation/deallocation/construction
// destruction etc.
typedef size_t size_type;
//Unsigned integral value that can represent the difference between two pointers
typedef ptrdiff_t difference_type;
// Pointer type for the class
typedef T* pointer;
// Const pointer type for the class
typedef const T* const_pointer;
//Reference type for the class
typedef T& reference;
//Const Reference for the class
typedef const T& const_reference;
// Value type
typedef T value_type;
//template structure, which allows any allocator might allocate memory of another type indirectly.
template <class U> struct rebind { typedef allocator<U>
other; };
allocator() throw();
allocator(const allocator&) throw();
template <class U> allocator(const allocator<U>&) throw();
~allocator() throw();
pointer address(reference x) const;
const_pointer address(const_reference x) const;
// This function will be called, whenever a new memory
// allocation is required. As in vector push_back
pointer allocate(size_type,
allocator<void>::const_pointer hint = 0);
// This function will be called when the memory location needs to be
// freed.
void deallocate(pointer p, size_type n);
size_type max_size() const throw();
// Following are required to initialize/de-initialize the allocated
// memory location.
void construct(pointer p, const T& val);
void destroy(pointer p);
};
Now after we have understood how our Allocator class should look like, lets put some life into this class. Lets make it usable by defining atleast allocate/deallocate functions.
Here is how I have defined it in my test program.
pointer allocator::allocate(size_type sz, std::allocator<void>::const_pointer hint = 0)
{
cout << "Allocating\n";
char* ch = (char*)malloc(sizeof(sz));
return (pointer)(ch);
}
void allocator::deallocate(pointer p, size_type n)
{
cout << "De-Allocating\n";
free(p);
}
Now lets see, how does it work in real use.
int main()
{
vector<int> myVector;
myVector.push_back(1);
}
On compiling and running the program following out put is obtained.
Allocating
De-Allocating
At this point atleast we are aware of some internals of allocators, and we know "wht the hell allocators are" . Going further we can define our pool of memory and allocate from that pool and handle all allocations/deallocations in that chunk of memory using our own creative memory management algorithm.
I hope I will cover that advanced topic some other day , till then cya .....
