Specific Allocators for STL-containers

Astrail-Home
Software-Team

© 2005 Andreas Wißmeier, Änderungsstand: 12. Januar 2006 <<--
-->>

What are Allocators?

Allocators for a container class specify how that class manages storage.

template <
class Type,
class Allocator = allocator<Type>
>

STL containers are templates where the last argument is the allocator class. Generally we do not supply this allocator class explicitly but use the default value.

Why Write Specific Allocators?

One important reason might be: We want to determine in which part of memory the container will be kept: For instance in shared memory for multiple processes. Still we want to use the STL, for it supplies very elaborate code, i.e. algorithms we would not want to rewrite.

Small Sample Program

The following program compiles and runs well with: Microsoft Visual C++ .NET. 

The allocator can be used for vectors, but not for maps.

The purpose of the program is to show that the elements of the vector are now stored in the static member of the class PoolMemory. That member could be located in shared memory, in a real application. 

#include <iostream>
#include <vector>
#include <string>
#include <limits>

template <typename PoolElement>
class PoolMemory {
public:
enum {
numberOfElements = 100
};
typedef PoolElement PoolElement_;
static PoolElement_ pool[numberOfElements];
private:
PoolMemory(const PoolMemory &i){}
PoolMemory(void){}
};

typedef std::pair <int, double> PairIntDouble;

PoolMemory<PairIntDouble>::PoolElement_ PoolMemory<PairIntDouble>::pool[];
PoolMemory<int>::PoolElement_ PoolMemory<int>::pool[];


// Traits that describes an object T
template<typename T>
class ObjectTraits {
public :
// convert an ObjectTraits<T> to ObjectTraits<U>
template<typename U>
struct rebind {
typedef ObjectTraits<U> other;
};

public :
inline explicit ObjectTraits() {}
inline ~ObjectTraits() {}
inline explicit ObjectTraits(ObjectTraits const&) {}
template <typename U>
inline explicit ObjectTraits(ObjectTraits<U> const&) {}

// address
inline T* address(T& r) { return &r; }
inline T const* address(T const& r) { return &r; }

inline static void construct(T* p, const T& t) {
new(p) T(t);
}
inline static void destroy(T* p) { p->~T(); }
}; // end of class ObjectTraits

///////////////////////////////////////////////////////////////////////////
// class StandardAllocPolicy
///////////////////////////////////////////////////////////////////////////
// a standard allocation policy using the free store
template<typename T>
class StandardAllocPolicy {
public :
// typedefs
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 :
// convert an StandardAllocPolicyY<T> to StandardAllocPolicyY<U>
template<typename U>
struct rebind {
typedef StandardAllocPolicy<U> other;
};

public :
inline explicit StandardAllocPolicy() {}
inline ~StandardAllocPolicy() {}
inline explicit StandardAllocPolicy(StandardAllocPolicy const&) {}
template <typename U>
inline explicit StandardAllocPolicy(StandardAllocPolicy<U> const&) {}

// memory allocation
inline pointer allocate(size_type cnt, typename std::allocator<void>::const_pointer = 0)
{
return reinterpret_cast<pointer>(::operator new(cnt * sizeof (T)));
}
inline void deallocate(pointer p, size_type) { ::operator delete(p); }

// size
inline size_type max_size(void) const { return std::numeric_limits<size_type> ::max() / sizeof(T); }
}; // end of class StandardAllocPolicy


//////////////////////////////////////////////////////////////////////////
// class FixedArrayAllocPolicy
///////////////////////////////////////////////////////////////////////////

// a fixed size array allocation policy
// should be used with vector only
template<typename T>
class FixedArrayAllocPolicy {
public :
// typedefs
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 :
// convert an FixedArrayAllocPolicy<T> to FixedArrayAllocPolicy<U>
template<typename U>
struct rebind {
typedef FixedArrayAllocPolicy<value_type> other;
};

public :
inline explicit FixedArrayAllocPolicy(): data_(&PoolMemory<value_type>::pool[0]){
std::cout << __FUNCTION__ << std::endl;
}
inline ~FixedArrayAllocPolicy() {
std::cout << __FUNCTION__ << std::endl;
}
inline explicit FixedArrayAllocPolicy(FixedArrayAllocPolicy const&): data_(&PoolMemory<value_type>::pool[0]) {
std::cout << __FUNCTION__ << std::endl;
}
// memory allocation
/* needed for header-file vector */
inline pointer allocate(size_type cnt, std::allocator<void>::const_pointer = 0) {
return reinterpret_cast<pointer>(this->data_);
}
inline void deallocate(pointer p, size_type)
{
// std::cout << "no deallocation" << std::endl;
}
// size
inline size_type max_size() const { return PoolMemory<value_type>::numberOfElements; }
private :
PoolMemory<value_type>::PoolElement_ * data_;
}; // end of class FixedArrayAllocPolicy


///////////////////////////////////////////////////////////////////////////
// class Allocator
///////////////////////////////////////////////////////////////////////////

// Policy driven allocator object
template<typename T, typename Policy = StandardAllocPolicy<T>, typename Traits = ObjectTraits<T> >
class Allocator : public Policy, public Traits {
private :
typedef Policy AllocationPolicy;
typedef Traits TTraits;

public :
typedef typename AllocationPolicy::size_type size_type;
typedef typename AllocationPolicy::difference_type difference_type;
typedef typename AllocationPolicy::pointer pointer;
typedef typename AllocationPolicy::const_pointer const_pointer;
typedef typename AllocationPolicy::reference reference;
typedef typename AllocationPolicy::const_reference const_reference;
typedef typename AllocationPolicy::value_type value_type;

public :
template<typename U>
struct rebind {
typedef Allocator<U, typename AllocationPolicy::rebind<U>::other> other;
};

public :
inline explicit Allocator() {}
inline ~Allocator() {}
inline Allocator(Allocator const& rhs):Traits(rhs), Policy(rhs) {}
template <typename U>
inline explicit Allocator(Allocator<U> const&) {}
template <typename U, typename P, typename T2>
inline Allocator(Allocator<U, P, T2> const& rhs):Traits(rhs), Policy(rhs) {}
/* needed for header-file vector */
// memory allocation
inline pointer allocate(size_type cnt, typename std::allocator<void>::const_pointer hint = 0) {
return AllocationPolicy::allocate(cnt, hint);
}
inline void deallocate(pointer p, size_type cnt) {
AllocationPolicy::deallocate(p, cnt);
}
}; // end of class Allocator

int
main()
{
int a = std::numeric_limits<int> ::max();
typedef Allocator<int, FixedArrayAllocPolicy<int>, ObjectTraits<int> > AFIX;
typedef Allocator<PairIntDouble, FixedArrayAllocPolicy<PairIntDouble>, ObjectTraits<PairIntDouble> > AFIX_PAIR;

std::vector<PairIntDouble, AFIX_PAIR> v3;
std::vector<PairIntDouble, AFIX_PAIR>::const_iterator constIter3;

std::vector<int, AFIX> v2;
std::vector<int, AFIX>::const_iterator constIter2;


v2.reserve(10);
v2.push_back(211);
v2.push_back(212);
v2.push_back(213);

PairIntDouble p(1,1.1);
v3.reserve(10);
v3.push_back( PairIntDouble(1,1.1) );
v3.push_back( PairIntDouble(2,1.1) );
v3.push_back( PairIntDouble(3,1.1) );
v3.push_back( PairIntDouble(4,1.1) );

int i=0;
for(constIter2 = v2.begin(); constIter2 != v2.end(); constIter2++,i++)
{
std::cout << "i=" << i << " " << *constIter2 << std::endl;
std::cout << "PoolMemory::=" << PoolMemory<int>::pool[i] << std::endl;
}
i=0;
for(constIter3 = v3.begin(); constIter3 != v3.end(); constIter3++,i++)
{
std::cout << "i=" << i << " " << (*constIter3).first << std::endl;
std::cout << "PoolMemory::pool[" << i << "].first=" << PoolMemory<PairIntDouble>::pool[i].first << std::endl;
std::cout << "PoolMemory::pool[" << i << "].second=" << PoolMemory<PairIntDouble>::pool[i].second << std::endl;
}
v2[1] = 99;
i=0;
for(constIter2 = v2.begin(); constIter2 != v2.end(); constIter2++,i++)
{
std::cout << "i=" << i << " " << *constIter2 << std::endl;
std::cout << "PoolMemory::=" << PoolMemory<int>::pool[i] << std::endl;
}
}

 

 

 

Sources:

Title of book or link
( last visit of the link )
Description
[1]http://www.codeguru.com/Cpp/Cpp/cpp_mfc/stl/article.php/c4079

( September 2005)

Explains well how to write an allocator for vector
[2]http://www.codeproject.com/cpp/allocator.asp

( September 2005)

Explains well the decomposition of allocators with traits and policies