***This stage mainly focuses on C + + generic programming and STL technology, and discusses the deeper use of C + +**
Concept of template: establish a general mold to greatly improve reusability
C + + provides two types of template mechanisms: function template and class template
Function template
Function declaration or definition
Template / / declaration or definition of function template
//Using templates to provide general exchange functions
template
void mySwap(T& a, T& b)
{
T temp = a;
a = b;
b = temp;
}
//Function template exchange
1. Automatic type exchange can only be used after consistent data types are derived
int a = 10;
int b = 20;
mySwap(a, b);
2. Display the specified type
mySwap(a,b);
1. When using automatic type derivation, the consistent data type T must be derived before it can be used
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
}
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
//Function template
template<class T>
T myAdd02(T a, T b)
{
return a + b;
}
//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
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
void myPrint(int a, int b)
{
cout << "Ordinary function 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;
}
//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 ordinary functions exist, but only declare that they are not implemented, or they are not implemented in the current file Now, it will report an error and cannot be found
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
Since the function template is provided, it is better not to provide ordinary functions, which will lead to ambiguity
Syntax of class template: establish a general class, and the member data in the class can not be specified.
#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;
}
There are two main differences between class templates and function templates:
1. Class templates do not use automatic type derivation, so display type derivation must be used
2. Class templates can have default parameters in the template parameter list
The member function of the class template is not created at the beginning, but only when called.
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;
}
There are three ways to pass parameters to a function for an object materialized by a class template
1. Specify the type of incoming data – directly display the data type of the object
2. Parameter templating: change the parameters in the object into templates for transfer
3. The whole class is templated
//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);
}
When the subclass template encounters inheritance, you should pay attention to the following points: when the parent class inherited by the subclass is a template, the subclass needs to indicate the type of parent class T when declaring. If it is not specified, the compiler cannot allocate memory for the subclass. If you want to flexibly specify the parent type, the subclass also needs to be changed into a class template. In either case, you need to display the type of declared parent class.
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;
}
Internal and external implementation of class template
//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;
}
**
Summary: when the member function in the class template is implemented outside the class, the template parameter list needs to be added**
Preparation of class template by file: 1 Direct inclusion cpp file 2 Write the declaration and implementation to the same file and change the suffix to hpp.
Class template and friends: it is recommended to implement the global function in class, which is simple to use and can be directly recognized by the compiler.
As long as STL is divided into six categories, it focuses on learning containers, algorithms, iterators and imitation functions.
- 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.
Common containers:
vector nested container:
#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;
}
}
stirng manages the memory allocated by char * without worrying about copying and value crossing. It is managed internally.
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
string assignment
* `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
**Summary: * * string has many assignment methods, and operator = is more practical
String string splicing
* `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
Find and replace string
* `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
Summary:
- find is from left to back, and rfind is from right to left
- find returns the first character position after finding the string. If it is not found, it returns - 1
- When replacing, you need to specify where to start, how many characters to replace and what kind of string to replace
String comparison:
* `int compare(const string &s) const; ` //Compare with string s * `int compare(const char *s) const;` //Compare with string s
String access
* `char& operator[](int n); ` //Take characters by [] * `char& at(int n); ` //Get characters through at method
Insertion and deletion of strings
* `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
Summary: subscripts inserted and deleted start from 0
String interception
* `string substr(int pos = 0, int n = npos) const;` //Returns a string of n characters starting with pos
vector container – single ended array – supports random access
The difference between vector and array: vector can be expanded dynamically. Dynamic expansion is not in the static space of the array, but to find a larger array space, and then copy the original data to the new space to release the original space.
Create vector container
* `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 elem s to itself. * `vector(const vector &vec);` //Copy constructor.
Assign values to the vector container
* `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.
vector capacity and size
* `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 is 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 is deleted
vector insertion and deletion
* `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();`
vector data access
* `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
vector interchange container
* `swap(vec);` // Swap vec with its own elements
swap function enables two containers to be interchanged, which can achieve the practical effect of shrinking memory.
vector reserved space
Reduce the expansion times of vector in dynamic expansion capacity
* `reserve(int len);`//The container reserves len element lengths. The reserved positions are not initialized and the elements are inaccessible.
deque – double ended array 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
Working principle of deque: there is a central controller inside deque, which maintains the contents of each buffer. The buffer stores real data. The central controller maintains the address of each buffer, so that the queue stores a continuous memory space.
Constructor for deque:
* `deque<T>` deqT; //Default construction form * `deque(beg, end);` //The constructor copies the elements in the [beg, end) interval to itself. * `deque(n, elem);` //The constructor copies n elem s to itself. * `deque(const deque &deq);` //copy constructor
Assignment operation of deque
`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.
Size operation of deque:
`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 is 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 is deleted. deque Container not capacity It can expand backward and forward without limitation
Insertion and deletion of deuqe
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.
deque data access
- `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
deque sort
* `sort(iterator beg, iterator end)` //Sort the elements in the range of beg and end
Using sort sorting algorithm needs to include header file algorithm
Stack: a data structure is a first in first out data structure. The stack only allows the top element to be used by the outside world. Therefore, the stack is not allowed to be traversed.
Common interfaces outside the stack
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
Queue container: a first in first out data structure. The queue can only be used externally at the head and tail of the queue, so traversal is not allowed.
Common interfaces of queue:
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
List container - a discontinuous storage structure on a physical storage unit. The logic of data elements is realized through a linked list. The linked list is composed of a series of nodes. One node is the data field of the data element and the other is the pointer field of the storage node. The linked list is a two-way circular linked list. The storage mode of the linked list is not a continuous storage space, so the iterator of the linked list only supports forward and backward.
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 pointer field and time traversal consume extra memory
Constructor for List:
* `list<T> lst;` //list is implemented by template class, and the default construction form of object is: * `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 &lst);` //Copy constructor.
list assignment exchange
* `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.
list size operation:
* `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.
list insert and delete
* 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.
list data access:
* `front();` //Returns the first element. * `back();` //Returns the last element.
list inversion and sorting:
* `reverse();` //Reverse linked list * `sort();` //Linked list sorting
set/multiset
set container - the bottom layer is implemented by binary tree and belongs to associative container
Difference between set and multiset:
- set does not allow duplicate elements in the container
- multiset allows duplicate elements in a container
Construction: * `set<T> st;` //Default constructor: * `set(const set &st);` //copy constructor Assignment: * `set& operator=(const set &st);` //Overloaded equal sign operator
When the set container inserts data, using the insert element will sort automatically
set size and swap
* `size();` //Returns the number of elements in the container * `empty();` //Determine whether the container is empty * `swap(st);` //Swap two collection containers
Insertion and deletion of set
* `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.
Set search and statistics – search and statistics the set container
* `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
multiset
**difference:** * set Duplicate data cannot be inserted, and multiset sure * set When inserting data, the insertion result will be returned, indicating whether the insertion is successful * multiset Data is not detected, so duplicate data can be inserted
pair's creation of a group – the data appearing in the team. Two data can be returned by using the array
* `pair<type, type> p ( value1, value2 );` * `pair<type, type> p = make_pair( value1, value2 );`
The default data sorting rule of set is from small to large. The sorting rule can be changed by using the imitation function. Functor: functor, also known as Function Object, is a class that can perform function functions. The syntax of functor mimicry is almost the same as that of ordinary function calls, but as a class of functor mimicry, the operator() operator must be overloaded. Because calling the imitation function is actually calling the overloaded operator() through the class object.
set custom sort data type:
#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 in descending order
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;
}
map/multimap container
Basic concepts of map:
All elements in the map are pair. The first element in pair is key and the second element is value. All elements will be sorted automatically according to the key value.
Advantages: value can be found quickly by using 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
map container data structure and assignment operation
* `map <T1, T2> mp;` //map default constructor: * `map(const map &mp);` //copy constructor **Assignment:** * `map& operator=(const map &mp);` //Overloaded equal sign operator
map size and interchange
- `size();` //Returns the number of elements in the container - `empty();` //Determine whether the container is empty - `swap(st);` //Swap two collection containers
map insertion and deletion
- `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.
//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; **
Search and statistics of map
- `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
Map container technology sorting: the default sorting rule of map container is to sort according to the key value from small to large, and master how to change the sorting rule.
– the sorting rules can be changed by using the imitation function
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;
}
}
STL – function object
Function object concept: * the class of overloaded function call operator, and its object is often called 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
The function object is a class, not a function
Features of function objects:
1. When a function object is used, it can be called like an ordinary function. It can have its own parameters and its own return value.
2. Function objects go beyond the concept of ordinary functions. Function objects can have their own states.
3. Function objects can have their own parameters
//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;
}
predicate
- 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
STL built-in function object classification: arithmetic imitation function, relational imitation function, logical imitation function
If the built-in function object is used, the header file '#include' needs to be introduced
Arithmetic imitation function: realize four operations, among which negative is unary operation and the others are binary operation
* `template<class T> T plus<T>` //Additive affine function * `template<class T> T minus<T>` //Subtractive imitation function * `template<class T> T multiplies<T>` //Multiplicative affine function * `template<class T> T divides<T>` //Division imitation function * `template<class T> T modulus<T>` //Take imitation function * `template<class T> T negate<T>` //Take inverse imitation function
#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;
}
Relational functor – implement relational comparison
* `template<class T> bool equal_to<T>` //be 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
#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;
}
Logical imitation functions are rarely used, so you can understand them.
stl – common algorithms
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.
Algorithm Introduction:
* `for_each` //Traversal container * `transform` //Transport container to another container
-
for_each(iterator beg, iterator end, _func);
//Traversal algorithm traverses container elements
//beg start iterator
//End end iterator
// _ func function or function object
#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);//Call normal function
cout << endl;
for_each(v.begin(), v.end(), print02());//Call imitation function
cout << endl;
}
int main() {
test01();
system("pause");
return 0;
}
- 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
#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;
}
It is concluded that the reserved space shall be specified in advance for the handling of containers, otherwise they cannot be handled normally.
Common search algorithms
- `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
-
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
#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;
}
}
-
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)
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
-
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
#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;
}
}
-
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
#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;
}
The efficiency of binary search is very low. The elements in the search container must be an ordered sequence
-
count(iterator beg, iterator end, value);
//Count the number of occurrences of the element
//beg start iterator
//End end iterator
//Element of value statistics
#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==
-
count_if(iterator beg, iterator end, _Pred);
//Count the occurrence times of elements by conditions
//beg start iterator
//End end iterator
// _ Pred predicate
#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;
}
Common sorting algorithms:
- `sort` //Sort the elements in the container - `random_shuffle` //Shuffle the elements in the specified range to adjust the order randomly - `merge ` // Container elements are merged and stored in another container - `reverse` // Inverts the elements of the specified range
-
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
#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;
}
random_shuffle(iterator beg, iterator end);
//Randomly adjust the order of elements within the specified range
//beg start iterator
//End end iterator
#include <algorithm>
#include <vector>
#include <ctime>
class myPrint
{
public:
void operator()(int val)
{
cout << val << " ";
}
};
void test01()
{
srand((unsigned int)time(NULL));//Define random number seed
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;
}
-
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, and the order is the same
//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
#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 container merging must be orderly.
-
reverse(iterator beg, iterator end);
//Inverts the elements of the specified range
//beg start iterator
//End end iterator
#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;
}
Copy: copy the specified elements in the container to another container.
-
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
#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;
}
-
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
#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;
}
-
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
#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;
}
-
swap(container c1, container c2);
//Swap elements of two containers
//c1 container 1
//c2 container 2
#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;
}
Common arithmetic generation algorithms – small generation algorithms included in header file "#include"
Algorithm Introduction:
-
Calculate / / calculate the cumulative sum of container elements
-
fill / / add element to container
accumulate(iterator beg, iterator end, value);
//Calculate the cumulative sum of container elements
//beg start iterator
//End end iterator
//Value starting value
#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;
}
-
fill(iterator beg, iterator end, value);
//Fill the container with elements
//beg start iterator
//End end iterator
//Value filled value