reference material
STL Usage Summary

Basic concepts of STL

Basic components

name	explain
Container	Holds an object that contains a set of elements
iterator	Iterators are generalized pointers that provide access to each element in a container
Function object	Objects that behave like functions, header files < functional >
Algorithms	Widely 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 template	give an example
Sequential container	array, vector, deque, forward_list (single linked list), list (list)
Ordered Association container	set, multiset, map, multimap
Unordered Association container	unordered_set (unordered), unordered_multiset, unordered_ Map, unordered_multimap (unordered Multimap)

b. General functions of containers

Function name	Functional 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 name	Functional interpretation
s1 op s2	op 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(){
	set<double>s;
	while (true)
	{
		double v;
		cin>>v;
		if (v==0) break;
		pair<set<double>::iterator,bool>r=s.insert(v);
		if(!r.second)
			cout<<v<<"is duplicated"<<endl;
	}
	set<double>::iterator iter1 = s.begin();
	set<double>::iterator iter2 = s.end();
	double medium = (*iter1+*(--iter2))/2;
	cout<<"<=medium"<<endl;
	cout<<">=medium"<<endl;
	copy(s.begin(),s.upper_bound(medium),ostream_iterator<double>(cout," "));
	copy(s.lower_bound(medium),s.end(),ostream_iterator<double>(cout," "));
    return 0;
}

map
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(){
	map<string,int>courses;
	courses.insert(make_pair("A++",3));
	courses.insert(make_pair("B++",2));
	courses.insert(make_pair("C++",4));
	courses.insert(make_pair("D++",4));
	courses.insert(make_pair("E++",5));
	int n=3;//Number of courses selected
	int sum =0;//Total credits
	while (n>0)
	{
		string name;
		cin>>name;
		map<string,int>::iterator iter = courses.find(name);
		if(iter == courses.end()){
		cout<<name<<"is not available"<<endl;
		}
		else
		{
			sum +=iter->second;
			courses.erase(name);
			n--;
			}
	}
	
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(){
	map<char,int>s;
	char c;
	do{
		cin>>c;
		if (isalpha(c))
		{
			c = tolower(c);//Case insensitive, just add such a conversion
			s[c]++;
		}	
	}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"<<" "<<
	accumulate(a,a+N,1,multiplies<int>())<<endl;
	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;
	copy(a.begin(),a.end(),ostream_iterator<int>(cout,"\t"));
	cout<<endl;
	sort(a.begin(),a.end(),greater<int>());
	cout<<"after sorting:"<<endl;
	copy(a.begin(),a.end(),ostream_iterator<int>(cout,"\t"));	
}

(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 type	Algorithm description	Application examples
Immutable sequence algorithm	Algorithms that do not directly modify the contents of containers	Find the specified container, compare whether the two sequences are equal, and count the elements
Variable sequence algorithm	Modify the object of the container you are working on	Kill, replace and modify the sequence
Sorting and search algorithm	There are commonly used sorting and search algorithms
Numerical algorithm	Numerical operation using elements