Expanding ring mem heap implementation at first approx. See README.

README

Ringmem is self-compacting and self-expanding heap
 for homogeneous elements.

Given `Type` having ctor Type(int, string, float) typical use is:

> Ringmem<Type> heap;

> Type * ptr = heap.place(1, "lol", 4.2); // ctor is called inside
>                                         // all hail variadic templates!

> ...

> heap.free(ptr);

Use any kind of refcounters/smart_ptrs, if you want to.

Initially it planned to be formed as allocator class, but std::smart_ptr
 doesn't support allocator specification.

All remaining elements will be destroyed with calling their ~dtors() when
 heap's ~dtor() called.

The compactment is done using priority queue of "holes" - unallocated points
 surrounded with allocated ones. The queue.top() always returns the leftmost hole,
 assuming we grow from left to right.

ringmem.h

#ifndef RINGMEM_H
#define RINGMEM_H

#include <vector>
#include <queue>

using namespace std;

template <class Item, int initial_cap = 1024, bool debud_mode = false>
class Ringmem {

    typedef char Filler[sizeof(Item)];

    Filler * array;
    int      size,
             last;

    priority_queue <ptrdiff_t, vector <ptrdiff_t>, greater<ptrdiff_t>> 
        holes;

    vector<bool> exists;

public:
    Ringmem():
      array(new Filler[initial_cap]),
      size (initial_cap),
      last (0)
    {
        exists.resize(initial_cap, false);
    }

    ~Ringmem() {
        for (int i = 0; i < size; i++) {

            if (exists[i]) {
                at(i)->Item::~Item();
            }
        }
    }

    template <class... Args>
    unsigned place(Args... args) {

        Filler * address;

        if (last < size) {

            address = array + last++;

        } else if (!holes.empty()) {

            address = array + holes.top();

            holes.pop();

        } else {

            expand();

            return place(args...);
        }

        exists[address - array] = true;

        new (address) Item(args...);

        return address - array;
    }

    void free(unsigned item) {

        if (item == last - 1) {

            last--;

            if (last <= size / 4) retract();

        } else {

            holes.push(item);

        }

        exists[item] = false;

        at(item)->Item::~Item();
    }

    Item * at(unsigned n) { return (Item *) array[n]; }

private:
    void expand()  { resize_to(size * 2); }
    void retract() { resize_to(size / 2); }

    void resize_to(int new_size) {

        Filler * new_array = new Filler[new_size];

        move_memory(array, new_array, new_size, new_size < size);

        delete array;

        exists.resize(new_size);

        array = new_array;
        size =  new_size;
    }

    void move_memory(
        Filler * from,
        Filler * to, 
        unsigned count, 
        bool     no_test_for_existence = false) 
    {
        for (int i = 0; i < count; i++) {

            if (no_test_for_existence || exists[i]) {

                Item * src = (Item *) (from + i);
                Item * dst = (Item *) (to   + i);

                *dst = move(*src);
            }
        }
    }
};

#endif

smart_ptr.h

#ifndef SMART_PTR_H
#define SMART_PTR_H

template <class Node, class Heap>
class SmartPtr {
    Node * node;
    Heap  &heap;

public:
    SmartPtr(Node * node, Heap &heap):
      node(node),
      heap(heap) 
    {
        node->refcount++;
    }

    SmartPtr(const SmartPtr &inst):
      SmartPtr(inst.node, inst.heap)
    { }

    SmartPtr(SmartPtr &&inst):
      SmartPtr(inst.node, inst.heap)
    { }

    ~SmartPtr() {
        if (!--node->refcount) {
            heap.free(node);
        }
    }
};

#endif