Lesson 173 +10 XP

Data Structures and the STL

A data structure is a way to organize data so that a program can store it, find it, and change it quickly. The same collection of values can be arranged several different ways, and every design is good at some operations and weak at others.

The three pieces of the STL

The STL (short for Standard Template Library) is C++'s ready-made toolbox, built with templates. It gives you:

Containers - objects that hold a collection of elements.
Algorithms - functions that process the collections (sort, find, count).
Iterators - objects that let the algorithms move through a container.

You do not have to rewrite a linked list or a sorting routine; the library has working, tested ones already.

The containers at a glance

Container	The idea behind it
`std::vector`	A growable array
`std::list`	A doubly-linked chain of nodes
`std::stack`	Last in, first out
`std::queue`	First in, first out
`std::deque`	Add and remove at both ends
`std::set`	Unique values, kept sorted
`std::map`	Keys that point to values

Include the header you use

Each container lives in its own header. Tell the compiler which one you are asking for:

#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>

Forgetting the #include is a classic first STL mistake: the compiler has never heard of std::vector and refuses to build.

Why the structure you pick matters

There is no single best container. Reading vector[5] is instant, but inserting at the front of a vector is slow. A list inserts in the middle cheaply but cannot jump straight to entry 42. A map finds values by key quickly. Think about which operations your problem needs most, then choose the container that matches.

TL;DR

The STL bundles containers, algorithms, and iterators.
Data structures exist because different operations have different costs.
Each container comes in its own header: #include <vector>, #include <list>, and so on.
Pick the container whose strengths fit the operations your problem needs.

Data Structures and the STL