13.5. The Standard Template Library (STL)

The 1976 book Algorithms + Data Structures = Programs by Niklaus Wirth suggests that algorithms and data structures are an integral part of programs. We can view every non-trivial problem we solve with a program as a sequence of story problems. We solve each story problem with an algorithm, either a well-known algorithm or one we design specifically for the problem. Every algorithm uses data spanning a broad spectrum from single variables to binary trees to complex databases. The compiler can process single variables, arrays, structures, and classes but can't deal directly with more complex organizations without becoming overly complex and slow. Although the complex structures are inappropriate as language primitives, they are too beneficial to ignore. The previous example demonstrates that programmers can create data structures like binary trees, but doing so distracts us from the algorithm we're currently trying to implement.

Most general-purpose programming languages provide libraries of common, frequently-used data structures. However, these libraries of ready-made data structures don't absolve programmers of the responsibility for understanding them. Application (i.e., "real world") programs often manipulate large volumes of data, and how they organize it profoundly impacts program efficiency and effectiveness. A program's efficiency governs the data size that it can successfully handle, and a program based on poorly organized data may work well with a dozen data items but prove completely unusable for two dozen. Computer scientists must know which data structure to use for a particular problem. The advantages and disadvantages of many well-known data structures are the primary topics of a "Data Structures and Algorithms" course.

One C++ library, The Standard Template Library or STL, provides many common and beneficial data structures. As suggested by its name, the STL relies on templates to make the structures general.