C + + improve programming

Mainly for C + + generic programming and STL technology

Template 1

1. Concept

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

Template features

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

2. Function template

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

2.1 function template syntax

Function template function: establish a general function whose function return value type and formal parameter type can not be specifically determined, but can be represented by a virtual type

grammar

template<typename T>
Function declaration or definition

parameter

Template: declares the creation of a template
typename: indicates that the symbol behind it is a data type, which can be replaced by class
T: A generic data type whose name can be replaced, usually in uppercase letters

// Two integer exchange functions
void swap(int& a, int& b)
{
	int temp = a;
	a = b; 
	b = temp;
}
// Swap floating point functions
void swap(double& a, double& b)
{
	double temp = a;
	a = b;
	b = temp;
}
// Function template
template <typename T>  // Declare the template and tell the compiler that the following code is followed by T. don't report errors. T is a general data type
void m_swap(T& a, T& b)
{
	T temp = a;
	a = b;
	b = temp;
}
void test()
{
	int a = 1;
	int b = 3;
	double a1 = 4;
	double b1 = 5;
	/* swap(a, b);
	cout << a << b << endl;
	swap(a1, b1);
	cout << a1 << b1 << endl; */
	// Using function templates
	// 1. Automatic derivation
	m_swap(a, b);
	cout << a << b << endl;
	// 2. Displays the specified type
	m_swap<int>(a, b);
	cout << a << b << endl;
}

Templates can parameterize data types

How to use the template

Automatic derivation
Displays the specified type

2.2 precautions

matters needing attention

Automatically deduce the data type. You must deduce the consistent data type T before you can use it
The template can be used only after the data type of T is determined

2.3 differences between ordinary functions and function templates

Automatic type conversion (implicit type replacement) can occur when calling ordinary functions
When a function template is called, if automatic type derivation is used, implicit type replacement will not occur
If you use the method of displaying the specified type, implicit type conversion can occur

2.4 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

The function template can be forcibly called through the empty template parameter list

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

void test()
{
	int a = 10;
	int b = 20;
	myPrint<>(a, b);  // Calling template function with empty template parameter list
}

Function templates can also be overloaded

If the function template can produce a better matching pattern, call the function template first

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

void test()
{
	char a = 'a';
	char b = 'b';
	myPrint(a, b);  // Function templates can produce better matches 
}

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

2.5 limitations of formwork

The versatility of templates is not everything

If a tuple and custom data type are passed in, it cannot be implemented

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

// Template overload
// Compare whether the two data are equal
class Person
{
public:
	Person(string name, int age)
	{
		m_Age = age;
		m_Name = name;
	}
	string m_Name;
	int m_Age;
};
template<class T>
bool myCompare(T& a, T& b)  // What if a custom data type is passed in
{
	if (a == b)
	{
		return true;
	}
	else
	{
		return false;
	}
}
// Use the version of materialized Person to realize the code, and materialization takes priority to call
// You can also use operator overloading
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 test()
{
	Person p1("Tom", 10);
	Person p2("Tom", 10);
	cout << myCompare(p1, p2) << endl;
}

Learning templates is not to write templates, but to use the templates provided by the system in STL

3. Class template

3.1 class template syntax

Class template function

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

grammar

template<typename T>
class

parameter

Template: declares the creation of a template
typename: indicates that the symbol behind it is a data type, which can be replaced by class
T: A generic data type whose name can be replaced, usually in uppercase letters

template<typename NameT, typename AgeT>
class Person
{
public:
	Person(NameT name, AgeT age)
	{
		m_Age = age;
		m_Name = name;
	}
	NameT m_Name;
	AgeT m_Age;
};
void test()
{
	Person<string, int>("Tom", 30);  // Call - there is only one way to call
}

3.2 difference between class template and function template

There are two main differences between class template and function template

Class templates do not use automatic type derivation

The default template class can have parameters in the template list

template<typename NameT, typename AgeT = int>  // Default parameters
class Person
{
public:
	Person(NameT name, AgeT age)
	{
		m_Age = age;
		m_Name = name;
	}
	NameT m_Name;
	AgeT m_Age;
};
void test()
{
	Person<string>("Tom", 30);
}

3.3 use timing

The creation time 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

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

};

template<typename T>
class Person
{
public:
    // If not called, it will not compile because the data type of T cannot be determined
	T p1;
	void func1()
	{
		p1.show();
	}
	
};
void test()
{
	Person<Person1> p;
	p.func1();
}

3.4 type template object function as parameter

Class template instance to pass parameters to the function

There are three ways of transmission

Specify the incoming data type: directly display the data type of the object
- ```
// Specify incoming type
void printPerson1(Person<string, int> &p); 
```

Parameter templating: change the parameters in the object into templates for transfer

// Parameter Templating
template<class T1, class T2>
void printPerson2(Person<T1, T2>& p);

Whole class templating: pass this object type templating

// Whole class Templating
template<class T>
void printPerson3(T &p);

// Class template as function parameters
template<class T1, class T2>
class Person
{
public:
	Person(T1 name, T2 age)
	{
		m_Name = name;
		m_Age = age;
	}
	T1 m_Name;
	T2 m_Age;
	void showPerson()
	{
		cout << "name:" << m_Name << " age:" << m_Age << endl;
	}
};
// Specify incoming type
void printPerson1(Person<string, int> &p)  
{
	p.showPerson();
}
// 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;
}
// Whole class Templating
template<class T>
void printPerson3(T &p)
{
	p.showPerson();
}
void test()
{
	Person<string, int> p("Tom", 12);
	printPerson1(p);
	printPerson2(p);
	printPerson3(p);
}

How to view data types

typeid(T2).name()

Class 3.5 template and inheritance

When a class template encounters inheritance, you need to pay attention to the following points

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

// Class template and inheritance
template<class T>
class Base
{
public:
	T m_M;
};
// When the parent class inherited by the subclass is a class template, the data type of T in the parent class shall be specified when the subclass is declared
class Son : public Base<string> {};
// If you want to flexibly use the T type in the parent class, the child class also needs to be changed into a class template
template<class T1, class T2>
class Son1 : public Base<T2> {};

3.6 implementation outside class of class template member function

Be able to master the out of class implementation of member functions in class templates

// Out of class implementation
template<class T1, class T2>
class Person
{
public:
	Person(T1 age, T2 name);
	void shouPerson();
	T1 m_Age;
	T2 m_Name;
};
template <class T1, class T2>
Person<T1, T2>::Person(T1 age, T2 name)
{
	this->m_Name = name;
	m_Age = age;
}
// To reflect the class function as a class template, add it without parameters
template <class T1, class T2>
void Person<T1, T2>::shouPerson()
{
	cout << "name:" << m_Name << " age:" << m_Age << endl;
}

Preparation of class 3.7 template documents

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

problem

The creation time of the member function in the class template is in the calling stage, resulting in the file writing is not linked

solve

Direct inclusion cpp source file
Write the declaration and implementation to the same file and change the suffix to hpp, hpp is the agreed name, not mandatory

person. Code in HPP

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


template<class T1, class T2>
class Person
{
public:
	Person(T1 age, T2 name);
	void shouPerson();
	T1 m_Age;
	T2 m_Name;
};
template <class T1, class T2>
Person<T1, T2>::Person(T1 age, T2 name)
{
	this->m_Name = name;
	m_Age = age;
}
template <class T1, class T2>
void Person<T1, T2>::shouPerson()
{
	cout << "name:" << m_Name << " age:" << m_Age << endl;
}

Program entry code

#include <iostream>
using namespace std;
#include <fstream>
// The first solution includes cpp source file
// #include"Person.cpp"

// The second solution will be h and The contents of cpp are written to In hpp file
#include "Person.hpp"

void test()
{
	Person<string, int> p("Tom", 132);
	p.shouPerson();
}
int main() {
	test();

	system("pause");
	return 0;
}

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

Class 3.8 templates and friends

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

Implementation of global function in class: directly declare friends in class
Out of class implementation of global functions: the compiler needs to know the existence of global functions in advance

// Print global information through global function
 // Let the compiler know the existence of the Person class in advance
template<class T1, class T2>
class Person;

// If it is implemented outside the class, the compiler needs to know the existence of the function in advance
template<class T1, class T2>
void printPerson1(Person<T1, T2>& p);

template<class T1, class T2>
class Person
{
	// Global function, implemented in class
	friend void printPerson(Person<T1, T2>& p)
	{
		cout << "full name:" << p.m_Name << " Age:" << p.m_Age << endl;
 	}
	// Global function, out of class implementation
	friend void printPerson1<>(Person<T1, T2>& p);  // < > it is a function template declaration
public:
	Person(T1 name, T2 age)
	{
		m_Name = name;
		m_Age = age;
	}
private:
	T1 m_Name;
	T2 m_Age;
};
template<class T1, class T2>
void printPerson1(Person<T1, T2>& p)
{
	cout << "full name:" << p.m_Name << " Age:" << p.m_Age << endl;
	cout << "Out of class implementation" << endl;
}

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

3.9 array class encapsulation

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 opertator = to prevent shallow copy problems
The elements in the array can be accessed by subscript
You can get the current number of elements in the array and the number of arrays

myArray. Code in HPP

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

template<class T1>  // Output function
void printArray();
template<class T1>
class MyArray
{
public:
	MyArray(int capacity);  // Parametric structure
	MyArray(const MyArray& arr);  // copy construction 
	MyArray& operator=(const MyArray& arr);  // Overload of assignment operators to prevent shallow copy problems
	void pushBack(const T1& val);  //  Inserting data by tail interpolation
	void delBack();  // Tail deletion method to delete data
	T1& operator[](int index);  // Overload [], so that the array can be accessed by index, and the value can be assigned at the same time
	int getCapacity();// Returns the capacity of the array
	int getSize();// Returns the size of the array
	~MyArray();  // Clear heap data
private:
	T1* pAddress;  // The pointer points to the real array opened to the heap
	int m_Capacity; // Array capacity
	int m_Size;  // Array size
};

template<class T1>
MyArray<T1>::MyArray(int capacity)
{
	this->m_Capacity = capacity;
	this->m_Size = 0;
	this->pAddress = new T1[this->m_Capacity];  // Open up array space
}
template<class T1>
MyArray<T1>::~MyArray()
{
	if (this->pAddress)
	{
		delete[] pAddress;
		pAddress = NULL;
	}
}
template<class T1>
MyArray<T1>::MyArray(const MyArray& arr)
{
	this->m_Capacity = arr.m_Capacity;
	this->m_Size = arr.m_Size;
	// This - > paddress = arr.paddress / / shallow copy
	this->pAddress = new T1[arr.m_Capacity];  // Deep copy
	// The data in arr is copied
	for (int i = 0; i < this->m_Size; i++)
	{
		this->pAddress[i] = arr.pAddress[i];
	}
}
template<class T1>
MyArray<T1>& MyArray<T1>::operator=(const MyArray& arr)
{
	// First judge whether there is data in the original heap area. If so, release it first
	if (this->pAddress)
	{
		delete[] pAddress;
		this->pAddress = NULL;
		this->m_Size = 0;
		this->m_Capacity = 0;
	}
	// Deep copy
	this->m_Capacity = arr.m_Capacity;
	this->m_Size = arr.m_Size;
	this->pAddress = new T1[this->m_Capacity];
	for (int i = 0; i < this->m_Size; i++)
	{
		this->pAddress[i] = arr.pAddress[i];
	}
	return *this;
}
template<class T1>
void MyArray<T1>::pushBack(const T1& val)
{
	// Judge whether the capacity is equal to the size
	if (this->m_Capacity == this->m_Size)
	{
		cout << "Array capacity reached, unable to insert" << endl;
		return;
	}
	this->pAddress[this->m_Size] = val;
	this->m_Size++;  // Update array size
}
template<class T1>
void MyArray<T1>::delBack()
{
	// Let users not access the last element, that is, tail deletion, logical deletion
	if (!this->m_Size)
	{
		cout << "There are no elements in the array" << endl;
		return;
	}
	this->m_Size--;  // Cannot access that element
}
template<class T1>
T1& MyArray<T1>::operator[](int index)
{
	return this->pAddress[index];
}
template<class T1>
int MyArray<T1>::getCapacity()
{
	return this->m_Capacity;
}
template<class T1>
int MyArray<T1>::getSize()
{
	return this->m_Size;
}
template<class T1>
void printArray(MyArray<T1>& arr)
{
	for (int i = 0; i < arr.getSize(); i++)
	{
		cout << arr[i] << endl;
	}
}

Main function call

#include <iostream>
using namespace std;
#include <fstream>
#include "Person.hpp"

void test()
{
	MyArray<int> arr(5);
	for (int i = 0; i < 5; i++)
	{
		arr.pushBack(i);
	}
	cout << "Start output array" << endl;
	printArray(arr);
}
int main() {
	test();

	system("pause");
	return 0;
}

The array can also store custom data types

2, STL acquaintance

1. Basic concepts

STL basic template library
STL is broadly divided into container, algorithm and iterator
Container and algorithm events are seamlessly connected through iterators
Almost all STL codes adopt template classes or template functions

2. STL six components

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

Container: various data structures: 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: a function with similar behavior, 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.1 containers, algorithms, iterators

Container: a place to put things

STL container is to implement some of the most widely used data structures

Common data structures: array, list, tree, stack, queue, set, mapping table, etc

These containers are divided into sequential containers and associative containers

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

Algorithm: the solution of the problem

Limited steps to solve logical or mathematical problems are 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, such as copy, replacement, deletion, 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

Iterators: glue between containers and algorithms

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

Each container has its own iterator

Iterators use much like pointers

Iterator Categories

type	jurisdiction	Support operation
Input iterator	read-only	++,==,!=
Output iterator	Write only	++
Forward iterator	Read and write, and push the iterator	++,==,!=
Bidirectional iterator	Read and write, which can be operated forward or backward	++,–
Random access iterator	Read and write. Can jump to access any data	++,–,[n],-n,<,>

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

3. Iterator initialization

3.1 vector stores built-in data types

Containers: vector

Algorithm: for_each

Iterator: vector < int >:: iterator

#Include < vector > / / vector header file
#Include < algorithm > / / standard algorithm header file

void printVector(int value)
{
	cout << value << endl;
}
// vector stores built-in data types
void test()
{
	// Create a vector container - array
	vector<int> v;

	// Insert data into container
	v.push_back(10);  // Tail interpolation data
	v.push_back(11);
	v.push_back(12);

	// Accessing data in a container through iterators
	vector<int>::iterator itBegin = v.begin(); // The starting iterator points to the first element in the container and is used as a pointer
	vector<int>::iterator itEnd = v.end();  // Ends the iterator and points to the next position of the last element of the container

	// The first traversal method
	while (itBegin != itEnd)
	{
		cout << *itBegin << endl;
		itBegin++;
	}
	// The second traversal method
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << *it << endl;
	}
	// The third traversal method
	for_each(v.begin(), v.end(), printVector);  // Callback function
}

3.2 vector stores user-defined data types

The user-defined data type is stored in the vector and printed out

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

void test()
{
	vector<Person> v;
	Person p1("a", 20);
	Person p2("b", 34);
	Person p3("c", 20);
	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);

	// Traversal data
	for (vector<Person>::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << "name:" << it->m_Name  
			<< " age:" << it->m_Age << endl;  // it is a pointer
	}

	// Pointer for storing custom data type
	vector<Person*> v1;
	v1.push_back(&p1);
	v1.push_back(&p2);
	v1.push_back(&p3);
	// Traversal data
	for (vector<Person*>::iterator its = v1.begin(); its != v1.end(); its++)
	{
		cout << "name:" << (*its)->m_Name
			<< " age:" << (*its)->m_Age << endl;  // it is a pointer
	}
}

3.3 nested containers in vector

The container is nested in the container, and we traverse all the data through the output

// Container nested container
void test()
{
	vector<vector<int>> V;
	// Create a small container
	vector<int> v1;
	vector<int> v2;
	vector<int> v3;
	vector<int> v4;

	// Adding data to a small container
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
		v2.push_back(10 - i);
		v3.push_back(20 - i);
		v4.push_back(i + 10);
	}
	// Insert the small container into the large container
	V.push_back(v1);
	V.push_back(v2);
	V.push_back(v3);
	V.push_back(v4);

	// Traverse large containers
	for (vector<vector<int>>::iterator i = V.begin(); i != V.end(); i++)
	{
		// *i is a container
		for (vector<int>::iterator j = (*i).begin(); j != (*i).end(); j++)
		{
			cout << *j << "\t";
		}
		cout << endl;
	}
}

3, STL common containers

Header files should be added to each container

1. string container

Basic concept of string 1.1

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, which encapsulates char * inside. Managing this string is a char * container

characteristic

string class encapsulates many member methods
- For example: find, copy, delete, replace, insert
string manages the memory allocated by char * without worrying about copying and value crossing. It is the responsibility of the class

1.2 string constructor

Constructor prototype

string(); Create an empty string

string(const char* s); Initialize with string s
string(const string& str); Initializing another string object with one string object
string(int, char c); Initialize with n characters C

/*
- string();							Create an empty string
  string(const char* s);			Initialize with string s
- string(const string& str);		Initializing another string object with one string object
- string(int, char c);              Initialize with n characters c
*/
void test()
{
	string s1;  // Default construction
	const char* str = "hello world";
	string s2(str);  // Parametric structure
	cout << "s2:" << s2 << endl;
	string s3(s2);  // copy construction 
	cout << "s3:" << s3 << endl;
	string s4(10, 'a');  // 10 a structures
	cout << "s4:" << s4 << endl;
}

The various construction methods of string are not comparable and have high flexibility

1.3 string assignment

Function description

Assign a value to a string

Prototype of assignment 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);  // Assigns a character 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 the current string
string& assign(const string &s);  // Assign the string s to the current string
string& assign(int n, char c);  // Assign n characters c to the current string

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);  // Concatenates 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 string
string& append(const string& s);  // Same as operator + = (const string & STR);
string& append(const string& s, int pos, int n);  // String s connects n characters from pos to the end of the string

1.5 string find and replace

Function description

Find: finds whether the specified character 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 first appears, 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 position where the first n characters of s appear for the first time from the pos position
int find(const char c, int pos = 0) const;  // Find the position 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 where s last appeared, starting from pos
int rfind(const char* s, int pos, int n) const;  // Find the position of the last occurrence of the first n characters of s from pos
int rfind(const char c, int pos = 0) const;  // Finds the last occurrence of the 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

summary

find is from left to right 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

1.6 string comparison

Function description

Comparison between strings

Comparison mode

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

It mainly compares whether the two strings are equal

1.7 string character access

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

char& operator[](int n);  // Get characters through [] method
char& at(int n);  // Get characters through at method
str.size();  // Returns the length of the string

Characters can be modified, STR [int n] ='c '

1.8 string insertion and deletion

Function description

Insert and delete characters on string 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

1.9 substring in string

Function description

Get the desired substring from the string

Function principle

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

2. vector container

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 connecting 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 iteration of the vector container is an iterator that supports random access

2.2 vector constructor

Function description

Create vector container

Function prototype

vector<T> v;  // Using template implementation class implementation, default constructor
vector v2(v.begin(), v.end());  // Copy the elements in the v[begin(), end()] interval to itself, closing on the left and opening on the right
vector v3(n, elem);  // The constructor copies n elem s to itself
vector v4(const vector& vec);  // copy constructor

Many construction methods of vector are not comparable and can be used flexibly

2.3 vector assignment

Function description

Assign a value to the vector container

Function principle

vector& operator=(const vector &vec);  // Overload assignment operator
assign(v.begin(), v.end());  // Assign the data copy in the v[begin, end] interval to itself
assign(n, elem);  // Assign n elem copies to itself

2.4 vector size operation

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();  // Number of elements returned in the container
resize(int num);  // Reassign the length of the container to num. if the container becomes longer, fill the new position with the default value; If the container becomes shorter, the element whose end exceeds the length of the container is deleted (0 by default)
resize(int num, elem);  // Reassign the length of the container to num. if the side of the container is long, fill the new position with elem value; If the container becomes shorter, the element whose end exceeds the length of the container is deleted

void printVector(vector<int>& v)
{
	for (vector<int>::iterator i = v.begin(); i != v.end(); i++)
	{
		cout << *i << " ";
	}
	cout << endl;
}
void test()
{
	vector<int> v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}
	cout << v.capacity() << endl;
	cout << v.size() << endl;
	v.resize(20);  // Fill with 0 by default
	cout << v.size() << endl;
	cout << v.capacity() << endl;
	printVector(v);
}

Capacity greater than or equal to size

2.5 vector insertion and deletion

Function description

Insert and delete the vector container

Function prototype

push_back(elem);  // Tail insert elem ent
pop_back();  // Delete last element
insert(const_iterator pos, elem);  // The iterator points to the position pos to insert the element elem
insert(const_iterator pos, int n, elem);  // The iterator points to the position pos and inserts n elements
erase(const_iterator pos);  // Deletes the length pointed to by the iterator
erase(const_iterator start, const_iterator end);  // Delete the elements from start to end of the iterator, close left and open right
clear();  // Delete all elements in the container

v1.insert(v1.begin(), 100); // The first parameter is the iterator

2.6 vector data access

Function description

Access to data in vector

Data prototype

at(int idx);  // Returns the object that the index idx refers to
operator[](int idx);  // Returns the data indicated by the index idx
fornt();  // Returns the first data element in the container
back();  // Returns the last data element in the container

2.7 vector interchange container

Function description

Realize the exchange of elements in two containers

Function prototype

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

void test()
{
	vector<int> v;
	vector<int> v1;
	for (int i = 0; i < 10; i++)
	{
		v.insert(v.begin(), i);
		v1.push_back(i + 100);
	}
	cout << "Before exchange" << endl;
	printVector(v);
	printVector(v1);
	v.swap(v1);
	cout << "After exchange" << endl;
	printVector(v);
	printVector(v1);
}

Function: using swap skillfully can shrink the memory space vector < int > (V) swap(v); // Use anonymous objects

2.8 reserved space for vector

Function description

Reduce the expansion times of vector when dynamically expanding capacity

Function principle

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

void test()
{
	vector<int> v;

	int num = 0;  // Statistics of development times
	v.reserve(1000000);  // When this code is not added, 35 memory spaces are opened up
	int* p = NULL;  
	for (int i = 0; i < 1000000; i++)
	{
		v.push_back(i);
		if (p != &v[0])  // Once the memory is opened, its first address will change
		{
			p = &v[0];
			num++;
		}
	}
	cout << num << endl;
}

If the reserved space is large, the reserved data can be used

3. deque container

3.1 deque basic concept

function

Double ended array: the header can be inserted or deleted

The difference between deque and vector

vector has low efficiency in inserting and deleting header, large amount of data and low efficiency
deque relatively speaking, the insertion and deletion speed of the head will be faster than that of the vector
vector accesses elements faster than deque, which is related to the implementation of both

deque internal working principle

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.2 deque constructor

Function description

deque vessel construction

Function principle

deque<T> deq;  // Default construction form
deque d2(deq.begin(), deq.end());  // The constructor copies the elements in the [beg, end] interval to itself
deque d3(n, elem);  // The constructor copies n elem s to itself
deque d4(const deque &deq);  // copy constructor

3.3 deque assignment

Function description

Assign a value to the deque container

Function principle

deque& operator=(const deque& d);  // Overload assignment operator
assign(beg, end);  // Assign the data copy in the [beg, end] interval to itself
assign(n, elem);  // Assign n elem copies to itself

3.4 deque size operation

Function description

Operate on the size of the deque container

Function principle

empty();  // Determine whether the container is empty
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, fill the new position with the default value; If the container becomes shorter, the element whose end exceeds the length of the container is deleted (0 by default)
resize(int num, elem);  // Reassign the length of the container to num. if the side of the container is long, fill the new position with elem value; If the container becomes shorter, the element whose end exceeds the length of the container is deleted

deque has no concept of capacity

3.5 deque insertion and deletion

Function description

Inserting and deleting data into the deque container

Function prototype

// Two end operation
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 the first element of the container

// Specify location operation
insert(pos, elem);  // Insert a copy of the elem element in the pos position and return the location of the data
insert(pos, n, elem);  // Insert n elem data in pos position, no return value
insert(pos, beg, end);  // Insert (D1. Begin()) at the pos position End()) data, 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

The pos inside is the position of the iterator pointer

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[])(int idx);  // Returns the value of index idx
front();  // Returns the first data element of the container
back();  // Returns the last data element of the container

3.7 deque sorting

Function description

Use the deque algorithm to sort the data

Function prototype

sort(iterator beg, iterator end);  // Sort the elements in the [beg, end] interval

Note that the header file #include < algorithm > should be included when using

For containers that support random access iterators, they can be sorted directly by sort algorithm

vector can also be sorted using sort

4. Case - judges' scoring

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

4.2 implementation steps

Create five players and put them in the vector container
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

// Player category
class Person
{
public:
	Person(string name, int score)
	{
		m_Name = name;
		m_Score = score;
	}
	string m_Name;
	int m_Score;  // average
};
void createPerson(vector<Person>& v)
{
	// Create five players
	for (int i = 0; i < 5; i++)
	{
		char nameSeed[] = { 'A', 'B', 'C', 'D', 'E' };
		string name = "player";
		name += nameSeed[i];
		int score = 0;  // The default is 0
		Person p(name, score);
		v.push_back(p);
	}
}
void setScore(vector<Person>& v)
{
	// Score
	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;  // Score between 60 and 100, random
			d.push_back(score);  // Put the score into the container
		}
		// sort
		sort(d.begin(), d.end());

		// Remove the highest score and the lowest score
		d.pop_front();
		d.pop_back();
		// Average score
		int sum = 0;
		for (deque<int>::iterator dit = d.begin(); dit != d.end(); dit++)
		{
			sum += *dit;  // Cumulative score
		}
		int avr = sum / d.size();
		it->m_Score = avr;
	}
}
void showScore(vector<Person> v)
{
	for (vector<Person>::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << "The name is:" << it->m_Name << "  The average score is:" << it->m_Score << endl;
	}
}
void test()
{
	// Random number seed
	srand((unsigned int)time(NULL));

	vector<Person> v;  // Store contestants
	v.reserve(5);

	createPerson(v);

	setScore(v);

	showScore(v);
}

5. stack container

5.1 basic concept of stack

Concept: stack is a data structure with first in and last out. It has only one exit

Elements entering the stack are called push();

Pop up elements in the stack are called out of stack: pop();

5.2 stack common interfaces

Function Description:

Common external interface of stack container

5.2.1 constructor

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

5.2.2 assignment operation

stack& operator=(const stack& stk);  // Overload assignment operator

5.2.3 size operation

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

5.2.4 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

6. queue container

6.1 basic concept of queue

Concept:

queue is a first in first out 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();

6.2 common interfaces of queue

Function description

Common external interface of stack container

6.2.1 constructor

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

6.2.2 assignment operation

queue& operator=(const queue& q);  // Overload assignment operator

6.2.3 size operation

empty();  // Determine whether the stack is empty
size();  // Return stack size

6.2.4 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 of the queue header

7. list container

7.1 basic concepts

Function: chain storage of data

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

Composition of linked list: 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

The linked list in STL is a two-way circular 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 or backward, which belongs to a two-way iterator

list advantages

Dynamic memory allocation is adopted, which 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 amount of data

list disadvantages

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 nor delete will invalidate the original list iterator, which is not true in vector

Summary: list and vector are the most commonly used containers in STL, with their own advantages and disadvantages

7.2 list constructor

Function description

Create a list container

Function prototype

list<T> l;  // list is implemented by template class, and the default construction form of object
list(beg, end);  // The constructor copies the elements in the [beg, end] interval to itself
list(n, elem);  // The constructor copies n elem s to itself
list(const list& l);  // copy constructor

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& l);  // Overload assignment operator
swap(l);  // Swap the list with its own elements

7.4 list size operation

Function description

Operate on the size of the list container

Function prototype

size();  // Number of elements returned in the container
empty();  // Determine whether the container is empty
resize(int num);  // Reassign the length of the container to num. if the container becomes longer, fill the new position with the default value; If the container becomes shorter, the element whose end exceeds the length of the container is deleted (0 by default)
resize(int num, elem);  // Reassign the length of the container to num. if the side of the container is long, fill the new position with elem value; If the container becomes shorter, the element whose end exceeds the length of the container is deleted

7.5 list insertion and deletion

Function description

Insert and delete data from the list container

Function prototype

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 the first element of the container
insert(pos, elem);  // Insert a copy of the elem element in the pos position and return the location of the data
insert(pos, n, elem);  // Insert n elem data in pos position, no return value
insert(pos, beg, end);  // Insert (l.begin(), l.end()) data in pos position, 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
remove(elem);  // Delete all elements in the container that match the element value

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

Note that you cannot access elements in a container using at and []

The reason is that the list is essentially a linked list, rather than using continuous linear space to store data, and the iterator does not support random access

Iterators do not support random access and support two-way access

7.7 list inversion and sorting

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, which is a member function

All containers that do not support random access iterators cannot use standard algorithms

Containers that do not support random access iterators will provide corresponding algorithms internally

For custom data types, sort() brackets can add a collation

Advanced sorting is just another logical rule formulation on the sorting rules, which is not complicated

bool comparePerson(Person& p1, Person& p2)
{
    // Ascending by age
    if (p1.m_Age == p2.m_Name)
    {
        // Same age, ascending height
        return p1.Height > p2.Height;
    }
    else
    {
        return p1.m_Age < p2.m_Age;
    }
}
l.sort(comparePerson);  // Sorting algorithm

8. set / multiset container

8.1 basic concepts

Introduction:

All elements are automatically sorted on insertion

essence

set is an associative container, and the 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

8.2 set construction and assignment

Function description

Create set container and assign values

Function prototype

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

set& operator=(const set& s);  // Overload assignment operator
inset(elem);  // insert data

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(s);  // Swap two collection containers

8.4 set insertion and deletion

Function description

set container to insert and delete

Function prototype

insert(elem);  // Insert element in container
clear();  // Empty 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

8.5 set search and statistics

Function description

Find data and make data statistics for the 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

8.6 differences between set and multiset

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

ret.second is used to check whether the insertion is successful
multiset does not detect data, so you can insert data repeatedly

8.7 pair group creation

Function description

For the data that appears successfully, two data can be returned by using the pair group

Two creation methods

pair<type1, type2> p (value1, value2);  // The two types correspond to the data type of value respectively
pair<type1, type2> p = make_pair(value1, value2);

There are two creation methods. Just remember one

Mode of use

pair<string, int> p ("Tom", 20);
cout << "name:" << p.first << "  age:" << p.second;

8.8 set sorting

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

Using the imitation function, the sorting rules can be changed

#include <set>
class MyCompare
{
public:
	bool operator()(int v1, int v2) const  
	{
		return v1 > v2;  // Descending sort
	}
};

void test()
{
	// Store built-in data types and change sorting rules
	set<int, MyCompare> s1;  // The essence of affine function is a class
	s1.insert(10);
	s1.insert(30);
	s1.insert(20);
	s1.insert(40);
	for (set<int, MyCompare>::iterator it = s1.begin(); it != s1.end(); it++)
	{
		cout << *it << endl;
	}
}

For custom data types, to create a collation, you must specify a collation

class MyCompare
{
public:	  
    bool operator()(const Person& p1, const Person& p2)
    {
        // In descending order of age
        return p1.m_Age > p2.m_Age;
    }
};

9. map / multimap container

9.1 basic concepts

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 realized by binary tree

advantage:

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

map/ multimap differences

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

9.2 map construction and assignment

Function Description:

Construct and assign the map container

Function prototype

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

map& operator=(const map& mp);  // Overload assignment operator

All elements in the map container appear in pairs, and pairs should be used when inserting data

9.3 map size and swap

Function Description:

Map container size and exchange map values

Function prototype

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

9.4 map insertion and deletion

Function Description:

map container to insert and delete data

Function prototype

insert(elem);  // Insert element in container
clear();  // Empty 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 whose container key is key

Note that you are inserting a pair of groups

// First kind
m.insert(pair<int, int>(1, 10));
// Second
m.insert(make_pair(2, 20));
// Third
m.insert(map<int, int>::value_type(3, 30));
// Fourth
m[4] = 40;  // It is not recommended. You can use [] to access the value

9.5 map search and statistics

Function Description:

Search data and statistics of map container

Function prototype

find();  // Find out whether the key exists and return the iteration value of the element that changed the key; If it does not exist, return m.end();
count();  // Count the number of key elements

Map. 6 sorting

The default collation of the map container is to sort in ascending order by key

The sorting rules can be changed by using the imitation function

It is similar to [set sort] (#8.8 set sort)

10. Case - employee grouping

10.1 case description

The company recruits 10 employees every day. After 10 employees enter the company, which department should they be assigned to work in
Employee information: 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
Show employees by segment

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

10.3 code demonstration

class Worker
{
	// Create employee
public:
	string m_Name;
	int m_Salary;
};
void createWorker(vector<Worker>& v)
{
	// Create 10 employees
	for (int i = 0; i < 10; i++)
	{
		Worker worker;
		string nameSeed = "ABCDEFGHIJ";
		worker.m_Name = "staff";
		worker.m_Name += nameSeed[i];
		worker.m_Salary = rand() % 10000 + 10000;  // 10000~19999
		v.push_back(worker);  // Put employees into groups
	}
}
void printWorker(const vector<Worker>& v)
{
	for (vector<Worker>::const_iterator it = v.begin(); it != v.end(); it++)
	{
		cout << "name: " << it->m_Name << "   salary: " << it->m_Salary << endl;
	}
}
void printWorker(multimap<string, Worker>& mp, string* arr)
{
	string s0(20, '-');
	for (int i = 0; i < 3; i++)
	{
		string s = arr[i];
		s += "Department information";
		cout << s << endl;
		multimap<string, Worker>::iterator pos = mp.find(arr[i]);  // Returns the iterator object
		int count = mp.count(arr[i]);
		for (int index = 0; pos != mp.end() && index < count; pos++, index++)
		{
			cout << "full name:" << pos->second.m_Name << "   Salary:" << pos->second.m_Salary << endl;
		}
		cout << s0 << endl;
	}
}
void setGroup(vector<Worker>& v, multimap<string, Worker>& mp, string* arr)
{
	for (vector<Worker>::iterator it = v.begin(); it != v.end(); it++)
	{
		// Generate random department number
		int depId = rand() % 3;  // 0 1 2 random number
		// Insert the employee into the group, key number, value employee
		mp.insert(pair<string, Worker>(arr[depId], *it));
	}
}
void test()
{
	// Add random seed
	srand((unsigned int)time(NULL));
	string dep[] = { "plan", "Fine Arts", "research and development" };
	vector<Worker> v;
	createWorker(v);
	printWorker(v);

	// Employee grouping
	multimap<string, Worker> mp;
	setGroup(v, mp, dep);
	printWorker(mp, dep);
}

4, STL function object

1. Function object

1.1 basic concepts

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

1.2 application method

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

// Function object
class MyAdd
{
public:
	MyAdd()
	{
		this->count = 0;
	}
	int operator()(int v1, int v2)
	{
		this->count++;
		return v1 + v2;
	}
	int count;  // Function objects can have their own internal state
};
void test()
{
	MyAdd ma;
	cout << ma(1, 2) << endl;
	cout << ma(1, 2) << endl;
	cout << ma(1, 2) << endl;
	cout << ma(1, 2) << endl;
	cout << "The number of calls is:" << ma.count << endl;
}

2. Predicate

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

2.2 unary predicate

class CreateFive
{
public:
	bool operator()(int val)
	{
		return val > 5 ? true : false;
	}  // one-element predicate

};

void test()
{
	vector<int> v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}
	// Find out if there is a number greater than 5 in the container
	vector<int>::iterator it = find_if(v.begin(), v.end(), CreateFive());  // It is an anonymous function object, find_ The return value of if is an iteration object
	if (it == v.end())
	{
		cout << "Can't find" << endl;
	}
	else
	{
		cout << "Numbers greater than five are:" << *it << endl;
	}
}

2.3 binary predicate

// two-place predicate
class MySort
{
public:
	bool operator()(int a, int b)
	{
		return a > b ? true : false;
	}
};
void test()
{
	vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);
	v.push_back(50);
	// sort(v.begin(), v.end());  //  Ascending arrangement
	// Use the function object to change the algorithm strategy into descending arrangement of sorting rules
	sort(v.begin(), v.end(), MySort());
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

3. Built in function object

3.1 significance

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
When using built-in function objects, the header file #include < functional > needs to be introduced

3.2 arithmetic imitation function

Function Description:

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

Function imitating principle

template<class T> T plus<T>;  // Addition operation
template<class T> T minus<T>;  // Subtraction operation
template<class T> T multiplies<T>;  // Multiplication
template<class T> T divides<T>;  // Division operation
template<class T> T modulus<T>;  // Modular operation
template<class T> T negate<T>;  // Inverse operation, and the inverse of 10 is - 10

plus<int> p;
cout << p(10, 20) << endl;
negate<int> n;
cout << n(20) << endl;

3.3 relation imitation function

Function description

Implement relationship comparison

Function imitating principle

template<class T> bool equal_to<T>;  // =
template<class T> bool not_equal_to<T>;  // !=
template<class T> bool greater<T>;  // >
template<class T> bool greater_equal<T>;  // >=
template<class T> bool less<T>;  // <
template<class T> bool less_equal<T>;  // <=

3.4 logic imitation function

Function description

Realize logical operation

Imitative function principle

template<typename T> bool logical_and<T>;  // And
template<typename T> bool logical_or<T>;  // or
template<typename T> bool logical_not<T>;  // wrong

5, STL common algorithms

Description:

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, assignment, etc
< numeric > is small in size and only includes several module functions that perform simple mathematical operations on the sequence
< functional > defines some modular classes to declare function objects

1. Common traversal algorithms

Learning objectives:

Master common traversal algorithms

Algorithm Introduction:

for_each();  // Traversal container
transform();  // Transport container to another container

1.1 for_each

Function Description:

Implement traversal container

Function prototype

for_each(iterator beg, iterator end, _func);

Traversal algorithm: traversal of container elements

Parameters:

beg: start iterator
End: end iterator
_ func: function or function object, which is generally a function of output content and a callback function

1.2 transform

Function Description:

Transport container to another container

Function prototype

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

The target container should open up space in advance, otherwise an error will be reported

Parameters:

beg1: source container start iterator
end1: source container end iterator
beg2: target container start iterator
_ func: function or function object

2. Common search algorithms

Learning objectives:

Master common search algorithms

Algorithm Introduction:

find();  // Find element
find_if();  // Find elements by criteria
adjacent_find();  // Find adjacent duplicate elements
binary_search();  // Binary search method
count();  // Number of statistical elements
count_if();  // Count the number of elements by condition

2.1 find

Function Description:

Finds the specified element, finds the iterator that returns the specified element, and cannot find the return end iterator

Function prototype

find(iterator beg, iterator end, value);

Parameters:

beg: start iterator
End: end iterator
value: the element to find

If it is a custom data type, the equal sign operator should be overloaded when searching

2.2 find_if

Function Description:

Find elements by criteria

Function prototype

find_if(iterator beg, iterator end, _Pred);

Parameters:

beg: start iterator
End: end iterator
_ Pred: function or predicate (return bool type imitation function)

2.3 adjacent_find

Function Description:

Find adjacent duplicate elements

Function prototype

adjacent_find(iterator beg, iterator end);

Parameters:

beg: start iterator
End: end iterator

2.4 binary_search

Function Description:

Finds whether the specified element exists

Function prototype

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

Note: not available in unordered sequences

Parameters:

beg: start iterator
End: end iterator
value: the element to find

2.5 count

Function Description:

Number of statistical elements

Function prototype

count(iterator beg, iterator end, value);

beg: start iterator

End: end iterator

value: statistical element

When making statistics on user-defined data types, you should use imitation functions

class Person
{
public:
    Person(string name, int age)  
    {
        this->m_Name = name;
        this->m_Age = age;
    }
    bool operator==(const Person& p)  // You need to overload the equal sign operator before you can count
    {
        return this->m_Age == p.m_Age && this->m_Name = p.m_Name? true : flase;
    }
    int m_Age;
    string m_Name;
};

When counting user-defined data types, you need to overload the operator==

2.6 count_if

Function Description:

Count the number of elements by condition

Function prototype

count_if(iterator beg, iterator end, _Pred);

Parameters:

beg: start iterator
Iterator: end
_ Pred: predicate

3. Common sorting algorithms

Learning objectives

Master common sorting algorithms

Algorithm Introduction:

sort();  // Sort the elements in the container
random_shuffle();  // Shuffle, randomly adjust the order of elements within the specified range
merge();  // Container elements are merged and stored in another container
reverse();  // Inverts the elements in the specified range

3.1 sort

Function description

Sort the elements in the container

Function prototype

sort(iterator beg, iterator end, _Pred);

Parameters:

beg: start iterator
End: end iterator
_ Pred: predicate

3.2 random_shuffle

Function description

Shuffle, randomly adjust the order of elements within the specified range

Function prototype

random_shuffle(iterator beg, iterator end);

Remember to add random seeds when using

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

Parameters:

beg: start iterator
End: end iterator

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);

be careful:

The two containers must be ordered
Allocate space to the target container in advance

Parameters:

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

3.4 reverse

Function description

Invert the elements in the container

Function prototype

reverse(iterator beg, iterator end);

Parameters:

beg: start iterator
End: end iterator

4. Common copy and replace algorithms

Learning objectives

Master common copy and replacement algorithms

Algorithm Introduction

copy();  // Copy the elements within 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 elements that meet the conditions of the specified range in the container with new elements
swap();  // Swap elements of two containers

4.1 copy

Function Description:

Copies a specified range of elements within a 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

You need to book the space of the target container first

Parameters:

beg: start iterator
End: end iterator
dest: destination container start iterator

4.2 replace

Function description

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

Function prototype

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

It will replace all qualified elements in the interval

Parameters:

beg: start iterator
End: end iterator
Oldline: Old element
newvalue: new element

4.3 replace_if

Functional usage

Replace the qualified elements in the interval with specific elements

Function principle

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

It will replace all qualified elements in the interval

Parameters:

beg: start iterator
End: end iterator
_ Pred: predicate
newvalue: new element to replace

4.4 swap

Function Description:

Swap elements of two containers

Function prototype

swap(container c1, container c2);

Containers of the same data type can be interchanged

Parameters:

c1: container 1
c2: container 2

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 to be included when using is #include < numeric >

Algorithm Introduction

accumulate();  // Container summation element
fill();  // Add element to container

5.1 accumulate

Function Description:

Calculate the sum of elements in the interval

Function prototype

accumulate(iterator beg, iterator end, firstValue);

Parameters:

beg: start iterator
End: end iterator
firstValue: initial cumulative value

5.2 fill

Function Description:

Fills the container with the specified element

Function prototype

fill(iterator beg, iterator end, value);

Parameters:

beg: start iterator
End: end iterator
Value: filled value

6. Common set algorithm

Learning objectives:

Master common set algorithms

Algorithm Introduction

set_insersection();  // Find the intersection of two containers
set_union();  // Find the union of two containers
set_different();  // Find the difference set of two containers

6.1 set_insersection

Function Description:

Find the intersection of two containers and duplicate elements

Function prototype

iterator itEnd = set_insersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);  // Intersection, an iterator that returns the last value

It is necessary to open up space in advance. In the most special case: large containers include small containers. Open up space and take the size of small containers

dest.resize(c1.size() > c2.size() ? c2.size() : c1.size());

Parameters:

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

6.2 set_union

Function Description:

Find the union of two containers

Function prototype

iterator itEnd = set_insersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);  // Union, an iterator that returns the last value

The target container should open up space in advance. The most special case is that the two containers do not intersect

dest.resize(c1.size() + c2.size());

Parameters:

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

6.3 set_difference

Function Description:

Find the difference set of two containers

Function prototype

iterator itEnd = set_insersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);  // The difference set of c1 and c2, the iterator that returns the last value, c1 - c2

The target container should open up space in advance. The most special case is that there is no intersection between the two containers, and the larger size is taken as the space of the container

dest.resize(c1.size() > c2.size() ? c1.size() : c2.size());  // You can also use max (C1. Size(), C2 size());

Parameters:

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

Keywords: C++ Back-end

Added by onyx on Fri, 18 Feb 2022 16:40:29 +0200

Programming VIP

C + + improve programming

C + + improve programming

Template 1

1. Concept

2. Function template

2.1 function template syntax

2.2 precautions

2.3 differences between ordinary functions and function templates

2.4 call rules for ordinary functions and function templates

2.5 limitations of formwork

3. Class template

3.1 class template syntax

3.2 difference between class template and function template

3.3 use timing

3.4 type template object function as parameter

Class 3.5 template and inheritance

3.6 implementation outside class of class template member function

Preparation of class 3.7 template documents

Class 3.8 templates and friends

3.9 array class encapsulation

2, STL acquaintance

1. Basic concepts

2. STL six components

2.1 containers, algorithms, iterators

3. Iterator initialization

3.1 vector stores built-in data types

3.2 vector stores user-defined data types

3.3 nested containers in vector

3, STL common containers

1. string container

Basic concept of string 1.1

1.2 string constructor

1.3 string assignment

1.4 string splicing

1.5 string find and replace

1.6 string comparison

1.7 string character access

1.8 string insertion and deletion

1.9 substring in string

2. vector container

2.1 basic concept of vector

2.2 vector constructor

2.3 vector assignment

2.4 vector size operation

2.5 vector insertion and deletion

2.6 vector data access

2.7 vector interchange container

2.8 reserved space for vector

3. deque container

3.1 deque basic concept

3.2 deque constructor

3.3 deque assignment

3.4 deque size operation

3.5 deque insertion and deletion

3.6 deque data access

3.7 deque sorting

4. Case - judges' scoring

4.1 case description

4.2 implementation steps

5. stack container

5.1 basic concept of stack

5.2 stack common interfaces

5.2.1 constructor

5.2.2 assignment operation

5.2.3 size operation

5.2.4 data access

6. queue container

6.1 basic concept of queue

6.2 common interfaces of queue

6.2.1 constructor

6.2.2 assignment operation

6.2.3 size operation

6.2.4 data access

7. list container

7.1 basic concepts

7.2 list constructor

7.3 list assignment and exchange

7.4 list size operation

7.5 list insertion and deletion