C++ Custom Allocators for STL Containers: Pool, Stack, Tracking Allocators and PMR

Default allocator

#include <memory>

// Default allocator
allocator<int> alloc;

// Allocate memory
int* ptr = alloc.allocate(10);  // space for 10 ints

// Construct an object
alloc.construct(ptr, 42);

// Destroy an object
alloc.destroy(ptr);

// Deallocate memory
alloc.deallocate(ptr, 10);

Every STL container you’ve ever used has been backed by an allocator the whole time — std::vector<int> is really std::vector<int, std::allocator<int>>, with the second template argument silently defaulted. std::allocator itself just calls ::operator new/::operator delete under the hood, so this explicit walk through allocate/construct/destroy/deallocate is worth doing once precisely because containers normally hide it — it’s the exact sequence vector::push_back performs internally every time it grows, just spelled out by hand instead of buried inside the container’s implementation.

Container and Allocator

// Default allocator
vector<int> v1;
// Custom allocator
vector<int, MyAllocator<int>> v2;
// Passing an allocator instance
MyAllocator<int> alloc;
vector<int, MyAllocator<int>> v3(alloc);

The allocator is part of the container’s type, not just a runtime configuration option — vector<int> and vector<int, MyAllocator<int>> are two distinct, incompatible types, the same way vector<int> and vector<double> are. That has a real consequence: a function taking const vector<int>& cannot accept a vector<int, MyAllocator<int>> argument without a conversion, and you can’t mix elements from containers with different allocator types in APIs that expect a single container type. This is exactly why custom allocators tend to spread through a codebase as a deliberate, upfront architectural choice rather than something bolted on later to one container in isolation.

Custom Allocator implementation

template<typename T>
class MyAllocator {
public:
    using value_type = T;
    
    MyAllocator() noexcept {}
    
    template<typename U>
    MyAllocator(const MyAllocator<U>&) noexcept {}
    
    T* allocate(size_t n) {
        cout << "Allocating: " << n << " objects" << endl;
        return static_cast<T*>(::operator new(n * sizeof(T)));
    }
    
    void deallocate(T* ptr, size_t n) noexcept {
        cout << "Deallocating: " << n << " objects" << endl;
        ::operator delete(ptr);
    }
};
template<typename T, typename U>
bool operator==(const MyAllocator<T>&, const MyAllocator<U>&) {
    return true;
}
template<typename T, typename U>
bool operator!=(const MyAllocator<T>&, const MyAllocator<U>&) {
    return false;
}
int main() {
    vector<int, MyAllocator<int>> v;
    
    v.push_back(1);  // triggers an allocation
    v.push_back(2);
    v.push_back(3);
}

The minimum contract a type needs to satisfy to work as an allocator is smaller than most people expect: a value_type alias, allocate/deallocate, and a converting constructor template (template<typename U> MyAllocator(const MyAllocator<U>&)) — that last one exists because containers like list and map need to allocate a differently-typed internal node (Node<T>, not T itself) using an allocator that was configured for T, which requires rebinding the allocator to a different value type. Everything else — construct, destroy, and various typedefs — has sensible defaults supplied by std::allocator_traits, which is what actually mediates between a container and an allocator; the container never calls your allocator’s methods directly, it goes through allocator_traits<Alloc>::allocate(...) and similar, falling back to defaults for anything your allocator doesn’t define.

The converting-constructor template being a no-op here ({}, doing nothing) is fine for a stateless allocator like this one, but it’s the exact place a stateful allocator (one wrapping a memory pool, say) needs to actually copy the relevant state across — get that wrong and rebind operations silently lose track of which pool an allocator instance was supposed to be using.

Pool, Stack, and Tracing Allocators

Memory pool allocator

template<typename T>
class PoolAllocator {
private:
    struct Block {
        T data;
        Block* next;
    };
    
    Block* freeList = nullptr;
    vector<Block*> pools;
    
    static constexpr size_t POOL_SIZE = 1024;
    
    void allocatePool() {
        Block* pool = static_cast<Block*>(::operator new(POOL_SIZE * sizeof(Block)));
        pools.push_back(pool);
        
        for (size_t i = 0; i < POOL_SIZE - 1; i++) {
            pool[i].next = &pool[i + 1];
        }
        pool[POOL_SIZE - 1].next = nullptr;
        
        freeList = pool;
    }
    
public:
    using value_type = T;
    
    PoolAllocator() {
        allocatePool();
    }
    
    ~PoolAllocator() {
        for (Block* pool : pools) {
            ::operator delete(pool);
        }
    }
    
    T* allocate(size_t n) {
        if (n != 1) {
            throw bad_alloc();
        }
        
        if (!freeList) {
            allocatePool();
        }
        
        Block* block = freeList;
        freeList = freeList->next;
        
        return &block->data;
    }
    
    void deallocate(T* ptr, size_t n) noexcept {
        if (n != 1) return;
        
        Block* block = reinterpret_cast<Block*>(ptr);
        block->next = freeList;
        freeList = block;
    }
};
int main() {
    list<int, PoolAllocator<int>> myList;
    
    for (int i = 0; i < 1000; i++) {
        myList.push_back(i);  // allocated from the pool
    }
}

Pairing this specifically with list (not vector) is a deliberate design constraint, not an arbitrary example choice — notice allocate immediately throws if n != 1. A linked-list node allocator only ever needs to allocate one node at a time, so the pool can pre-carve its 1024-block arena into a fixed-size free list and hand out/reclaim single blocks in O(1) with simple pointer manipulation, no bookkeeping about variable-sized regions. vector periodically needs to allocate one large contiguous block for many elements at once (n far greater than 1), which this fixed-block-size pool structure can’t satisfy at all — a pool allocator like this is fundamentally a node-based-container allocator, not a general-purpose replacement for std::allocator.

Stack allocator

template<typename T, size_t N>
class StackAllocator {
private:
    alignas(T) char buffer[N * sizeof(T)];
    size_t used = 0;
    
public:
    using value_type = T;
    
    T* allocate(size_t n) {
        if (used + n > N) {
            throw bad_alloc();
        }
        
        T* result = reinterpret_cast<T*>(buffer + used * sizeof(T));
        used += n;
        return result;
    }
    
    void deallocate(T* ptr, size_t n) noexcept {
        // A stack allocator doesn't actually free anything — the whole
        // buffer is reclaimed at once when it goes out of scope.
    }
};
int main() {
    // Allocated on the stack, not the heap
    vector<int, StackAllocator<int, 100>> v;
    
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    
    // Automatically freed when the scope ends
}

The empty deallocate here is not a bug or an oversight — it’s the entire point of this allocator. buffer is a fixed-size array embedded directly in the allocator object (which itself typically lives on the stack, hence the name), so there’s no heap bookkeeping to release; the memory simply ceases to exist when StackAllocator’s enclosing scope ends. The real limitation to be aware of: this allocator only ever grows (used never decreases), so a vector using it that grows past N elements throws bad_alloc rather than falling back to heap allocation — it’s best suited for a known, bounded number of elements with a short, scope-limited lifetime, like a temporary buffer inside a single function call.

Trace allocator

template<typename T>
class TrackingAllocator {
private:
    static size_t allocCount;
    static size_t deallocCount;
    static size_t bytesAllocated;
    
public:
    using value_type = T;
    
    T* allocate(size_t n) {
        allocCount++;
        bytesAllocated += n * sizeof(T);
        
        cout << "Allocating: " << n * sizeof(T) << " bytes" << endl;
        return static_cast<T*>(::operator new(n * sizeof(T)));
    }
    
    void deallocate(T* ptr, size_t n) noexcept {
        deallocCount++;
        bytesAllocated -= n * sizeof(T);
        
        cout << "Deallocating: " << n * sizeof(T) << " bytes" << endl;
        ::operator delete(ptr);
    }
    
    static void printStats() {
        cout << "Allocation count: " << allocCount << endl;
        cout << "Deallocation count: " << deallocCount << endl;
        cout << "Currently in use: " << bytesAllocated << " bytes" << endl;
    }
};
template<typename T>
size_t TrackingAllocator<T>::allocCount = 0;
template<typename T>
size_t TrackingAllocator<T>::deallocCount = 0;
template<typename T>
size_t TrackingAllocator<T>::bytesAllocated = 0;
int main() {
    {
        vector<int, TrackingAllocator<int>> v;
        
        for (int i = 0; i < 100; i++) {
            v.push_back(i);
        }
    }
    
    TrackingAllocator<int>::printStats();
}

Making the counters static means every TrackingAllocator<int> instance shares the same counts — which is exactly what you want for a diagnostic tool that answers “how much memory has this program allocated for int containers in total,” but it also means this specific implementation can’t distinguish between two independent containers you might want to track separately; both would increment the same shared counters. A more surgical version would make the counts instance members instead, at the cost of each container needing its own explicitly-constructed allocator instance rather than relying on the default.

PMR (Polymorphic Memory Resources)

#include <memory_resource>
int main() {
    // Monotonic buffer
    char buffer[1024];
    pmr::monotonic_buffer_resource pool(buffer, sizeof(buffer));
    
    // PMR vector
    pmr::vector<int> v(&pool);
    
    for (int i = 0; i < 100; i++) {
        v.push_back(i);  // allocated from buffer
    }
}

PMR (C++17) solves the type-pollution problem from the “Container and Allocator” section above in a fundamentally different way: instead of the allocator being baked into the container’s type as a template parameter, pmr::vector<int> is a type alias for vector<int, pmr::polymorphic_allocator<int>> — a single concrete type whose allocator behavior is chosen at runtime via virtual dispatch to a memory_resource*. That means a function can take a plain pmr::vector<int>& parameter and work correctly regardless of which memory resource actually backs it, something impossible with template-parameterized custom allocators like MyAllocator above. monotonic_buffer_resource specifically never releases individual allocations — like the stack allocator, it only grows, and frees everything at once when the resource itself is destroyed — making it ideal for short-lived, allocate-heavy scopes where you don’t care about reclaiming individual objects mid-scope.

Over-aligned allocations for SIMD and cache lines

A common reason to write a custom allocator is to get memory aligned to 32 or 64 bytes, for AVX loads or to keep elements on separate cache lines. The tempting implementation calls std::aligned_alloc, and it has two portability problems: the requested size must be a multiple of the alignment (so n * sizeof(T) for small n can make the call fail), and MSVC does not provide std::aligned_alloc at all. Since C++17, the aligned forms of operator new and operator delete work everywhere:

#include <cstddef>
#include <new>
#include <vector>

template <class T, std::size_t Align = 64>
struct AlignedAllocator {
    static_assert(Align >= alignof(T) && (Align & (Align - 1)) == 0, "power of two");
    using value_type = T;
    using is_always_equal = std::true_type;   // stateless: any two instances are interchangeable

    template <class U> struct rebind { using other = AlignedAllocator<U, Align>; };

    AlignedAllocator() = default;
    template <class U> AlignedAllocator(const AlignedAllocator<U, Align>&) noexcept {}

    T* allocate(std::size_t n) {
        return static_cast<T*>(::operator new(n * sizeof(T), std::align_val_t{Align}));
    }
    void deallocate(T* p, std::size_t) noexcept {
        ::operator delete(p, std::align_val_t{Align});   // must match the aligned new
    }
};
template <class T, class U, std::size_t A>
bool operator==(const AlignedAllocator<T, A>&, const AlignedAllocator<U, A>&) { return true; }

std::vector<float, AlignedAllocator<float, 64>> v(1024);   // v.data() is 64-byte aligned

Three details matter. The explicit rebind is needed because the allocator has a non-type template parameter, which std::allocator_traits cannot rebind automatically. The deallocation must use the matching aligned operator delete; pairing aligned new with plain delete or free() is undefined behavior. And is_always_equal = std::true_type tells containers that any two instances can free each other’s memory, which enables cheap move assignment and swap. For a stateful allocator, such as one holding a pointer to a pool, leave it false and define operator== to compare the pool pointers, because memory from one pool must never be returned to another.

Only the start of the buffer gets this alignment: the elements after the first are spaced by sizeof(T), so they are not each 64-byte aligned unless the element type itself is alignas(64). Node-based containers allocate their nodes through a rebound allocator whose alignment you should check separately.

Allocator Equality, Propagation, and Alignment Problems

Allocator comparison

// ❌ No allocator comparison
template<typename T>
class BadAllocator {
    // no operator==
};
// ✅ Allocator comparison implemented
template<typename T>
class GoodAllocator {
    // ...
};
template<typename T, typename U>
bool operator==(const GoodAllocator<T>&, const GoodAllocator<U>&) {
    return true;
}

Containers use allocator equality to decide whether two allocator instances can safely share ownership of each other’s allocated memory — for example, when swapping two containers or move-assigning one into another. If your allocator is stateless (like MyAllocator earlier, where every instance behaves identically), operator== should simply always return true, since any instance can safely deallocate memory allocated by any other instance. For a stateful allocator (one wrapping a specific memory pool), returning true unconditionally would be actively wrong — it would tell containers it’s safe to mix memory across two allocator instances backed by two different, unrelated pools, which is undefined behavior.

Allocator propagation

// Whether the allocator propagates on container copy
template<typename T>
struct allocator_traits<MyAllocator<T>> {
    using propagate_on_container_copy_assignment = true_type;
    using propagate_on_container_move_assignment = true_type;
    using propagate_on_container_swap = true_type;
};

In practice, these propagate_on_* flags are usually defined as nested typedefs directly inside your allocator class (using propagate_on_container_copy_assignment = std::true_type; inside MyAllocator itself), which std::allocator_traits picks up automatically — specializing allocator_traits externally, as shown here, works too but is less common. Either way, the flags answer a genuinely subtle question: when a container is copy-assigned, does the destination container keep its own existing allocator (propagate = false, the default) or adopt the source’s allocator (propagate = true)? For a stateless allocator this distinction is invisible, but for a stateful one — say, an allocator bound to a specific memory arena — getting this wrong means a copied container can end up allocating from a pool nobody intended it to use, or holding onto a pool that’s about to be destroyed.

Misaligned memory

// ❌ Alignment not considered
char buffer[100];
int* ptr = reinterpret_cast<int*>(buffer);  // not aligned!
// ✅ Use alignas
alignas(int) char buffer[100];
int* ptr = reinterpret_cast<int*>(buffer);

A plain char buffer[100] has no alignment guarantee beyond alignof(char) (which is 1), but reinterpreting it as an int* and dereferencing it requires the address to satisfy alignof(int) (commonly 4). On x86, misaligned access usually just costs a performance penalty; on ARM and several other architectures, it can raise a hardware fault and crash the program outright — alignas(int) fixes this by telling the compiler to place buffer at an address that already satisfies int’s alignment requirement, which is exactly the same technique the stack allocator example above uses for its own buffer.

FAQ

Q1: When do I use a custom allocator?

A:

• memory pool
• Special memory area (GPU, shared memory)
• Memory tracing/debugging
• Performance optimization

Q2: What are the performance benefits?

A: A pool or arena allocator hands out fixed-size blocks from memory it already owns, so an allocation is often just popping a free-list node or bumping a pointer, with no size-class lookup, locking, or metadata bookkeeping. That makes allocation much cheaper than general-purpose new/delete when a hot path allocates many small objects, and it keeps those objects close together in memory. Modern general-purpose allocators (glibc’s tcache, jemalloc, mimalloc) are already fast on their common paths, though, so profile first and adopt a custom allocator only when allocation actually shows up as a hotspot.

Q3: What is PMR?

A: Polymorphic memory resources in C++17. You can change the allocator at runtime.

Q4: Is it difficult to implement an allocator?

A: The basic implementation is simple, but the complete implementation is complex. Use allocator_traits.

Q5: What about allocator debugging?

A:

• Use a tracking allocator
• Valgrind
• AddressSanitizer

Q6: What are Allocator learning resources?

A:

• cppreference.com
• “The C++ Standard Library” (Nicolai Josuttis)
• Boost.Pool source code

---

Related Articles

• std::pmr Memory Resources
• Custom C++ Memory Pools
• C++ vector reserve vs resize
• C++ Algorithm Generate Guide

---