catalogue

2. STL acquaintance

2.1 birth of STL

2.2 basic concepts of STL

2.3 STL six components

2.4 containers, algorithms and iterators in STL

2.5 initial knowledge of container algorithm iterator

2.5.2 Vector stores user-defined data types

2.5.3 Vector container nested container

2. STL acquaintance

2.1 birth of STL

• For a long time, the software industry has been hoping to build something that can be reused

• The object-oriented and generic programming idea of C + + aims to improve the reusability

• In most cases, data structures and algorithms fail to have a set of standards, resulting in being forced to do a lot of repetitive work

• In order to establish a set of standards for data structure and algorithm, STL was born

2.2 basic concepts 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 codes use template classes or template functions

2.3 STL six 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, deque, set, map, etc., are used to store data.

2. Algorithm: various commonly used algorithms, such as sort, find, copy and for_each et al

3. Iterator: acts as the glue between the container and the algorithm.

4. Imitation function: the behavior is similar to the function, which 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.

2.4 containers, algorithms and iterators in STL

Container: a place to put things

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

These 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: the solution of the problem

Limited steps to solve logical or mathematical problems. This discipline is called algorithms

Algorithms are divided into: qualitative algorithm and non qualitative algorithm.

Qualitative change algorithm: refers to the content of elements in the interval that will be changed during operation. For example, copy, replace, delete and so on

Non qualitative algorithm: it means that the element content in the interval will not be changed during the operation, such as searching, counting, traversing, searching for extreme values, etc

Iterators: glue between containers and algorithms

A method is provided to enable it to search the elements contained in a container in order without exposing the internal representation of the container.

Each container has its own iterator

The use of iterators is very similar to pointers. At the beginning of learning, we can understand that iterators are pointers

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 and write operation, which can access any data in a jumping way. It is the most powerful iterator	Read and write, support + +, --, [n], - N, <, < =, >, >=

Commonly used iterators in containers are bidirectional iterators and random access iterators

2.5 initial knowledge of container algorithm iterator

After understanding the concepts of container, algorithm and iterator in STL, we use the code to feel the charm of STL

The most commonly used container in STL is Vector, which can be understood as array. Next, we will learn how to insert data into this container and traverse this container

2.5.1 vector stores built-in data types

Containers: vector

Algorithm: for_each

Iterator: vector < int >:: iterator

Example:

#include <vector>
#include <algorithm>
​
void MyPrint(int val)
{
    cout << val << endl;
}
​
void test01() {
​
    //Create a vector container object, and specify the type of data stored in the container through template parameters
    vector<int> v;
    //Put data into container
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);
​
    //Each container has its own iterator, which is used to traverse the elements in the container
    //v.begin() returns an iterator that points to the first data in the container
    //v.end() returns an iterator that points to the next location of the last element of the container element
    //Vector < int >:: iterator gets the iterator type of the container vector < int >
​
    vector<int>::iterator pBegin = v.begin();
    vector<int>::iterator pEnd = v.end();
​
    //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;
    }
    cout << endl;
​
    //The third traversal method:
    //Use STL to provide standard traversal algorithm header file algorithm
    for_each(v.begin(), v.end(), MyPrint);
}
​
int main() {
​
    test01();
​
    system("pause");
​
    return 0;
}

2.5.2 Vector stores user-defined data types

Learning objectives: store user-defined data types in vector and print them out

Example:

#include <vector>
#include <string>
​
//Custom data type
class Person {
public:
    Person(string name, int age) {
        mName = name;
        mAge = age;
    }
public:
    string mName;
    int mAge;
};
//Storage object
void test01() {
​
    vector<Person> v;
​
    //Create data
    Person p1("aaa", 10);
    Person p2("bbb", 20);
    Person p3("ccc", 30);
    Person p4("ddd", 40);
    Person p5("eee", 50);
​
    v.push_back(p1);
    v.push_back(p2);
    v.push_back(p3);
    v.push_back(p4);
    v.push_back(p5);
​
    for (vector<Person>::iterator it = v.begin(); it != v.end(); it++) {
        cout << "Name:" << (*it).mName << " Age:" << (*it).mAge << endl;
​
    }
}
​
​
//Drop object pointer
void test02() {
​
    vector<Person*> v;
​
    //Create data
    Person p1("aaa", 10);
    Person p2("bbb", 20);
    Person p3("ccc", 30);
    Person p4("ddd", 40);
    Person p5("eee", 50);
​
    v.push_back(&p1);
    v.push_back(&p2);
    v.push_back(&p3);
    v.push_back(&p4);
    v.push_back(&p5);
​
    for (vector<Person*>::iterator it = v.begin(); it != v.end(); it++) {
        Person * p = (*it);
        cout << "Name:" << p->mName << " Age:" << (*it)->mAge << endl;
    }
}
​
​
int main() {
​
    test01();
    
    test02();
​
    system("pause");
​
    return 0;
}

2.5.3 Vector container nested container

Learning goal: nested containers in containers, we will traverse all data and output

Example:

#include <vector>
​
//Container nested container
void test01() {
​
    vector< vector<int> >  v;
​
    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 container element into the vector v
    v.push_back(v1);
    v.push_back(v2);
    v.push_back(v3);
    v.push_back(v4);
​
​
    for (vector<vector<int>>::iterator it = v.begin(); it != v.end(); it++) {
​
        for (vector<int>::iterator vit = (*it).begin(); vit != (*it).end(); vit++) {
            cout << *vit << " ";
        }
        cout << endl;
    }
​
}
​
int main() {
​
    test01();
​
    system("pause");
​
    return 0;
}