Rethinking "Generic" Through the Origins of the STL
Looking back at my own C++ learning journey, I've noticed that many C++ tutorials on the market treat the STL as nothing more than the "containers + algorithms + iterators" trio, using it as a toolbox: grab whatever container you need #include, call std::sort when you need to sort. It's certainly convenient, and it truly lives up to the name "standard library" (everyone just uses it directly — I suspect unless something breaks, nobody is silently reciting the underlying template implementation while writing code!). But few people ever ask why it was designed this way. Digging into the history alongside Stepanov [1] Matt Godbolt, C++: Some Assembly Required, CppCon 2025, we discover something: the STL was never created to "provide containers." Its ultimate goal was to write a once-and-for-all sorting algorithm.
This might sound strange at first. What's so "once-and-for-all" about a sorting algorithm? When we study data structures, quicksort, merge sort, and heap sort are all written for arrays, aren't they? But if you write a quicksort that only sorts int[], what about double[]? What about std::string arrays? What about arrays of custom structs? The common approach is copy-paste: change int to T, and wrap it in a template. But in the early 1980s, Stepanov was pondering a far more radical question: could we write a sort that has absolutely no idea what it's sorting, yet still works?
Today, this idea just sounds like templates — nothing special. But in the context of that era, it was entirely different. Faced with the same challenge of "generic algorithms," Knuth's approach in The Art of Computer Programming [2] Donald Knuth, The Art of Computer Programming, 1968 was to invent a hypothetical computer [6] Wikipedia, MIX (abstract machine) (called MIX) along with its assembly language, MIXAL. He then used this machine language to precisely implement and analyze the running time and memory usage of all algorithms [7] Knuth, MMIX page, purpose of machine language in TAOCP. The core idea behind this path was to design a sufficiently abstract machine model, run algorithms on it, and thereby precisely measure the cost of every operation. Stepanov took the exact opposite path — he didn't need to abstract the machine; he needed to abstract the operations themselves that the algorithm relies on. Sorting doesn't need to know what it's sorting; it only needs to know that items can be compared and swapped. As long as those two things are possible, the sort works.
Once we understand this distinction, many previously fuzzy concepts become clear. For example, the real reason iterators exist — iterators aren't "generic pointers" at all. They are the contract Stepanov used to decouple algorithms from data structures. Algorithms don't operate on containers directly; they operate on iterators. The algorithm only depends on whatever operations the iterator provides. This is how algorithms truly achieve being "once-and-for-all."
What's even more interesting is that when Stepanov first implemented these ideas, he didn't even use C++. In his first paper in 1981, he used a language called Tecton [3] Kapur, Musser, Stepanov, Tecton language, 1981 — designed in collaboration with Deepak Kapur and David Musser, purely to express the concepts of generic programming. This detail shows that the idea of "generic programming" preceded the language. It wasn't that C++ had templates and therefore had generic programming; rather, Stepanov had the idea first, and then he needed a language to express it — first Tecton, then Scheme, then Ada, and finally C++. Templates, as a core C++ feature, are admittedly difficult to use — the error messages from SFINAE and concepts give many people headaches — but from another perspective, templates are merely the tool Stepanov used to realize his dream of "once-and-for-all algorithms." If we understand why they were designed this way, we won't resist them as much.
Following this line of thought, we can run an experiment to verify what "algorithms depending only on operation contracts" actually means. The code below doesn't use any STL containers; it purely uses raw arrays to run std::sort:
#include <algorithm>
#include <iostream>
int main() {
int arr[] = {5, 3, 1, 4, 2};
// std::sort 不关心你传的是什么容器
// 它只关心：迭代器是不是 RandomAccessIterator（能不能做加减法、能不能解引用）
// 元素能不能用 operator< 比较、能不能 swap 和移动
std::sort(std::begin(arr), std::end(arr));
for (int x : arr) {
std::cout << x << ' ';
}
// 输出: 1 2 3 4 5
}This looks unremarkable, but think about it carefully — there isn't a single line of code inside std::sort's implementation that knows arr is an array. All it sees are two pointers (in this scenario, the iterators are pointers). It needs to perform ++, --, +=, -=, *, and < on these pointers — this is actually the complete requirement set for a RandomAccessIterator [5] cppreference, std::sort, RandomAccessIterator requirements (random access + dereference + comparison), plus the swap and move semantics of the value type, for the sort to work. This is exactly what Stepanov wanted back then.
Taking it a step further, let's try a custom type:
#include <algorithm>
#include <iostream>
#include <string>
struct Person {
std::string name;
int age;
};
// 算法不关心 Person 是什么，它只关心能不能比较
// 这里我们告诉编译器——你可以比较两个Person对象，而且可以更加具体的说
// 是根据年龄比较的！
bool operator<(const Person& a, const Person& b) {
return a.age < b.age;
}
int main() {
Person people[] = {
{"Alice", 30},
{"Bob", 25},
{"Charlie", 35}
};
std::sort(std::begin(people), std::end(people));
for (const auto& p : people) {
std::cout << p.name << ": " << p.age << '\n';
}
// 输出:
// Bob: 25
// Alice: 30
// Charlie: 35
}std::sort still has no idea what Person is. It only knows that the expression *it < *it compiles. If you provide <, it can sort; if you don't, the compiler throws an error — the error message is admittedly ugly, but the behavior itself is incredibly clean. (A small part of the work in modern C++ abstractions is specifically trying to fix these unreadable error messages!)
At this point, we can understand why the STL is called a "generic library" rather than a "container library." Containers are merely the carriers; the core is the algorithms. And the reason algorithms can be generic is that they are designed to depend only on a minimal set of operations. This idea isn't unique to C++. Stepanov validated it in Tecton, then validated it again in Scheme and Ada, and finally found that C++'s template system could express this idea most directly — which gave us the STL we see today. When learning the STL, we can spend our energy on how to use vector, map, and unordered_map, but we really shouldn't just stop there. It's even more worthwhile to spend time understanding the algorithm layer. Containers can be swapped out — we can even use our own data structures — but the design philosophy of the algorithms is the true soul of the entire STL.
From Explicit to Implicit Instantiation: The Story of How the STL Almost Didn't Make It Into C++
I felt particularly moved when I read this piece of history. We write templates every day and enjoy the convenience of implicit instantiation, but few people ever consider — if Bjarne hadn't trusted his instincts back then, the C++ we write today might look completely different.
First, Let's Clarify What "Explicit Instantiation" Actually Looks Like
Before telling this story, it's necessary to understand what the "explicit instantiation" Stepanov saw in Ada actually meant — many people's understanding of this concept has always been vague.
Explicit instantiation means that before using a generic function, you must tell the compiler in advance: "I need an int version, I need a double version." The compiler won't deduce it for you; if you don't say it, it won't generate the code. And the templates we write in C++ today? We write a function with template<typename T>, pass in a int when calling it, and the compiler automatically replaces T with int and generates the corresponding code — that's implicit instantiation.
To intuitively feel the difference, let's look at a comparison. First, a style simulating "explicit instantiation" — of course, this isn't real Ada syntax, but it uses C++ concepts to express the idea:
// 模拟 Ada 风格的显式实例化
// 你必须提前声明"我要哪些类型的版本"
template<typename T>
T my_accumulate(T* begin, T* end, T init) {
for (T* p = begin; p != end; ++p) {
init = init + *p;
}
return init;
}
// 显式实例化声明：告诉编译器"我需要这两个版本"
template int my_accumulate<int>(int*, int*, int);
template double my_accumulate<double>(double*, double*, double);
int main() {
int arr[] = {1, 2, 3, 4, 5};
// 编译器看到调用，发现已经有 int 版本的实例了，直接用
int sum = my_accumulate(arr, arr + 5, 0);
// double arr2[] = {1.0, 2.0, 3.0};
// double sum2 = my_accumulate(arr2, arr2 + 3, 0.0);
// 如果取消上面两行注释，但没有提前声明 double 版本，
// 在纯显式实例化的模型下，这会直接报错
}Then there's the implicit instantiation we're all used to, which is C++'s actual approach:
#include <iostream>
template<typename T>
T my_accumulate(T* begin, T* end, T init) {
for (T* p = begin; p != end; ++p) {
init = init + *p;
}
return init;
}
int main() {
int arr1[] = {1, 2, 3, 4, 5};
int sum1 = my_accumulate(arr1, arr1 + 5, 0);
std::cout << sum1 << "\n"; // 15
double arr2[] = {1.5, 2.5, 3.5};
double sum2 = my_accumulate(arr2, arr2 + 3, 0.0);
std::cout << sum2 << "\n"; // 7.5
// 你甚至可以传一个从来没提前声明过的类型，
// 编译器在调用点自动推导、自动生成
long arr3[] = {10L, 20L, 30L};
long sum3 = my_accumulate(arr3, arr3 + 3, 0L);
std::cout << sum3 << "\n"; // 60
}See? In the second approach, there's no advance declaration saying "I need an int version, a double version, a long version." The compiler deduces what T is at each call site and generates the corresponding function body on the spot. That is the power of implicit instantiation.
Why Stepanov Initially Thought Explicit Was Better
At first glance, explicit instantiation is clearly more cumbersome — why would a genius algorithm designer think this was better?
It makes sense from Stepanov's perspective. He came from the more "mathematical" environments of Ada and Scheme. In mathematics, when you define a function, you know exactly which set it operates on. accumulate acting on a sequence of integers is the integer version; acting on a sequence of reals is the real version — these are two different things and should be stated explicitly. Furthermore, from an engineering standpoint, explicit instantiation gives you complete control over "exactly which code gets generated," preventing issues like template instantiation explosion.
This idea isn't stupid at all. In fact, even today, C++ retains the syntax for explicit instantiation (the template int func<int>(...) syntax shown above). In large projects sensitive to compile times, centralizing template instantiations in a single .cpp file is a common optimization technique. So Stepanov's intuition had its merits.
Why Bjarne Insisted on Implicit
But Bjarne saw something Stepanov didn't.
The key lies in the STL's core design philosophy: algorithms should not be bound to specific types; they should be bound to the "concepts satisfied by iterators." accumulate doesn't care whether you're accumulating int, double, or some custom BigNum. It only cares that the iterator can be dereferenced, and that the value type supports + and =.
With explicit instantiation, every time you want to support a new type, you have to go back and add an explicit instantiation declaration. This means the algorithm author must know all possible types in advance — but this completely violates the original intent of generic programming! The whole point of generic programming is "I write it once, you take it and use it, regardless of your type, as long as you meet my requirements." Generic programming is a posteriori to the implementation itself — the compiler instantiates whatever code it deems necessary. Explicit declaration takes a step backward here!
Implicit instantiation made this a reality: algorithm authors write templates, type authors write types, and the two sides are completely decoupled, with the compiler acting as the bridge in between. Without this mechanism, the STL's three-layer decoupled architecture of "algorithm + iterator + type" simply could not have been built.
Looking Back, It Doesn't Seem So Hard
Today, looking back at the "explicit instantiation vs. implicit instantiation" debate, the answer seems obvious. But this was the late 1980s and early 1990s. C++ templates themselves were still rough; no one had written a template library on the scale of the STL, and no one knew whether implicit instantiation could actually scale. Bjarne made this judgment without any precedent, and he was right. When learning C++, it's easy to feel that "these designs are a matter of course." But the truth is, behind every line of standard library code, there might be a story of "it almost went down a completely different path." Understanding this context is far more interesting than simply memorizing syntax, and it helps us much more in understanding "why C++ is the way it is."