STL is part of C++ and includes a series of reusable components, such as containers, algorithms, iterators, etc. These components are designed following the principles of generic programming, making them widely applicable to different types of data.
Containers
Sequential Containers
vector: Dynamic array, supports random access.deque: Double-ended queue, supports fast insertion and deletion at both ends.list: Doubly linked list, supports fast insertion and deletion at any position.
Using vector
#include <iostream>
#include <vector>
int main() {
std::vector<int> numbers = {1, 2, 3, 4, 5};
// Add elements
numbers.push_back(6);
numbers.insert(numbers.begin(), 0);
// Remove elements
numbers.pop_back();
numbers.erase(numbers.begin());
// Access elements
for (int num : numbers) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
Advanced usage of std::vector
#include <iostream>
#include <vector>
int main() {
std::vector<int> v = {1, 2, 3, 4, 5};
// Use reserve to pre-allocate memory
v.reserve(10);
// Use emplace_back to construct elements directly in the container
v.emplace_back(6);
// Use at to access elements
std::cout << "Element at index 3: " << v.at(3) << std::endl;
// Traverse using begin and end
for (auto it = v.begin(); it != v.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
return 0;
}
std::deque
- Double-ended queue: Efficient insertion and deletion at both ends.
- Member functions:
push_front,pop_front,push_back,pop_back.
Example code: Using std::deque
#include <iostream>
#include <deque>
int main() {
std::deque<int> d = {1, 2, 3, 4, 5};
// Add element at the front
d.push_front(0);
// Add element at the back
d.push_back(6);
// Traverse using begin and end
for (auto it = d.begin(); it != d.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
return 0;
}
std::list
- Doubly linked list: Suitable for frequent insertions and deletions.
- Member functions:
push_front,pop_front,push_back,pop_back,splice.
Example code: Using std::list
#include <iostream>
#include <list>
int main() {
std::list<int> l = {1, 2, 3, 4, 5};
// Add element at the front
l.push_front(0);
// Add element at the back
l.push_back(6);
// Use splice to move elements
auto it = l.begin();
std::advance(it, 2); // Move to the third element
std::list<int>::iterator pos = l.begin();
l.splice(pos, l, it);
// Traverse using begin and end
for (auto it = l.begin(); it != l.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
return 0;
}
Associative Containers
set: Sorted collection, no duplicate elements allowed.map: Sorted key-value mapping, keys cannot be duplicated.multiset: Sorted collection, duplicate elements allowed.multimap: Sorted key-value mapping, keys can be duplicated.
Example code: Using map
#include <iostream>
#include <map>
int main() {
std::map<std::string, int> scores = {
{"Alice", 100},
{"Bob", 90},
{"Charlie", 80}
};
// Insert element
scores["David"] = 95;
// Update element
scores["Alice"] = 105;
// Access elements
for (const auto& [name, score] : scores) {
std::cout << name << ": " << score << std::endl;
}
return 0;
}
std::set
- Ordered collection: Implemented using a red-black tree.
- Member functions:
insert,erase,find,count.
Example code: Using std::set
#include <iostream>
#include <set>
int main() {
std::set<int> s = {1, 2, 3, 4, 5};
// Insert new element
s.insert(6);
// Find element
auto it = s.find(4);
if (it != s.end()) {
std::cout << "Found element: " << *it << std::endl;
}
// Traverse using begin and end
for (const auto& elem : s) {
std::cout << elem << " ";
}
std::cout << std::endl;
return 0;
}
Container Adapters
stack: Stack, last in, first out.queue: Queue, first in, first out.priority_queue: Priority queue, sorted by priority.
Example code: Using priority_queue
#include <iostream>
#include <queue>
int main() {
std::priority_queue<int> pq;
// Add elements
pq.push(10);
pq.push(5);
pq.push(20);
// Access elements
while (!pq.empty()) {
std::cout << pq.top() << " ";
pq.pop();
}
std::cout << std::endl;
return 0;
}
Iterators
Iterators are objects in STL used to traverse container elements. They support different operations such as moving, comparing, and dereferencing.
Example code: Using iterators to traverse vector
#include <iostream>
#include <vector>
int main() {
std::vector<int> numbers = {1, 2, 3, 4, 5};
// Traverse container
for (auto it = numbers.begin(); it != numbers.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
return 0;
}
Algorithms
Algorithms are functions in STL used to process container elements. They can be used for sorting, searching, transforming, etc.
Non-modifying Sequence Operations
for_each: Applies a function to each element in the sequence.copy: Copies a sequence.
Example code: Using for_each
#include <iostream>
#include <vector>
#include <algorithm>
void print(int x) {
std::cout << x << " ";
}
int main() {
std::vector<int> numbers = {1, 2, 3, 4, 5};
// Traverse container
std::for_each(numbers.begin(), numbers.end(), print);
std::cout << std::endl;
return 0;
}
Modifying Sequence Operations
sort: Sorts.reverse: Reverses the sequence.fill: Fills the sequence.
Example code: Using sort
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> numbers = {5, 3, 1, 4, 2};
// Sort container
std::sort(numbers.begin(), numbers.end());
// Output sorted result
for (int num : numbers) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
Replacement Operations
replace: Replaces elements.
Example code: Using replace
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> numbers = {1, 2, 3, 2, 4, 2};
// Replace elements
std::replace(numbers.begin(), numbers.end(), 2, 10);
// Output replaced result
for (int num : numbers) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
Removal Operations
remove: Removes elements.unique: Removes duplicate elements.
Example code: Using remove
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> numbers = {1, 2, 3, 2, 4, 2};
// Remove elements
numbers.erase(std::remove(numbers.begin(), numbers.end(), 2), numbers.end());
// Output removed result
for (int num : numbers) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
Search Operations
find: Finds an element.find_if: Finds an element using a predicate.
Example code: Using find_if
#include <iostream>
#include <vector>
#include <algorithm>
bool is_even(int x) {
return x % 2 == 0;
}
int main() {
std::vector<int> numbers = {1, 2, 3, 4, 5};
// Find element
auto it = std::find_if(numbers.begin(), numbers.end(), is_even);
if (it != numbers.end()) {
std::cout << "Found even number: " << *it << std::endl;
} else {
std::cout << "No even number found." << std::endl;
}
return 0;
}
Partition Operations
partition: Partitions the sequence.
Example code: Using partition
#include <iostream>
#include <vector>
#include <algorithm>
bool is_odd(int x) {
return x % 2 != 0;
}
int main() {
std::vector<int> numbers = {1, 2, 3, 4, 5};
// Partition sequence
auto it = std::partition(numbers.begin(), numbers.end(), is_odd);
// Output partitioned result
for (int num : numbers) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
Sorting Operations
stable_sort: Stable sort.partial_sort: Partial sort.
Example code: Using stable_sort
#include <iostream>
#include <vector>
#include <algorithm>
struct Person {
std::string name;
int age;
bool operator<(const Person& other) const {
return age < other.age;
}
};
int main() {
std::vector<Person> people = {
{"Alice", 30},
{"Bob", 25},
{"Charlie", 25},
{"David", 35}
};
// Stable sort
std::stable_sort(people.begin(), people.end());
// Output sorted result
for (const auto& person : people) {
std::cout << person.name << ": " << person.age << std::endl;
}
return 0;
}
Example code: Using partial_sort
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> numbers = {5, 3, 1, 4, 2};
// Partially sort the first three elements
std::partial_sort(numbers.begin(), numbers.begin() + 3, numbers.end());
// Output partially sorted result
for (int num : numbers) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
Merge Operations
merge: Merges two sorted sequences.
Example code: Using merge
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> vec1 = {1, 3, 5};
std::vector<int> vec2 = {2, 4, 6};
std::vector<int> result(vec1.size() + vec2.size());
// Merge two sorted sequences
std::merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), result.begin());
// Output merged result
for (int num : result) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
Transform Operations
transform: Transforms a sequence.
Example code: Using transform
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
int main() {
std::vector<int> vec1 = {1, 2, 3};
std::vector<int> vec2 = {4, 5, 6};
std::vector<int> result(vec1.size());
// Transform two sequences using addition
std::transform(vec1.begin(), vec1.end(), vec2.begin(), result.begin(), std::plus<int>());
// Output transformed result
for (int num : result) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
Function Objects
A function object is an object that can be called like a function. STL provides various predefined function objects, such as plus, minus, etc.
Example code: Using plus
#include <iostream>
#include <functional>
int main() {
std::plus<int> adder;
int a = 5;
int b = 3;
int sum = adder(a, b);
std::cout << "Sum: " << sum << std::endl;
return 0;
}
Advanced Topics
Generic Programming
- Template metaprogramming
- SFINAE (Substitution Failure Is Not An Error)
Example code: Using template metaprogramming
#include <iostream>
#include <type_traits>
template<typename T>
struct IsInteger {
static constexpr bool value = std::is_integral<T>::value;
};
template<typename T>
void printType() {
if (IsInteger<T>::value) {
std::cout << "Type is an integer." << std::endl;
} else {
std::cout << "Type is not an integer." << std::endl;
}
}
int main() {
printType<int>(); // Output "Type is an integer."
printType<double>(); // Output "Type is not an integer."
return 0;
}
Adapters
- Container adapters
- Iterator adapters
Example code: Using iterator adapter
#include <iostream>
#include <vector>
#include <iterator>
int main() {
std::vector<int> numbers = {1, 2, 3, 4, 5};
// Use reverse iterator adapter
for (auto rit = numbers.rbegin(); rit != numbers.rend(); ++rit) {
std::cout << *rit << " ";
}
std::cout << std::endl;
return 0;
}
Allocators
allocator: Default allocator- Custom allocators
Example code: Using allocator
#include <iostream>
#include <vector>
int main() {
std::vector<int> numbers(10); // Create vector using default allocator
// Get allocator
std::allocator<int> alloc = numbers.get_allocator();
// Allocate memory using allocator
int* data = alloc.allocate(5);
// Initialize data
for (int i = 0; i < 5; ++i) {
alloc.construct(&data[i], i);
}
// Output data
for (int i = 0; i < 5; ++i) {
std::cout << data[i] << " ";
}
std::cout << std::endl;
// Destroy data
for (int i = 0; i < 5; ++i) {
alloc.destroy(&data[i]);
}
// Deallocate memory
alloc.deallocate(data, 5);
return 0;
}
Practical Applications
Efficient Algorithm Design
- Algorithm complexity analysis
- Algorithm optimization techniques
Example code: Using binary search
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> numbers = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
int target = 7;
// Use binary search
auto it = std::lower_bound(numbers.begin(), numbers.end(), target);
if (it != numbers.end() && *it == target) {
std::cout << "Found at index: " << std::distance(numbers.begin(), it) << std::endl;
} else {
std::cout << "Not found." << std::endl;
}
return 0;
}
Container Selection and Usage
- Performance comparison
- Choosing the right data structure
Example code: Comparing performance of vector and list
#include <iostream>
#include <vector>
#include <list>
#include <chrono>
int main() {
const int N = 1000000;
// Test vector
{
std::vector<int> vec;
auto start = std::chrono::high_resolution_clock::now();
for (int i = 0; i < N; ++i) {
vec.push_back(i);
}
auto end = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
std::cout << "Vector time: " << duration << " ms" << std::endl;
}
// Test list
{
std::list<int> lst;
auto start = std::chrono::high_resolution_clock::now();
for (int i = 0; i < N; ++i) {
lst.push_back(i);
}
auto end = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
std::cout << "List time: " << duration << " ms" << std::endl;
}
return 0;
}
Comprehensive Exercises
Writing Your Own Container
Design and implement a simple container
Example code: Implementing a simple stack
#include <iostream>
#include <vector>
template<typename T>
class SimpleStack {
public:
void push(const T& item) {
data.push_back(item);
}
T pop() {
if (empty()) {
throw std::runtime_error("Stack is empty.");
}
T topItem = data.back();
data.pop_back();
return topItem;
}
bool empty() const {
return data.empty();
}
private:
std::vector<T> data;
};
int main() {
SimpleStack<int> stack;
stack.push(1);
stack.push(2);
stack.push(3);
while (!stack.empty()) {
std::cout << stack.pop() << " ";
}
std::cout << std::endl;
return 0;
}
Best Practices
Code Style and Naming Conventions
- Use clear and meaningful variable names
- Avoid using single letters as variable names unless they have clear meaning
Example code: Following coding standards
#include <iostream>
#include <vector>
// Use clear naming
void print_vector(const std::vector<int>& numbers) {
for (int number : numbers) {
std::cout << number << " ";
}
std::cout << std::endl;
}
int main() {
std::vector<int> sample_numbers = {1, 2, 3, 4, 5};
print_vector(sample_numbers);
return 0;
}
Code Refactoring
- Regularly refactor code to improve readability and maintainability
- Avoid duplicate code
Example code: Refactoring duplicate code
#include <iostream>
#include <vector>
void process_numbers(const std::vector<int>& numbers, int threshold) {
for (int number : numbers) {
if (number > threshold) {
std::cout << "Number " << number << " is greater than " << threshold << std::endl;
}
}
}
int main() {
std::vector<int> numbers = {1, 2, 3, 4, 5};
int threshold = 3;
process_numbers(numbers, threshold);
return 0;
}
Performance Optimization
Memory Management
- Reduce unnecessary memory allocation and deallocation
- Use caching mechanisms
Example code: Reducing memory allocation
#include <iostream>
#include <vector>
void process_data(const std::vector<int>& data) {
// Process data...
}
int main() {
std::vector<int> data;
data.reserve(10000); // Pre-allocate memory
for (int i = 0; i < 10000; ++i) {
data.push_back(i);
}
process_data(data);
return 0;
}
Parallel Processing
- Use multithreading or parallel libraries for parallel processing
- Consider using OpenMP or the
<thread>library in C++11 standard
Example code: Using C++11 <thread> for parallel processing
#include <iostream>
#include <vector>
#include <thread>
void process_chunk(const std::vector<int>& chunk) {
for (int i : chunk) {
// Process data...
}
}
int main() {
std::vector<int> data(1000000);
for (size_t i = 0; i < data.size(); ++i) {
data[i] = i;
}
const size_t chunk_size = 10000;
const size_t num_threads = 10;
std::vector<std::thread> threads;
for (size_t i = 0; i < num_threads; ++i) {
size_t start = i * chunk_size;
size_t end = (i + 1) * chunk_size;
threads.emplace_back(process_chunk, std::vector<int>(data.begin() + start, data.begin() + end));
}
for (auto& t : threads) {
t.join();
}
return 0;
}



