They often write that code can work faster with a non-standard allocator, but how do you write your own allocator?
Answer 1, authority 100%
Allocator requirements and their default values are given in the “Allocator requirements [allocator.requirements]” chapter . The same chapter provides an example of a minimal allocator:
template & lt; class Tp & gt;
struct SimpleAllocator {
typedef Tp value_type;
SimpleAllocator (constructor arguments);
template & lt; class T & gt; SimpleAllocator (const SimpleAllocator & lt; T & gt; & amp; other);
Tp * allocate (std :: size_t n);
void deallocate (Tp * p, std :: size_t n);
};
template & lt; class T, class U & gt;
bool operator == (const SimpleAllocator & lt; T & gt; & amp ;, const SimpleAllocator & lt; U & gt; & amp;);
template & lt; class T, class U & gt;
bool operator! = (const SimpleAllocator & lt; T & gt; & amp ;, const SimpleAllocator & lt; U & gt; & amp;);
Containers are supposed to access the allocator not directly, but through the std :: allocator_traits template, which provides default values such as typedef T * pointer; , etc.
However, existing standard library implementations do not use allocator_traits everywhere.
Therefore, if we try to compile the code for example
std :: basic_string & lt; char, std :: char_traits & lt; char & gt ;, SimpleAllocator & lt; char & gt; & gt; s;
then we get errors like this:
/ usr / local / bin /../ lib / gcc / x86_64-unknown-linux-gnu / 4.9. 2 /../../../../ include / C++ / 4.9.2 / bits / basic_string.h: 114: 41: error: 'rebind' following the 'template' keyword does not refer to a template
typedef typename _Alloc :: template rebind & lt; _CharT & gt; :: other _CharT_alloc_type;
or
1 & gt; S: \ MSVS2013 \ VC \ include \ xstring (664): error C2903: 'rebind': symbol is neither a class template nor a function template
In both cases, the standard library implementation says _Alloc :: rebind instead of allocator_traits & lt; _Alloc & gt; :: rebind .
Thus, when writing your own allocator, you need to look at compilation errors and, if necessary, add the necessary class members.
Below is an example of an Arena allocator that compiles (VC++ 2013, g ++ – 4.9.2)
# include & lt; cassert & gt;
#include & lt; memory & gt;
#include & lt; vector & gt;
#include & lt; deque & gt;
class Arena {
public:
Arena () {}
~ Arena () {
assert (m_allocations == 0);
}
void * allocate (std :: size_t n) {
if (n & gt; m_available) {
m_chunks.emplace_back (100500);
m_available = m_chunks.back (). size ();
m_memory = & amp; m_chunks.back (). front ();
}
auto mem = m_memory;
m_available - = n;
m_memory + = n;
++ m_allocations;
return mem;
}
void deallocate (void * p, std :: size_t n) {
--m_allocations;
auto mem = (unsigned char *) p;
if (mem + n == m_memory) {
m_memory = mem;
m_available + = n;
}
}
private:
std :: deque & lt; std :: vector & lt; unsigned char & gt; & gt; m_chunks;
std :: size_t m_available = 0;
unsigned char * m_memory;
int m_allocations = 0;
};
template & lt; class T & gt;
struct ArenaAllocator {
using value_type = T;
using Traits = std :: allocator_traits & lt; ArenaAllocator & lt; T & gt; & gt ;;
#if! defined _MSC_VER
// libstdC++ uses the default constructor:
// __a == _Alloc ()
ArenaAllocator (): m_arena (nullptr) {}
// libstdC++ requires the following definitions
using size_type = typename std :: allocator & lt; T & gt; :: size_type;
using difference_type = typename std :: allocator & lt; T & gt; :: difference_type;
using pointer = typename std :: allocator & lt; T & gt; :: pointer;
using const_pointer = typename std :: allocator & lt; T & gt; :: const_pointer;
// "reference" is not included in Allocator Requirements,
// But LIBSTDC++ thinks that it always works with STD :: Allocator.
Using Reference = TypeName Std :: Allocator & LT; T & GT; :: Reference;
Using const_reference = typename std :: allocator & lt; t & gt; :: const_reference;
#Endif
Explicit Arenaallocator (Arena & Amp; Arena): M_ARENA (& AMP; ARENA) {}
TEMPLATE & LT; Class U & GT; Arenaallocator (Const Arenaallocator & LT; U & GT; & amp; Other): M_ARENA (Other.m_arena) {}
T * Allocate (STD :: SIZE_T N) {RETURN (T *) M_ARENA- & GT; ALLOCATE (N * SizeOF (T)); }
Void DEALLOCATE (T * P, STD :: SIZE_T N) {M_ARENA- & GT; DEALLOCATE (P, N * SIZEOF (T)); }
// Required in VC++ and LIBSTDC++
TEMPLATE & LT; Class U, Class ... Args & GT; Void Construct (u * p, args & amp; & amp; ... args) {std :: allocator & lt; t & gt; (). Construct (P, STD :: FORWARD & LT; Args & GT; (Args) ...); }
TEMPLATE & LT; Class U & GT; Void Destroy (U * P) {STD :: ALLOCATOR & LT; T & GT; (). Destroy (P); }
TEMPLATE & LT; Class U & GT; STRUCT REBIND {USING OTHER = ARENAALLOCATOR & LT; U & GT ;; };
Arena * M_ARENA;
};
TEMPLATE & LT; Class T, Class U & GT; BOOL Operator == (Const Arenaallocator & LT; T & GT; & amp; LHS, Const Arenaallocator & LT; U & GT; & AMP; RHS) {Return LHS.M_ARENA == RHS.M_ARENA; }
TEMPLATE & LT; Class T, Class U & GT; BOOL OPERATOR! = (Const Arenaallocator & LT; T & GT; & amp; LHS, Const Arenaallocator & lt; u & gt; & amp; RHS) {RETURN! (LHS == RHS); }
#Include & lt; deque & gt;
#Include & lt; Functional & gt;
#Include & lt; List & gt;
#Include & lt; Map & GT;
#Include & lt; Memory & gt;
#Include & lt; set & gt;
#Include & lt; String & GT;
#Include & lt; unordered_set & gt;
#Include & lt; unordered_map & gt;
#Include & lt; vector & gt;
using a_string = std :: basic_string & lt; char, std :: char_traits & lt; char & gt;, Arenaallocator & lt; Char & gt; & gt ;;
TEMPLATE & LT; Class T & GT; using a_vector = std :: vector & lt; t, arenaallocator & lt; t & gt; & gt ;;
TEMPLATE & LT; Class T & GT; using a_deque = std :: deque & lt; t, arenaallocator & lt; t & gt; & gt ;;
TEMPLATE & LT; Class T & GT; Using a_list = std :: list & lt; t, arenaallocator & lt; t & gt; & gt ;;
Template & lt; Class K & GT; Using a_set = std :: set & lt; k, std :: less & lt; k & gt;, Arenaallocator & lt; k & gt; & gt ;;
TEMPLATE & LT; Class K, Class V & GT; Using a_map = STD :: MAP & LT; K, V, STD :: LESS & LT; K & GT;, Arenaallocator & LT; STD :: PAIR & LT; Const K, V & GT; & GT; & GT ;;
Template & lt; Class K & GT; Using a_unordered_set = STD :: unordered_set & lt; k, std :: hash & lt; k & gt;, std :: equal_to & lt; k & gt;, Arenaallocator & lt; k & gt; & gt ;;
TEMPLATE & LT; Class K, Class V & GT; Using a_unordered_map = STD :: unordered_map & lt; k, std :: hash & lt; k & gt;, std :: equal_to & lt; k & gt;, Arenaallocator & lt; STD :: PAIR & LT; const k, V & gt; & gt; & gt ;;
STRUCT X {};
INT MAIN () {
Arena Arena;
Arenaallocator & lt; Char & GT; Arena_allocator (Arena);
A_STRING S_EMPTY (Arena_Allocator);
A_String S_123 ("123", Arena_allocator);
A_Vector & LT; Int & GT; v_int ({1, 2, 3}, arena_allocator);
A_Vector & LT; X & GT; V_X (42, X {}, Arena_allocator);
A_Vector & LT; A_String & GT; v_str ({s_empty, s_123}, anena_allocator);
A_Vector & LT; A_String & GT; V_STR_COPY (V_STR, ARENA_ALLOCATOR);
a_deque & lt; int & gt; d_int ({1, 2, 3}, arena_allocator);
a_list & lt; int & gt; L_INT ({1, 2, 3}, Arena_Allocator);
a_set & lt; int & gt; s_int ({1, 2, 3}, STD :: LESS & LT; INT & GT; {}, Arena_Allocator);
A_MAP & LT; A_STRING, INT & GT; M_STR_INT (ARENA_ALLOCATOR);
A_UNORDERED_SET & LT; INT & GT; US_INT (Arena_allocator);
AUTO P = STD :: ALLOCATE_SHARED & LT; INT & GT; (Arena_allocator, 123);
#if 0 // This code does not work in VC++ and G ++
A_UNORDERED_MAP & LT; A_STRING, INT & GT; UM_STR_INT (Arena_Allocator);
STD :: FUNCTION & LT; Void () & gt; f (std :: allocator_arg_t {}, anena_allocator, [] {});
#Endif
}