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
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.