First, here are two reference articles: STL Function Reference What is STL?

Generic Programming and STL Structure

Basic Concepts of Generic Programming

Refers to writing programs that do not depend on specific data types. Templates are the main tools of generic programming.

Terminology: Concepts

Used to define data types that have certain functions. For example: * The concept of “all data types that can be compared (with comparison operators)” is denoted as Comparable * The concept of “data types that have public copy constructors and can be assigned with ‘=’” is denoted as Assignable * The concept of “all data types that can be compared, have public copy constructors and can be assigned with ‘=’” is denoted as Sortable.

For two different concepts A and B, if all the functions required by concept A are also required by concept B, then concept B is said to be a sub-concept of concept A. For example: * Sortable is both a sub-concept of Comparable and a sub-concept of Assignable

Actually, this sub-concept is similar to derived classes from base classes.

Terminology: Models

Model: A data type that conforms to a concept is called a model of that concept * int type is a model of the Comparable concept; * Static array type is not a type of the Assignable concept (static arrays cannot be assigned).

Using concepts as template parameter names

  • Many STL implementation codes use concepts to name template parameters.
  • Give a concept a name and use that name as a template parameter name.

For example: Representing the prototype of a function template like insertionSort: 

1
2
template <class Sortable>
void insertionSort(Sortable a[], int n);

STL Introduction

Standard Template Library provides some very commonly used data structures and algorithms.

Basic components of STL: * Container * Iterator * Function object * Algorithms

Basic relationships: * Iterator is the bridge between algorithms and containers. Use iterators as algorithm parameters and access containers through iterators rather than passing containers directly as algorithm parameters; * Use function objects as algorithm parameters rather than making the operations performed by functions part of the algorithm.

Relationship diagram:

Basic Components of STL - Containers

Containers are objects that hold a group of elements. The container class library includes seven basic containers: vector, deque, list, set, multiset, map, and multimap.

  • Sequential containers: array, vector, deque, forward_list (singly linked list), list (list, underlying is doubly linked list);
  • Ordered associative containers: set, multiset, map, multimap;
  • Unordered associative containers: unordered_set, unordered_multiset, unordered_map, unordered_multimap.

Container adapters: stack, queue, priority_queue (priority queue, underlying is max or min binary heap)

To use containers, you need to include the corresponding header files.

Basic Components of STL - Iterators

  • Iterators are generalized pointers that provide methods for sequential access to each element in a container;
  • Provide methods for sequential access to each element in a container;
  • Can use the “++” operator to get an iterator pointing to the next element;
  • Can use the “*” operator to access the element pointed to by an iterator. If the element type is a class or structure, you can also use the “->” operator to directly access a member of that element;
  • Some iterators also support getting an iterator pointing to the previous element through the “–” operator;
  • Iterators are generalized pointers: pointers have the same characteristics, so pointers themselves are a type of iterator;
  • To use iterators independent of STL containers, you need to include the header file <iterator>.

Basic Components of STL - Function Objects

  • An object that behaves like a function, which can be called like a function.
  • Function objects are generalized functions: any ordinary function and any object of a class that overloads the “()” operator can be used as a function object.
  • To use STL function objects, you need to include the header file <functional>.

Basic Components of STL - Algorithms

  • STL includes more than 70 algorithms, such as: sorting algorithms, elimination algorithms, counting algorithms, comparison algorithms, transformation algorithms, permutation algorithms, and container management;
  • Can be widely used for different objects and built-in data types;
  • To use STL algorithms, you need to include the header file <algorithm>.

Algorithm Example - transform Algorithm

The transform algorithm sequentially traverses the elements pointed to by the two iterators first and last; * Uses each element’s value as a parameter for the function object op; * Outputs op’s return value sequentially through iterator result; * After traversal is complete, the result iterator points to the position after the last output element, and transform will return that iterator.

For example, the following could be one implementation of the transform algorithm: 

1
2
3
4
5
6
7
8
9
template <class InputIterator, class OutputIterator, class UnaryFunction>
OutputIterator transform(InputIterator first, InputIterator last, OutputIterator result, UnaryFunction op)
{
	for (;first != last; ++first, ++result) 
		{
			*result = op(*first);
		}
	return result;
}

Example: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//Read several integers from standard input, store in vector container, output their negatives

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <functional>
using namespace std;

int main()
{
const int N = 5;
vector<int> s(N);
for (int i = 0; i < N; i++)
{
cin >> s[i];
}
transform(s.begin(),s.end(), ostream_iterator<int>(cout," "),negate<int>());
cout << endl;
return 0;
}

Iterators

Iterators are the bridge between algorithms and containers: * Iterators are used to access elements in containers * Algorithms do not directly operate on data in containers, but indirectly through iterators

Algorithms and containers are independent: * Adding new algorithms does not affect container implementation * Adding new containers, existing algorithms can still be applied

Input Stream Iterators and Output Stream Iterators

Input stream iterators * istream_iterator<T> * Constructed with input stream (such as cin) as parameter * Can use (p++) to get the next input element Output stream iterators ostream_iterator<T> * Need to provide output stream (such as cout) when constructing * Can use (*p++) = x to output x to the output stream

Both belong to adapters * Adapters are objects used to provide new interfaces for existing objects * Input stream adapters and output stream adapters provide iterator interfaces for stream objects

Program example: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//Read several real numbers from standard input, output their squares
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;

double square(double x)
{
    return x * x;
}

int main()
{
    transform(istream_iterator<double>(cin),istream_iterator<double>(),ostream_iterator<double>(cout,"\t"),square);
    //istream_iterator<double>() calls the default constructor of the input stream iterator, making it point to the end position of the input stream.
    cout << endl;
    return 0;
    //If you don't manually terminate the program, it will keep running because the input stream is always waiting for your input
}

Iterator Classification

Classified by access method: Fetching Title#2j8d

Relationship diagram:

Classified by operation type:

Iterator Ranges

  • Two iterators represent a range: [p1, p2), the range includes p1 but not p2;
  • STL algorithms often use iterator ranges as input to pass input data;
  • Valid range: p1 satisfies p1 == p2 after n (n > 0) increment (++) operations.

Program example: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//Example of comprehensive use of various iterators
#include <algorithm>
#include <iterator>
#include <vector>
#include <iostream>
using namespace std;

template <class T, class InputIterator, class OutputIterator>
void mySort(InputIterator first, InputIterator last, OutputIterator result)
{
    vector<T> s;
    while (first != last)
    {
        s.push_back(*first);
        first++;
    }
    sort(s.begin(), s.end()); //sort parameters must be random access iterators
    copy(s.begin(), s.end(), result);
}

int main()
{
    double a[5] = {1.2, 2.4, 0.8, 3.3, 3.2};
    //Sort known array
    mySort<double>(a, a + 5, ostream_iterator<double>(cout, " "));
    cout << endl;
    //Read several integers from standard input, output sorted results
    mySort<int>(istream_iterator<int>(cin), istream_iterator<int>(), ostream_iterator<int>(cout, " "));
    cout << endl;
    return 0;
}

Iterator Helper Functions

  • advance(p,n): Perform n increment operations on p
  • distance(first,last): Calculate the distance between two iterators first and last

Containers

Basic Functions and Classification of Containers

Common functions of containers * Construct empty containers with default constructors * Support relational operators: ==, !=, <, <=, >, >= * begin(), end(): Get container head and tail iterators (actually pointing to the element after the last element of the container) * cbegin(), cend(): Get container head and tail const iterators, safer when not changing the container * clear(): Clear the container * empty(): Check if the container is empty * size(): Get the number of elements in the container * s1.swap(s2): Swap the contents of containers s1 and s2

Related data types (S represents container type) * S::iterator: Iterator type pointing to container elements * S::const_iterator: Const iterator type

Using begin()/end() of general containers, the iterators obtained are all forward iterators, while reversible containers provide bidirectional iterators.

In fact, STL templates provide standard containers that are at least reversible containers, but some non-standard template libraries provide containers like slist (singly linked list) that only provide forward iterators.

Access to Reversible Containers

STL provides reverse iterators for each reversible container, which can be obtained through the following member functions: * rbegin(): Reverse iterator pointing to the end of the container * rend(): Reverse iterator pointing to the beginning of the container

The type names of reverse iterators are represented as follows (S represents container type): * S::reverse_iterator: Reverse iterator type * S::const_reverse_iterator: Reverse const iterator type

Reverse iterators are adapters of ordinary iterators, where ++ of reverse iterators is mapped to – of forward iterators.

Details: An iterator and its reverse iterator can be converted to each other. For example: if p1 is an iterator of type S::iterator, then using the expression S::reverse_iterator(p1) can get the reverse iterator corresponding to p1; you can also use the base function to get the ordinary iterator corresponding to the reverse iterator, such as: r1 is a reverse iterator constructed through S::reverse_iterator(p1), then r1.base() == p1. But r1 and p1 do not point to the same element, the element pointed to by r1 is always the same as the element pointed to by p1-1.

Sequential Containers

Sequential containers in STL * vector * deque * list * forward_list * array

  • Elements are arranged linearly, and elements can be inserted and deleted at specified positions at any time.
  • Must conform to the Assignable concept (i.e., have public copy constructors and can be assigned with “=”).
  • array objects have fixed size, forward_list has special add and delete operations.

Sequential Container Interface

Does not include singly linked list (forward_list) and array

  1. Constructors
    • List initialization, such as vector<int> arr = {1,4,5,7};
  2. Assignment functions
    • assign
  3. Insert functions
    • insert(iterator pos, const T& v), after inserting at pos position, returns the iterator of the newly inserted element;
    • push_front (only for list and deque), push_back;
    • emplace_front, emplace and emplace_back, these operations construct rather than copy elements into the container, these operations correspond to push_front, insert and push_back respectively, allowing us to place elements at the head of the container, a specified position and the tail of the container.
  4. Delete functions
    • erase, clear, pop_front (only for list and deque), pop_back
  5. Direct access to head and tail elements
    • front, back
  6. Change size
    • resize

Remember that operations on the head are not suitable for data structures with contiguous physical addresses.

Vector

Features: * A dynamic array that can be extended * Fast random access, fast insertion or deletion at the tail * Slow insertion or deletion in the middle or head

Vector capacity: The size of actually allocated space * s.capacity(): Returns current capacity * s.reserve(n): If capacity is less than n, extend s to make its capacity at least n * s.shrink_to_fit(): Reclaim unused element space, i.e., size and capacity function return values are equal

Invalidation: If adding elements causes vector to expand, then all iterators, pointers and references will be invalidated because memory space is reallocated; if there is no expansion, then only iterators after the inserted (or deleted) elements will be invalidated (because elements are moved).

Deque

Features * Fast insertion or deletion at both ends * Slow insertion or deletion in the middle * Random access is faster, but slower than vector container

Deque is a segmented array in many STL implementations. Elements in the container are stored in fixed-size arrays in segments. In addition, the container needs to maintain an index array storing the first addresses of these segmented arrays, so deque’s continuity is an illusion.

https://img-blog.csdnimg.cn/20190217155302649.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg==,size_16,color_FFFFFF,t_70 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//First output odd numbers in descending order, then output even numbers in ascending order.
#include <iostream>
#include <deque>
#include <iterator>
#include <vector>
using namespace std;

int main()
{
    istream_iterator<int> i1(cin), i2; //Create a pair of input stream iterators, first is the beginning of standard input, second is the end of standard input
    vector<int> s1(i1, i2);            //Input data from standard input stream through input stream iterators
    sort(s1.begin(), s1.end());        //Sort the input integers
    deque<int> s2;
    //The following loop traverses s1
    for (vector<int>::iterator iter = s1.begin(); iter != s1.end(); ++iter)
    {
        if (*iter % 2 == 0) //Even numbers go to s2 tail
            s2.push_back(*iter);
        else //Odd numbers go to s2 head
            s2.push_front(*iter);
    }
    //Output the results of s2
    copy(s2.begin(), s2.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
    return 0;
}

List

The underlying logic is a doubly linked list.

Features * Fast insertion and deletion of elements at any position * Does not support random access

Splice operation s1.splice(p, s2, q1, q2) means moving [q1, q2) from s2 to before the element pointed to by p in s1

Forward List

Features: * Each node in a singly linked list only has a pointer to the next node, with no simple way to get the predecessor of a node; * insert, emplace and erase operations are not defined, but insert_after, emplace_after and erase_after operations are defined. Their parameters are the same as list’s insert, emplace and erase, but they don’t insert or delete the element pointed to by iterator p1, but operate on the node after the element pointed to by p1; * Does not support size operation.

Array

Features: * array is a wrapper for built-in arrays, providing a safer and more convenient way to use arrays * The size of array objects is fixed. When defining, you need to specify both the element type and the container size. * Cannot dynamically change container size

Sequential Container Insert Iterators and Adapters

Sequential Container Insert Iterators

Concept: Iterators used to insert elements at the head, tail, or specified position in the middle of a container, including front inserter (front_inserter), back inserter (back_inserter), and arbitrary position inserter (inserter).

1
2
3
list<int> s;
back_inserter iter(s);
*(iter++) = 5; //Insert 5 at the end of s through iter

Sequential Container Adapters

Build some commonly used data structures based on sequential containers, which are wrappers of sequential containers: * Stack: The first pushed element is popped last * Queue: The first pushed element is popped first * Priority queue: The “largest” element is popped first

Stack can use any sequential container as the base container, but queue only allows front-inserting sequential containers (deque or list)

The essence of priority queue is max (min) binary heap.

Common Operations Supported by Stack and Queue

  • s1 op s2 op can be one of ==, !=, <, <=, >, >=, it compares elements between two container adapters in lexicographic order;
  • s.size() returns the number of elements in s;
  • s.empty() returns whether s is empty;
  • s.push(t) pushes element t into s;
  • s.pop() pops an element from s. For stack, the element popped each time is the last pushed element, while for queue, the element popped each time is the first pushed element;
  • Does not support iterators because they do not allow access to arbitrary elements.

Different Operations of Stack and Queue

Stack operations: * s.top() returns a reference to the top element of the stack

Queue operations: * s.front() gets a reference to the head element of the queue * s.back() gets a reference to the tail element of the queue

Priority Queue

Priority queue also supports element pushing and popping like stack and queue, but the order of element popping is related to element size. The element popped each time is always the “largest” element in the container. 

1
2
template <class T, class Sequence = vector<T>
class priority_queue;
The base container of priority queue must be a sequential container that supports random access. * Supports the size, empty, push, pop member functions of stack and queue, with the same usage as stack and queue. * Priority queue does not support comparison operations. * Similar to stack, priority queue provides a top function that can get a reference to the next element to be popped (i.e., the “largest” element).

Associative Containers

Classification and Basic Functions of Associative Containers

For associative containers, each element has a key, and the order of elements in the container is arranged in ascending order of key values.

Unlike sequential containers where finding elements has time complexity \(O(n)\), associative containers organize elements into a balanced binary tree based on key size, with time complexity \(O(\log n)\).

Classification of ordered associative containers: * Single associative containers (set and map) * Key values are unique, one key value can only correspond to one element * Multiple associative containers (multiset and multimap) * Key values are not unique, one key value can correspond to multiple elements * Simple associative containers (set and multiset) * Container has only one type parameter, such as set, multiset, representing key type * The element of the container is the key itself * Binary associative containers (map and multimap) * Container has two type parameters, such as map<K,V>, multimap<K,V>, representing key and additional data types respectively * The element type of the container is pair<K,V>, i.e., a binary tuple composed of key type and additional data type

Interface * Construction: List initialization, such as map<string, int> id_map = {{"Xiao Ming", 1}, {"Li Hua", 2}} * Insert: insert * Delete: erase * Find: find * Bounds: lower_bound, upper_bound, equal_range * Count: count

C++11 new standard defines 4 unordered associative containers unordered_set, unordered_map, unordered_multiset, unordered_multimap * Do not use comparison operators to organize elements, but through a hash function and the == operator of key type. * Provide the same operations as ordered containers * Can directly define unordered containers with built-in type keywords. * Cannot directly define unordered containers with custom class key types. If needed, must provide our own hash template.

Set

Set is used to store a group of non-duplicate elements. Since the elements of the set are ordered, it can efficiently find specified elements and conveniently get the range of elements with specified size in the container.

1
2
3
4
pair<set<double>::iterator,bool> r=s.insert(v); 
if (!r.second);
//Let me explain this a bit. The return value of the insert function is a binary tuple, first is an iterator, second is a bool value indicating whether insertion is possible.
//The first line constructs an r binary tuple, and the way to access its two elements is r.first and r.second.

Map

Map and set both belong to single associative containers. Their main difference is that the element type of set is the key itself, while the element type of map is a binary tuple composed of key and additional data.

When looking up an element by key in a set, it is generally only used to determine whether the element exists, while when looking up an element by key in a map, in addition to determining its existence, you can also get corresponding additional data.

1
2
3
courses.insert(make_pair("CSAPP", 3));
//Binary tuple initialization can use pair<first_type,second_type> r = {element1,element2}
//At the same time, if you want to use it as a function parameter, you can omit the construction step and directly use make_pair(element1,element2)

Multiset and Multimap

Multiset is a set that allows duplicate elements, and multimap is a map that allows one key to correspond to multiple additional data.

The usage of multiset and set, multimap and map is similar, with only subtle differences in a few member functions. The difference is mainly manifested in removing the restriction that keys must be unique.

Function Objects

Basic Concepts and Classification of Function Objects

Function objects are actually objects that behave like functions. They can have no parameters or several parameters, and their function is to get a value or change the state of an operation.

Any ordinary function and any object of a class that overloads the call operator operator() satisfies the characteristics of function objects

The following are two programs with the same result: 

1
2
3
4
5
6
7
8
9
10
11
#include <iostream> 
#include <numeric> //Include numerical algorithm header file
using namespace std;
//Define an ordinary function
int mult(int x, int y) { return x * y; };
int main() {
	int a[] = { 1, 2, 3, 4, 5 };
	const int N = sizeof(a) / sizeof(int);
	cout << "The result by multipling all elements in a is " << accumulate(a, a + N, 1, mult) << endl;
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <numeric> //Include numerical algorithm header file
using namespace std;
class MultClass{ //Define MultClass class
public:
//Overload operator operator()
	int operator() (int x, int y) const { return x * y; }
};
int main() {
	int a[] = { 1, 2, 3, 4, 5 };
	const int N = sizeof(a) / sizeof(int);
	cout << "The result by multipling all elements in a is " << accumulate(a, a + N, 1, MultClass()) //MultClass object passed to generic algorithm 
	<< endl;
	return 0;
}

One ordinary function, one class overloads ().

Function objects provided by STL: * Function objects for arithmetic operations * Function objects for relational operations and logical operations (require return value to be bool)

Lambda Expressions

Lambda Expression Details Definition: [capture list] (parameter list) -> return type {function body} * Capture list can capture local variables of the function where lambda is located * Parameter list, return type and function body are consistent with ordinary functions * Can be defined inside functions, understood as unnamed inline functions * auto lambda = [] { return “Hello World!”; }; * cout<< lambda() <<std::endl; //Execution is consistent with function objects

Capture list has value capture, reference capture and implicit capture methods * int size = 10, base = 0; //Local variables * auto longer = size{return s.size()>size;} //Value capture * auto longer = &size{return s.size()>size;}//Reference capture * auto longer = ={return s.size()>base;}//Implicit value capture * auto longer = &{return s.size()>size;}//Implicit reference capture ## Function Adapters

bind2nd produces an instance of binder2nd function adapter 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <functional>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using namespace placeholders; //Namespace for placeholder _n
int main() 
{
	int intArr[] = { 30, 90, 10, 40, 70, 50, 20, 80 };
	const int N = sizeof(intArr) / sizeof(int);
	vector<int> a(intArr, intArr + N);
	auto p = find_if(a.begin(), a.end(),bind2nd(greater<>(), 40));
	if (p == a.end())
		cout << "no element greater than 40" << endl;
	else
		cout << "first element greater than 40 is: " << *p << endl;
	return 0;
}

Function templates have much more content, learn gradually in practice

Algorithms

Characteristics of algorithms: * STL algorithms are themselves function templates * Get input data through iterators * Process data through function objects * Output results through iterators * STL algorithms are generic, independent of specific data types and container types

Classification of algorithms: * Non-mutable sequence algorithms * Mutable sequence algorithms * Sorting and searching algorithms * Numerical algorithms

All algorithms used in the code can be found in the images, so no explanation is given.

Non-Mutable Sequence Algorithms

Algorithms that do not directly modify the content of the operated container, used for finding specified elements, comparing whether two sequences are equal, counting elements, etc.

Example: 

1
2
3
template<class InputIterator, class UnaryPredicate>
InputIterator find_if(InputIterator first, InputIterator last, UnaryPredicate pred);
//Find the first element in [first, last) range where pred(x) is true

Non-Mutable Sequence Algorithm Examples

Mutable Sequence Algorithms

Can modify the container objects they operate on, including algorithms for copying, deleting, replacing, reversing, rotating, swapping, partitioning, deduplicating, filling, shuffling sequences and generating a sequence.

Example: 

1
2
3
template<class ForwardIterator, class T>
void fill(ForwardIterator first, ForwardIterator last, const T& x);
//Rewrite all elements in [first, last) range to x.

The Deceptive Nature of remove_if

Removing is done by shifting (by means of copy assignment (until C++11)move assignment (since C++11)) the elements in the range in such a way that the elements that are not to be removed appear in the beginning of the range. Relative order of the elements that remain is preserved and the physical size of the container is unchanged. Iterators pointing to an element between the new logical end and the physical end of the range are still dereferenceable, but the elements themselves have unspecified values (as per MoveAssignable post-condition).

Mutable Sequence Algorithm Examples

Sorting and Searching Algorithms

  • Sort sequences
  • Merge two ordered sequences
  • Search ordered sequences
  • Set operations on ordered sequences
  • Heap algorithms

1
2
3
template <class RandomAccessIterator , class UnaryPredicate>
void sort(RandomAccessIterator first, RandomAccessIterator last, UnaryPredicate comp);
//Use function object comp as "<" to sort data in [first, last) range

sort requires first and last to be random iterator types, because sort’s specific implementation uses quicksort, and using random iterators is for efficiency considerations.

Numerical Algorithms

Find the “sum” of elements in a sequence, partial “sum”, “difference” of adjacent elements, or inner product of two sequences. The “+” for finding “sum”, “-” for finding “difference”, and “+” and “·” for finding inner product can all be specified by function objects.

Example: 

1
2
3
template<class InputIterator, class OutputIterator, class BinaryFunction> ▫ OutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result, BinaryFunction op);
//Find partial "sum" of elements in [first, last) (so-called partial "sum" is a sequence with the same length as the input sequence, where the nth term is the "sum" of the first n elements of the input sequence)
//Use function object op as "+" operator, output result through result, return iterator pointing to the element after the last element of the output sequence

[Numerical Algorithm Examples](https://github.com/hustlixiang21/cpp-practice/tree/main/%E6%95%B0%E5%80%BC%E7%AE%97%E6%B3%95%E5%BA%94%E7%94%A8%E5%AE%9E%E4%BE%8B

Comprehensive Example - Bank Account Management

Source Code + Updates