Learn C++ - Data Structures & STL Containers

#Introduction

Writing your own data structures — linked lists, hash tables, trees — is a good academic exercise, but in the real world you'll almost never need to. The Standard Template Library (STL) provides containers that are tested, efficient, and safe.

Episode 8 introduces the STL systematically: sequence containers for ordered data, associative containers for fast lookup, iterators as the universal bridge, ready-made std::algorithm algorithms, and container adaptors for stack and queue patterns. Choosing the right container is one of the most impactful design decisions on program performance.

#Sequence Containers

#std::vector, std::array, and std::deque

std::vector is the default container: a dynamic array that grows automatically with contiguous memory. std::array is a fixed-size array on the stack. std::deque supports fast insertion and removal at both ends. std::list is a doubly-linked list with O(1) insertion at any position:

cat > sequence.cpp <<'EOF'
#include <iostream>
#include <vector>
#include <array>
#include <deque>
 
int main() {
    std::vector<int> v{1, 2, 3};
    v.push_back(4);
    std::cout << "vector: " << v.size() << " elemen\n";
 
    std::array<int, 3> a{10, 20, 30};
    std::cout << "array: " << a[1] << "\n";
 
    std::deque<int> d;
    d.push_back(5);
    d.push_front(1);
    std::cout << "deque depan: " << d.front() << "\n";
}
EOF
g++ -std=c++20 sequence.cpp -o sequence
./sequence

v.push_back(4) appends an element to the end of the vector. std::array<int, 3> stores the element type and size as part of the type, so this array doesn't leak memory and can be used like a regular array.

#Choosing a Container

The rule of thumb: default to std::vector. vector has the best cache locality because its elements are adjacent in memory. Use deque if you often insert/delete at both ends, list is rarely used because its random access is slow, and std::array if the size is known at compile time.

#Associative Containers

#std::set, std::map, and std::unordered_map

std::set stores unique sorted elements. std::map stores key-value pairs with unique, sorted keys. std::unordered_map uses a hash table so lookup is O(1) on average, but the order isn't guaranteed. std::string is also a container — you can iterate over its characters:

cat > assosiatif.cpp <<'EOF'
#include <iostream>
#include <map>
#include <set>
#include <unordered_map>
 
int main() {
    std::map<std::string, int> umur;
    umur["Arman"] = 28;
    umur["Budi"] = 30;
 
    std::cout << "Umur Arman: " << umur["Arman"] << "\n";
    std::cout << "Key terurut: ";
    for (const auto& [nama, u] : umur) {
        std::cout << nama << " ";
    }
    std::cout << "\n";
 
    std::set<int> unik{3, 1, 2, 3, 1};
    std::cout << "Set berisi: " << unik.size() << " elemen\n";
 
    std::unordered_map<int, std::string> cepat;
    cepat[42] = "answer";
    std::cout << cepat[42] << "\n";
}
EOF
g++ -std=c++20 assosiatif.cpp -o assosiatif
./assosiatif

for (const auto& [nama, u] : umur) uses structured bindings (C++17) to unpack key-value pairs. std::set<int> unik{3, 1, 2, 3, 1} automatically removes duplicates. Choose map when you need key order, unordered_map when you need lookup speed.

#Iterators and the std::algorithm Algorithms

#Iterators as the Bridge

An iterator is an object that walks along a container like a pointer. Containers provide begin() and end(), and all STL algorithms work on these iterator pairs — that's why one algorithm can be used for all containers:

cat > algoritma.cpp <<'EOF'
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
 
int main() {
    std::vector<int> v{5, 2, 8, 1, 9};
 
    std::sort(v.begin(), v.end());
    std::cout << "Terurut: ";
    for (int x : v) std::cout << x << " ";
    std::cout << "\n";
 
    auto maks = *std::max_element(v.begin(), v.end());
    std::cout << "Maksimum: " << maks << "\n";
 
    int total = std::accumulate(v.begin(), v.end(), 0);
    std::cout << "Total: " << total << "\n";
}
EOF
g++ -std=c++20 algoritma.cpp -o algoritma
./algoritma

std::sort(v.begin(), v.end()) sorts the whole vector, std::accumulate(v.begin(), v.end(), 0) sums the elements. Since C++20, there are more concise ranges variants without explicit begin() and end() — episode 16 will cover them.

#Container Adaptors

#stack, queue, and priority_queue

Container adaptors wrap a base container with a restricted interface. std::stack works with the LIFO pattern (last in, first out). std::queue with the FIFO pattern. std::priority_queue always pops the largest element:

cat > adaptor.cpp <<'EOF'
#include <iostream>
#include <stack>
#include <queue>
 
int main() {
    std::stack<int> s;
    s.push(1);
    s.push(2);
    std::cout << "Stack top: " << s.top() << "\n";
 
    std::queue<int> q;
    q.push(10);
    q.push(20);
    std::cout << "Queue depan: " << q.front() << "\n";
 
    std::priority_queue<int> pq;
    pq.push(5);
    pq.push(15);
    pq.push(10);
    std::cout << "Priority teratas: " << pq.top() << "\n";
}
EOF
g++ -std=c++20 adaptor.cpp -o adaptor
./adaptor

pq.top() always returns the largest element because priority_queue is a max-heap. The stack pattern is used for undo operations and parsing, the queue for work queues, and priority_queue for task schedulers — episode 12 will use them again in the concurrency context.

#Conclusion

Here's what to take away:

• std::vector is the default container with the best cache locality.
• std::array for fixed sizes, std::deque for two-ended access.
• std::set and std::map are sorted; std::unordered_map has O(1) lookup.
• Iterators connect containers with algorithms universally.
• std::sort, max_element, and accumulate replace manual code.
• stack, queue, and priority_queue wrap containers for specific patterns.

In the next episode, episode 9, we'll discuss input/output and file handling — the basic std::istream and std::ostream streams, file I/O with std::ifstream, std::ofstream, and std::fstream, formatted input output with manipulators, binary I/O, as well as error handling for file operations.