This is a demonstration how to write your own allocators to be used with standard containers. This tutorial does not show the most efficient allocator implementation but rather the principles.
alloc.cpp
:
#include "alloc_new_delete.hpp"
#include "alloc_pool.hpp"
#include <vector>
#include <iostream>
template <class Allocator> void test(void)
{
{
std::vector<int, Allocator> v;
std::cout << "=========================== " << __FUNCTION__ << ":" << __LINE__ << std::endl;
v.push_back(10);
std::cout << "=========================== " << __FUNCTION__ << ":" << __LINE__ << std::endl;
v.push_back(20);
std::cout << "=========================== " << __FUNCTION__ << ":" << __LINE__ << std::endl;
v.push_back(30);
std::cout << "=========================== " << __FUNCTION__ << ":" << __LINE__ << std::endl;
v.push_back(40);
std::cout << "=========================== " << __FUNCTION__ << ":" << __LINE__ << std::endl;
v.push_back(50);
v.push_back(60);
v.push_back(70);
v.push_back(80);
}
std::cout << "=========================== " << __FUNCTION__ << ":" << __LINE__ << std::endl;
{
std::vector<int, Allocator> v;
std::cout << "=========================== " << __FUNCTION__ << ":" << __LINE__ << std::endl;
v.push_back(10);
v.push_back(20);
std::cout << "=========================== " << __FUNCTION__ << ":" << __LINE__ << std::endl;
v.erase(v.begin());
std::cout << "=========================== " << __FUNCTION__ << ":" << __LINE__ << std::endl;
}
std::cout << "=========================== " << __FUNCTION__ << ":" << __LINE__ << std::endl;
}
int main(int, char **)
{
test<alloc_new_delete<int> >();
test<alloc_pool<int, 16> >();
return 0;
}
alloc_new_delete.hpp
:
#ifndef __ALLOC_NEW_DELETE__HPP__
#define __ALLOC_NEW_DELETE__HPP__
#include <limits>
#include <cstddef>
#include <bits/allocator.h>
template <typename T> class alloc_new_delete
{
public:
typedef T value_type;
typedef value_type * pointer;
typedef const value_type * const_pointer;
typedef value_type & reference;
typedef const value_type const_reference;
typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;
public:
template <typename U> struct rebind
{
typedef alloc_new_delete<U> other;
};
public:
explicit alloc_new_delete()
{}
~alloc_new_delete()
{}
explicit alloc_new_delete(const alloc_new_delete &)
{}
template <typename U> explicit alloc_new_delete(alloc_new_delete<U> const &)
{}
public:
pointer address(reference a)
{
return &a;
}
const_pointer address(const_reference a)
{
return &a;
}
public:
pointer allocate(size_type n, typename std::allocator<void>::const_pointer = NULL)
{
return reinterpret_cast<pointer>(::operator new(n * sizeof(T)));
}
void deallocate(pointer p, size_type)
{
::operator delete(p);
}
public:
size_type max_size() const
{
return std::numeric_limits<size_type>::max() / sizeof(T);
}
public:
void construct(pointer p, const T & t)
{
new(p) T(t);
}
void destroy(pointer p)
{
p->~T();
}
public:
bool operator==(const alloc_new_delete &)
{
return true;
}
bool operator!=(const alloc_new_delete & a)
{
return !operator==(a);
}
};
#endif
alloc_pool.hpp
:
#ifndef __ALLOC_POOL__HPP__
#define __ALLOC_POOL__HPP__
#include <limits>
#include <cstddef>
#include <bits/allocator.h>
template <typename T, std::size_t N> class alloc_pool
{
private:
T data[N];
bool state[N];
public:
typedef T value_type;
typedef value_type * pointer;
typedef const value_type * const_pointer;
typedef value_type & reference;
typedef const value_type const_reference;
typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;
public:
template <typename U> struct rebind
{
typedef alloc_pool<U, N> other;
};
public:
explicit alloc_pool()
{
for (size_type i = 0; i < N; ++i) state[i] = false;
}
~alloc_pool()
{}
private: // disable them for pulic use
explicit alloc_pool(const alloc_pool &)
{}
template <typename U> explicit alloc_pool(alloc_pool<U, N> const &)
{}
alloc_pool & operator=(const alloc_pool &)
{
return *this;
}
template <typename U> alloc_pool<T,N> & operator=(const alloc_pool<U, N> &)
{
return *this;
}
public:
pointer address(reference a)
{
return &a;
}
const_pointer address(const_reference a)
{
return &a;
}
public:
pointer allocate(size_type n, typename std::allocator<void>::const_pointer = NULL)
{
pointer p;
size_type j = 0;
size_type num_free = 0;
for (size_type i = 0; (i < N) && (num_free < n); ++i) {
if (!state[i]) {
if (num_free == 0) {
p = &data[i];
j = i;
}
++num_free;
} else {
num_free = 0;
}
}
if (num_free < n) return pointer();
for (; num_free > 0; --num_free, ++j) state[j] = true;
return p;
}
void deallocate(pointer p, size_type n)
{
for (size_type i = 0; i < N; ++i) {
if (&data[i] == p) {
for (size_type j = 0; j < n; ++j, ++i) {
state[i] = false;
}
return;
}
}
}
public:
size_type max_size() const
{
return N;
}
public:
void construct(pointer p, const T & t)
{
new(p) T(t);
}
void destroy(pointer p)
{
p->~T();
}
public:
bool operator==(const alloc_pool &)
{
return true;
}
bool operator!=(const alloc_pool & a)
{
return !operator==(a);
}
};
#endif
Makefile
:
.PHONY: all clean
CXX=g++
CXXFLAGS=-ggdb -Wall -Wextra -ansi -pedantic -O2
all : alloc
ALLOC_SRC=alloc.cpp
alloc : $(ALLOC_SRC:.cpp=.o)
$(CXX) -o $@ $^ $(CXXFLAGS)
-include $(ALLOC_SRC:.cpp=.d)
clean :
rm -f *.o *.d *.exe *.stackdump
rm -f alloc
%.o : %.cpp
$(CXX) -o $@ -c $< $(CXXFLAGS)
$(CXX) -MM $< > $*.d