SlotArray: an array as convenient as a dynamic list but with exposed indexes (similar to using a Dictionary<int,T> but more memory friendly, or an ArrayList which self-manages free slots)

SlotArray.cs

using System;
using System.Collections;
using System.Collections.Generic;

/// <summary>
/// Utility class which stores a dynamic array of objects or value types, and exposes
/// where it places them in its internal storage so you can remove them by index
/// if you need to. Indexes remain stable at all times.
///
/// This is useful for cases like Coroutine where you may not have a reference
/// to the object itself (inside the Coroutine) but can allocate an index ahead
/// of time.
///
/// General operations in this class are O(n) with early exit, so it performs best
/// when either fairly small, or fairly unfragmented. New items are placed in the
/// lowest free slot but gaps caused by Remove are not closed (to preserve indexes).
/// Insertion can be O(1) if you only ever add in sequence, and then remove from the end
/// first. When there are gaps it becomes O(n) but will return to O(1) if the gaps
/// are filled, which subsequent insertion will try to do.
/// Resizing is unsurprisingly very expensive.
/// </summary>
/// <typeparam name="T"></typeparam>
public class SlotArray<T> : IEnumerable<T> {

    T[] slots;
    BitArray slotOccupancy; // separate from slots to support value types & reserve
    int freeSlots;
    int sentinel; // maxIndex+1

    /// <summary>
    /// Returns the number of items in the array.
    /// </summary>
    /// <returns></returns>
    public int Count { get { return slots.Length - freeSlots; } }

    /// <summary>
    /// Construct a new array
    /// </summary>
    /// <param name="capacity">Number of items able to store without expensive resizing</param>
    public SlotArray(int capacity = 32) {
        slots = new T[capacity];
        slotOccupancy = new BitArray(capacity);
        freeSlots = capacity;
        sentinel = 0;
    }

    /// <summary>
    /// Reserve a slot in the array and return its index. This index will be considered
    /// used until you call Remove, RemoveAt or Clear even before you place any
    /// value in it.
    /// </summary>
    /// <remarks>
    /// This method is O(n) if there are gaps in the array (where n = number of
    /// items added), and O(1) if the array has no gaps in it
    /// </remarks>
    /// <param name="extend">True if you want to extend the array if there are no free slots</param>
    /// <returns>The reserved index to be used with InsertAt, or -1 if there were
    /// no free slots and extending was disabled.</returns>
    public int Reserve(bool extend = true) {
        if (freeSlots == 0) {
            if (extend) {
                freeSlots = slots.Length;
                Array.Resize(ref slots, slots.Length * 2);
                slotOccupancy.Length = slotOccupancy.Length * 2;
            } else {
                return -1;
            }
        }

        int idx = FindFreeSlot();
        slotOccupancy[idx] = true;
        --freeSlots;
        sentinel = Math.Max(sentinel, idx+1);
        return idx;

    }

    /// <summary>
    /// Insert a new item and return its index. This is equivalent to calling
    /// Reserve followed by InsertAt.
    /// </summary>
    /// <remarks>
    /// This method is O(n) if there are gaps in the array (where n = number of
    /// items added), and O(1) if the array has no gaps in it
    /// </remarks>
    /// <param name="val">Value to insert</param>
    /// <param name="extend">True to extend the array if there are no free slots</param>
    /// <returns>The index the item was inserted at, or -1 if there were no free slots
    /// and extending was disabled</returns>
    public int Insert(T val, bool extend = true) {
        int idx = Reserve(extend);
        if (idx != -1)
            slots[idx] = val;
        return idx;
    }

    /// <summary>
    /// Insert an item into an index you have received from Reserve(). Can also
    /// be used to replace an item previously inserted if you want to swap them.
    /// Will overwrite any entry already at that index with no warning, but will
    /// fail if the index is marked as free.
    /// </summary>
    /// <param name="idx"></param>
    /// <param name="val"></param>
    public void InsertAt(int idx, T val) {
        if (idx < 0 || idx >= slots.Length || idx >= sentinel)
            throw new ArgumentException("Index out of range");
        if (!slotOccupancy[idx])
            throw new ArgumentException("Index is invalid, must not be a free index");

        slots[idx] = val;

        // No change to slotOccupancy, should always be allocated already with Reserve
    }

    protected int FindFreeSlot() {
        // Special case forward insertion from empty, when we know we must add to end
        if (slots.Length - freeSlots == sentinel) {
            return sentinel;
        }

        // no need to use sentinel here since early-outs on first free
        for (int i = 0; i < slotOccupancy.Length; ++i) {
            if (!slotOccupancy[i]) {
                return i;
            }
        }

        throw new Exception(string.Format(
            "Should never not find a free slot. freeSlots: {0} sentinel: {1} len: {2}",
            freeSlots, sentinel, slotOccupancy.Length));

    }

    /// <summary>
    /// Remove an item by value, freeing up its slot
    /// </summary>
    /// <param name="val">The value to remove</param>
    /// <returns>True if the item was actually removed</returns>
    public bool Remove(T val) {
        for (int i = 0; i < sentinel; ++i) {
            if (Object.Equals(val, slots[i])) {
                return RemoveAt(i);
            }
        }
        return false;
    }

    /// <summary>
    /// Remove an item at a given index
    /// </summary>
    /// <param name="i">The index at which to remove the item</param>
    /// <returns>True if there was an item there which was removed</returns>
    public bool RemoveAt(int i) {
        if (slotOccupancy[i]) {
            slotOccupancy[i] = false;
            slots[i] = default(T); // to ensure reftypes are nulled (GC)
            // retract sentinel if removing from end
            // we could re-scan to detect packing from all remove locations but
            // that would be more expensive
            if (i+1 == sentinel)
                --sentinel;
            ++freeSlots;
            return true;
        }
        return false;
    }

    /// <summary>
    /// Remove all items from the array.
    /// </summary>
    public void Clear() {
        for (int i = 0; i < sentinel; ++i) {
            slotOccupancy[i] = false;
        }
        freeSlots = slots.Length;
        sentinel = 0;
    }

    /// <summary>
    /// Return whether a given item is in the list.
    /// </summary>
    /// <param name="val"></param>
    /// <returns></returns>
    public bool Contains(T val) {
        for (int i = 0; i < sentinel; ++i) {
            // Value types could be equal even if defaulted so check occupancy
            if (slotOccupancy[i] && Object.Equals(val, slots[i])) {
                return true;
            }
        }
        return false;
    }

    /// <summary>
    /// Visit every item in the array with both its index and value
    /// </summary>
    /// <param name="visitor">Callback for each item. Arguments are index and value of
    /// each item, and the visitor function should return true to continue
    /// iterating, or false to stop.</param>
    public void Visit(Func<int, T, bool> visitor) {
        for (int i = 0; i < sentinel; ++i) {
            if (slotOccupancy[i]) {
                // visitor returns false to early-out
                if (!visitor(i, slots[i]))
                    return;
            }
        }
    }

    public IEnumerator<T> GetEnumerator() {
        for (int i = 0; i < sentinel; ++i) {
            if (slotOccupancy[i]) {
                yield return slots[i];
            }
        }
    }

    IEnumerator IEnumerable.GetEnumerator() {
        return GetEnumerator();
    }
}