A data structure with: O(1) random access, O(1) insertion, and O(1) deletion.

randset.d

/**
 * data structure with:
 *  O(1) random access
 *  O(1) insertion
 *  O(1) deletion
 *  O(1) containment
 */
class RandomAccessSet(T)
{
	private {
		size_t size;
		T[] array;
		size_t[T] indexMap;
	}

	this() {
		size = 0;
		array.length = 1;
	}

	auto add(T item) {
		if (item in indexMap) return false;
		indexMap[item] = size;
		if (size == array.length) {
			array.length *= 2;
		}
		array[size++] = item;
		return true;
	}

	auto remove(T item) {
		if (item !in indexMap) return false;
		auto index = indexMap[item];
		--size;
		swap(index, size);
		indexMap[array[index]] = index;
		return indexMap.remove(item);
	}

	private auto swap(size_t a, size_t b) {
		auto tmp = array[a];
		array[a] = array[b];
		array[b] = tmp;
	}

	bool contains(T item) {
		return (item in indexMap) != null;
	}

	T getRandom() {
		import std.random;
		auto i = uniform(0, size);
		return array[i];
	}

	int opApply(int delegate(ref T) dg) {
		int result = 0;
		foreach (i; 0 .. size) {
			result = dg(array[i]);
			if (result) break;
		}
		return result;
	}

	override
	string toString() {
		import std.conv;
		return text(array);
	}
}