Large templated projects are slow to compile, the STL being a main culprit of this it seems from empiric evidence. But, why is it slow to compile?
I've optimized builds before by watching for header includes and by combining compilation units, but I don't get why template libraries are quite so slow to compile.
Part of the answer is in your question. You can't watch for header includes with templates, because the full implementation must be included into every compilation unit that uses them.
C++ in general is slow to compile because of the ancient include mechanism, which causes the compiler to recursively re-parse every header with all its declarations and definitions and all that's included for every translation unit.
Templates just build on that "feature". But they require all code to be in headers, too, forcing the compiler to also re-parse all implementations of all templates included.
Templated code has to be taken as another language to generate C++ code.
In this way of thinking, templated code has to be parsed, executed, then the compiler can generate C++ code that has to be added to the current unit file, and then we can compile the whole C++ code.
I've heard that not all compilers do this exactly but that's the main idea, and that suppose that there is a lot more happening before really compiling the code as some of the code has to be generated first.
Think about what a real-world template is -- it's not an actual thing, but directions on how to build actual things.
In the case of C++ templates, the header file doesn't contain an actual, e.g. 'vector', but instructions on how to build a vector. Every time we build a source file that #includes <vector>, the compiler has to build new vector code, perhaps multiple times if we are instantiating vectors with different template parameters.
The build of each source file is independent, and doesn't know if you've already built a vector for another source file, so it builds a new one each time.