But putting tens of thousands of lines of basic library code into headers isn't commonly done in the C ecosystem for very good reasons--e.g. ability to fix a bug or improve performance[1] without having to recompile dependent binaries.

That said, in the BSD universe there are linked-list and tree implementations provided in <sys/queue.h> and <sys/tree.h> that are almost universally used, in both the kernel and userland. The macro definitions might be uglier than templates but no less typesafe and nobody forces you to look at the headers. Unlike sorting and hash algorithms 1) these never change and 2) they make it possible to create intrusive (space-efficient, zero-allocation) data structures, so it just makes sense to provide them in headers.

[1] qsort is not always implemented using quicksort. In fact, I think it's the exception rather than the norm.

I haven't ever seen std::vector using in-place realloc when resizing. The implementations I've seen simply always allocate a larger vector and copy the elements over.

Realloc tries to expand already allocated memory region if there's enough space immediately after current block. New allocation and copy is only done when this is not possible.