Pardon my...

10s 256 MB
Exclusive Hard 5.5
Data StructuresMemory Management +1

Implement ListHook and IntrusiveList<T, Hook>: an intrusive doubly-linked list where the link pointers live inside the elements (via an embedded hook) rather than in nodes the list allocates. The list owns nothing and allocates nothing — it threads through objects whose storage is owned elsewhere (here, a pool provided by the grader).

This problem is designed to require careful handling of:

  • the container_of idiom (recovering an element from a pointer to its embedded hook)
  • O(1) erase given only the element (no search, no position)
  • multiple simultaneous list memberships via multiple hooks in one object
  • auto-unlink: coupling an element's destruction to its removal from every list

An intrusive list stores no values of its own. Each element embeds one or more ListHook members; a list threads its ring through one specific hook. Because the hook lives in the element:

  • linking/unlinking allocates nothing,
  • an element can be removed in O(1) given only a reference to it,
  • one element can be on several lists at once (one hook per list),
  • destroying an element must splice it out of whatever list holds it.
C++ 
#include <cstddef>

// Embed one ListHook per list-membership in your element type.
struct ListHook {
    ListHook() noexcept;                       // starts unlinked
    ~ListHook();                               // AUTO-UNLINK if still linked
    ListHook(const ListHook&) = delete;        // hooks are not copyable/movable
    ListHook& operator=(const ListHook&) = delete;

    bool linked() const noexcept;              // true if currently in a list
    void unlink() noexcept;                    // splice self out; become unlinked
    // (internal link pointers are yours to define)
};

// Threads a ring through the hook identified by the pointer-to-member Hook.
//   IntrusiveList<Order, &Order::book_hook> book;
template <class T, ListHook T::* Hook>
class IntrusiveList {
public:
    IntrusiveList() noexcept;                  // empty
    ~IntrusiveList();                          // unlinks all elements; destroys none
    IntrusiveList(const IntrusiveList&) = delete;
    IntrusiveList& operator=(const IntrusiveList&) = delete;

    bool empty() const noexcept;
    std::size_t size() const noexcept;         // O(n) walk is acceptable

    void push_back(T& x) noexcept;             // link x at the tail
    void push_front(T& x) noexcept;            // link x at the head
    static void unlink(T& x) noexcept;         // O(1) remove x given only x

    T& front() noexcept;                       // returns the element, by identity
    T& back()  noexcept;

    void clear() noexcept;                     // unlink all; destroy none

    template <class Fn>
    void for_each(Fn fn);                      // call fn(T&) front-to-back
};

The element type, its hook member(s), and the backing pool are provided by the grader. You implement only ListHook and IntrusiveList.

When walking the ring you hold a ListHook*, but callers want the enclosing T. Recover it by subtracting the hook's offset within T:

C++ 
T* obj = reinterpret_cast<T*>(
    reinterpret_cast<char*>(hook_ptr) - offset_of(Hook));

front(), back(), and for_each must return / pass the actual element objects the caller linked — never copies. The grader checks pointer identity (&list.front() == &the_object_you_pushed) and that mutating an element is visible through the list.

  • The list never allocates. push_back, push_front, unlink, clear, and iteration must perform zero heap allocations. (The grader interposes operator new and asserts the count does not move across a long run of link/unlink operations.)
  • The list never constructs or destroys elements. It borrows objects owned by the pool. Destroying the list (or calling clear) unlinks elements but must not run their destructors.
  • A ListHook is not copyable or movable: its address is baked into its neighbors' links, so copying would alias and moving would dangle.

When an element is destroyed while still linked, its hook's destructor must splice it out of the list, so that no dangling link into freed/reused storage survives.

C++ 
Item* a = pool.create(...); Item* b = pool.create(...); Item* c = pool.create(...);
list.push_back(*a); list.push_back(*b); list.push_back(*c);   // [a, b, c]

pool.destroy(b);   // ends b's lifetime. NO unlink(b) call.
                   // ~ListHook must have removed b, leaving [a, c].

The grader destroys a linked element without any manual unlink call, then immediately reuses that slot (the pool is address-stable and reclaims LIFO, so the new object occupies the freed element's exact address, overwriting its old hook bytes). An implementation that does not auto-unlink leaves a neighbor pointing into the reused slot; the ring is then corrupted and the subsequent walk is wrong. The grader compiles with AddressSanitizer, so a stale read of the freed hook is also caught directly.

IntrusiveList::~IntrusiveList() and clear() must likewise leave every element's hook in the unlinked state, so an element that outlives the list can be re-linked or destroyed cleanly afterward.

  • unlink(x) is O(1) and requires nothing but x. It is valid only when x is currently linked into the list of the matching hook.
  • for_each(fn) must tolerate fn calling unlink on the current element (cache the next pointer before invoking fn).
  • One element carrying two hooks may be on two lists simultaneously; unlinking it from one must not affect the other.
  • size() may be O(n).
  • push_back, push_front, unlink(x), front, back, empty: O(1).
  • size, clear, for_each, ~IntrusiveList: O(n).
  • All of the above: zero allocation.

Single-threaded. No threads, timing, randomness, or OS-specific behavior.

  • Recommended internal design: a circular sentinel ring (a dummy hook the list owns as its anchor). An element hook is "unlinked" when its next/prev point at itself. The sentinel makes every splice branchless — no special-casing the empty list or the ends.
  • The grader provides an address-stable pool (create / destroy) and a tracked element type embedding two hooks. You do not implement the pool.
  • You may use <cstddef> and <utility>. You may not use std::list, std::vector, std::deque, or any standard container as the backing structure — the links must live in the elements. These identifiers are reserved and will fail to compile if used.
  • The grader compiles with -fsanitize=address,undefined. Use-after-free from a missing auto-unlink, and dangling reads from a broken container_of, are detected immediately.
Accepted 1/1
Acceptance 100%
Next up
Pool party! Similar problem
Expert 8
Consumerism (Hard version) Similar problem
Grandmaster 10
Stacked up (Hard Version) Similar problem
Glitched 11
Loading editor...
Input 
Running against custom tests...
Expected Output