For C++ an "object pool" makes little sense, since you have the ability to construct and destroy objects without allocating and freeing memory with placement new and manual invocations of a dtor. "Memory pools" make more sense *.

> * Note that I distinguish "object pool" from certain types of "resource pools" like thread pools. Thread pools aren't intended to save the cost of allocating and destroying a thread handle's memory. They pool threads in order to avoid the operating-system level cost of repeatedly creating and destroying threads. Those types of resource pools make sense in *any* language, but I wouldn't call them "object pools" since that term is often reserved for use cases where objects are deliberately kept reachable to avoid GC overhead.

Here your best bet is probably a simple free list for each type of object you allocate if you genuinely have heap allocation/deallocation-related hotspots (along with some additional page faults and cache misses). A free list exploits the fact that all the memory it pools is going to be pooled in the same-sized chunks which is going to be sufficient if you use a separate free list for each object type or subtype you'll be allocating and freeing. It's not a variable-sized allocator. It returns a fixed-size amount of memory for the client to use each time.

Here's a basic free list to get you started. I didn't bother to make it thread-safe and generally you'd probably want to use these locally for a given thread anyway if you're suffering allocation/freeing-related bottlenecks since this implementation, at least on my machine, is about 20 times faster than `malloc/free` but it slows down to being only twice as fast as `malloc/free` the moment you involve a completely uncontended spin lock. I also didn't bother with exception-safety if `new` fails in the code below, though I don't think it's worth bothering in a game context (but you can if you want with a little more work or if you don't mind paying for the overhead of using `std::vector` and `std::list` which require a little more memory for size and capacity and so forth in exchange for proper reversal of side effects on `std::bad_alloc`).

    #ifndef FIXED_ALLOCATOR_HPP
    #define FIXED_ALLOCATOR_HPP
    
    class FixedAllocator
    {
    public:
        /// Creates a fixed allocator with the specified type and block size.
        explicit FixedAllocator(int type_size, int block_size = 2048);
    
        /// Destroys the allocator.
        ~FixedAllocator();
    
        /// @return A pointer to a newly allocated chunk.
        void* allocate();
    
        /// Frees the specified chunk.
        void deallocate(void* mem);
    
    private:
        struct Block;
        struct FreeElement;
    
        FreeElement* free_element;
        Block* head;
        int type_size;
        int num_block_elements;
    };
    
    #endif

    #include "FixedAllocator.hpp"
    #include <cstdlib>
    
    struct FixedAllocator::FreeElement
    {
        // Allocated chunks serve as a singly-linked list node when free,
        // client data when used.
        FreeElement* next_element;
    };
    
    struct FixedAllocator::Block
    {
        // Blocks are linked together as singly-linked lists, pooling contiguous
        // blocks of memory.
        Block* next;
        char* mem;
    };
    
    FixedAllocator::FixedAllocator(int itype_size, int block_size): free_element(0), head(0)
    {
        // Initialize the free list.
        type_size = itype_size > sizeof(FreeElement) ? itype_size: sizeof(FreeElement);
        num_block_elements = block_size / type_size;
        if (num_block_elements == 0)
            num_block_elements = 1;
    }
    
    FixedAllocator::~FixedAllocator()
    {
        // Free each block in the list, popping a block until the stack is empty.
        while (head)
        {
            Block* block = head;
            head = head->next;
            delete[] block->mem;
            delete block;
        }
        free_element = 0;
    }
    
    void* FixedAllocator::allocate()
    {
        // Common case: just pop free element and return.
        if (free_element)
        {
            void* mem = free_element;
            free_element = free_element->next_element;
            return mem;
        }
    
        // Rare case when we're out of free elements.
        // Create new block.
        Block* new_block = new Block;
        new_block->mem = new char[type_size * num_block_elements];
        new_block->next = head;
        head = new_block;
    
        // Push all but one of the new block's elements to the free stack.
        char* mem = new_block->mem;
        for (int j=1; j < num_block_elements; ++j)
        {
            void* ptr = mem + j*type_size;
            FreeElement* element = static_cast<FreeElement*>(ptr);
            element->next_element = free_element;
            free_element = element;
        }
        return mem;
    }
    
    void FixedAllocator::deallocate(void* mem)
    {
        // Just push a free element to the stack.
        FreeElement* element = static_cast<FreeElement*>(mem);
        element->next_element = free_element;
        free_element = element;
    }

As for your idea:

> The object pool will use the swap-with-last trick for fast removal (it
> will invoke the object's ~destructor first)

If you use swap-with-last then you'll end up invalidating pointers to the last object (as well as any indices to it). For a memory allocator, it's similar to creating a data structure except you deal with a very firm requirement that you cannot invalidate pointers to memory that is not freed no matter what. With a free list like the above, you don't have to do that while keeping dirt cheap constant-time allocation and freeing.

Also the free list will give you nice spatial locality for memory chunks you allocate against it if you access the pointers in a sorted sequential fashion. However, if you start freeing and allocating a lot against it and the pointers becoming unsorted, then you could end up with lots of cache misses zig-zagging back and forth in memory. It helps to sort those pointers you get from the allocator periodically if you suffer cache misses (a radix sort can do that really fast). The free list, when combined with sorted pointers, does give you very cache-friendly access patterns, but you do have to keep those pointer reasonably sorted by address.

**With That Said...**

With all that being said, IMO when you feel the need to reach heavily for memory pools or object pools, I consider it a sign that your design is too granular. You'll never be able to find breathing room to optimize *that* much if your designs are very granular.

By granular, I mean like a system where everything in the system depends on a "pixel" object instead of an "image" object, or a "particle" object instead of a "particle emitter" object, or a "dog" object instead of a "dogs" object. To find sufficient breathing room to try all kinds of optimizations like eliminating vptr and virtual dispatch overhead for a boatload of teeny objects, using SoA reps, multithreading the homogeneous processing of many teeny things at a central level without rewriting the entire system, etc., you should be designing things at a coarser level: at the level of a collection of things, or sometimes even a collection of a collection of things.

That applies even for inheritance and OOP-based polymorphism. You don't have to make a `Dog` inherit from a `Mammal`. You can have `Dogs` inheriting from `Mammals` with a `Mammals` interface that contains operations that apply to multiple mammals at once. You can have abstract containers, just like abstract images instead of abstract pixels, and that will leave you so much more breathing room to optimize when you have so many fewer object types to deal with, and instead a handful of "container object" types.

Allocating each and every dog on a heap might be expensive. Allocating a container that could store a million dogs one time on the heap is not so expensive as that overhead is now reduced to 1/1,000,000. The easiest way to reduce the expense of allocating or freeing accessing or modifying a boatload of teeny objects is to avoid designing a boatload of teeny object types in the first place, and instead design a handful of bigger, coarser types of collection objects.