C++ Data Structures and STL

🧩 C++ Data Structures and STL (Standard Template Library)

Data Structures organize data efficiently, and the STL provides ready-made, high-performance implementations using templates.
STL saves time, reduces bugs, and is the standard way to work with collections in modern C++.

🔹 1. What Is STL?

The STL is a collection of generic classes and functions. It has four main components:

  1. Containers – store data

  2. Algorithms – process data

  3. Iterators – traverse data

  4. Functors (function objects) – customizable behavior

🔹 2. STL Containers

🔸 Sequence Containers (ordered, indexed)

  • vector – dynamic array (most used)

  • deque – double-ended queue

  • list – doubly linked list

  • array – fixed-size array (C++11)

  • forward_list – singly linked list

#include <vector>
vector<int> v = {1, 2, 3};
v.push_back(4);

🔸 Associative Containers (sorted)

  • set – unique keys

  • multiset – duplicate keys

  • map – key–value, unique keys

  • multimap – key–value, duplicate keys

#include <map>
map<string, int> marks;
marks["Amit"] = 90;

🔸 Unordered Containers (hash-based, fast)

  • unordered_set

  • unordered_map

  • unordered_multiset

  • unordered_multimap

#include <unordered_map>
unordered_map<int, string> um;
um[1] = "One";

🔸 Container Adapters

  • stack – LIFO

  • queue – FIFO

  • priority_queue – heap (max by default)

#include <stack>
stack<int> s;
s.push(10);

🔹 3. STL Algorithms (<algorithm>)

Common algorithms (work with iterators):

#include <algorithm>
sort(v.begin(), v.end()); // sort
reverse(v.begin(), v.end()); // reverse
find(v.begin(), v.end(), 3); // search
count(v.begin(), v.end(), 2); // count

With lambda:

sort(v.begin(), v.end(), [](int a, int b){ return a > b; });

🔹 4. Iterators

Iterators act like pointers to container elements.

for (auto it = v.begin(); it != v.end(); ++it) {
cout << *it << " ";
}

Types:

  • Input, Output

  • Forward, Bidirectional

  • Random Access (e.g., vector)

🔹 5. Functors (Function Objects)

Objects that behave like functions.

struct Square {
int operator()(int x) const {
return x * x;
}
};

Square sq;
cout << sq(5); // 25

Often replaced by lambdas today.

🔹 6. Choosing the Right Data Structure

Use CaseBest Choice
Fast indexingvector, array
Frequent insert/delete (middle)list
Sorted unique dataset
Key–value lookupmap
Fast hash lookupunordered_map
LIFOstack
FIFOqueue

🔹 7. Complexity (Big-O Highlights)

  • vector access: O(1)

  • map insert/search: O(log n)

  • unordered_map average search: O(1)

  • set insert/search: O(log n)

  • sort: O(n log n)

🔹 8. Example: Word Frequency Counter

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int main() {
unordered_map<string, int> freq;
string word;

while (cin >> word) {
freq[word]++;
}

for (auto &p : freq) {
cout << p.first << " : " << p.second << endl;
}
}

🔹 9. STL vs Custom Data Structures

STLCustom
Tested & optimizedRisk of bugs
Faster developmentMore control
GenericSpecific
StandardCustom behavior

🔹 10. Best Practices

  • Prefer STL containers over raw arrays

  • Use auto with iterators

  • Pass containers by const&

  • Use unordered_* for speed, map/set for order

  • Combine algorithms + lambdas for clean code

📌 Summary

  • STL provides ready-made data structures & algorithms

  • Containers store data; algorithms process it

  • Iterators connect containers and algorithms

  • Use the right container for the problem

  • Essential for interviews and real-world C++ projects

You may also like...