Learning notes of C + + course in Tsinghua University -- Chapter 10 generic programming

reference material
STL Usage Summary

Basic concepts of STL

Basic components

ContainerHolds an object that contains a set of elements
iteratorIterators are generalized pointers that provide access to each element in a container
Function objectObjects that behave like functions, header files < functional >
AlgorithmsWidely used for different objects and built-in data types, header file < algorithm >

(1) Container

An object that contains a set of elements

a. Container classification

Container templategive an example
Sequential containerarray, vector, deque, forward_list (single linked list), list (list)
Ordered Association containerset, multiset, map, multimap
Unordered Association containerunordered_set (unordered), unordered_multiset, unordered_ Map, unordered_multimap (unordered Multimap)

b. General functions of containers

Function nameFunctional interpretation
begin()end()Get container head and tail iterators
clear()Empty the container
empty()Check whether the container is empty
size()Get the number of container elements
s1.swap(s2)Exchange the contents of s1 and s2 containers

Related data types
S::iterator: iterator type pointing to the container element
S::const_iterator: constant iterator type

c. Sequential container

Some basic functions of sequential containers

Operations supported by stack and queue

Operation nameFunctional interpretation
s1 op s2op can be = =,! =, < =, >, >=
s,size()Returns the number of elements in s
s.empty()Returns whether s is empty
s,push(t)Press element t into s
s.pop()Pop up an element from s. the last element pushed in is popped out of the stack, and the queue is the first element pushed in

Stack and column operations are different
Stack: s.top() returns the reference of the top element of the stack
Queue: s.front() gets the reference to the header element; s.back() gets a reference to the end of the queue element

d. Associated container

Features: each associated container has a key
You can efficiently find elements based on.
Interface: insert delete find lower_bound, upper_bound, equal_range count

Collection: used to store a set of non repeating elements. The set element itself is ordered, which can efficiently find the specified element and conveniently get the interval of the specified element in the container
Tail iterator, pointing to the next position in the collection
eg: find out the maximum value and minimum value of the data in the set, and output the median value

# include <iostream>
# include <utility>
# include <iterator>
# include <set>
using  namespace std;

int main(){
	while (true)
		double v;
		if (v==0) break;
			cout<<v<<"is duplicated"<<endl;
	set<double>::iterator iter1 = s.begin();
	set<double>::iterator iter2 = s.end();
	double medium = (*iter1+*(--iter2))/2;
	copy(s.begin(),s.upper_bound(medium),ostream_iterator<double>(cout," "));
	copy(s.lower_bound(medium),s.end(),ostream_iterator<double>(cout," "));
    return 0;

Comparison with set

Mapping and set contract belong to single Association containers. Their main difference is that the element type of the set is the key itself, while the mapped element is a binary composed of keys and additional data.
Searching for elements by key in the collection can only determine whether the elements exist;
Searching for elements in the mapping can not only determine the existence, but also obtain the corresponding additional data;
eg: there are 5 courses, 3 of which are selected to output the total credits

# include <iostream>
# include <utility>
# include <string>
# include <map>
# include <iterator>
using namespace std;

int main(){
	int n=3;//Number of courses selected
	int sum =0;//Total credits
	while (n>0)
		string name;
		map<string,int>::iterator iter = courses.find(name);
		if(iter == courses.end()){
		cout<<name<<"is not available"<<endl;
			sum +=iter->second;
cout<<"Totol credit"<<sum<<endl;	/* code */
return 0;

eg: Statistics of input character data

# include <iostream>
# include <utility>
# include <string>
# include <map>
# include <iterator>
using namespace std;

int main(){
	char c;
		if (isalpha(c))
			c = tolower(c);//Case insensitive, just add such a conversion
	}while (c!='.');//String output end tag
	for (map<char,int>::iterator iter=s.begin(); iter !=s.end(); ++iter)
		cout<<iter->first<<" "<<iter->second<<" "<<endl;//Output statistical results
	return 0;

Multiple set multiple mapping
Multiple sets: sets with duplicate elements are allowed. Multiple mapping allows one key to map multiple additional data
eg: query of class time (a course can have multiple class times)

(2) Iterator

a. Basic definition: it is the bridge between algorithm and container

b. Basic operations related to iterators: just remember a few related to pointers

Auxiliary function of iterator
advance(p, n) performs n auto increment operations on p
distance(first,last) calculates the distance between the two iterators first and last, that is, how many "+ +" operations can be performed on first to make first==last

(3) Function object

a. Basic concepts

An object that behaves like a function,
There can be no parameters or several parameters
Its function is to obtain a value or change the state of the operation.

b. Function object provided by STL

eg. use STL standard function object multiples to realize the concatenation operation of elements

# include <iostream>
# include <utility>
# include <numeric>
# include <functional>
using namespace std;

int main(){
	int a[]={1,2,3,4,5};
	const int N =sizeof(a)/sizeof(int);
	cout<<"The result by multipling all elements in A is"<<" "<<
	return 0 ;

eg sorts the elements from large to small

# include <iostream>
# include <algorithm>
# include <vector>
# include <functional>
# include <iterator>
using namespace std;

int main(){
	int intArr[]={30,90,60,70,50,20,80};
	const int N =sizeof(intArr)/sizeof(int);
	vector<int> a(intArr,intArr+N);
	cout<<"before sorting:"<<endl;
	cout<<"after sorting:"<<endl;

(4) Algorithm

a. Algorithm features

As a function template, STL algorithm is universal and independent of data type and container type;
The input data is obtained through the iterator, the data is processed through the function object, and the result is output through the iterator;

b. Algorithm classification

Algorithm typeAlgorithm descriptionApplication examples
Immutable sequence algorithmAlgorithms that do not directly modify the contents of containersFind the specified container, compare whether the two sequences are equal, and count the elements
Variable sequence algorithmModify the object of the container you are working onKill, replace and modify the sequence
Sorting and search algorithmThere are commonly used sorting and search algorithms
Numerical algorithmNumerical operation using elements

Keywords: C++ Back-end

Added by prabhuksmani on Sun, 06 Feb 2022 01:42:49 +0200