stack_alloc

Howard Hinnant

Introduction


Update:

I've updated this article with a new allocator that is fully C++11 conforming. The allocator it replaces was not fully C++03 nor C++11 conforming because copies were not equal.


Sometimes you need a container that is almost always going to hold just a few elements, but it must be prepared for the "large" use case as well. It is often advantageous to have the container allocate off of the local stack up to a given size, in order to avoid a dynamic allocation for the common case.

Programmers often believe they need to write custom containers to get this optimization instead of using the standard containers such as std::vector<T> and std::list<T>. This is certainly doable. However I do not believe this is the best way to go.

Instead I prefer to write a custom allocator which can be used with any of the standard containers. This custom allocator can be written in several different variants and this brief paper outlines only one. But in general, such an allocator refers to a buffer either on the stack, or with static or thread storage duration. So the end result is the same as writing your own container, but you get to reuse the standard container code.

Allocator requirements for C++11 are backwards compatible in that C++98/03 allocators will work in C++11 containers. However C++11 allocators will not work in C++98/03 containers. The allocator demonstrated here is purposefully a C++11 allocator and thus will not work with C++98/03 containers. I chose this presentation because C++11 allocators need not have a lot of distracting boiler-plate (it can be defaulted). However it is a relatively trivial task to add the boiler-plate C++98/03 allocator requirements to this allocator if desired.

A small vector

#include "short_alloc.h"
#include <vector>
#include <new>
#include <iostream>

std::size_t memory = 0;
std::size_t alloc = 0;

void* operator new(std::size_t s) throw(std::bad_alloc)
{
    memory += s;
    ++alloc;
    return malloc(s);
}

void  operator delete(void* p) throw()
{
    --alloc;
    free(p);
}

void memuse()
{
    std::cout << "memory = " << memory << '\n';
    std::cout << "alloc = " << alloc << '\n';
}

int main()
{
    const unsigned N = 200;
    typedef short_alloc<int, N> Alloc;
    typedef std::vector<int, Alloc> SmallVector;
    arena<N> a;
    SmallVector v{Alloc(a)};
    v.push_back(1);
    memuse();
    v.push_back(2);
    memuse();
    v.push_back(3);
    memuse();
    v.push_back(4);
    memuse();
    for (auto i : v)
        std::cout << i << ' ';
    std::cout << '\n';
}

memory = 0
alloc = 0
memory = 0
alloc = 0
memory = 0
alloc = 0
memory = 0
alloc = 0
1 2 3 4 

In the above example I've created a custom new/delete just for the purpose of monitoring heap allocations. A vector<int> is created that will allocate up to 100 bytes's before going to the heap.

A small list

This works with list too:

int main()
{
    const unsigned N = 200;
    typedef short_alloc<int, N> Alloc;
    typedef std::list<int, Alloc> SmallList;
    arena<N> a;
    SmallList v{Alloc(a)};
    v.push_back(1);
    memuse();
    v.push_back(2);
    memuse();
    v.push_back(3);
    memuse();
    v.push_back(4);
    memuse();
    for (auto i : v)
        std::cout << i << ' ';
    std::cout << '\n';
}

memory = 0
alloc = 0
memory = 0
alloc = 0
memory = 0
alloc = 0
memory = 0
alloc = 0
1 2 3 4 

A small set

Yes, you can make a small set too:

typedef std::set<int, std::less<int>, short_alloc<int, 200>> SmallSet;

Next time you're tempted to write your own container, take a moment to explore the possibility of reusing the standard containers. That's what they are there for. You may be surprised at how they can be customized to meet your needs.