Pieces of the standard library, rebuilt by hand. Written for the C++ courses at MIPT and kept because writing these is still the fastest way to find out what the standard library actually promises, as opposed to what you assume it promises.
Each directory is a single self-contained header. That was the submission format, which is
why matrix/matrix.h carries its own copy of BigInteger and Rational rather than
including biginteger/.
unordered_map/ — an UnorderedMap built on top of a hand-written intrusive doubly
linked List. The elements live in the list; the bucket table is a vector of iterator pairs
delimiting each bucket's run inside it. Allocator-aware the whole way down through
std::allocator_traits: node types obtained with rebind_alloc, copies going through
select_on_container_copy_construction, assignment respecting
propagate_on_container_copy_assignment. That last part is the one nobody gets right by
accident, and the reason to write the container at all.
deque/ — a Deque over a map of fixed-size buckets, the way std::deque actually
works rather than the way people assume it does. The interesting code is the iterator: it
holds both the element pointer and the bucket pointer, so += n has to divide by the bucket
size and carry, and negative offsets need their own rounding. Random access is O(1), and
pushing at either end does not move the elements already there.
shared_ptr/ — SharedPtr and WeakPtr over a polymorphic control block, with two
implementations behind it. ControlBlockDirect is what you get from a raw pointer: it stores
the deleter and the allocator alongside the counts. ControlBlockViaMakeShared stores the
object inside the block, so makeShared performs one allocation where the two-step version
performs two. Both counts live in the block, which is what lets a WeakPtr outlive the
object without outliving the bookkeeping.
list_and_allocator/ — StackStorage<N> plus a StackAllocator over it: a bump
allocator on an array with no heap involved, aligning each request by hand, with rebind and
operator== so a container can actually adopt it. Paired with a List to prove the
container survives a stateful allocator.
biginteger/ — arbitrary-precision BigInteger, including division and modulo, which is
the part that is genuinely awkward. On top of it, Rational: exact arithmetic with
normalisation, so no rounding happens anywhere in the chain.
matrix/ — Matrix<N, M, Field> with the dimensions in the type. Multiplication that
does not typecheck cannot be written, and det, trace, rank and inverted are guarded
by static_assert(N == M). Gaussian elimination underneath, generic over the field.
The field can be Residue<N>, arithmetic modulo N — and Z/N is a field only when N is prime.
So operator/= carries static_assert(IsSimple<N>::ans), where IsSimple is a template
recursion doing trial division at compile time and stopping once the divisor squared passes
N. Adding and multiplying modulo 4 compiles. Dividing modulo 4 does not, and the compiler
says so rather than the program discovering it later.
string/ — the earliest thing here and it shows: a plain dynamic buffer with geometric
growth, no small-string optimisation, no allocator support.
This is student code from 2022–2023, preserved rather than maintained. There is no build system and no test suite in this repository; the courses ran these headers against their own graders. The newer C++ I would rather be judged on is elsewhere.