Dark horse programmer / C + + improve programming handout

=Generic programming and STL = = technology are explained in detail to explore the deeper use of C + +

1 template

1.1 concept of template

Template is to establish a general mold, which greatly improves the reusability

Characteristics of formwork:

The template cannot be used directly. It is just a framework
The universality of templates is not everything

1.2 function template

Another programming idea of C + + is called generic programming, which mainly uses template technology
C + + provides two template mechanisms: function template and class template

1.2.1 function template syntax

Function template function:

Establish a general function whose function return value type and formal parameter type can be represented by a virtual type without specific formulation.

Syntax:

template<typename T>
Function declaration or definition

Explanation:

Template - declare to create a template

typename - the symbol behind the surface is a data type, which can be replaced by class

T-A common data type whose name can be replaced, usually in uppercase letters

Example:

//Commutative integer function
void swapInt(int& a, int& b) {
	int temp = a;
	a = b;
	b = temp;
}

//Swap floating point functions
void swapDouble(double& a, double& b) {
	double temp = a;
	a = b;
	b = temp;
}

//Using templates to provide general exchange functions
template<typename T>
void mySwap(T& a, T& b)
{
	T temp = a;
	a = b;
	b = temp;
}

void test01()
{
	int a = 10;
	int b = 20;
	
	//swapInt(a, b);

	//Exchange using template
	//1. Automatic type derivation
	mySwap(a, b);

	//2. Displays the specified type
	mySwap<int>(a, b);

	cout << "a = " << a << endl;
	cout << "b = " << b << endl;

}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary:

The function template uses the keyword template
There are two ways to use function templates: automatic type derivation and display of specified types
The purpose of template is to improve reusability and parameterize types

1.2.2 precautions for function template

matters needing attention:

For automatic type derivation, a consistent data type T must be derived before it can be used
The template can be used only after the data type of T is determined

Example:

//Using templates to provide general exchange functions
template<class T>
void mySwap(T& a, T& b)
{
	T temp = a;
	a = b;
	b = temp;
}


// 1. For automatic type derivation, a consistent data type T must be derived before it can be used
void test01()
{
	int a = 10;
	int b = 20;
	char c = 'c';

	mySwap(a, b); // Correct, a consistent T can be derived
	//mySwap(a, c); //  Error, unable to deduce a consistent T type
}


// 2. The template can be used only after the data type of T is determined
template<class T>
void func()
{
	cout << "func call" << endl;
}

void test02()
{
	//func(); // Error: the template cannot be used independently. The type of T must be determined
	func<int>(); //The template can be used only after T is given a type by displaying the specified type
}

int main() {

	test01();
	test02();

	system("pause");

	return 0;
}

Summary:

When using the template, the general data type T must be determined and the consistent type can be deduced

1.2.3 function template cases

Case description:

Using the function template to encapsulate a sorting function, you can sort arrays of different data types
The sorting rules are from large to small, and the sorting algorithm is selective sorting
Test with char array and int array respectively

Example:

//Exchanged function templates
template<typename T>
void mySwap(T &a, T&b)
{
	T temp = a;
	a = b;
	b = temp;
}


template<class T> // You can also replace it with typename
//Select sorting is used to sort the array from large to small
void mySort(T arr[], int len)
{
	for (int i = 0; i < len; i++)
	{
		int max = i; //Subscript of maximum number
		for (int j = i + 1; j < len; j++)
		{
			if (arr[max] < arr[j])
			{
				max = j;
			}
		}
		if (max != i) //If the subscript of the maximum number is not i, swap the two
		{
			mySwap(arr[max], arr[i]);
		}
	}
}
template<typename T>
void printArray(T arr[], int len) {

	for (int i = 0; i < len; i++) {
		cout << arr[i] << " ";
	}
	cout << endl;
}
void test01()
{
	//Test char array
	char charArr[] = "bdcfeagh";
	int num = sizeof(charArr) / sizeof(char);
	mySort(charArr, num);
	printArray(charArr, num);
}

void test02()
{
	//Test int array
	int intArr[] = { 7, 5, 8, 1, 3, 9, 2, 4, 6 };
	int num = sizeof(intArr) / sizeof(int);
	mySort(intArr, num);
	printArray(intArr, num);
}

int main() {

	test01();
	test02();

	system("pause");

	return 0;
}

Conclusion: template can improve code reuse, which needs to be mastered skillfully

1.2.4 differences between ordinary functions and function templates

Differences between ordinary functions and function templates:

Automatic type conversion (implicit type conversion) can occur when calling ordinary functions
When a function template is called, if automatic type derivation is used, implicit type conversion will not occur
Implicit type conversion can occur if the specified type is displayed

Example:

//Ordinary function
int myAdd01(int a, int b)
{
	return a + b;
}

//Function template
template<class T>
T myAdd02(T a, T b)  
{
	return a + b;
}

//When using function templates, if automatic type derivation is used, automatic type conversion will not occur, that is, implicit type conversion
void test01()
{
	int a = 10;
	int b = 20;
	char c = 'c';
	
	cout << myAdd01(a, c) << endl; //Correct, implicitly convert 'c' of char type to ASCII code 99 corresponding to int type 'c'

	//myAdd02(a, c); //  An error is reported. When automatic type derivation is used, implicit type conversion will not occur

	myAdd02<int>(a, c); //Correct, if you specify the type with display, implicit type conversion can occur
}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary: it is recommended to call the function template by displaying the specified type, because you can determine the general type T yourself

1.2.5 call rules for ordinary functions and function templates

The calling rules are as follows:

If both function templates and ordinary functions can be implemented, ordinary functions will be called first
You can force a function template to be called through an empty template parameter list
Function templates can also be overloaded
If the function template can produce a better match, call the function template first

Example:

//General function and function template calling rules
void myPrint(int a, int b)
{
	cout << "Ordinary functions called" << endl;
}

template<typename T>
void myPrint(T a, T b) 
{ 
	cout << "Called template" << endl;
}

template<typename T>
void myPrint(T a, T b, T c) 
{ 
	cout << "Call overloaded template" << endl; 
}

void test01()
{
	//1. If both function templates and ordinary functions can be implemented, ordinary functions will be called first
	// Note that if you tell the compiler that there are ordinary functions, but only declare that they are not implemented or not implemented in the current file, you will report an error and cannot find them
	int a = 10;
	int b = 20;
	myPrint(a, b); //Call normal function

	//2. You can force a function template to be called through an empty template parameter list
	myPrint<>(a, b); //Calling function template

	//3. Function templates can also be overloaded
	int c = 30;
	myPrint(a, b, c); //Call overloaded function template

	//4. If the function template can produce a better match, call the function template first
	char c1 = 'a';
	char c2 = 'b';
	myPrint(c1, c2); //Calling function template
}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary: since the function template is provided, it is better not to provide ordinary functions, otherwise ambiguity is likely to occur

1.2.6 limitations of formwork

limitations:

The versatility of templates is not everything

For example:

	template<class T>
	void f(T a, T b)
	{ 
    	a = b;
    }

The assignment operation provided in the above code cannot be implemented if the passed in a and b are an array

Another example:

	template<class T>
	void f(T a, T b)
	{ 
    	if(a > b) { ... }
    }

In the above code, if the data type of T is a user-defined data type such as Person, it will not work normally

Therefore, in order to solve this problem, C + + provides template overloading, which can provide specific templates for these specific types

Example:

#include<iostream>
using namespace std;

#include <string>

class Person
{
public:
	Person(string name, int age)
	{
		this->m_Name = name;
		this->m_Age = age;
	}
	string m_Name;
	int m_Age;
};

//Common function template
template<class T>
bool myCompare(T& a, T& b)
{
	if (a == b)
	{
		return true;
	}
	else
	{
		return false;
	}
}


//Materialize, display the materialized prototype and definition, start with template < >, and indicate the type by name
//Concretization takes precedence over regular templates
template<> bool myCompare(Person &p1, Person &p2)
{
	if ( p1.m_Name  == p2.m_Name && p1.m_Age == p2.m_Age)
	{
		return true;
	}
	else
	{
		return false;
	}
}

void test01()
{
	int a = 10;
	int b = 20;
	//The built-in data type can directly use the general function template
	bool ret = myCompare(a, b);
	if (ret)
	{
		cout << "a == b " << endl;
	}
	else
	{
		cout << "a != b " << endl;
	}
}

void test02()
{
	Person p1("Tom", 10);
	Person p2("Tom", 10);
	//User defined data types do not call normal function templates
	//You can create a template of materialized Person data type for special processing of this type
	bool ret = myCompare(p1, p2);
	if (ret)
	{
		cout << "p1 == p2 " << endl;
	}
	else
	{
		cout << "p1 != p2 " << endl;
	}
}

int main() {

	test01();

	test02();

	system("pause");

	return 0;
}

Summary:

The generalization of user-defined types can be solved by using specific templates
Learning templates is not to write templates, but to use the templates provided by the system in STL

Type 1.3 formwork

1.3.1 class template syntax

Class template function:

Establish a general class. The member data types in the class can be represented by a virtual type without specific formulation.

Syntax:

template<typename T>
class

Explanation:

Template - declare to create a template

typename - the symbol behind the surface is a data type, which can be replaced by class

T-A common data type whose name can be replaced, usually in uppercase letters

Example:

#include <string>
//Class template
template<class NameType, class AgeType> 
class Person
{
public:
	Person(NameType name, AgeType age)
	{
		this->mName = name;
		this->mAge = age;
	}
	void showPerson()
	{
		cout << "name: " << this->mName << " age: " << this->mAge << endl;
	}
public:
	NameType mName;
	AgeType mAge;
};

void test01()
{
	// Specify NameType as string type and AgeType as int type
	Person<string, int>P1("Sun WuKong", 999);
	P1.showPerson();
}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary: the syntax of class template is similar to that of function template. Add class after declaration template, which is called class template

1.3.2 difference between class template and function template

There are two main differences between class templates and function templates:

Class templates do not use automatic type derivation
Class templates can have default parameters in the template parameter list

Example:

#include <string>
//Class template
template<class NameType, class AgeType = int> 
class Person
{
public:
	Person(NameType name, AgeType age)
	{
		this->mName = name;
		this->mAge = age;
	}
	void showPerson()
	{
		cout << "name: " << this->mName << " age: " << this->mAge << endl;
	}
public:
	NameType mName;
	AgeType mAge;
};

//1. Class templates do not use automatic type derivation
void test01()
{
	// Person p("Monkey King", 1000)// Automatic type derivation is not allowed when error class templates are used
	Person <string ,int>p("Sun WuKong", 1000); //The class template must be used in a way that displays the specified type
	p.showPerson();
}

//2. Class templates can have default parameters in the template parameter list
void test02()
{
	Person <string> p("Zhu Bajie", 999); //The template parameter list in the class template can specify default parameters
	p.showPerson();
}

int main() {

	test01();

	test02();

	system("pause");

	return 0;
}

Summary:

Class templates can only be used by displaying the specified type
The template parameter list in the class template can have default parameters

1.3.3 creation time of member function in class template

The creation timing of member functions in class templates is different from that in ordinary classes:

Member functions in ordinary classes can be created from the beginning
Member functions in class templates are created only when called

Example:

class Person1
{
public:
	void showPerson1()
	{
		cout << "Person1 show" << endl;
	}
};

class Person2
{
public:
	void showPerson2()
	{
		cout << "Person2 show" << endl;
	}
};

template<class T>
class MyClass
{
public:
	T obj;

	//The member functions in the class template are not created at the beginning, but are generated when the template is called

	void fun1() { obj.showPerson1(); }
	void fun2() { obj.showPerson2(); }

};

void test01()
{
	MyClass<Person1> m;
	
	m.fun1();

	//m.fun2();// There will be an error in compilation, which means that the function call will create the member function
}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary: the member functions in the class template are not created at the beginning, but only when called

1.3.4 function parameters of class template objects

Learning objectives:

The object instantiated by the class template is the way to pass parameters to the function

There are three incoming methods:

Specify the type of incoming - displays the data type of the object directly
Parameter templating - changes parameters in an object into templates for transfer
Whole class templating - pass this object type templating

Example:

#include <string>
//Class template
template<class NameType, class AgeType = int> 
class Person
{
public:
	Person(NameType name, AgeType age)
	{
		this->mName = name;
		this->mAge = age;
	}
	void showPerson()
	{
		cout << "name: " << this->mName << " age: " << this->mAge << endl;
	}
public:
	NameType mName;
	AgeType mAge;
};

//1. Specify the type of incoming
void printPerson1(Person<string, int> &p) 
{
	p.showPerson();
}
void test01()
{
	Person <string, int >p("Sun WuKong", 100);
	printPerson1(p);
}

//2. Parameter Templating
template <class T1, class T2>
void printPerson2(Person<T1, T2>&p)
{
	p.showPerson();
	cout << "T1 The types of are: " << typeid(T1).name() << endl;
	cout << "T2 The types of are: " << typeid(T2).name() << endl;
}
void test02()
{
	Person <string, int >p("Zhu Bajie", 90);
	printPerson2(p);
}

//3. Whole class Templating
template<class T>
void printPerson3(T & p)
{
	cout << "T The types of are: " << typeid(T).name() << endl;
	p.showPerson();

}
void test03()
{
	Person <string, int >p("Tang Monk", 30);
	printPerson3(p);
}

int main() {

	test01();
	test02();
	test03();

	system("pause");

	return 0;
}

Summary:

There are three ways to pass parameters to functions for objects created through class templates
The first one is widely used: specify the type of incoming

1.3.5 class template and inheritance

When the class template encounters inheritance, you should pay attention to the following points:

When the parent class inherited by the subclass is a class template, when declaring the subclass, specify the type of T in the parent class
If not specified, the compiler cannot allocate memory to subclasses
If you want to flexibly specify the type of T in the parent class, the subclass also needs to be changed into a class template

Example:

template<class T>
class Base
{
	T m;
};

//class Son:public Base / / error: memory needs to be allocated to subclasses for c + + compilation. You must know the type of T in the parent class before you can inherit downward
class Son :public Base<int> //You must specify a type
{
};
void test01()
{
	Son c;
}

//The class template inherits the class template. You can use T2 to specify the T type in the parent class
template<class T1, class T2>
class Son2 :public Base<T2>
{
public:
	Son2()
	{
		cout << typeid(T1).name() << endl;
		cout << typeid(T2).name() << endl;
	}
};

void test02()
{
	Son2<int, char> child1;
}


int main() {

	test01();

	test02();

	system("pause");

	return 0;
}

Summary: if the parent class is a class template, the child class needs to specify the data type of T in the parent class

1.3.6 implementation outside class of class template member function

Learning objectives: be able to master the implementation of member functions outside the class in the class template

Example:

#include <string>

//Implementation outside class of member function in class template
template<class T1, class T2>
class Person {
public:
	//Member function class declaration
	Person(T1 name, T2 age);
	void showPerson();

public:
	T1 m_Name;
	T2 m_Age;
};

//Constructor out of class implementation
template<class T1, class T2>
Person<T1, T2>::Person(T1 name, T2 age) {
	this->m_Name = name;
	this->m_Age = age;
}

//Out of class implementation of member function
template<class T1, class T2>
void Person<T1, T2>::showPerson() {
	cout << "full name: " << this->m_Name << " Age:" << this->m_Age << endl;
}

void test01()
{
	Person<string, int> p("Tom", 20);
	p.showPerson();
}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary: when the member function in the class template is implemented outside the class, the template parameter list needs to be added

1.3.7 preparation of class template by document

Learning objectives:

Master the problems and solutions arising from the preparation of class template member function sub files

Question:

The creation time of the member function in the class template is in the calling stage, which leads to the link failure when writing the sub file

solve:

Solution 1: include directly cpp source file
Solution 2: write the declaration and implementation to the same file and change the suffix to hpp, hpp is the agreed name, not mandatory

Example:

person. Code in HPP:

#pragma once
#include <iostream>
using namespace std;
#include <string>

template<class T1, class T2>
class Person {
public:
	Person(T1 name, T2 age);
	void showPerson();
public:
	T1 m_Name;
	T2 m_Age;
};

//Constructor out of class implementation
template<class T1, class T2>
Person<T1, T2>::Person(T1 name, T2 age) {
	this->m_Name = name;
	this->m_Age = age;
}

//Out of class implementation of member function
template<class T1, class T2>
void Person<T1, T2>::showPerson() {
	cout << "full name: " << this->m_Name << " Age:" << this->m_Age << endl;
}

Class templates are written in files Code in cpp

#include<iostream>
using namespace std;

//#include "person.h"
#include "person.cpp" / / solution 1: include the cpp source file

//Solution 2: write the declaration and implementation together, and change the file suffix to hpp
#include "person.hpp"
void test01()
{
	Person<string, int> p("Tom", 10);
	p.showPerson();
}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary: the second solution is to write the class template member functions together and change the suffix to hpp

1.3.8 class templates and friends

Learning objectives:

Master the in class and out of class implementation of class template and friend function

Implementation of global function in class - just declare friends directly in class

Out of class implementation of global functions - you need to let the compiler know the existence of global functions in advance

Example:

#include <string>

//2. The global function is implemented outside the friend class - first make the function template declaration, and then make the function template definition, and then make the friend
template<class T1, class T2> class Person;

//If the function template is declared, you can write the implementation to the back, otherwise you need to write the implementation to the front of the class for the compiler to see in advance
//template<class T1, class T2> void printPerson2(Person<T1, T2> & p); 

template<class T1, class T2>
void printPerson2(Person<T1, T2> & p)
{
	cout << "Out of class implementation ---- full name: " << p.m_Name << " Age:" << p.m_Age << endl;
}

template<class T1, class T2>
class Person
{
	//1. Global functions are implemented within friend classes
	friend void printPerson(Person<T1, T2> & p)
	{
		cout << "full name: " << p.m_Name << " Age:" << p.m_Age << endl;
	}


	//The global function is implemented outside the friend class
	friend void printPerson2<>(Person<T1, T2> & p);

public:

	Person(T1 name, T2 age)
	{
		this->m_Name = name;
		this->m_Age = age;
	}


private:
	T1 m_Name;
	T2 m_Age;

};

//1. Global functions are implemented within classes
void test01()
{
	Person <string, int >p("Tom", 20);
	printPerson(p);
}


//2. Global functions are implemented outside the class
void test02()
{
	Person <string, int >p("Jerry", 30);
	printPerson2(p);
}

int main() {

	//test01();

	test02();

	system("pause");

	return 0;
}

Summary: it is recommended to implement the global function in class, which is simple to use and can be directly recognized by the compiler

1.3.9 type template cases

Case description: implement a general array class. The requirements are as follows:

Data of built-in data type and user-defined data type can be stored
Store the data in the array in the heap
The capacity of the array that can be passed in the constructor
Provide the corresponding copy constructor and operator = to prevent shallow copy problems
Tail interpolation and tail deletion methods are provided to add and delete data in the array
The elements in the array can be accessed by subscript
You can get the current number of elements in the array and the capacity of the array

Example:

myArray. Code in HPP

#pragma once
#include <iostream>
using namespace std;

template<class T>
class MyArray
{
public:
    
	//Constructor
	MyArray(int capacity)
	{
		this->m_Capacity = capacity;
		this->m_Size = 0;
		pAddress = new T[this->m_Capacity];
	}

	//copy construction 
	MyArray(const MyArray & arr)
	{
		this->m_Capacity = arr.m_Capacity;
		this->m_Size = arr.m_Size;
		this->pAddress = new T[this->m_Capacity];
		for (int i = 0; i < this->m_Size; i++)
		{
			//If T is an object and contains a pointer, the = operator must be overloaded, because the equal sign is not a construction but an assignment,
			// Ordinary types can be directly = but pointer types need deep copy
			this->pAddress[i] = arr.pAddress[i];
		}
	}

	//Overload = operator prevents shallow copy problems
	MyArray& operator=(const MyArray& myarray) {

		if (this->pAddress != NULL) {
			delete[] this->pAddress;
			this->m_Capacity = 0;
			this->m_Size = 0;
		}

		this->m_Capacity = myarray.m_Capacity;
		this->m_Size = myarray.m_Size;
		this->pAddress = new T[this->m_Capacity];
		for (int i = 0; i < this->m_Size; i++) {
			this->pAddress[i] = myarray[i];
		}
		return *this;
	}

	//Overload [] operator arr[0]
	T& operator [](int index)
	{
		return this->pAddress[index]; //Do not consider crossing the boundary, and the user will handle it by himself
	}

	//Tail interpolation
	void Push_back(const T & val)
	{
		if (this->m_Capacity == this->m_Size)
		{
			return;
		}
		this->pAddress[this->m_Size] = val;
		this->m_Size++;
	}

	//Tail deletion
	void Pop_back()
	{
		if (this->m_Size == 0)
		{
			return;
		}
		this->m_Size--;
	}

	//Get array capacity
	int getCapacity()
	{
		return this->m_Capacity;
	}

	//Get array size
	int	getSize()
	{
		return this->m_Size;
	}


	//Deconstruction
	~MyArray()
	{
		if (this->pAddress != NULL)
		{
			delete[] this->pAddress;
			this->pAddress = NULL;
			this->m_Capacity = 0;
			this->m_Size = 0;
		}
	}

private:
	T * pAddress;  //Points to a heap space that stores real data
	int m_Capacity; //capacity
	int m_Size;   // size
};

Class template case - array class encapsulation In cpp

#include "myArray.hpp"
#include <string>

void printIntArray(MyArray<int>& arr) {
	for (int i = 0; i < arr.getSize(); i++) {
		cout << arr[i] << " ";
	}
	cout << endl;
}

//Test built-in data types
void test01()
{
	MyArray<int> array1(10);
	for (int i = 0; i < 10; i++)
	{
		array1.Push_back(i);
	}
	cout << "array1 Printout:" << endl;
	printIntArray(array1);
	cout << "array1 Size of:" << array1.getSize() << endl;
	cout << "array1 Capacity:" << array1.getCapacity() << endl;

	cout << "--------------------------" << endl;

	MyArray<int> array2(array1);
	array2.Pop_back();
	cout << "array2 Printout:" << endl;
	printIntArray(array2);
	cout << "array2 Size of:" << array2.getSize() << endl;
	cout << "array2 Capacity:" << array2.getCapacity() << endl;
}

//Test custom data types
class Person {
public:
	Person() {} 
		Person(string name, int age) {
		this->m_Name = name;
		this->m_Age = age;
	}
public:
	string m_Name;
	int m_Age;
};

void printPersonArray(MyArray<Person>& personArr)
{
	for (int i = 0; i < personArr.getSize(); i++) {
		cout << "full name:" << personArr[i].m_Name << " Age: " << personArr[i].m_Age << endl;
	}

}

void test02()
{
	//Create array
	MyArray<Person> pArray(10);
	Person p1("Sun WuKong", 30);
	Person p2("Han Xin", 20);
	Person p3("Daji", 18);
	Person p4("Wang Zhaojun", 15);
	Person p5("Zhao Yun", 24);

	//insert data
	pArray.Push_back(p1);
	pArray.Push_back(p2);
	pArray.Push_back(p3);
	pArray.Push_back(p4);
	pArray.Push_back(p5);

	printPersonArray(pArray);

	cout << "pArray Size of:" << pArray.getSize() << endl;
	cout << "pArray Capacity:" << pArray.getCapacity() << endl;

}

int main() {

	//test01();

	test02();

	system("pause");

	return 0;
}

Summary:

Be able to use the knowledge points learned to realize a general array

First knowledge STL

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

Container: various data structures, such as vector, list, deque, set, map, etc., are used to store data.
Algorithm: various commonly used algorithms, such as sort, find, copy and for_each et al
Iterator: acts as the glue between the container and the algorithm.
Imitation function: the behavior is similar to the function, which can be used as a strategy of the algorithm.
Adapter: something used to decorate a container or an interface to an emulator or iterator.
Space configurator: responsible for space configuration and management.

2.4 containers, algorithms and iterators in STL

**Container: * * place of storage

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: * * 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, etc

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

**Iterator: * * glue between container and algorithm

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() {

	//The data type in the container is specified by the parameter vector in the template
	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;
}

3 STL - Common containers

3.1 string container

3.1.1 basic concept of string

Essence:

String is a C + + style string, and string is essentially a class

The difference between string and char *:

char * is a pointer
String is a class with char * encapsulated inside. It is a container of char * type to manage this string.

characteristic:

string class encapsulates many member methods

For example: find, copy, delete, replace, insert

string manages the memory allocated by char * without worrying about copy out of bounds and value out of bounds. It is the responsibility of the class

3.1.2 string constructor

Constructor prototype:

string(); // Create an empty string, for example: string str;
string(const char* s); // Initialize with string s
string(const string& str); // Initializing another string object with one string object
string(int n, char c); // Initialize with n characters C

Example:

#include <string>
//string construction
void test01()
{
	string s1; //Create an empty string and call the parameterless constructor
	cout << "str1 = " << s1 << endl;

	const char* str = "hello world";
	string s2(str); //Put c_string converted to string

	cout << "str2 = " << s2 << endl;

	string s3(s2); //Call copy constructor
	cout << "str3 = " << s3 << endl;

	string s4(10, 'a');
	cout << "str3 = " << s3 << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary: there is no comparability in the various construction methods of string, so it can be used flexibly

3.1.3 string assignment

Function Description:

Assign a value to a string

Prototype of assigned function:

string& operator=(const char* s); // Char * type string is assigned to the current string
string& operator=(const string &s); // Assign the string s to the current string
string& operator=(char c); // The character is assigned to the current string
string& assign(const char *s); // Assign the string s to the current string
string& assign(const char *s, int n); // Assign the first n characters of string s to the current string
string& assign(const string &s); // Assign string s to the current string
string& assign(int n, char c); // Assign n characters C to the current string

Example:

//assignment
void test01()
{
	string str1;
	str1 = "hello world";
	cout << "str1 = " << str1 << endl;

	string str2;
	str2 = str1;
	cout << "str2 = " << str2 << endl;

	string str3;
	str3 = 'a';
	cout << "str3 = " << str3 << endl;

	string str4;
	str4.assign("hello c++");
	cout << "str4 = " << str4 << endl;

	string str5;
	str5.assign("hello c++",5);
	cout << "str5 = " << str5 << endl;


	string str6;
	str6.assign(str5);
	cout << "str6 = " << str6 << endl;

	string str7;
	str7.assign(5, 'x');
	cout << "str7 = " << str7 << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary:

There are many ways to assign values to string s, and operator = is more practical

3.1.4 string splicing

Function Description:

Implements splicing strings at the end of a string

Function prototype:

string& operator+=(const char* str); // Overload + = operator
string& operator+=(const char c); // Overload + = operator
string& operator+=(const string& str); // Overload + = operator
string& append(const char *s); // Connects the string s to the end of the current string
string& append(const char *s, int n); // Connect the first n characters of string s to the end of the current string
string& append(const string &s); // Same as operator + = (const string & STR)
string& append(const string &s, int pos, int n);// N characters from POS in string s are connected to the end of the string

Example:

//String splicing
void test01()
{
	string str1 = "I";

	str1 += "Love playing games";

	cout << "str1 = " << str1 << endl;
	
	str1 += ':';

	cout << "str1 = " << str1 << endl;

	string str2 = "LOL DNF";

	str1 += str2;

	cout << "str1 = " << str1 << endl;

	string str3 = "I";
	str3.append(" love ");
	str3.append("game abcde", 4);
	//str3.append(str2);
	str3.append(str2, 4, 3); // Starting from the subscript 4 position, intercept 3 characters and splice them to the end of the string
	cout << "str3 = " << str3 << endl;
}
int main() {

	test01();

	system("pause");

	return 0;
}

Summary: there are many overloaded versions of string splicing. Just remember several at the beginning of learning

3.1.5 string find and replace

Function Description:

Find: finds whether the specified string exists
Replace: replaces the string at the specified position

Function prototype:

int find(const string& str, int pos = 0) const; // Find the location where STR appears for the first time, starting from POS
int find(const char* s, int pos = 0) const; // Find the location where s first appears, starting from POS
int find(const char* s, int pos, int n) const; // Find the first position of the first n characters of s from the POS position
int find(const char c, int pos = 0) const; // Find where the character c first appears
int rfind(const string& str, int pos = npos) const; // Find the last position of STR, starting from POS
int rfind(const char* s, int pos = npos) const; // Find the location of the last occurrence of S, starting from POS
int rfind(const char* s, int pos, int n) const; // Find the last position of the first n characters of s from POS
int rfind(const char c, int pos = 0) const; // Find the last occurrence of character c
string& replace(int pos, int n, const string& str); // Replace n characters starting from POS with string str
string& replace(int pos, int n,const char* s); // Replace the n characters starting from POS with the string s

Example:

//Find and replace
void test01()
{
	//lookup
	string str1 = "abcdefgde";

	int pos = str1.find("de");

	if (pos == -1)
	{
		cout << "not found" << endl;
	}
	else
	{
		cout << "pos = " << pos << endl;
	}
	

	pos = str1.rfind("de");

	cout << "pos = " << pos << endl;

}

void test02()
{
	//replace
	string str1 = "abcdefgde";
	str1.replace(1, 3, "1111");

	cout << "str1 = " << str1 << endl;
}

int main() {

	//test01();
	//test02();

	system("pause");

	return 0;
}

Summary:

find is from left to back, and rfind is from right to left
find returns the position of the first character after finding the string. If not, it returns - 1
When replacing, you need to specify where to start, how many characters to replace and what kind of string to replace

3.1.6 string comparison

Function Description:

Comparison between strings

Comparison method:

String comparison is based on the ASCII code of characters

=Return 0

>Return 1

< return - 1

Function prototype:

int compare(const string &s) const; // Compare with string s
int compare(const char *s) const; // Compare with string s

Example:

//string comparison
void test01()
{

	string s1 = "hello";
	string s2 = "aello";

	int ret = s1.compare(s2);

	if (ret == 0) {
		cout << "s1 be equal to s2" << endl;
	}
	else if (ret > 0)
	{
		cout << "s1 greater than s2" << endl;
	}
	else
	{
		cout << "s1 less than s2" << endl;
	}

}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary: string comparison is mainly used to compare whether two strings are equal. It is not of great significance to judge who is big and who is small

3.1.7 string character access

There are two ways to access a single character in a string

char& operator[](int n); // Take characters by []
char& at(int n); // Get characters through at method

Example:

void test01()
{
	string str = "hello world";

	for (int i = 0; i < str.size(); i++)
	{
		cout << str[i] << " ";
	}
	cout << endl;

	for (int i = 0; i < str.size(); i++)
	{
		cout << str.at(i) << " ";
	}
	cout << endl;


	//Character modification
	str[0] = 'x';
	str.at(1) = 'x';
	cout << str << endl;
	
}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary: there are two ways to access a single character in a string, using [] or at

3.1.8 string insertion and deletion

Function Description:

Insert and delete characters from a string

Function prototype:

string& insert(int pos, const char* s); // Insert string
string& insert(int pos, const string& str); // Insert string
string& insert(int pos, int n, char c); // Insert n characters in the specified position C
string& erase(int Pos, int n = npos); // Delete n characters starting from Pos

Example:

//String insertion and deletion
void test01()
{
	string str = "hello";
	str.insert(1, "111");
	cout << str << endl;

	str.erase(1, 3);  //3 characters from position 1
	cout << str << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

**Summary: * * the initial subscripts of insertion and deletion start from 0

3.1.9 string substring

Function Description:

Get the desired substring from the string

Function prototype:

string substr(int pos = 0, int n = npos) const; // Returns a string of n characters starting with POS

Example:

//Substring
void test01()
{

	string str = "abcdefg";
	string subStr = str.substr(1, 3);
	cout << "subStr = " << subStr << endl;

	string email = "hello@sina.com";
	int pos = email.find("@");
	string username = email.substr(0, pos);
	cout << "username: " << username << endl;

}

int main() {

	test01();

	system("pause");

	return 0;
}

**Summary: * * flexible use of substring function can obtain effective information in actual development

3.2 vector container

3.2.1 basic concept of vector

Function:

vector data structure is very similar to array, also known as single ended array

The difference between vector and ordinary array:

The difference is that the array is a static space, while the vector can be extended dynamically

Dynamic expansion:

Instead of adding a new space after the original space, find a larger memory space, and then copy the original data to the new space to release the original space

The iterator of the vector container is an iterator that supports random access

3.2.2 vector constructor

Function Description:

Create vector container

Function prototype:

vector<T> v; // Using template implementation class implementation, default constructor
vector(v.begin(), v.end()); // Copy the elements in the v[begin(), end()) interval to itself.
vector(n, elem); // The constructor copies n elems to itself.
vector(const vector &vec); // Copy constructor.

Example:

#include <vector>

void printVector(vector<int>& v) {

	for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

void test01()
{
	vector<int> v1; //Nonparametric structure
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	printVector(v1);

	vector<int> v2(v1.begin(), v1.end());
	printVector(v2);

	vector<int> v3(10, 100);
	printVector(v3);
	
	vector<int> v4(v3);
	printVector(v4);
}

int main() {

	test01();

	system("pause");

	return 0;
}

**Summary: * * many construction methods of vector are not comparable and can be used flexibly

3.2.3 vector assignment

Function Description:

Assign a value to the vector container

Function prototype:

vector& operator=(const vector &vec);// Overloaded equal sign operator
assign(beg, end); // Assign the data copy in the [beg, end) interval to itself.
assign(n, elem); // Assign n elem copies to itself

Example:

#include <vector>

void printVector(vector<int>& v) {

	for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

//Assignment operation
void test01()
{
	vector<int> v1; //Nonparametric structure
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	printVector(v1);

	vector<int>v2;
	v2 = v1;
	printVector(v2);

	vector<int>v3;
	v3.assign(v1.begin(), v1.end());
	printVector(v3);

	vector<int>v4;
	v4.assign(10, 100);
	printVector(v4);
}

int main() {

	test01();

	system("pause");

	return 0;
}

Conclusion: the assignment method of vector is relatively simple. You can use operator =, or assign

3.2.4 vector capacity and size

Function Description:

Operation on the capacity and size of the vector container

Function prototype:

empty(); // Determine whether the container is empty
capacity(); // Capacity of container
size(); // Returns the number of elements in the container
resize(int num); // Reassign the length of the container to num. if the container becomes longer, the new location will be filled with the default value.

/ / if the container becomes shorter, the element whose end exceeds the length of the container will be deleted.
resize(int num, elem); // Reassign the length of the container to num. if the container becomes longer, fill the new position with elem value.

/ / if the container becomes shorter, the element whose end exceeds the length of the container will be deleted

Example:

#include <vector>

void printVector(vector<int>& v) {

	for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

void test01()
{
	vector<int> v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	printVector(v1);
	if (v1.empty())
	{
		cout << "v1 Empty" << endl;
	}
	else
	{
		cout << "v1 Not empty" << endl;
		cout << "v1 Capacity of = " << v1.capacity() << endl;
		cout << "v1 Size of = " << v1.size() << endl;
	}

	//resize re specifies the size. If the specified size is larger, the new location will be filled with 0 by default. You can use the overloaded version to replace the default filling
	v1.resize(15,10);
	printVector(v1);

	//resize re specifies the size. If the specified size is smaller, the excess elements will be deleted
	v1.resize(5);
	printVector(v1);
}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary:

Judge whether it is empty empty
Return the number of elements - size
Return container capacity - capacity
Resize - resize

3.2.5 vector insertion and deletion

Function Description:

Insert and delete the vector container

Function prototype:

push_back(ele); // Tail insert element ele
pop_back(); // Delete last element
insert(const_iterator pos, ele); // The iterator points to the position POS and inserts the element ele
insert(const_iterator pos, int count,ele);// The iterator points to the position POS and inserts count elements ele
erase(const_iterator pos); // Delete the element pointed to by the iterator
erase(const_iterator start, const_iterator end);// Delete the elements of the iterator from start to end
clear(); // Delete all elements in the container

Example:

#include <vector>

void printVector(vector<int>& v) {

	for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

//Insert and delete
void test01()
{
	vector<int> v1;
	//Tail insertion
	v1.push_back(10);
	v1.push_back(20);
	v1.push_back(30);
	v1.push_back(40);
	v1.push_back(50);
	printVector(v1);
	//Tail deletion
	v1.pop_back();
	printVector(v1);
	//insert
	v1.insert(v1.begin(), 100);
	printVector(v1);

	v1.insert(v1.begin(), 2, 1000);
	printVector(v1);

	//delete
	v1.erase(v1.begin());
	printVector(v1);

	//empty
	v1.erase(v1.begin(), v1.end());
	v1.clear();
	printVector(v1);
}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary:

Tail push_back
Tail deletion pop_back
Insert insert (position iterator)
Delete - erase (position iterator)
Empty - clear

3.2.6 vector data access

Function Description:

Access to data in vector

Function prototype:

at(int idx); // Returns the data indicated by the index idx
operator[]; // Returns the data indicated by the index idx
front(); // Returns the first data element in the container
back(); // Returns the last data element in the container

Example:

#include <vector>

void test01()
{
	vector<int>v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}

	for (int i = 0; i < v1.size(); i++)
	{
		cout << v1[i] << " ";
	}
	cout << endl;

	for (int i = 0; i < v1.size(); i++)
	{
		cout << v1.at(i) << " ";
	}
	cout << endl;

	cout << "v1 The first element of is: " << v1.front() << endl;
	cout << "v1 The last element of the is: " << v1.back() << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary:

In addition to using iterators to get the elements in the vector container, [] and at can also be used
front returns the first element of the container
back returns the last element of the container

3.2.7 vector interchange container

Function Description:

Realize the exchange of elements in two containers

Function prototype:

swap(vec); // Swap VEC with its own elements

Example:

#include <vector>

void printVector(vector<int>& v) {

	for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

void test01()
{
	vector<int>v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	printVector(v1);

	vector<int>v2;
	for (int i = 10; i > 0; i--)
	{
		v2.push_back(i);
	}
	printVector(v2);

	//Interchangeable container
	cout << "After exchange" << endl;
	v1.swap(v2);
	printVector(v1);
	printVector(v2);
}

void test02()
{
	vector<int> v;
	for (int i = 0; i < 100000; i++) {
		v.push_back(i);
	}

	cout << "v The capacity of the is:" << v.capacity() << endl;
	cout << "v The size of the is:" << v.size() << endl;

	v.resize(3);

	cout << "v The capacity of the is:" << v.capacity() << endl;
	cout << "v The size of the is:" << v.size() << endl;

	//Shrink memory
	vector<int>(v).swap(v); //Anonymous object

	cout << "v The capacity of the is:" << v.capacity() << endl;
	cout << "v The size of the is:" << v.size() << endl;
}

int main() {

	test01();

	test02();

	system("pause");

	return 0;
}

Conclusion: swap can exchange two containers and achieve the practical effect of shrinking memory

3.2.8 reserved space for vector

Function Description:

Reduce the expansion times of vector when dynamically expanding capacity

Function prototype:

reserve(int len);// The container reserves len element lengths. The reserved positions are not initialized and the elements are inaccessible.

Example:

#include <vector>

void test01()
{
	vector<int> v;

	//Reserved space
	v.reserve(100000);

	int num = 0;
	int* p = NULL;
	for (int i = 0; i < 100000; i++) {
		v.push_back(i);
		if (p != &v[0]) {
			p = &v[0];
			num++;
		}
	}

	cout << "num:" << num << endl;
}

int main() {

	test01();
    
	system("pause");

	return 0;
}

Conclusion: if the amount of data is large, reserve space can be used to reserve space at the beginning

3.3 deque container

3.3.1 basic concept of deque container

Function:

Double ended array, which can insert and delete the head end

The difference between deque and vector:

vector is inefficient for inserting and deleting headers. The larger the amount of data, the lower the efficiency
deque relatively speaking, the insertion and deletion speed of the head is faster than that of the vector
vector accesses elements faster than deque, which is related to their internal implementation

Internal working principle of deque:

deque has a central controller inside, which maintains the contents of each buffer and stores real data in the buffer

The central controller maintains the address of each buffer, making deque like a continuous memory space

The iterator of deque container also supports random access

3.3.2 deque constructor

Function Description:

deque vessel construction

Function prototype:

deque<T> deqT; // Default construction form
deque(beg, end); // Copy the element in the [End] constructor to itself.
deque(n, elem); // The constructor copies n elems to itself.
deque(const deque &deq); // copy constructor

Example:

#include <deque>

void printDeque(const deque<int>& d) 
{
	for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
		cout << *it << " ";

	}
	cout << endl;
}
//deque structure
void test01() {

	deque<int> d1; //non-parameter constructor 
	for (int i = 0; i < 10; i++)
	{
		d1.push_back(i);
	}
	printDeque(d1);
	deque<int> d2(d1.begin(),d1.end());
	printDeque(d2);

	deque<int>d3(10,100);
	printDeque(d3);

	deque<int>d4 = d3;
	printDeque(d4);
}

int main() {

	test01();

	system("pause");

	return 0;
}

**Summary: * * the structure of deque container and vector container are almost the same, which can be used flexibly

3.3.3 deque assignment

Function Description:

Assign a value to the deque container

Function prototype:

deque& operator=(const deque &deq); // Overloaded equal sign operator
assign(beg, end); // Assign the data copy in the [beg, end) interval to itself.
assign(n, elem); // Assign n elem copies to itself.

Example:

#include <deque>

void printDeque(const deque<int>& d) 
{
	for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
		cout << *it << " ";

	}
	cout << endl;
}
//Assignment operation
void test01()
{
	deque<int> d1;
	for (int i = 0; i < 10; i++)
	{
		d1.push_back(i);
	}
	printDeque(d1);

	deque<int>d2;
	d2 = d1;
	printDeque(d2);

	deque<int>d3;
	d3.assign(d1.begin(), d1.end());
	printDeque(d3);

	deque<int>d4;
	d4.assign(10, 100);
	printDeque(d4);

}

int main() {

	test01();

	system("pause");

	return 0;
}

Conclusion: the deque assignment operation is also the same as that of vector, which needs to be mastered

3.3.4 deque size operation

Function Description:

Operate on the size of the deque container

Function prototype:

deque.empty(); // Determine whether the container is empty
deque.size(); // Returns the number of elements in the container
deque.resize(num); // Reassign the length of the container to num. if the container becomes longer, the new location will be filled with the default value.

/ / if the container becomes shorter, the element whose end exceeds the length of the container will be deleted.
deque.resize(num, elem); // Reassign the length of the container to num. if the container becomes longer, fill the new position with elem value.

/ / if the container becomes shorter, the element whose end exceeds the length of the container will be deleted.

Example:

#include <deque>

void printDeque(const deque<int>& d) 
{
	for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
		cout << *it << " ";

	}
	cout << endl;
}

//Size operation
void test01()
{
	deque<int> d1;
	for (int i = 0; i < 10; i++)
	{
		d1.push_back(i);
	}
	printDeque(d1);

	//Determine whether the container is empty
	if (d1.empty()) {
		cout << "d1 Empty!" << endl;
	}
	else {
		cout << "d1 Not empty!" << endl;
		//Statistical size
		cout << "d1 The size of the is:" << d1.size() << endl;
	}

	//Reassign size
	d1.resize(15, 1);
	printDeque(d1);

	d1.resize(5);
	printDeque(d1);
}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary:

deque has no concept of capacity
Judge whether it is empty empty
Return the number of elements - size
Reassign number - resize

3.3.5 deque insertion and deletion

Function Description:

Inserting and deleting data into the deque container

Function prototype:

Insert at both ends:

push_back(elem); // Add a data at the end of the container
push_front(elem); // Insert a data in the head of the container
pop_back(); // Delete the last data in the container
pop_front(); // Delete first data of container

Specify location operation:

insert(pos,elem); // Insert a copy of the elem element in the POS position and return the location of the new data.
insert(pos,n,elem); // Insert n elem data in POS position, and there is no return value.
insert(pos,beg,end); // Insert the data of the [beg, end) interval in the POS position, and there is no return value.
clear(); // Empty all data in the container
erase(beg,end); // Delete the data in the [beg, end) interval and return the position of the next data.
erase(pos); // Delete the data in POS position and return to the position of the next data.

Example:

#include <deque>

void printDeque(const deque<int>& d) 
{
	for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
		cout << *it << " ";

	}
	cout << endl;
}
//Two end operation
void test01()
{
	deque<int> d;
	//Tail insertion
	d.push_back(10);
	d.push_back(20);
	//Head insert
	d.push_front(100);
	d.push_front(200);

	printDeque(d);

	//Tail deletion
	d.pop_back();
	//Header deletion
	d.pop_front();
	printDeque(d);
}

//insert
void test02()
{
	deque<int> d;
	d.push_back(10);
	d.push_back(20);
	d.push_front(100);
	d.push_front(200);
	printDeque(d);

	d.insert(d.begin(), 1000);
	printDeque(d);

	d.insert(d.begin(), 2,10000);
	printDeque(d);

	deque<int>d2;
	d2.push_back(1);
	d2.push_back(2);
	d2.push_back(3);

	d.insert(d.begin(), d2.begin(), d2.end());
	printDeque(d);

}

//delete
void test03()
{
	deque<int> d;
	d.push_back(10);
	d.push_back(20);
	d.push_front(100);
	d.push_front(200);
	printDeque(d);

	d.erase(d.begin());
	printDeque(d);

	d.erase(d.begin(), d.end());
	d.clear();
	printDeque(d);
}

int main() {

	//test01();

	//test02();

    test03();
    
	system("pause");

	return 0;
}

Summary:

Insert and delete the position provided is an iterator!
Tail push_back
Tail deletion pop_back
Head push_front
Header deletion - pop_front

3.3.6 deque data access

Function Description:

Access to data in deque

Function prototype:

at(int idx); // Returns the data indicated by the index idx
operator[]; // Returns the data indicated by the index idx
front(); // Returns the first data element in the container
back(); // Returns the last data element in the container

Example:

#include <deque>

void printDeque(const deque<int>& d) 
{
	for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
		cout << *it << " ";

	}
	cout << endl;
}

//data access 
void test01()
{

	deque<int> d;
	d.push_back(10);
	d.push_back(20);
	d.push_front(100);
	d.push_front(200);

	for (int i = 0; i < d.size(); i++) {
		cout << d[i] << " ";
	}
	cout << endl;


	for (int i = 0; i < d.size(); i++) {
		cout << d.at(i) << " ";
	}
	cout << endl;

	cout << "front:" << d.front() << endl;

	cout << "back:" << d.back() << endl;

}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary:

In addition to using iterators to get the elements in the deque container, [] and at can also be used
front returns the first element of the container
back returns the last element of the container

3.3.7 deque sorting

Function Description:

Using algorithm to sort deque containers

Algorithm:

sort(iterator beg, iterator end) / / sort the elements in the beg and end intervals

Example:

#include <deque>
#include <algorithm>

void printDeque(const deque<int>& d) 
{
	for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
		cout << *it << " ";

	}
	cout << endl;
}

void test01()
{

	deque<int> d;
	d.push_back(10);
	d.push_back(20);
	d.push_front(100);
	d.push_front(200);

	printDeque(d);
	sort(d.begin(), d.end());
	printDeque(d);

}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary: the sort algorithm is very practical. When used, it can include the header file algorithm

3.4 cases - scoring by judges

3.4.1 case description

There are five contestants: contestant ABCDE, and 10 judges will score each contestant respectively, removing the highest score and the lowest score among the judges, and taking the average score.

3.4.2 implementation steps

Create five players and put them in the vector
Traverse the vector container, take out each player, execute the for loop, and save 10 scores into the deque container
sort algorithm sorts the scores in deque container to remove the highest and lowest scores
The deque container is traversed and the total score is accumulated
Get average score

Example code:

//Player category
class Person
{
public:
	Person(string name, int score)
	{
		this->m_Name = name;
		this->m_Score = score;
	}

	string m_Name; //full name
	int m_Score;  //average
};

void createPerson(vector<Person>&v)
{
	string nameSeed = "ABCDE";
	for (int i = 0; i < 5; i++)
	{
		string name = "player";
		name += nameSeed[i];

		int score = 0;

		Person p(name, score);

		//Put the created person object into the container
		v.push_back(p);
	}
}

//Score
void setScore(vector<Person>&v)
{
	for (vector<Person>::iterator it = v.begin(); it != v.end(); it++)
	{
		//Put the judges' scores into the deque container
		deque<int>d;
		for (int i = 0; i < 10; i++)
		{
			int score = rand() % 41 + 60;  // 60 ~ 100
			d.push_back(score);
		}

		//Cout < < player: "< it - > m_ Name < < score: "< endl;
		//for (deque<int>::iterator dit = d.begin(); dit != d.end(); dit++)
		//{
		//	cout << *dit << " ";
		//}
		//cout << endl;

		//sort
		sort(d.begin(), d.end());

		//Remove the highest and lowest scores
		d.pop_back();
		d.pop_front();

		//Average score
		int sum = 0;
		for (deque<int>::iterator dit = d.begin(); dit != d.end(); dit++)
		{
			sum += *dit; //Accumulate the scores of each judge
		}

		int avg = sum / d.size();

		//Assign the average score to the player
		it->m_Score = avg;
	}

}

void showScore(vector<Person>&v)
{
	for (vector<Person>::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << "full name: " << it->m_Name << " average: " << it->m_Score << endl;
	}
}

int main() {

	//Random number seed
	srand((unsigned int)time(NULL));

	//1. Create 5 players
	vector<Person>v;  //Container for storing players
	createPerson(v);

	//test
	//for (vector<Person>::iterator it = v.begin(); it != v.end(); it++)
	//{
	//	Cout < < "Name:" < < (* it) m_ Name < < "score:" < < (* it) m_ Score << endl;
	//}

	//2. Score five players
	setScore(v);

	//3. Show last score
	showScore(v);

	system("pause");

	return 0;
}

Conclusion: selecting different container operation data can improve the efficiency of the code

3.5 stack container

3.5.1 basic concept of stack

Concept: stack is a first in last out (Filo) data structure with only one exit

Only the top elements in the stack can be used by the outside world, so the stack is not allowed to traverse

Data entering the stack is called - push

The pop-up data in the stack is called out of stack pop

3.5.2 common interfaces of stack

Function Description: common external interface of stack container

Constructor:

stack<T> stk; // Stack is implemented by template class, which is the default construction form of stack object
stack(const stack &stk); // copy constructor

Assignment operation:

stack& operator=(const stack &stk); // Overloaded equal sign operator

Data access:

push(elem); // Add an element to the top of the stack
pop(); // Remove the first element from the top of the stack
top(); // Return stack top element

Size operation:

empty(); // Determine whether the stack is empty
size(); // Returns the size of the stack

Example:

#include <stack>

//Common interface of stack container
void test01()
{
	//Create stack containers. Stack containers must comply with the requirements of first in first out
	stack<int> s;

	//Adding elements to the stack is called pushing on the stack
	s.push(10);
	s.push(20);
	s.push(30);

	while (!s.empty()) {
		//Output stack top element
		cout << "Stack top elements are: " << s.top() << endl;
		//Pop up stack top element
		s.pop();
	}
	cout << "The stack size is:" << s.size() << endl;

}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary:

Stack push
Out of stack - pop
Return to top of stack - Top
Determine whether the stack is empty - empty
Return stack size - size

3.6 queue container

3.6.1 basic concept of queue

Concept: Queue is a first in first out (FIFO) data structure with two exits

Queue containers allow you to add elements from one end and remove elements from the other

Only the head and tail of the queue can be used by the outside world, so the queue is not allowed to traverse

Incoming data in the queue is called - incoming push

Out of queue data is called out of queue pop

3.6.2 common interfaces of queue

Function Description: common external interface of stack container

Constructor:

queue<T> que; // Queue is implemented by template class, which is the default construction form of queue object
queue(const queue &que); // copy constructor

Assignment operation:

queue& operator=(const queue &que); // Overloaded equal sign operator

Data access:

push(elem); // Add elements to the end of the queue
pop(); // Remove the first element from the team head
back(); // Returns the last element
front(); // Returns the first element

Size operation:

empty(); // Determine whether the stack is empty
size(); // Returns the size of the stack

Example:

#include <queue>
#include <string>
class Person
{
public:
	Person(string name, int age)
	{
		this->m_Name = name;
		this->m_Age = age;
	}

	string m_Name;
	int m_Age;
};

void test01() {

	//Create queue
	queue<Person> q;

	//Prepare data
	Person p1("Tang Monk", 30);
	Person p2("Sun WuKong", 1000);
	Person p3("Zhu Bajie", 900);
	Person p4("Monk Sha", 800);

	//Adding elements to a queue
	q.push(p1);
	q.push(p2);
	q.push(p3);
	q.push(p4);

	//Queues do not provide iterators, nor do they support random access	
	while (!q.empty()) {
		//Output header element
		cout << "Team head element-- full name: " << q.front().m_Name 
              << " Age: "<< q.front().m_Age << endl;
        
		cout << "Tail element-- full name: " << q.back().m_Name  
              << " Age: " << q.back().m_Age << endl;
        
		cout << endl;
		//Pop up queue header element
		q.pop();
	}

	cout << "The queue size is:" << q.size() << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary:

Join the team - push
Out of line - pop
Return queue header element - front
Return to end of queue element - back
Judge whether the queue is empty empty
Return queue size - size

3.7 container

3.7.1 basic concept of list

**Function: * * chain store data

A linked list is a discontinuous storage structure on a physical storage unit. The logical order of data elements is realized through pointer links in the linked list

Composition of linked list: the linked list is composed of a series of nodes

Composition of nodes: one is the data field for storing data elements, and the other is the pointer field for storing the address of the next node

STL is a two-way linked list

Because the storage mode of the linked list is not a continuous memory space, the iterator in the linked list only supports forward and backward, which belongs to a two-way iterator

Advantages of list:

Dynamic storage allocation will not cause memory waste and overflow
It is very convenient to insert and delete the linked list. You can modify the pointer without moving a large number of elements

Disadvantages of list:

The linked list is flexible, but the additional cost of space (pointer field) and time (traversal) is large

List has an important property. Neither insert operation nor delete operation will cause the invalidation of the original list iterator, which is not tenable in vector.

Summary: List and vector in STL are the two most commonly used containers, each with advantages and disadvantages

3.7.2 list constructor

Function Description:

Create a list container

Function prototype:

list<T> lst; // List is implemented by template class, and the default construction form of object is:
list(beg,end); // Copy the element in the [End] constructor to itself.
list(n,elem); // The constructor copies n elems to itself.
list(const list &lst); // Copy constructor.

Example:

#include <list>

void printList(const list<int>& L) {

	for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

void test01()
{
	list<int>L1;
	L1.push_back(10);
	L1.push_back(20);
	L1.push_back(30);
	L1.push_back(40);

	printList(L1);

	list<int>L2(L1.begin(),L1.end());
	printList(L2);

	list<int>L3(L2);
	printList(L3);

	list<int>L4(10, 1000);
	printList(L4);
}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary: the structure of list is the same as that of several other STL common containers, which can be mastered skillfully

3.7.3 list assignment and exchange

Function Description:

Assign values to the list container and exchange list containers

Function prototype:

assign(beg, end); // Assign the data copy in the [beg, end) interval to itself.
assign(n, elem); // Assign n elem copies to itself.
list& operator=(const list &lst); // Overloaded equal sign operator
swap(lst); // Swap LST with its own elements.

Example:

#include <list>

void printList(const list<int>& L) {

	for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

//Assignment and exchange
void test01()
{
	list<int>L1;
	L1.push_back(10);
	L1.push_back(20);
	L1.push_back(30);
	L1.push_back(40);
	printList(L1);

	//assignment
	list<int>L2;
	L2 = L1;
	printList(L2);

	list<int>L3;
	L3.assign(L2.begin(), L2.end());
	printList(L3);

	list<int>L4;
	L4.assign(10, 100);
	printList(L4);

}

//exchange
void test02()
{

	list<int>L1;
	L1.push_back(10);
	L1.push_back(20);
	L1.push_back(30);
	L1.push_back(40);

	list<int>L2;
	L2.assign(10, 100);

	cout << "Before exchange: " << endl;
	printList(L1);
	printList(L2);

	cout << endl;

	L1.swap(L2);

	cout << "After exchange: " << endl;
	printList(L1);
	printList(L2);

}

int main() {

	//test01();

	test02();

	system("pause");

	return 0;
}

Conclusion: list assignment and exchange can be used flexibly

3.7.4 list size operation

Function Description:

Operate on the size of the list container

Function prototype:

size(); // Returns the number of elements in the container
empty(); // Determine whether the container is empty
resize(num); // Reassign the length of the container to num. if the container becomes longer, the new location will be filled with the default value.

/ / if the container becomes shorter, the element whose end exceeds the length of the container will be deleted.

resize(num, elem); // Reassign the length of the container to num. if the container becomes longer, fill the new position with elem value.

  	 	 						    //If the container becomes shorter, the element whose end exceeds the length of the container is deleted.

Example:

#include <list>

void printList(const list<int>& L) {

	for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

//Size operation
void test01()
{
	list<int>L1;
	L1.push_back(10);
	L1.push_back(20);
	L1.push_back(30);
	L1.push_back(40);

	if (L1.empty())
	{
		cout << "L1 Empty" << endl;
	}
	else
	{
		cout << "L1 Not empty" << endl;
		cout << "L1 The size of the is: " << L1.size() << endl;
	}

	//Reassign size
	L1.resize(10);
	printList(L1);

	L1.resize(2);
	printList(L1);
}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary:

Judge whether it is empty empty
Return the number of elements - size
Reassign number - resize

3.7.5 list insertion and deletion

Function Description:

Insert and delete data from the list container

Function prototype:

push_back(elem);// Add an element at the end of the container
pop_back();// Delete the last element in the container
push_front(elem);// Insert an element at the beginning of the container
pop_front();// Remove the first element from the beginning of the container
insert(pos,elem);// Insert a copy of the elem element in the POS position and return the location of the new data.
insert(pos,n,elem);// Insert n elem data in POS position, and there is no return value.
insert(pos,beg,end);// Insert the data of the [beg, end) interval in the POS position, and there is no return value.
clear();// Remove all data from the container
erase(beg,end);// Delete the data in the [beg, end) interval and return the position of the next data.
erase(pos);// Delete the data in POS position and return to the position of the next data.
remove(elem);// Delete all elements in the container that match the element value.

Example:

#include <list>

void printList(const list<int>& L) {

	for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

//Insert and delete
void test01()
{
	list<int> L;
	//Tail insertion
	L.push_back(10);
	L.push_back(20);
	L.push_back(30);
	//Head insert
	L.push_front(100);
	L.push_front(200);
	L.push_front(300);

	printList(L);

	//Tail deletion
	L.pop_back();
	printList(L);

	//Header deletion
	L.pop_front();
	printList(L);

	//insert
	list<int>::iterator it = L.begin();
	L.insert(++it, 1000);
	printList(L);

	//delete
	it = L.begin();
	L.erase(++it);
	printList(L);

	//remove
	L.push_back(10000);
	L.push_back(10000);
	L.push_back(10000);
	printList(L);
	L.remove(10000);
	printList(L);
    
    //empty
	L.clear();
	printList(L);
}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary:

Tail push_back
Tail deletion pop_back
Head push_front
Header deletion - pop_front
Insert - insert
Delete erase
Remove - remove
Empty - clear

3.7.6 list data access

Function Description:

Access the data in the list container

Function prototype:

front(); // Returns the first element.
back(); // Returns the last element.

Example:

#include <list>

//data access 
void test01()
{
	list<int>L1;
	L1.push_back(10);
	L1.push_back(20);
	L1.push_back(30);
	L1.push_back(40);

	
	//cout << L1. at(0) << endl;// Error: at access to data is not supported
	//cout << L1[0] << endl; // Error: accessing data in [] mode is not supported
	cout << "The first element is: " << L1.front() << endl;
	cout << "The last element is: " << L1.back() << endl;

	//The iterator of the list container is a bidirectional iterator and does not support random access
	list<int>::iterator it = L1.begin();
	//it = it + 1;// Error, cannot skip access, even + 1
}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary:

Data cannot be accessed through [] or at in the list container
Return the first element - front
Returns the last element - back

Reverse sort and list 3.7

Function Description:

Invert the elements in the container and sort the data in the container

Function prototype:

reverse(); // Reverse linked list
sort(); // Linked list sorting

Example:

void printList(const list<int>& L) {

	for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

bool myCompare(int val1 , int val2)
{
	return val1 > val2;
}

//Reverse and sort
void test01()
{
	list<int> L;
	L.push_back(90);
	L.push_back(30);
	L.push_back(20);
	L.push_back(70);
	printList(L);

	//Invert the elements of the container
	L.reverse();
	printList(L);

	//sort
	L.sort(); //The default collation is from small to large
	printList(L);

	L.sort(myCompare); //Specify rules, from large to small
	printList(L);
}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary:

Reverse reverse
Sort - sort (member function)

3.7.8 sorting cases

Case description: sort the user-defined data type of Person. The attributes in Person include name, age and height

Sorting rule: ascending by age, descending by height if the age is the same

Example:

#include <list>
#include <string>
class Person {
public:
	Person(string name, int age , int height) {
		m_Name = name;
		m_Age = age;
		m_Height = height;
	}

public:
	string m_Name;  //full name
	int m_Age;      //Age
	int m_Height;   //height
};


bool ComparePerson(Person& p1, Person& p2) {

	if (p1.m_Age == p2.m_Age) {
		return p1.m_Height  > p2.m_Height;
	}
	else
	{
		return  p1.m_Age < p2.m_Age;
	}

}

void test01() {

	list<Person> L;

	Person p1("Liu Bei", 35 , 175);
	Person p2("Cao Cao", 45 , 180);
	Person p3("Sun Quan", 40 , 170);
	Person p4("Zhao Yun", 25 , 190);
	Person p5("Fei Zhang", 35 , 160);
	Person p6("Guan Yu", 35 , 200);

	L.push_back(p1);
	L.push_back(p2);
	L.push_back(p3);
	L.push_back(p4);
	L.push_back(p5);
	L.push_back(p6);

	for (list<Person>::iterator it = L.begin(); it != L.end(); it++) {
		cout << "full name: " << it->m_Name << " Age: " << it->m_Age 
              << " Height: " << it->m_Height << endl;
	}

	cout << "---------------------------------" << endl;
	L.sort(ComparePerson); //sort

	for (list<Person>::iterator it = L.begin(); it != L.end(); it++) {
		cout << "full name: " << it->m_Name << " Age: " << it->m_Age 
              << " Height: " << it->m_Height << endl;
	}
}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary:

For custom data types, the collation must be specified, otherwise the compiler does not know how to sort
Advanced sorting is just another logical rule formulation on the sorting rules, which is not complicated

3.8 set/ multiset container

3.8.1 basic concept of set

Introduction:

All elements are automatically sorted on insertion

Essence:

set/multiset is an associative container, and its underlying structure is implemented by binary tree.

Difference between set and multiset:

set does not allow duplicate elements in the container
multiset allows duplicate elements in a container

3.8.2 set construction and assignment

Function Description: create set container and assign value

Construction:

set<T> st; // Default constructor:
set(const set &st); // copy constructor

Assignment:

set& operator=(const set &st); // Overloaded equal sign operator

Example:

#include <set>

void printSet(set<int> & s)
{
	for (set<int>::iterator it = s.begin(); it != s.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

//Construction and assignment
void test01()
{
	set<int> s1;

	s1.insert(10);
	s1.insert(30);
	s1.insert(20);
	s1.insert(40);
	printSet(s1);

	//copy construction 
	set<int>s2(s1);
	printSet(s2);

	//assignment
	set<int>s3;
	s3 = s2;
	printSet(s3);
}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary:

insert is used when inserting data into the set container
The data inserted into the set container will be sorted automatically

3.8.3 set size and swap

Function Description:

Count the size of set container and exchange set container

Function prototype:

size(); // Returns the number of elements in the container
empty(); // Determine whether the container is empty
swap(st); // Swap two collection containers

Example:

#include <set>

void printSet(set<int> & s)
{
	for (set<int>::iterator it = s.begin(); it != s.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

//size
void test01()
{

	set<int> s1;
	
	s1.insert(10);
	s1.insert(30);
	s1.insert(20);
	s1.insert(40);

	if (s1.empty())
	{
		cout << "s1 Empty" << endl;
	}
	else
	{
		cout << "s1 Not empty" << endl;
		cout << "s1 The size of the is: " << s1.size() << endl;
	}

}

//exchange
void test02()
{
	set<int> s1;

	s1.insert(10);
	s1.insert(30);
	s1.insert(20);
	s1.insert(40);

	set<int> s2;

	s2.insert(100);
	s2.insert(300);
	s2.insert(200);
	s2.insert(400);

	cout << "Before exchange" << endl;
	printSet(s1);
	printSet(s2);
	cout << endl;

	cout << "After exchange" << endl;
	s1.swap(s2);
	printSet(s1);
	printSet(s2);
}

int main() {

	//test01();

	test02();

	system("pause");

	return 0;
}

Summary:

Statistical size - size
Judge whether it is empty empty
swap container - swap

3.8.4 set insertion and deletion

Function Description:

The set container inserts and deletes data

Function prototype:

insert(elem); // Insert an element into the container.
clear(); // Clear all elements
erase(pos); // Delete the element referred to by the POS iterator and return the iterator of the next element.
erase(beg,end); // Delete all elements of the interval [beg, end], and return the iterator of the next element.
erase(elem); // Delete the element with element in the container.

Example:

#include <set>

void printSet(set<int> & s)
{
	for (set<int>::iterator it = s.begin(); it != s.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

//Insert and delete
void test01()
{
	set<int> s1;
	//insert
	s1.insert(10);
	s1.insert(30);
	s1.insert(20);
	s1.insert(40);
	printSet(s1);

	//delete
	s1.erase(s1.begin());
	printSet(s1);

	s1.erase(30);
	printSet(s1);

	//empty
	//s1.erase(s1.begin(), s1.end());
	s1.clear();
	printSet(s1);
}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary:

Insert - insert
Delete erase
Empty - clear

3.8.5 set search and statistics

Function Description:

Search data and statistics of set container

Function prototype:

find(key); // Find out whether the key exists. If so, return the iterator of the element of the key; If it does not exist, return set end();
count(key); // Count the number of key elements

Example:

#include <set>

//Search and statistics
void test01()
{
	set<int> s1;
	//insert
	s1.insert(10);
	s1.insert(30);
	s1.insert(20);
	s1.insert(40);
	
	//lookup
	set<int>::iterator pos = s1.find(30);

	if (pos != s1.end())
	{
		cout << "Found element: " << *pos << endl;
	}
	else
	{
		cout << "Element not found" << endl;
	}

	//Statistics
	int num = s1.count(30);
	cout << "num = " << num << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary:

Find - find (the iterator is returned)
Statistics - count (for set, the result is 0 or 1)

3.8.6 difference between set and multiset

Learning objectives:

Master the difference between set and multiset

difference:

set cannot insert duplicate data, while multiset can
set will return the insertion result when inserting data, indicating whether the insertion is successful
multiset does not detect data, so duplicate data can be inserted

Example:

#include <set>

//Difference between set and multiset
void test01()
{
	set<int> s;
	pair<set<int>::iterator, bool>  ret = s.insert(10);
	if (ret.second) {
		cout << "First insertion successful!" << endl;
	}
	else {
		cout << "First insertion failed!" << endl;
	}

	ret = s.insert(10);
	if (ret.second) {
		cout << "The second insertion was successful!" << endl;
	}
	else {
		cout << "The second insertion failed!" << endl;
	}
    
	//multiset
	multiset<int> ms;
	ms.insert(10);
	ms.insert(10);

	for (multiset<int>::iterator it = ms.begin(); it != ms.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary:

If it is not allowed to insert duplicate data, set can be used
If you need to insert duplicate data, use multiset

3.8.7 pair group creation

Function Description:

For paired data, two data can be returned by using the pair group

There are two creation methods:

pair<type, type> p ( value1, value2 );
pair<type, type> p = make_pair( value1, value2 );

Example:

#include <string>

//Create a group
void test01()
{
	pair<string, int> p(string("Tom"), 20);
	cout << "full name: " <<  p.first << " Age: " << p.second << endl;

	pair<string, int> p2 = make_pair("Jerry", 10);
	cout << "full name: " << p2.first << " Age: " << p2.second << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary:

You can create pair groups in both ways. Just remember one

3.8.8 set container sorting

Learning objectives:

The default sorting rule of set container is from small to large. Master how to change the sorting rule

Main technical points:

Using the imitation function, the sorting rules can be changed

Example 1: set stores built-in data types

#include <set>

class MyCompare 
{
public:
	bool operator()(int v1, int v2) {
		return v1 > v2;
	}
};
void test01() 
{    
	set<int> s1;
	s1.insert(10);
	s1.insert(40);
	s1.insert(20);
	s1.insert(30);
	s1.insert(50);

	//Default from small to large
	for (set<int>::iterator it = s1.begin(); it != s1.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;

	//Specify collation
	set<int,MyCompare> s2;
	s2.insert(10);
	s2.insert(40);
	s2.insert(20);
	s2.insert(30);
	s2.insert(50);

	for (set<int, MyCompare>::iterator it = s2.begin(); it != s2.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary: the sorting rules of the set container can be specified by using the imitation function

Example 2: storing user-defined data types

#include <set>
#include <string>

class Person
{
public:
	Person(string name, int age)
	{
		this->m_Name = name;
		this->m_Age = age;
	}

	string m_Name;
	int m_Age;

};
class comparePerson
{
public:
	bool operator()(const Person& p1, const Person &p2)
	{
		//Sort by age, descending
		return p1.m_Age > p2.m_Age;
	}
};

void test01()
{
	set<Person, comparePerson> s;

	Person p1("Liu Bei", 23);
	Person p2("Guan Yu", 27);
	Person p3("Fei Zhang", 25);
	Person p4("Zhao Yun", 21);

	s.insert(p1);
	s.insert(p2);
	s.insert(p3);
	s.insert(p4);

	for (set<Person, comparePerson>::iterator it = s.begin(); it != s.end(); it++)
	{
		cout << "full name: " << it->m_Name << " Age: " << it->m_Age << endl;
	}
}
int main() {

	test01();

	system("pause");

	return 0;
}

Summary:

For user-defined data types, set must specify sorting rules before inserting data

3.9 map/ multimap container

3.9.1 basic concept of map

Introduction:

All elements in the map are pair
The first element in pair is key (key value), which serves as an index, and the second element is value (real value)
All elements are automatically sorted according to the key value of the element

Essence:

map/multimap is an associative container, and its underlying structure is implemented by binary tree.

advantage:

You can quickly find the value value according to the key value

Difference between map and multimap:

map does not allow duplicate key value elements in the container
multimap allows duplicate key value elements in the container

3.9.2 map construction and assignment

Function Description:

Construct and assign the map container

Function prototype:

Construction:

map<T1, T2> mp; // Map default constructor:
map(const map &mp); // copy constructor

Assignment:

map& operator=(const map &mp); // Overloaded equal sign operator

Example:

#include <map>

void printMap(map<int,int>&m)
{
	for (map<int, int>::iterator it = m.begin(); it != m.end(); it++)
	{
		cout << "key = " << it->first << " value = " << it->second << endl;
	}
	cout << endl;
}

void test01()
{
	map<int,int>m; //Default construction
	m.insert(pair<int, int>(1, 10));
	m.insert(pair<int, int>(2, 20));
	m.insert(pair<int, int>(3, 30));
	printMap(m);

	map<int, int>m2(m); //copy construction 
	printMap(m2);

	map<int, int>m3;
	m3 = m2; //assignment
	printMap(m3);
}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary: all elements in the map appear in pairs, and pairs should be used when inserting data

3.9.3 map size and swap

Function Description:

Count the size of map container and exchange map container

Function prototype:

size(); // Returns the number of elements in the container
empty(); // Determine whether the container is empty
swap(st); // Swap two collection containers

Example:

#include <map>

void printMap(map<int,int>&m)
{
	for (map<int, int>::iterator it = m.begin(); it != m.end(); it++)
	{
		cout << "key = " << it->first << " value = " << it->second << endl;
	}
	cout << endl;
}

void test01()
{
	map<int, int>m;
	m.insert(pair<int, int>(1, 10));
	m.insert(pair<int, int>(2, 20));
	m.insert(pair<int, int>(3, 30));

	if (m.empty())
	{
		cout << "m Empty" << endl;
	}
	else
	{
		cout << "m Not empty" << endl;
		cout << "m The size of the is: " << m.size() << endl;
	}
}


//exchange
void test02()
{
	map<int, int>m;
	m.insert(pair<int, int>(1, 10));
	m.insert(pair<int, int>(2, 20));
	m.insert(pair<int, int>(3, 30));

	map<int, int>m2;
	m2.insert(pair<int, int>(4, 100));
	m2.insert(pair<int, int>(5, 200));
	m2.insert(pair<int, int>(6, 300));

	cout << "Before exchange" << endl;
	printMap(m);
	printMap(m2);

	cout << "After exchange" << endl;
	m.swap(m2);
	printMap(m);
	printMap(m2);
}

int main() {

	test01();

	test02();

	system("pause");

	return 0;
}

Summary:

Statistical size - size
Judge whether it is empty empty
swap container - swap

3.9.4 map insertion and deletion

Function Description:

The map container inserts and deletes data

Function prototype:

insert(elem); // Insert an element into the container.
clear(); // Clear all elements
erase(pos); // Delete the element referred to by the POS iterator and return the iterator of the next element.
erase(beg,end); // Delete all elements of the interval [beg, end], and return the iterator of the next element.
erase(key); // Delete the element with key in the container.

Example:

#include <map>

void printMap(map<int,int>&m)
{
	for (map<int, int>::iterator it = m.begin(); it != m.end(); it++)
	{
		cout << "key = " << it->first << " value = " << it->second << endl;
	}
	cout << endl;
}

void test01()
{
	//insert
	map<int, int> m;
	//First insertion method
	m.insert(pair<int, int>(1, 10));
	//Second insertion method
	m.insert(make_pair(2, 20));
	//The third insertion method
	m.insert(map<int, int>::value_type(3, 30));
	//The fourth insertion method
	m[4] = 40; 
	printMap(m);

	//delete
	m.erase(m.begin());
	printMap(m);

	m.erase(3);
	printMap(m);

	//empty
	m.erase(m.begin(),m.end());
	m.clear();
	printMap(m);
}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary:

There are many ways to insert map. Just remember one of them

Insert - insert
Delete erase
Empty - clear

3.9.5 map search and statistics

Function Description:

Search the map container for data and statistics

Function prototype:

find(key); // Find out whether the key exists. If so, return the iterator of the element of the key; If it does not exist, return set end();
count(key); // Count the number of key elements

Example:

#include <map>

//Search and statistics
void test01()
{
	map<int, int>m; 
	m.insert(pair<int, int>(1, 10));
	m.insert(pair<int, int>(2, 20));
	m.insert(pair<int, int>(3, 30));

	//lookup
	map<int, int>::iterator pos = m.find(3);

	if (pos != m.end())
	{
		cout << "Element found key = " << (*pos).first << " value = " << (*pos).second << endl;
	}
	else
	{
		cout << "Element not found" << endl;
	}

	//Statistics
	int num = m.count(3);
	cout << "num = " << num << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary:

Find - find (the iterator is returned)
Statistics - count (for map, the result is 0 or 1)

3.9.6 map container sorting

Learning objectives:

The default sorting rule of map container is to sort from small to large according to the key value. Master how to change the sorting rule

Main technical points:

Using the imitation function, the sorting rules can be changed

Example:

#include <map>

class MyCompare {
public:
	bool operator()(int v1, int v2) {
		return v1 > v2;
	}
};

void test01() 
{
	//Default sort from small to large
	//Sorting from large to small by using imitation function
	map<int, int, MyCompare> m;

	m.insert(make_pair(1, 10));
	m.insert(make_pair(2, 20));
	m.insert(make_pair(3, 30));
	m.insert(make_pair(4, 40));
	m.insert(make_pair(5, 50));

	for (map<int, int, MyCompare>::iterator it = m.begin(); it != m.end(); it++) {
		cout << "key:" << it->first << " value:" << it->second << endl;
	}
}
int main() {

	test01();

	system("pause");

	return 0;
}

Summary:

The sorting rules of the map container can be specified by using the affine function
For user-defined data types, map must specify sorting rules, the same as set container

3.10 case - employee grouping

3.10.1 case description

Today, the company recruited 10 employees (ABCDEFGHIJ). After 10 employees enter the company, they need to assign employees to work in that department
Employee information includes: name and salary composition; R & D and art planning departments
Randomly assign department and salary to 10 employees
Insert information through multimap key (department number) value (employee)
Display employee information by Department

3.10.2 implementation steps

Create 10 employees and put them into the vector
Traverse the vector container, take out each employee and group them randomly
After grouping, put the employee department number as the key and the specific employee as the value into the multimap container
Display employee information by Department

Case code:

#include<iostream>
using namespace std;
#include <vector>
#include <string>
#include <map>
#include <ctime>

/*
- Today, the company recruited 10 employees (ABCDEFGHIJ). After 10 employees enter the company, they need to assign employees to work in that department
- Employee information includes: name and salary composition; The departments are divided into: planning, art and R & D
- Randomly assign department and salary to 10 employees
- Insert information through multimap key (department number) value (employee)
- Display employee information by Department
*/

#define CEHUA  0
#define MEISHU 1
#define YANFA  2

class Worker
{
public:
	string m_Name;
	int m_Salary;
};

void createWorker(vector<Worker>&v)
{
	string nameSeed = "ABCDEFGHIJ";
	for (int i = 0; i < 10; i++)
	{
		Worker worker;
		worker.m_Name = "staff";
		worker.m_Name += nameSeed[i];

		worker.m_Salary = rand() % 10000 + 10000; // 10000 ~ 19999
		//Put employees into containers
		v.push_back(worker);
	}
}

//Employee grouping
void setGroup(vector<Worker>&v,multimap<int,Worker>&m)
{
	for (vector<Worker>::iterator it = v.begin(); it != v.end(); it++)
	{
		//Generate random department number
		int deptId = rand() % 3; // 0 1 2 

		//Insert employees into groups
		//key department number, value specific employee
		m.insert(make_pair(deptId, *it));
	}
}

void showWorkerByGourp(multimap<int,Worker>&m)
{
	// 0  A  B  C   1  D  E   2  F G ...
	cout << "Planning department:" << endl;

	multimap<int,Worker>::iterator pos = m.find(CEHUA);
	int count = m.count(CEHUA); // Count the specific number of people
	int index = 0;
	for (; pos != m.end() && index < count; pos++ , index++)
	{
		cout << "full name: " << pos->second.m_Name << " Salary: " << pos->second.m_Salary << endl;
	}

	cout << "----------------------" << endl;
	cout << "Art Department: " << endl;
	pos = m.find(MEISHU);
	count = m.count(MEISHU); // Count the specific number of people
	index = 0;
	for (; pos != m.end() && index < count; pos++, index++)
	{
		cout << "full name: " << pos->second.m_Name << " Salary: " << pos->second.m_Salary << endl;
	}

	cout << "----------------------" << endl;
	cout << "R & D department: " << endl;
	pos = m.find(YANFA);
	count = m.count(YANFA); // Count the specific number of people
	index = 0;
	for (; pos != m.end() && index < count; pos++, index++)
	{
		cout << "full name: " << pos->second.m_Name << " Salary: " << pos->second.m_Salary << endl;
	}

}

int main() {

	srand((unsigned int)time(NULL));

	//1. Create employee
	vector<Worker>vWorker;
	createWorker(vWorker);

	//2. Employee grouping
	multimap<int, Worker>mWorker;
	setGroup(vWorker, mWorker);


	//3. Show employees in groups
	showWorkerByGourp(mWorker);

	test
	//for (vector<Worker>::iterator it = vWorker.begin(); it != vWorker.end(); it++)
	//{
	//	Cout < < name: "< it - > m_ Name < < salary: "< it - > m_ Salary << endl;
	//}

	system("pause");

	return 0;
}

Summary:

When data exists in the form of key value pairs, you can consider using map or multimap

4 STL function object

4.1 function object

4.1.1 function object concept

Concept:

A class that overloads the function call operator. Its object is often called a function object
When a function object uses overloaded (), its behavior is similar to that of a function call, which is also called an imitation function

Essence:

A function object is a class, not a function

4.1.2 function object usage

characteristic:

When a function object is used, it can be called like an ordinary function, with parameters and return values
Function objects go beyond the concept of ordinary functions. Function objects can have their own states
Function objects can be passed as arguments

Example:

#include <string>

//1. When a function object is used, it can be called like an ordinary function, with parameters and return values
class MyAdd
{
public :
	int operator()(int v1,int v2)
	{
		return v1 + v2;
	}
};

void test01()
{
	MyAdd myAdd;
	cout << myAdd(10, 10) << endl;
}

//2. Function objects can have their own state
class MyPrint
{
public:
	MyPrint()
	{
		count = 0;
	}
	void operator()(string test)
	{
		cout << test << endl;
		count++; //Count usage times
	}

	int count; //Internal self state
};
void test02()
{
	MyPrint myPrint;
	myPrint("hello world");
	myPrint("hello world");
	myPrint("hello world");
	cout << "myPrint The number of calls is: " << myPrint.count << endl;
}

//3. Function objects can be passed as arguments
void doPrint(MyPrint &mp , string test)
{
	mp(test);
}

void test03()
{
	MyPrint myPrint;
	doPrint(myPrint, "Hello C++");
}

int main() {

	//test01();
	//test02();
	test03();

	system("pause");

	return 0;
}

Summary:

The imitation function is very flexible and can be passed as a parameter.

4.2 predicate

4.2.1 predicate concept

Concept:

Functions that return bool types are called predicates
If operator() accepts a parameter, it is called a unary predicate
If operator() accepts two parameters, it is called a binary predicate

4.2.2 unary predicate

Example:

#include <vector>
#include <algorithm>

//1. Unary predicate
struct GreaterFive{
	bool operator()(int val) {
		return val > 5;
	}
};

void test01() {

	vector<int> v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}

	vector<int>::iterator it = find_if(v.begin(), v.end(), GreaterFive());
	if (it == v.end()) {
		cout << "Can't find!" << endl;
	}
	else {
		cout << "find:" << *it << endl;
	}

}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary: predicates with only one parameter are called unary predicates

4.2.3 binary predicate

Example:

#include <vector>
#include <algorithm>
//two-place predicate
class MyCompare
{
public:
	bool operator()(int num1, int num2)
	{
		return num1 > num2;
	}
};

void test01()
{
	vector<int> v;
	v.push_back(10);
	v.push_back(40);
	v.push_back(20);
	v.push_back(30);
	v.push_back(50);

	//Default from small to large
	sort(v.begin(), v.end());
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
	cout << "----------------------------" << endl;

	//Use the function object to change the algorithm strategy and sort from large to small
	sort(v.begin(), v.end(), MyCompare());
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary: predicates with only two parameters are called binary predicates

4.3 built in function object

4.3.1 meaning of built-in function object

Concept:

STL has built-in function objects

Classification:

Arithmetic imitation function
Relational affine function
Logical imitation function

Usage:

The usage of the objects generated by these imitation functions is exactly the same as that of general functions
To use the built-in function object, you need to import the header file #include < functional >

4.3.2 arithmetic imitation function

Function Description:

Realize four operations
Among them, negate is a unary operation, and others are binary operations

Imitation function prototype:

Template < class T > t plus < T > / / addition functor
Template < class T > t minus < T > / / subtraction function
Template < class T > t multiples < T > / / multiplication functor
Template < class T > t divisions < T > / / division imitation function
Template < class T > t module < T > / / take the imitation function
Template < class T > t negate < T > / / take the inverse function

Example:

#include <functional>
//negate
void test01()
{
	negate<int> n;
	cout << n(50) << endl;
}

//plus
void test02()
{
	plus<int> p;
	cout << p(10, 20) << endl;
}

int main() {

	test01();
	test02();

	system("pause");

	return 0;
}

Summary: when using built-in function objects, the header file #include < functional > needs to be introduced

4.3.3 relation imitation function

Function Description:

Implement relationship comparison

Imitation function prototype:

template<class T> bool equal_ To < T > / / equal to
template<class T> bool not_ equal_ To < T > / / not equal to
Template < class T > bool greater < T > / / greater than
template<class T> bool greater_ Equal < T > / / greater than or equal to
Template < class T > bool less < T > / / less than
template<class T> bool less_ Equal < T > / / less than or equal to

Example:

#include <functional>
#include <vector>
#include <algorithm>

class MyCompare
{
public:
	bool operator()(int v1,int v2)
	{
		return v1 > v2;
	}
};
void test01()
{
	vector<int> v;

	v.push_back(10);
	v.push_back(30);
	v.push_back(50);
	v.push_back(40);
	v.push_back(20);

	for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;

	//Realize the imitation function by yourself
	//sort(v.begin(), v.end(), MyCompare());
	//STL built-in functor is larger than functor
	sort(v.begin(), v.end(), greater<int>());

	for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary: greater < > greater than is the most commonly used in relational imitation functions

4.3.4 logic imitation function

Function Description:

Realize logical operation

Function prototype:

template<class T> bool logical_ And < T > / / logic and
template<class T> bool logical_ Or < T > / / logical or
template<class T> bool logical_ Not < T > / / not logical

Example:

#include <vector>
#include <functional>
#include <algorithm>
void test01()
{
	vector<bool> v;
	v.push_back(true);
	v.push_back(false);
	v.push_back(true);
	v.push_back(false);

	for (vector<bool>::iterator it = v.begin();it!= v.end();it++)
	{
		cout << *it << " ";
	}
	cout << endl;

	//Logical non carries the v container into v2 and performs logical non operations
	vector<bool> v2;
	v2.resize(v.size());
	transform(v.begin(), v.end(),  v2.begin(), logical_not<bool>());
	for (vector<bool>::iterator it = v2.begin(); it != v2.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

Conclusion: there are few practical applications of logic imitation function, so you can understand it

5 STL common algorithms

summary:

The algorithm is mainly composed of header file < algorithm > < functional > < numeric >.
< algorithm > is the largest of all STL header files, covering comparison, exchange, search, traversal, copy, modification, etc
< numeric > is small in size and only includes a few template functions that perform simple mathematical operations on the sequence
< functional > defines some template classes to declare function objects.

5.1 common traversal algorithms

Learning objectives:

Master common traversal algorithms

Algorithm Introduction:

for_each / / traverse the container
transform / / transfer container to another container

5.1.1 for_each

Function Description:

Implement traversal container

Function prototype:

for_each(iterator beg, iterator end, _func);

//Traversal algorithm traverses container elements

//beg start iterator

//End end iterator

// _ func function or function object

Example:

#include <algorithm>
#include <vector>

//Ordinary function
void print01(int val) 
{
	cout << val << " ";
}
//Function object
class print02 
{
 public:
	void operator()(int val) 
	{
		cout << val << " ";
	}
};

//for_ Basic usage of each algorithm
void test01() {

	vector<int> v;
	for (int i = 0; i < 10; i++) 
	{
		v.push_back(i);
	}

	//inorder traversal 
	for_each(v.begin(), v.end(), print01);
	cout << endl;

	for_each(v.begin(), v.end(), print02());
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

**Summary: * * for_each is the most commonly used traversal algorithm in practical development, which needs to be mastered skillfully

5.1.2 transform

Function Description:

Transport container to another container

Function prototype:

transform(iterator beg1, iterator end1, iterator beg2, _func);

//beg1 source container start iterator

//end1 source container end iterator

//beg2 target container start iterator

//_ func function or function object

Example:

#include<vector>
#include<algorithm>

//Common traversal algorithms

class TransForm
{
public:
	int operator()(int val)
	{
		return val;
	}

};

class MyPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

void test01()
{
	vector<int>v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}

	vector<int>vTarget; //Target container

	vTarget.resize(v.size()); // The target container needs to open up space in advance

	transform(v.begin(), v.end(), vTarget.begin(), TransForm());

	for_each(vTarget.begin(), vTarget.end(), MyPrint());
}

int main() {

	test01();

	system("pause");

	return 0;
}

Conclusion: the target container to be handled must be opened up in advance, otherwise it cannot be handled normally

5.2 common search algorithms

Learning objectives:

Master common search algorithms

Algorithm Introduction:

Find / / find elements
find_if / / find elements by criteria
adjacent_find / / find adjacent duplicate elements
binary_search / / binary search
Count / / count the number of elements
count_if / / count the number of elements by condition

5.2.1 find

Function Description:

Find the specified element, find the iterator that returns the specified element, and cannot find the return end iterator end()

Function prototype:

find(iterator beg, iterator end, value);

//Find the element by value, find the iterator that returns the specified position, and the iterator that returns the end cannot be found

//beg start iterator

//End end iterator

//value lookup element

Example:

#include <algorithm>
#include <vector>
#include <string>
void test01() {

	vector<int> v;
	for (int i = 0; i < 10; i++) {
		v.push_back(i + 1);
	}
	//Find out if there is 5 this element in the container
	vector<int>::iterator it = find(v.begin(), v.end(), 5);
	if (it == v.end()) 
	{
		cout << "Can't find!" << endl;
	}
	else 
	{
		cout << "find:" << *it << endl;
	}
}

class Person {
public:
	Person(string name, int age) 
	{
		this->m_Name = name;
		this->m_Age = age;
	}
	//Heavy load==
	bool operator==(const Person& p) 
	{
		if (this->m_Name == p.m_Name && this->m_Age == p.m_Age) 
		{
			return true;
		}
		return false;
	}

public:
	string m_Name;
	int m_Age;
};

void test02() {

	vector<Person> v;

	//Create data
	Person p1("aaa", 10);
	Person p2("bbb", 20);
	Person p3("ccc", 30);
	Person p4("ddd", 40);

	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);

	vector<Person>::iterator it = find(v.begin(), v.end(), p2);
	if (it == v.end()) 
	{
		cout << "Can't find!" << endl;
	}
	else 
	{
		cout << "Find name:" << it->m_Name << " Age: " << it->m_Age << endl;
	}
}

Summary: find can find the specified element in the container, and the return value is the iterator

5.2.2 find_if

Function Description:

Find elements by criteria

Function prototype:

find_if(iterator beg, iterator end, _Pred);

//Find the element by value, find the iterator that returns the specified position, and the iterator that returns the end cannot be found

//beg start iterator

//End end iterator

// _ Pred function or predicate (an imitation function that returns bool type)

Example:

#include <algorithm>
#include <vector>
#include <string>

//Built in data type
class GreaterFive
{
public:
	bool operator()(int val)
	{
		return val > 5;
	}
};

void test01() {

	vector<int> v;
	for (int i = 0; i < 10; i++) {
		v.push_back(i + 1);
	}

	vector<int>::iterator it = find_if(v.begin(), v.end(), GreaterFive());
	if (it == v.end()) {
		cout << "Can't find!" << endl;
	}
	else {
		cout << "A number greater than 5 was found:" << *it << endl;
	}
}

//Custom data type
class Person {
public:
	Person(string name, int age)
	{
		this->m_Name = name;
		this->m_Age = age;
	}
public:
	string m_Name;
	int m_Age;
};

class Greater20
{
public:
	bool operator()(Person &p)
	{
		return p.m_Age > 20;
	}

};

void test02() {

	vector<Person> v;

	//Create data
	Person p1("aaa", 10);
	Person p2("bbb", 20);
	Person p3("ccc", 30);
	Person p4("ddd", 40);

	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);

	vector<Person>::iterator it = find_if(v.begin(), v.end(), Greater20());
	if (it == v.end())
	{
		cout << "Can't find!" << endl;
	}
	else
	{
		cout << "Find name:" << it->m_Name << " Age: " << it->m_Age << endl;
	}
}

int main() {

	//test01();

	test02();

	system("pause");

	return 0;
}

Summary: find_if search by condition makes the search more flexible, and the provided imitation function can change different strategies

5.2.3 adjacent_find

Function Description:

Find adjacent duplicate elements

Function prototype:

adjacent_find(iterator beg, iterator end);

//Find adjacent repeating elements and return the iterator of the first position of adjacent elements

//beg start iterator

//End end iterator

Example:

#include <algorithm>
#include <vector>

void test01()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(5);
	v.push_back(2);
	v.push_back(4);
	v.push_back(4);
	v.push_back(3);

	//Find adjacent duplicate elements
	vector<int>::iterator it = adjacent_find(v.begin(), v.end());
	if (it == v.end()) {
		cout << "can't find!" << endl;
	}
	else {
		cout << "The adjacent duplicate element found is:" << *it << endl;
	}
}

Conclusion: if you find adjacent repeating elements in the interview question, remember to use the adjacent in STL_ Find algorithm

5.2.4 binary_search

Function Description:

Finds whether the specified element exists

Function prototype:

bool binary_search(iterator beg, iterator end, value);

//Find the specified element and return true, otherwise false

//Note: not available in unordered sequences

//beg start iterator

//End end iterator

//value lookup element

Example:

#include <algorithm>
#include <vector>

void test01()
{
	vector<int>v;

	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}
	//Binary search
	bool ret = binary_search(v.begin(), v.end(),2);
	if (ret)
	{
		cout << "eureka" << endl;
	}
	else
	{
		cout << "not found" << endl;
	}
}

int main() {

	test01();

	system("pause");

	return 0;
}

**Summary: * * the binary search method is very efficient. It is worth noting that the elements in the container must be ordered

5.2.5 count

Function Description:

Number of statistical elements

Function prototype:

count(iterator beg, iterator end, value);

//Count the number of occurrences of the element

//beg start iterator

//End end iterator

//Element of value statistics

Example:

#include <algorithm>
#include <vector>

//Built in data type
void test01()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(4);
	v.push_back(5);
	v.push_back(3);
	v.push_back(4);
	v.push_back(4);

	int num = count(v.begin(), v.end(), 4);

	cout << "4 The number of is: " << num << endl;
}

//Custom data type
class Person
{
public:
	Person(string name, int age)
	{
		this->m_Name = name;
		this->m_Age = age;
	}
	bool operator==(const Person & p)
	{
		if (this->m_Age == p.m_Age)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	string m_Name;
	int m_Age;
};

void test02()
{
	vector<Person> v;

	Person p1("Liu Bei", 35);
	Person p2("Guan Yu", 35);
	Person p3("Fei Zhang", 35);
	Person p4("Zhao Yun", 30);
	Person p5("Cao Cao", 25);

	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);
	v.push_back(p5);
    
    Person p("Zhuge Liang",35);

	int num = count(v.begin(), v.end(), p);
	cout << "num = " << num << endl;
}
int main() {

	//test01();

	test02();

	system("pause");

	return 0;
}

Summary: when counting user-defined data types, it is necessary to overload the operator==

5.2.6 count_if

Function Description:

Count the number of elements by condition

Function prototype:

count_if(iterator beg, iterator end, _Pred);

//Count the occurrence times of elements by conditions

//beg start iterator

//End end iterator

// _ Pred predicate

Example:

#include <algorithm>
#include <vector>

class Greater4
{
public:
	bool operator()(int val)
	{
		return val >= 4;
	}
};

//Built in data type
void test01()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(4);
	v.push_back(5);
	v.push_back(3);
	v.push_back(4);
	v.push_back(4);

	int num = count_if(v.begin(), v.end(), Greater4());

	cout << "The number greater than 4 is: " << num << endl;
}

//Custom data type
class Person
{
public:
	Person(string name, int age)
	{
		this->m_Name = name;
		this->m_Age = age;
	}

	string m_Name;
	int m_Age;
};

class AgeLess35
{
public:
	bool operator()(const Person &p)
	{
		return p.m_Age < 35;
	}
};
void test02()
{
	vector<Person> v;

	Person p1("Liu Bei", 35);
	Person p2("Guan Yu", 35);
	Person p3("Fei Zhang", 35);
	Person p4("Zhao Yun", 30);
	Person p5("Cao Cao", 25);

	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);
	v.push_back(p5);

	int num = count_if(v.begin(), v.end(), AgeLess35());
	cout << "Number of children under 35:" << num << endl;
}


int main() {

	//test01();

	test02();

	system("pause");

	return 0;
}

**Summary: * * count by value, count by condition_ if

5.3 common sorting algorithms

Learning objectives:

Master common sorting algorithms

Algorithm Introduction:

Sort / / sort the elements in the container
random_shuffle / / shuffle the elements within the specified range to adjust the order randomly
Merge / / merge container elements and store them in another container
/ / reverse the specified range of elements

5.3.1 sort

Function Description:

Sort the elements in the container

Function prototype:

sort(iterator beg, iterator end, _Pred);

//Find the element by value, find the iterator that returns the specified position, and the iterator that returns the end cannot be found

//beg start iterator

//End end iterator

// _ Pred predicate

Example:

#include <algorithm>
#include <vector>

void myPrint(int val)
{
	cout << val << " ";
}

void test01() {
	vector<int> v;
	v.push_back(10);
	v.push_back(30);
	v.push_back(50);
	v.push_back(20);
	v.push_back(40);

	//sort sorts from small to large by default
	sort(v.begin(), v.end());
	for_each(v.begin(), v.end(), myPrint);
	cout << endl;

	//Sort from large to small
	sort(v.begin(), v.end(), greater<int>());
	for_each(v.begin(), v.end(), myPrint);
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

**Summary: * * sort is one of the most commonly used algorithms in development and needs to be mastered

5.3.2 random_shuffle

Function Description:

Shuffle the elements in the specified range to adjust the order randomly

Function prototype:

random_shuffle(iterator beg, iterator end);

//Randomly adjust the order of elements within the specified range

//beg start iterator

//End end iterator

Example:

#include <algorithm>
#include <vector>
#include <ctime>

class myPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

void test01()
{
	srand((unsigned int)time(NULL));
	vector<int> v;
	for(int i = 0 ; i < 10;i++)
	{
		v.push_back(i);
	}
	for_each(v.begin(), v.end(), myPrint());
	cout << endl;

	//Disorder order
	random_shuffle(v.begin(), v.end());
	for_each(v.begin(), v.end(), myPrint());
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

**Summary: * * random_shuffle shuffle algorithm is more practical. Remember to add random number seeds when using it

5.3.3 merge

Function Description:

The two container elements are merged and stored in another container

Function prototype:

merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

//Container elements are merged and stored in another container

//Note: the two containers must be in order

//beg1 container 1 start iterator
//end1 container 1 end iterator
//beg2 container 2 start iterator
//end2 container 2 end iterator
//dest destination container start iterator

Example:

#include <algorithm>
#include <vector>

class myPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

void test01()
{
	vector<int> v1;
	vector<int> v2;
	for (int i = 0; i < 10 ; i++) 
    {
		v1.push_back(i);
		v2.push_back(i + 1);
	}

	vector<int> vtarget;
	//The target container needs to open up space in advance
	vtarget.resize(v1.size() + v2.size());
	//Merging requires two ordered sequences
	merge(v1.begin(), v1.end(), v2.begin(), v2.end(), vtarget.begin());
	for_each(vtarget.begin(), vtarget.end(), myPrint());
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

**Summary: * * merge the ordered sequence of two containers that must be merged

5.3.4 reverse

Function Description:

Invert the elements in the container

Function prototype:

reverse(iterator beg, iterator end);

//Inverts the elements of the specified range

//beg start iterator

//End end iterator

Example:

#include <algorithm>
#include <vector>

class myPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

void test01()
{
	vector<int> v;
	v.push_back(10);
	v.push_back(30);
	v.push_back(50);
	v.push_back(20);
	v.push_back(40);

	cout << "Before reversing: " << endl;
	for_each(v.begin(), v.end(), myPrint());
	cout << endl;

	cout << "After reversal: " << endl;

	reverse(v.begin(), v.end());
	for_each(v.begin(), v.end(), myPrint());
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

**Summary: * * reverse reverses the elements in the interval, which may be involved in the interview question

5.4 common copy and replacement algorithms

Learning objectives:

Master common copy and replacement algorithms

Algorithm Introduction:

Copy / / copy the elements of the specified range in the container to another container
replace / / modify the old element of the specified range in the container to a new element
replace_if / / replace the qualified element in the specified range in the container with a new element
Swap / / swap elements of two containers

5.4.1 copy

Function Description:

Copy the specified range of elements in the container to another container

Function prototype:

copy(iterator beg, iterator end, iterator dest);

//Find the element by value, find the iterator that returns the specified position, and the iterator that returns the end cannot be found

//beg start iterator

//End end iterator

//dest target start iterator

Example:

#include <algorithm>
#include <vector>

class myPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

void test01()
{
	vector<int> v1;
	for (int i = 0; i < 10; i++) {
		v1.push_back(i + 1);
	}
	vector<int> v2;
	v2.resize(v1.size());
	copy(v1.begin(), v1.end(), v2.begin());

	for_each(v2.begin(), v2.end(), myPrint());
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

**Summary: * * when using the copy algorithm to copy, the target container should remember to open up space in advance

5.4.2 replace

Function Description:

Modify the old element of the specified range in the container to a new element

Function prototype:

replace(iterator beg, iterator end, oldvalue, newvalue);

//Replace the old element in the interval with a new element

//beg start iterator

//End end iterator

//oldvalue old element

//newvalue new element

Example:

#include <algorithm>
#include <vector>

class myPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

void test01()
{
	vector<int> v;
	v.push_back(20);
	v.push_back(30);
	v.push_back(20);
	v.push_back(40);
	v.push_back(50);
	v.push_back(10);
	v.push_back(20);

	cout << "Before replacement:" << endl;
	for_each(v.begin(), v.end(), myPrint());
	cout << endl;

	//Replace 20 in container with 2000
	cout << "After replacement:" << endl;
	replace(v.begin(), v.end(), 20,2000);
	for_each(v.begin(), v.end(), myPrint());
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

**Summary: * * replace will replace the qualified elements in the interval

5.4.3 replace_if

Function Description:

Replace the qualified elements in the interval with the specified elements

Function prototype:

replace_if(iterator beg, iterator end, _pred, newvalue);

//Replace the element according to the condition, and replace the qualified element with the specified element

//beg start iterator

//End end iterator

// _ pred predicate

//New element replaced by newvalue

Example:

#include <algorithm>
#include <vector>

class myPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

class ReplaceGreater30
{
public:
	bool operator()(int val)
	{
		return val >= 30;
	}

};

void test01()
{
	vector<int> v;
	v.push_back(20);
	v.push_back(30);
	v.push_back(20);
	v.push_back(40);
	v.push_back(50);
	v.push_back(10);
	v.push_back(20);

	cout << "Before replacement:" << endl;
	for_each(v.begin(), v.end(), myPrint());
	cout << endl;

	//Replace 30 or more in the container with 3000
	cout << "After replacement:" << endl;
	replace_if(v.begin(), v.end(), ReplaceGreater30(), 3000);
	for_each(v.begin(), v.end(), myPrint());
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

**Summary: * * replace_if search by conditions, you can use the imitation function to flexibly filter the conditions that are met

5.4.4 swap

Function Description:

Swap elements of two containers

Function prototype:

swap(container c1, container c2);

//Swap elements of two containers

//c1 container 1

//c2 container 2

Example:

#include <algorithm>
#include <vector>

class myPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

void test01()
{
	vector<int> v1;
	vector<int> v2;
	for (int i = 0; i < 10; i++) {
		v1.push_back(i);
		v2.push_back(i+100);
	}

	cout << "Before exchange: " << endl;
	for_each(v1.begin(), v1.end(), myPrint());
	cout << endl;
	for_each(v2.begin(), v2.end(), myPrint());
	cout << endl;

	cout << "After exchange: " << endl;
	swap(v1, v2);
	for_each(v1.begin(), v1.end(), myPrint());
	cout << endl;
	for_each(v2.begin(), v2.end(), myPrint());
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

**Summary: * * when swap containers, pay attention to the same type of containers to be exchanged

5.5 common arithmetic generation algorithms

Learning objectives:

Master common arithmetic generation algorithms

be careful:

The arithmetic generation algorithm is a small algorithm, and the header file included when using is #include < numeric >

Algorithm Introduction:

Calculate / / calculate the cumulative sum of container elements
fill / / add element to container

5.5.1 accumulate

Function Description:

Calculate the cumulative sum of interval content container elements

Function prototype:

accumulate(iterator beg, iterator end, value);

//Calculate the cumulative sum of container elements

//beg start iterator

//End end iterator

//Value starting value

Example:

#include <numeric>
#include <vector>
void test01()
{
	vector<int> v;
	for (int i = 0; i <= 100; i++) {
		v.push_back(i);
	}

	int total = accumulate(v.begin(), v.end(), 0);

	cout << "total = " << total << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

**Summary: * * when calculating, the header file should be numeric. This algorithm is very practical

5.5.2 fill

Function Description:

Fills the container with the specified element

Function prototype:

fill(iterator beg, iterator end, value);

//Fill the container with elements

//beg start iterator

//End end iterator

//Value filled value

Example:

#include <numeric>
#include <vector>
#include <algorithm>

class myPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

void test01()
{

	vector<int> v;
	v.resize(10);
	//fill
	fill(v.begin(), v.end(), 100);

	for_each(v.begin(), v.end(), myPrint());
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

**Summary: * * fill can be used to fill the elements in the container interval with the specified value

5.6 common set algorithms

Learning objectives:

Master common set algorithms

Algorithm Introduction:

set_intersection / / find the intersection of two containers
set_union / / find the union of two containers
set_difference / / find the difference set between two containers

5.6.1 set_intersection

Function Description:

Find the intersection of two containers

Function prototype:

set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

//Find the intersection of two sets

//Note: the two sets must be an ordered sequence

//beg1 container 1 start iterator
//end1 container 1 end iterator
//beg2 container 2 start iterator
//end2 container 2 end iterator
//dest destination container start iterator

Example:

#include <vector>
#include <algorithm>

class myPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

void test01()
{
	vector<int> v1;
	vector<int> v2;
	for (int i = 0; i < 10; i++)
    {
		v1.push_back(i);
		v2.push_back(i+5);
	}

	vector<int> vTarget;
	//Take the smaller of the two values to make room for the target container
	vTarget.resize(min(v1.size(), v2.size()));

	//Returns the iterator address of the last element of the destination container
	vector<int>::iterator itEnd = 
        set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());

	for_each(vTarget.begin(), itEnd, myPrint());
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary:

Find the ordered sequence of two sets of intersection
The target container needs to take a small value from the two containers to open up space
set_ The return value of intersection is the position of the last element in the intersection

5.6.2 set_union

Function Description:

Find the union of two sets

Function prototype:

set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

//Find the union of two sets

//Note: the two sets must be an ordered sequence

//beg1 container 1 start iterator
//end1 container 1 end iterator
//beg2 container 2 start iterator
//end2 container 2 end iterator
//dest destination container start iterator

Example:

#include <vector>
#include <algorithm>

class myPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

void test01()
{
	vector<int> v1;
	vector<int> v2;
	for (int i = 0; i < 10; i++) {
		v1.push_back(i);
		v2.push_back(i+5);
	}

	vector<int> vTarget;
	//Take the sum of the two containers to make room for the target container
	vTarget.resize(v1.size() + v2.size());

	//Returns the iterator address of the last element of the destination container
	vector<int>::iterator itEnd = 
        set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());

	for_each(vTarget.begin(), itEnd, myPrint());
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary:

Union of two ordered sets
The target container needs to add two containers to open up space
set_ The union return value is the position of the last element in the union set

5.6.3 set_difference

Function Description:

Find the difference set of two sets

Function prototype:

set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

//Find the difference set of two sets

//Note: the two sets must be an ordered sequence

//beg1 container 1 start iterator
//end1 container 1 end iterator
//beg2 container 2 start iterator
//end2 container 2 end iterator
//dest destination container start iterator

Example:

#include <vector>
#include <algorithm>

class myPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

void test01()
{
	vector<int> v1;
	vector<int> v2;
	for (int i = 0; i < 10; i++) {
		v1.push_back(i);
		v2.push_back(i+5);
	}

	vector<int> vTarget;
	//Take the larger of the two values to make room for the target container
	vTarget.resize( max(v1.size() , v2.size()));

	//Returns the iterator address of the last element of the destination container
	cout << "v1 And v2 The difference set of is: " << endl;
	vector<int>::iterator itEnd = 
        set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());
	for_each(vTarget.begin(), itEnd, myPrint());
	cout << endl;


	cout << "v2 And v1 The difference set of is: " << endl;
	itEnd = set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), vTarget.begin());
	for_each(vTarget.begin(), itEnd, myPrint());
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary:

The two sets of difference sets must be ordered sequences
The target container needs to take a larger value from the two containers to open up space
10; i++) {
v1.push_back(i + 1);
}
vector v2;
v2.resize(v1.size());
copy(v1.begin(), v1.end(), v2.begin());

for_each(v2.begin(), v2.end(), myPrint());
cout << endl;
}

int main() {

test01();

system("pause");

return 0;

}

**Summary:**utilize copy When the algorithm copies, the target container remembers to open up space in advance















#### 5.4.2 replace

**Function Description:**

* Modify the old element of the specified range in the container to a new element



**Function prototype:**

- `replace(iterator beg, iterator end, oldvalue, newvalue);  `

  // Replace the old element in the interval with a new element

  // beg start iterator

  // End end iterator

  // oldvalue old element

  // newvalue new element



**Example:**

```c++
#include <algorithm>
#include <vector>

class myPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

void test01()
{
	vector<int> v;
	v.push_back(20);
	v.push_back(30);
	v.push_back(20);
	v.push_back(40);
	v.push_back(50);
	v.push_back(10);
	v.push_back(20);

	cout << "Before replacement:" << endl;
	for_each(v.begin(), v.end(), myPrint());
	cout << endl;

	//Replace 20 in container with 2000
	cout << "After replacement:" << endl;
	replace(v.begin(), v.end(), 20,2000);
	for_each(v.begin(), v.end(), myPrint());
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

**Summary: * * replace will replace the qualified elements in the interval

5.4.3 replace_if

Function Description:

Replace the qualified elements in the interval with the specified elements

Function prototype:

replace_if(iterator beg, iterator end, _pred, newvalue);

//Replace the element according to the condition, and replace the qualified element with the specified element

//beg start iterator

//End end iterator

// _ pred predicate

//New element replaced by newvalue

Example:

#include <algorithm>
#include <vector>

class myPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

class ReplaceGreater30
{
public:
	bool operator()(int val)
	{
		return val >= 30;
	}

};

void test01()
{
	vector<int> v;
	v.push_back(20);
	v.push_back(30);
	v.push_back(20);
	v.push_back(40);
	v.push_back(50);
	v.push_back(10);
	v.push_back(20);

	cout << "Before replacement:" << endl;
	for_each(v.begin(), v.end(), myPrint());
	cout << endl;

	//Replace 30 or more in the container with 3000
	cout << "After replacement:" << endl;
	replace_if(v.begin(), v.end(), ReplaceGreater30(), 3000);
	for_each(v.begin(), v.end(), myPrint());
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

**Summary: * * replace_if search by conditions, you can use the imitation function to flexibly filter the conditions that are met

5.4.4 swap

Function Description:

Swap elements of two containers

Function prototype:

swap(container c1, container c2);

//Swap elements of two containers

//c1 container 1

//c2 container 2

Example:

#include <algorithm>
#include <vector>

class myPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

void test01()
{
	vector<int> v1;
	vector<int> v2;
	for (int i = 0; i < 10; i++) {
		v1.push_back(i);
		v2.push_back(i+100);
	}

	cout << "Before exchange: " << endl;
	for_each(v1.begin(), v1.end(), myPrint());
	cout << endl;
	for_each(v2.begin(), v2.end(), myPrint());
	cout << endl;

	cout << "After exchange: " << endl;
	swap(v1, v2);
	for_each(v1.begin(), v1.end(), myPrint());
	cout << endl;
	for_each(v2.begin(), v2.end(), myPrint());
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

**Summary: * * when swap containers, pay attention to the same type of containers to be exchanged

5.5 common arithmetic generation algorithms

Learning objectives:

Master common arithmetic generation algorithms

be careful:

The arithmetic generation algorithm is a small algorithm, and the header file included when using is #include < numeric >

Algorithm Introduction:

Calculate / / calculate the cumulative sum of container elements
fill / / add element to container

5.5.1 accumulate

Function Description:

Calculate the cumulative sum of interval content container elements

Function prototype:

accumulate(iterator beg, iterator end, value);

//Calculate the cumulative sum of container elements

//beg start iterator

//End end iterator

//Value starting value

Example:

#include <numeric>
#include <vector>
void test01()
{
	vector<int> v;
	for (int i = 0; i <= 100; i++) {
		v.push_back(i);
	}

	int total = accumulate(v.begin(), v.end(), 0);

	cout << "total = " << total << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

**Summary: * * when calculating, the header file should be numeric. This algorithm is very practical

5.5.2 fill

Function Description:

Fills the container with the specified element

Function prototype:

fill(iterator beg, iterator end, value);

//Fill the container with elements

//beg start iterator

//End end iterator

//Value filled value

Example:

#include <numeric>
#include <vector>
#include <algorithm>

class myPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

void test01()
{

	vector<int> v;
	v.resize(10);
	//fill
	fill(v.begin(), v.end(), 100);

	for_each(v.begin(), v.end(), myPrint());
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

**Summary: * * fill can be used to fill the elements in the container interval with the specified value

5.6 common set algorithms

Learning objectives:

Master common set algorithms

Algorithm Introduction:

set_intersection / / find the intersection of two containers
set_union / / find the union of two containers
set_difference / / find the difference set between two containers

5.6.1 set_intersection

Function Description:

Find the intersection of two containers

Function prototype:

set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

//Find the intersection of two sets

//Note: the two sets must be an ordered sequence

//beg1 container 1 start iterator
//end1 container 1 end iterator
//beg2 container 2 start iterator
//end2 container 2 end iterator
//dest destination container start iterator

Example:

#include <vector>
#include <algorithm>

class myPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

void test01()
{
	vector<int> v1;
	vector<int> v2;
	for (int i = 0; i < 10; i++)
    {
		v1.push_back(i);
		v2.push_back(i+5);
	}

	vector<int> vTarget;
	//Take the smaller of the two values to make room for the target container
	vTarget.resize(min(v1.size(), v2.size()));

	//Returns the iterator address of the last element of the destination container
	vector<int>::iterator itEnd = 
        set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());

	for_each(vTarget.begin(), itEnd, myPrint());
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary:

Find the ordered sequence of two sets of intersection
The target container needs to take a small value from the two containers to open up space
set_ The return value of intersection is the position of the last element in the intersection

5.6.2 set_union

Function Description:

Find the union of two sets

Function prototype:

set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

//Find the union of two sets

//Note: the two sets must be an ordered sequence

//beg1 container 1 start iterator
//end1 container 1 end iterator
//beg2 container 2 start iterator
//end2 container 2 end iterator
//dest destination container start iterator

Example:

#include <vector>
#include <algorithm>

class myPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

void test01()
{
	vector<int> v1;
	vector<int> v2;
	for (int i = 0; i < 10; i++) {
		v1.push_back(i);
		v2.push_back(i+5);
	}

	vector<int> vTarget;
	//Take the sum of the two containers to make room for the target container
	vTarget.resize(v1.size() + v2.size());

	//Returns the iterator address of the last element of the destination container
	vector<int>::iterator itEnd = 
        set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());

	for_each(vTarget.begin(), itEnd, myPrint());
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary:

Union of two ordered sets
The target container needs to add two containers to open up space
set_ The union return value is the position of the last element in the union set

5.6.3 set_difference

Function Description:

Find the difference set of two sets

Function prototype:

set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

//Find the difference set of two sets

//Note: the two sets must be an ordered sequence

//beg1 container 1 start iterator
//end1 container 1 end iterator
//beg2 container 2 start iterator
//end2 container 2 end iterator
//dest destination container start iterator

Example:

#include <vector>
#include <algorithm>

class myPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

void test01()
{
	vector<int> v1;
	vector<int> v2;
	for (int i = 0; i < 10; i++) {
		v1.push_back(i);
		v2.push_back(i+5);
	}

	vector<int> vTarget;
	//Take the larger of the two values to make room for the target container
	vTarget.resize( max(v1.size() , v2.size()));

	//Returns the iterator address of the last element of the destination container
	cout << "v1 And v2 The difference set of is: " << endl;
	vector<int>::iterator itEnd = 
        set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());
	for_each(vTarget.begin(), itEnd, myPrint());
	cout << endl;


	cout << "v2 And v1 The difference set of is: " << endl;
	itEnd = set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), vTarget.begin());
	for_each(vTarget.begin(), itEnd, myPrint());
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

Summary:

The two sets of difference sets must be ordered sequences
The target container needs to take a larger value from the two containers to open up space
set_ The return value of difference is the position of the last element in the difference set

This article is the dark horse programmer c + + tutorial handout, save and upload, only for the author's personal review and query
If there is infringement, please contact the author to delete

ps: finish this course in a work dormitory at 0:28 p.m. on February 24, 2022.

Keywords: C++

Added by Mortier on Wed, 23 Feb 2022 18:43:37 +0200

Programming VIP

Dark horse programmer / C + + improve programming handout

1 template

1.1 concept of template

1.2 function template

1.2.1 function template syntax

1.2.2 precautions for function template

1.2.3 function template cases

1.2.4 differences between ordinary functions and function templates

1.2.5 call rules for ordinary functions and function templates

1.2.6 limitations of formwork

Type 1.3 formwork

1.3.1 class template syntax

1.3.2 difference between class template and function template

1.3.3 creation time of member function in class template

1.3.4 function parameters of class template objects

1.3.5 class template and inheritance

1.3.6 implementation outside class of class template member function

1.3.7 preparation of class template by document

1.3.8 class templates and friends

1.3.9 type template cases

First knowledge STL

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.1 vector stores built-in data types

2.5.2 Vector stores user-defined data types

2.5.3 Vector container nested container

3 STL - Common containers

3.1 string container

3.1.1 basic concept of string

3.1.2 string constructor

3.1.3 string assignment

3.1.4 string splicing

3.1.5 string find and replace

3.1.6 string comparison

3.1.7 string character access

3.1.8 string insertion and deletion

3.1.9 string substring

3.2 vector container

3.2.1 basic concept of vector

3.2.2 vector constructor

3.2.3 vector assignment

3.2.4 vector capacity and size

3.2.5 vector insertion and deletion

3.2.6 vector data access

3.2.7 vector interchange container

3.2.8 reserved space for vector

3.3 deque container

3.3.1 basic concept of deque container

3.3.2 deque constructor

3.3.3 deque assignment

3.3.4 deque size operation

3.3.5 deque insertion and deletion

3.3.6 deque data access

3.3.7 deque sorting

3.4 cases - scoring by judges

3.4.1 case description

3.4.2 implementation steps

3.5 stack container

3.5.1 basic concept of stack

3.5.2 common interfaces of stack

3.6 queue container

3.6.1 basic concept of queue

3.6.2 common interfaces of queue

3.7 container

3.7.1 basic concept of list

3.7.2 list constructor

3.7.3 list assignment and exchange

3.7.4 list size operation

3.7.5 list insertion and deletion

3.7.6 list data access

Reverse sort and list 3.7

3.7.8 sorting cases

3.8 set/ multiset container

3.8.1 basic concept of set

3.8.2 set construction and assignment

3.8.3 set size and swap