Sequence Containers
Overview
Sequence Containers store data linearly, one item immediately after another. The undisputed king of the STL is `std::vector`. It is a dynamic array that automatically grows larger as you add items to it. Because its underlying memory is physically contiguous (side-by-side) in RAM, it provides blazing fast $O(1)$ random access and maximizes CPU Cache efficiency.
Other sequence containers include std::list (A Doubly-Linked List, great for inserting data in the middle but terrible for random access) and std::deque (A Double-Ended Queue, optimized for inserting data at both the front and the back).
Syntax
#include <iostream>
#include <vector>
int main() {
// 1. Creation (Dynamic Size)
std::vector<int> scores;
// 2. Adding data to the end (Dynamically resizes!)
scores.push_back(100);
scores.push_back(200);
scores.push_back(300);
// 3. Blazing fast O(1) random access
std::cout << scores[1] << "\n"; // 200
// 4. Checking metadata
std::cout << "Size: " << scores.size() << "\n"; // 3
std::cout << "Capacity: " << scores.capacity() << "\n"; // Often 4 (Pre-allocated)
return 0;
}Common Pitfalls
Vector Reallocation (The 'push_back' performance trap). When a Vector gets full, it has to find a new, larger block of RAM, physically copy every single item over, and delete the old block. If you
push_back1,000,000 items in a loop, it reallocates constantly, crippling performance. Always usevec.reserve(1000000);before the loop if you know the size!
Interview Questions
If std::list (Linked List) allows blazing fast $O(1)$ insertions in the middle of data, why does the C++ standard emphatically recommend using std::vector by default?
A Linked List scatters its nodes randomly across the RAM. When the CPU tries to read it, it suffers massive 'Cache Misses', having to fetch data from slow main memory constantly. A Vector stores everything in a single solid block. The CPU pre-fetches the entire block into the ultra-fast L1 Cache. A Vector is often significantly faster than a List even when doing insertions, purely because of hardware cache architecture.
Real-World Example
Using emplace_back in modern C++ (C++11) to construct objects directly inside the vector, entirely bypassing the expensive copy-constructor overhead of push_back.
#include <iostream>
#include <vector>
#include <string>
class Player {
public:
std::string name;
Player(std::string n) : name(n) { std::cout << "Built!\n"; }
};
int main() {
std::vector<Player> roster;
// push_back builds the object locally, then COPIES it into the vector (Slow)
roster.push_back(Player("Alice"));
// emplace_back takes the arguments and builds the object DIRECTLY inside the vector's memory (Fast!)
roster.emplace_back("Bob");
return 0;
}Check Your Knowledge
Test your understanding of Sequence Containers with these quick questions.