The Standard Template Library (STL) is a powerful feature of C++ that provides a set of common data structures and algorithms. It’s a must-know for any C++ programmer who wants to write efficient and maintainable code. In this tutorial, we will dive deep into the STL, covering its various components and showing you how to leverage them effectively in your programs.
1. Introduction to STL
What is STL?
The Standard Template Library (STL) is a set of C++ template classes to provide common programming data structures and functions such as lists, stacks, arrays, etc. It is a library of container classes, algorithms, and iterators.
Advantages of Using STL
- Reusability: STL provides ready-to-use implementations of common data structures and algorithms.
- Efficiency: STL algorithms are typically optimized for performance.
- Consistency: Using STL ensures that your code is consistent and follows the same conventions and practices as other C++ code.
- Generic Programming: STL uses templates, which means you can use the same code with different data types without rewriting it.
2. Containers
Containers are the foundation of the STL. They store collections of objects. Containers can be broadly categorized into three types: Sequence Containers, Associative Containers, and Unordered Containers.
Sequence Containers
Vector
std::vector is a dynamic array that can change size automatically when elements are added or removed. It provides fast random access and is efficient for insertions and deletions at the end.
#include <vector>
#include <iostream>
int main() {
std::vector<int> v = {1, 2, 3, 4, 5};
v.push_back(6); // Adds 6 at the end
v.pop_back(); // Removes last element
for (int i : v) {
std::cout << i << " ";
}
return 0;
}Code language: C++ (cpp)List
std::list is a doubly linked list. It allows fast insertions and deletions from anywhere in the sequence.
#include <list>
#include <iostream>
int main() {
std::list<int> l = {1, 2, 3, 4, 5};
l.push_back(6); // Adds 6 at the end
l.push_front(0); // Adds 0 at the beginning
for (int i : l) {
std::cout << i << " ";
}
return 0;
}Code language: C++ (cpp)Deque
std::deque is a double-ended queue that allows fast insertions and deletions at both the beginning and the end.
#include <deque>
#include <iostream>
int main() {
std::deque<int> d = {1, 2, 3, 4, 5};
d.push_back(6); // Adds 6 at the end
d.push_front(0); // Adds 0 at the beginning
for (int i : d) {
std::cout << i << " ";
}
return 0;
}Code language: C++ (cpp)Associative Containers
Set
std::set is a collection of unique keys, sorted by the keys themselves.
#include <set>
#include <iostream>
int main() {
std::set<int> s = {1, 2, 3, 4, 5};
s.insert(6); // Inserts 6
s.erase(3); // Removes 3
for (int i : s) {
std::cout << i << " ";
}
return 0;
}Code language: C++ (cpp)Map
std::map is a collection of key-value pairs, sorted by keys.
#include <map>
#include <iostream>
int main() {
std::map<int, std::string> m;
m[1] = "one";
m[2] = "two";
m[3] = "three";
for (const auto &p : m) {
std::cout << p.first << " => " << p.second << "\n";
}
return 0;
}Code language: C++ (cpp)Multiset and Multimap
std::multiset and std::multimap allow duplicate keys.
#include <set>
#include <map>
#include <iostream>
int main() {
std::multiset<int> ms = {1, 2, 2, 3, 3, 3};
std::multimap<int, std::string> mm;
mm.insert({1, "one"});
mm.insert({2, "two"});
mm.insert({2, "dos"});
for (int i : ms) {
std::cout << i << " ";
}
std::cout << "\n";
for (const auto &p : mm) {
std::cout << p.first << " => " << p.second << "\n";
}
return 0;
}Code language: C++ (cpp)Unordered Containers
Unordered containers use hashing for faster access compared to ordered containers.
Unordered Set
std::unordered_set is a collection of unique keys with no particular order.
#include <unordered_set>
#include <iostream>
int main() {
std::unordered_set<int> us = {1, 2, 3, 4, 5};
us.insert(6);
us.erase(3);
for (int i : us) {
std::cout << i << " ";
}
return 0;
}Code language: C++ (cpp)Unordered Map
std::unordered_map is a collection of key-value pairs with no particular order.
#include <unordered_map>
#include <iostream>
int main() {
std::unordered_map<int, std::string> um;
um[1] = "one";
um[2] = "two";
um[3] = "three";
for (const auto &p : um) {
std::cout << p.first << " => " << p.second << "\n";
}
return 0;
}Code language: C++ (cpp)Unordered Multiset and Unordered Multimap
std::unordered_multiset and std::unordered_multimap allow duplicate keys with no particular order.
#include <unordered_set>
#include <unordered_map>
#include <iostream>
int main() {
std::unordered_multiset<int> ums = {1, 2, 2, 3, 3, 3};
std::unordered_multimap<int, std::string> umm;
umm.insert({1, "one"});
umm.insert({2, "two"});
umm.insert({2, "dos"});
for (int i : ums) {
std::cout << i << " ";
}
std::cout << "\n";
for (const auto &p : umm) {
std::cout << p.first << " => " << p.second << "\n";
}
return 0;
}Code language: C++ (cpp)Container Adapters
Container adapters provide a different interface for sequential containers.
Stack
std::stack is a container adapter that gives the functionality of a stack (LIFO).
#include <stack>
#include <iostream>
int main() {
std::stack<int> st;
st.push(1);
st.push(2);
st.push(3);
while (!st.empty()) {
std::cout << st.top() << " ";
st.pop();
}
return 0;
}Code language: C++ (cpp)Queue
std::queue is a container adapter that gives the functionality of a queue (FIFO).
#include <queue>
#include <iostream>
int main() {
std::queue<int> q;
q.push(1);
q.push(2);
q.push(3);
while (!q.empty()) {
std::cout << q.front() << " ";
q.pop();
}
return 0;
}Code language: C++ (cpp)Priority Queue
std::priority_queue is a container adapter that provides the functionality of a heap.
#include <queue>
#include <iostream>
int main() {
std::priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(2);
while (!pq.empty
()) {
std::cout << pq.top() << " ";
pq.pop();
}
return 0;
}Code language: C++ (cpp)3. Iterators
Iterators are used to point at the memory addresses of STL containers. They are primarily used in sequence of numbers, characters, etc.
Input Iterators
Input iterators can read from the container.
#include <vector>
#include <iostream>
int main() {
std::vector<int> v = {1, 2, 3, 4, 5};
std::vector<int>::iterator it;
for (it = v.begin(); it != v.end(); ++it) {
std::cout << *it << " ";
}
return 0;
}Code language: C++ (cpp)Output Iterators
Output iterators can write to the container.
#include <vector>
#include <iostream>
#include <iterator>
int main() {
std::vector<int> v(5);
std::vector<int>::iterator it;
int value = 1;
for (it = v.begin(); it != v.end(); ++it) {
*it = value++;
}
for (int i : v) {
std::cout << i << " ";
}
return 0;
}Code language: C++ (cpp)Forward Iterators
Forward iterators can read/write from/to the container in a forward direction.
#include <list>
#include <iostream>
int main() {
std::list<int> l = {1, 2, 3, 4, 5};
std::list<int>::iterator it;
for (it = l.begin(); it != l.end(); ++it) {
std::cout << *it << " ";
}
return 0;
}Code language: C++ (cpp)Bidirectional Iterators
Bidirectional iterators can move in both directions.
#include <list>
#include <iostream>
int main() {
std::list<int> l = {1, 2, 3, 4, 5};
std::list<int>::reverse_iterator it;
for (it = l.rbegin(); it != l.rend(); ++it) {
std::cout << *it << " ";
}
return 0;
}Code language: C++ (cpp)Random Access Iterators
Random access iterators can move anywhere in the container.
#include <vector>
#include <iostream>
int main() {
std::vector<int> v = {1, 2, 3, 4, 5};
std::vector<int>::iterator it;
it = v.begin();
std::cout << *(it + 2) << "\n"; // Random access
return 0;
}Code language: C++ (cpp)4. Algorithms
The STL provides many algorithms that work on iterators to perform various operations.
Non-modifying Algorithms
These algorithms do not modify the container.
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> v = {1, 2, 3, 4, 5};
// Find an element
auto it = std::find(v.begin(), v.end(), 3);
if (it != v.end()) {
std::cout << "Found: " << *it << "\n";
}
// Count elements
int count = std::count(v.begin(), v.end(), 3);
std::cout << "Count: " << count << "\n";
return 0;
}Code language: C++ (cpp)Modifying Algorithms
These algorithms modify the container.
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> v = {1, 2, 3, 4, 5};
// Fill
std::fill(v.begin(), v.end(), 0);
for (int i : v) {
std::cout << i << " ";
}
std::cout << "\n";
// Replace
std::replace(v.begin(), v.end(), 0, 1);
for (int i : v) {
std::cout << i << " ";
}
std::cout << "\n";
return 0;
}Code language: C++ (cpp)Sorting Algorithms
These algorithms sort the container.
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> v = {5, 3, 1, 4, 2};
// Sort
std::sort(v.begin(), v.end());
for (int i : v) {
std::cout << i << " ";
}
std::cout << "\n";
// Reverse
std::reverse(v.begin(), v.end());
for (int i : v) {
std::cout << i << " ";
}
std::cout << "\n";
return 0;
}Code language: C++ (cpp)Numeric Algorithms
These algorithms perform numeric operations on the container.
#include <numeric>
#include <vector>
#include <iostream>
int main() {
std::vector<int> v = {1, 2, 3, 4, 5};
// Accumulate
int sum = std::accumulate(v.begin(), v.end(), 0);
std::cout << "Sum: " << sum << "\n";
// Inner product
int product = std::inner_product(v.begin(), v.end(), v.begin(), 1);
std::cout << "Product: " << product << "\n";
return 0;
}Code language: C++ (cpp)5. Functional
STL also provides functional utilities that are used to manipulate functions and function objects.
Function Objects
Function objects or functors are objects that can be used as functions.
#include <iostream>
#include <vector>
#include <algorithm>
struct MultiplyBy {
int factor;
MultiplyBy(int f) : factor(f) {}
int operator()(int x) const { return x * factor; }
};
int main() {
std::vector<int> v = {1, 2, 3, 4, 5};
std::transform(v.begin(), v.end(), v.begin(), MultiplyBy(2));
for (int i : v) {
std::cout << i << " ";
}
return 0;
}Code language: C++ (cpp)Bind and Bind2nd
std::bind and std::bind2nd are used to bind arguments to functions or functors.
#include <iostream>
#include <functional>
int add(int a, int b) {
return a + b;
}
int main() {
auto add_five = std::bind(add, 5, std::placeholders::_1);
std::cout << add_five(3) << "\n"; // Outputs 8
return 0;
}Code language: C++ (cpp)Function and Mem_fn
std::function and std::mem_fn are used to store and call any callable object.
#include <iostream>
#include <functional>
struct Foo {
void print_sum(int a, int b) {
std::cout << a + b << "\n";
}
};
int main() {
Foo foo;
auto fn = std::mem_fn(&Foo::print_sum);
fn(foo, 3, 5);
return 0;
}Code language: C++ (cpp)Lambda Expressions
Lambda expressions are a convenient way to create anonymous function objects.
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> v = {1, 2, 3, 4, 5};
std::for_each(v.begin(), v.end(), [](int &x) { x *= 2; });
for (int i : v) {
std::cout << i << " ";
}
return 0;
}Code language: C++ (cpp)6. Utilities
STL also includes several utility functions and classes that simplify common programming tasks.
Pair and Tuple
std::pair and std::tuple are used to store fixed-size collections of heterogeneous values.
#include <iostream>
#include <utility>
#include <tuple>
int main() {
std::pair<int, std::string> p = std::make_pair(1, "one");
std::cout << p.first << " => " << p.second << "\n";
std::tuple<int, std::string, double> t = std::make_tuple(1, "one", 3.14);
std::cout << std::get<0>(t) << " => " << std::get<1>(t) << " => " << std::get<2>(t) << "\n";
return 0;
}Code language: C++ (cpp)Move Semantics
Move semantics allows the resources owned by an rvalue to be moved rather than copied.
#include <iostream>
#include <vector>
int main() {
std::vector<int> v1 = {1, 2, 3, 4, 5};
std::vector<int> v2 = std::move(v1); // v1 is now empty
for (int i : v2) {
std::cout << i << " ";
}
std::cout << "\n";
std::cout << "v1 size: " << v1.size() << "\n"; // v1 size: 0
return 0;
}Code language: C++ (cpp)Forwarding
Forwarding allows you to pass arguments while preserving their value category (lvalue or rvalue).
#include <iostream>
#include <utility>
void print(int &x
) {
std::cout << "lvalue: " << x << "\n";
}
void print(int &&x) {
std::cout << "rvalue: " << x << "\n";
}
template <typename T>
void forward_print(T &&x) {
print(std::forward<T>(x));
}
int main() {
int a = 10;
forward_print(a); // Calls lvalue version
forward_print(20); // Calls rvalue version
return 0;
}Code language: C++ (cpp)7. Practical Examples
Implementing Common Algorithms
Let’s implement a few common algorithms using STL.
Finding the Maximum Element
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> v = {1, 3, 5, 7, 2, 4, 6};
auto max_elem = std::max_element(v.begin(), v.end());
std::cout << "Max element: " << *max_elem << "\n";
return 0;
}Code language: C++ (cpp)Removing Duplicates from a Vector
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> v = {1, 2, 2, 3, 4, 4, 5};
std::sort(v.begin(), v.end());
auto last = std::unique(v.begin(), v.end());
v.erase(last, v.end());
for (int i : v) {
std::cout << i << " ";
}
return 0;
}Code language: C++ (cpp)Finding the Intersection of Two Sets
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> v1 = {1, 2, 3, 4, 5};
std::vector<int> v2 = {3, 4, 5, 6, 7};
std::vector<int> v3;
std::sort(v1.begin(), v1.end());
std::sort(v2.begin(), v2.end());
std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(v3));
for (int i : v3) {
std::cout << i << " ";
}
return 0;
}Code language: C++ (cpp)Performance Considerations
When using STL, it’s important to choose the right container and algorithm to achieve optimal performance.
- Vectors vs. Lists: Use
std::vectorfor most cases as it provides better cache performance. Usestd::listonly when frequent insertions and deletions from the middle of the container are required. - Maps vs. Unordered Maps: Use
std::mapwhen you need ordered keys. Usestd::unordered_mapfor faster access when the order is not important.
Best Practices
- Use Algorithms: Prefer using STL algorithms over writing your own loops.
- Prefer Const Iterators: Use const iterators when you do not need to modify the elements.
- Use Auto: Use
autofor iterator declarations to improve readability. - Leverage Emplace Functions: Use
emplaceoverinsertfor in-place construction of elements.
Conclusion
The Standard Template Library (STL) is a powerful toolset in C++ that provides ready-to-use data structures and algorithms. By understanding and utilizing STL, you can write more efficient, maintainable, and clean C++ code. This tutorial has covered the basics and some advanced features of STL, equipping you with the knowledge to leverage STL in your projects. Remember, practice is key to mastering STL. Try to solve different problems using STL to become more proficient.