Pool party!

10s 256 MB
Exclusive Expert 8
Data StructuresDesign Patterns +2 Akuna Capital

Implement the class ObjectPool, a fixed-capacity object pool that manages raw storage manually and constructs objects in-place using placement new.

The pool is backed by a single contiguous byte buffer. Objects are created and destroyed explicitly, and slots are recycled for reuse.

This problem is designed to require careful handling of:

  • placement new
  • explicit destructor calls
  • reinterpret_cast
  • std::launder
  • alignment and pointer validation

A Certain Scientific Railgun

You must implement ObjectPool<T>, a template pool that supports:

  • acquire(args...): constructs a T in a free slot and returns a pointer to it
  • release(ptr): destroys the object and returns the slot to the pool

The pool must never allocate per object. It may allocate once up-front for its backing buffer.

C++ 
#include <cstddef>
#include <cstdint>
#include <new>
#include <utility>

template <class T>
class ObjectPool {
public:
    // Construct a pool that can hold at most `capacity` live objects at a time.
    explicit ObjectPool(std::size_t capacity);

    // Destroy all still-live objects (if any), then free backing storage.
    ~ObjectPool();

    ObjectPool(const ObjectPool&) = delete;
    ObjectPool& operator=(const ObjectPool&) = delete;

    // Acquire an object from the pool, constructing it in-place with `args...`.
    // Returns nullptr if the pool is exhausted (no free slots).
    template <class... Args>
    T* acquire(Args&&... args);

    // Return an object to the pool.
    //
    // Returns false if:
    //  - ptr is nullptr
    //  - ptr was not produced by this pool
    //  - ptr is not exactly at the start of a slot
    //  - ptr is misaligned for T
    //  - the slot is already free (double release)
    //
    // Otherwise:
    //  - calls the destructor for the object
    //  - marks the slot free
    //  - returns true
    bool release(T* ptr);

    std::size_t capacity() const noexcept;
    std::size_t in_use() const noexcept;
    std::size_t available() const noexcept;

private:
    // You decide the internal representation.
};

Your pool must allocate one contiguous storage region that can hold capacity objects of type T with correct alignment.

  • The storage must be raw bytes (not T[]).
  • The start address must be aligned to alignof(T).
  • Each slot must be exactly sizeof(T) bytes apart.

You may use any correct strategy to allocate aligned storage, e.g.:

  • ::operator new(total_bytes, std::align_val_t(alignof(T)))
  • another correct aligned allocation method in C++20

acquire(args...) must:

  1. Choose a free slot (any deterministic policy is fine; LIFO free-list recommended).
  2. Construct T in that slot using placement new:
C++ 
   void* p = slot_address(i);
   ::new (p) T(std::forward<Args>(args)...);
  • Return a pointer to the newly constructed object.

    • Because the same storage will be reused across multiple lifetimes, you must produce the returned pointer via:

    C++ 
    return std::launder(reinterpret_cast<T*>(p));

    release(ptr) must:

    1. Validate that ptr points to an object currently owned by this pool (see validation rules below).
    2. Detect double release.
    3. Call the destructor exactly once:
    C++ 
       ptr->~T();
  • Mark the slot as free and return it to the internal free-list.
  • Return true.

    • The judge will test invalid pointers. Your release(ptr) must return false for all invalid cases.

    At minimum, validate:

    • Null: ptr == nullptr → false
    • Range: ptr must lie within [buffer_begin, buffer_end)
    • Alignment: ptr must be aligned to alignof(T)
    • Slot boundary: ptr must equal buffer_begin + k * sizeof(T) for some integer k
    • Membership: the computed slot index k must be < capacity
    • Liveness: slot k must currently be in-use (not free)

    Note: The judge may pass pointers that are inside the buffer range but not at a slot boundary, such as reinterpret_cast<T*>(buffer_begin + 1) or ptr + 1. These must be rejected.

    • At any time, each slot is either free or contains one live T.
    • acquire creates a new lifetime for T in a free slot.
    • release ends the lifetime and returns the slot to the pool.
    • ObjectPool::~ObjectPool() must destroy all remaining live objects.

    For the same sequence of calls, behavior must be deterministic:

    • acquire selection order must not depend on randomness.
    • The pool must not use time, sleeping, threads, or OS-specific behavior.

    acquire(...)

    • If at least one slot is free:
      • Constructs T with the forwarded arguments
      • Returns a non-null T*
    • If no slots are free:
      • Returns nullptr
    • Must not allocate memory per call.

    release(ptr)

    • Returns true exactly once for each valid pointer returned by acquire.
    • Must reject:
      • double releases
      • pointers not from this pool
      • pointers not on slot boundaries
      • pointers to objects already released
    • Must not throw exceptions.
    • You may assume single-threaded usage.
    • You may use standard library containers for bookkeeping (e.g., free list / occupancy), but acquire/release must not perform per-object allocation.
    • The intent is to test low-level lifetime and memory correctness.

    Pointer provenance consideration:

    When returning pointers to objects constructed via placement new in reused storage, you should use std::launder to inform the compiler about the new object lifetime:

    C++ 
    void* storage = /* free slot */;
::new (storage) T(std::forward(args)...);
return std::launder(reinterpret_cast(storage));

    This prevents potential undefined behavior from compiler optimizations that might cache properties of the previous object. While tests may not detect its absence, it's essential for production-grade code.

    C++ 
    ObjectPool<std::string> pool(2);

auto* a = pool.acquire("hello");
auto* b = pool.acquire("world");
auto* c = pool.acquire("!");   // nullptr (exhausted)

pool.release(a);               // true
auto* d = pool.acquire("again");  // non-null; may reuse a's slot/address

pool.release(a);               // false (double release)

    The judge will compile and run your ObjectPool<T> implementation inside a hidden harness.

    You do not need to write any custom input/output parsing.

    Accepted 7/49
    Acceptance 14%
    Next up
    Consumerism (Hard version) Similar problem
    Grandmaster 10
    Consumerism (Easy version) Similar problem
    Master 9
    I'm single. Similar problem
    Harder 6
    Loading editor...
    Input 
    Compiling against custom test cases...
    Expected Output