1. Basic concept of STL

• STL(Standard Template Library)
• STL is broadly divided into container, algorithm and iterator
• Containers and algorithms are seamlessly connected through iterators
• Almost all STL code uses template classes or template functions

2. Six STL components

STL is generally divided into six components: container, algorithm, iterator, imitation function, adapter (adapter) and space configurator

1. Container: various data structures, such as vector, list, set, map, etc., are used to store data
2. Algorithm: various commonly used algorithms, such as sort, find and for_each et al
3. Iterators: act as glue between containers and algorithms
4. Imitative function: it behaves like a function and can be used as a strategy of the algorithm
5. Adapter: something used to decorate a container or an interface to an emulator or iterator
6. Space configurator: responsible for space configuration and management

3. Container, algorithm and iterator in STL

Container:

STL container is to implement some of the most widely used data structures
Common data structures: array, linked list, tree, stack, queue, set, mapping table, etc
Containers are divided into sequential containers and associated containers:

• Sequential container: it emphasizes the sorting of values. Each element in the sequential container has a fixed position
• Associative container: a binary tree structure in which there is no strict physical order between the elements

Algorithm:

There are two kinds of algorithms: qualitative algorithm and non qualitative algorithm:

• Qualitative change algorithm: refers to the content of elements in the interval that will be changed during operation, such as copy, replacement, deletion, etc
• Non qualitative algorithm: it means that the element content in the interval will not be changed during operation, such as search, traversal, etc

Iterator:

A method is provided to search the elements contained in a container in order without exposing the internal representation of the container
Each container has its own iterator, similar to a pointer

Iterator type:

type	function	Support operation
Input Iterator	Read only access to data	Read only, support + +, = ==
output iterators	Write only access to data	Write only, support++
forward iterators	Read and write operations, and can push the iterator forward	Read and write, support + +, = ==
Bidirectional Iterator	Read and write operations, and can operate forward and backward	Read and write, support + +, –
random access iterators	Read / write operation, which can access any data in a jumping way, is the most powerful iterator	Read and write, support + +, –, [n], < =, >=

The commonly used iterators in containers are bidirectional iterators and random access iterators

Example 1: using a vector container to store data types

Containers: vector
Algorithm: for_each
Iterator: vector < int >:: iterator

Purpose: traverse all data in the container to output

Example:

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm> 	// Standard algorithm header file

void MyPrint(int val)		//The third traversal method calls external functions
{
	cout << val << endl;
}

int main(void) {

	//Create a vector container object, and specify the data type stored in the container through the template parameter
	vector<int> v;
	//Storing data into containers
	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);

	vector<int>::iterator pBegin = v.begin();	//v.begin() returns an iterator that points to the first data location in the container
	vector<int>::iterator pEnd = v.end();			//v.end() returns an iterator that points to the next position of the last element of the container element
	
	//The first traversal method
	while (pBegin != pEnd) {
		cout << *pBegin << endl;
		pBegin++;
	}

	//The second traversal method
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
		cout << *it << endl;
	}

	//The third traversal method
	//Use the standard traversal algorithm provided by STL for_each needs to include the header file algorithm
	for_each(v.begin(), v.end(), MyPrint);
    
    return 0;
}

Example 2: nested containers using vector containers

Purpose: traverse all data in the container to output

Example:

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm> 	// Standard algorithm header file

int main() {
	vector<vector<int>>v;

	//Create a small container
	vector<int>v1;
	vector<int>v2;
	vector<int>v3;
	vector<int>v4;

	for (int i = 0; i < 4; i++) {
		v1.push_back(i + 1);
		v2.push_back(i + 2);
		v3.push_back(i + 3);
		v4.push_back(i + 4);
	}

	//Insert the small container into the large container
	v.push_back(v1);
	v.push_back(v2);
	v.push_back(v3);
	v.push_back(v4);

	//Traverse the large container
	for (vector<vector<int>>::iterator it = v.begin(); it != v.end(); it++) {
		//(* it) --- container vector < int >
		for (vector<int>::iterator vit = (*it).begin(); vit != (*it).end(); vit++) {
			cout << *vit << " ";
		}
		cout << endl;
	}

	return 0;
}