STL Container
vector
Stack
queue
linked list
set
map
sort function
next_permulation function

container
1. Sequential containers: vector,list,deque,queue,priority_queue,stack, etc.
2. Associative containers: set, multiset, map, multimap, etc.

vector

vector containers can hold any type of object:

function	Example	Explain
assignment	a.push_back(100);	Add element at tail
Number of elements	int size=a.size();	Number of elements
Is it empty	bool is Empty=a.empty();	Determine whether it is empty
Print	cout<<a[0]<<endl;	Print the first element
Intermediate insertion	a.insert(a.begin()+i,k);	Insert k before the f i rst element
Delete tail	a.pop_back();	Delete end element
Delete interval	a.erase(a.begin()+i,a.begin()+j);	Delete elements of interval [i,j-1]
Delete element	a.erase(a.begin()+2)	Delete the third element
Resize	a.resize(n,num)	Array size becomes n, if longer than the original size, the rest of the position is filled by num
empty	a.clear();
Flip	a.reverse(a.begin(),a.end());	Flip Array with Function reverse
sort	sort(a.begin(),a.end());	Sort from smallest to largest using function sort

There are 2n people sitting around the round table. Among them, n are good people and N are bad people. If you count from the first person to the mth person, you immediately execute the person; then you count from the end of the person being executed, and you execute the mth person you counted... By doing this, you will continue to execute the people sitting around the round table. Ask yourself how you should arrange the seats for these good and bad people beforehand.This enables the remaining n individuals sitting on the round table to be good people after the execution of n individuals.

Input
Multiple sets of data, each set of data input: number of good and bad people n (<=32767), step m (<=32767);

Output
For each set of data, output 2n uppercase letters,'G'for good people,'B' for bad people, 50 letters for one line, no white space is allowed. There is a blank line between adjacent data.

Sample Input

2 3
2 4

Sample Output

GBBG

The code is as follows:

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
int flag[50017];
vector<int>v;
int main()
{
   int n,m;
   int tot,now;
   int i;
   while(~scanf("%d%d",&n,&m))
   {
      v.clear();
      tot=2*n;
      for(i=1;i<=tot;i++)
      {
         v.push_back[i];
         flag[i]=0;
      }
      now=1;
      while(tot>n)//Just look for bad people
      {
         now+=(m-1);
         if(now<=tot)
         {
            flag[v[now-1]]=1;
            v.erase(v.begin()+now-1);
            now=(now==tot?1:now);
         }
         else
         {
            now%=tot;
            now=(now==0?tot:now);
            flag[v[now-1]]=1;
            v.erase(v.begin()+now-1);
            now=(now==tot?1:now);
         }
         tot--;
      }
      for(i=1;i<=2*n;i++)
      {
         if(flag[i])
            prinytf("B");
         else
            printf("G");
         if(i%50==0)
            printf("\n");
      }
      if(2*n%50!=0)
         printf("\n");
   }
}

This type of problem is actually a Joseph problem, and vector s are often used to simulate dynamic tables, which can be simplified as:

#include<bits/stdc++.h>
using namespace std;
int main()
{
   vector<int>table;//Simulated Round Table
   int n,m;
   while(cin>>n>>m)
   {
      table.clear();
      for(int i=0;i<2*n;i++)
         table.push_back(i);//Initialization
      int pos=0;//Record current location
      for(int i=0;i<n;i++)//Chase away n
      {
         pos=(pos+m-1)%table.size();
         //Round table is a ring, redundancy handling
         table.erase(table.begin()+pos);
         //Get rid of bad people, table count minus 1
      }
      int j=0;
      for(int i=0;i<2*n;i++)
      {//Print booked seats
         if(!(i%50)&&i)cout<<endl;
         //50 letters per line
         if(j<table.size()&&i==table[j])
         {//All table s leave are good people
            j++;
            cout<<"G";
         }
         else
            cout<<"B";
      }
      cout<<endl;
   }
   return 0;
}

Stack and stack
Stack: One of the basic data structures characterized by "in, out".

Stack operations:

Example	Explain
stackq;	Define stack, Type is data type
s.push(item);	Protect item from top of stack
s.top();	Returns the top element of the stack, but does not delete it
s.size();	Returns the number of elements in the stack
s.empty();	Determine if stack is empty

Example: flip string
For example, enter "olleh! Dlrow" and output "hello world!";
The code is as follows:

#include<bits/stdc++.h>
using namespace std;
int main()
{
   int n;
   char ch;
   scanf("%d",&n);getchar();
   while(n--)
   {
      stack<char>s;
      while(true)
      {
         ch=getchar();//Read one character at a time
         if(ch==' '||ch=='\n'||ch==EOF)
         {
            while(!empty())
            {
               printf("%c",s.pop());//Output stack top
               s.pop();//Clear top of stack
            }
            if(ch=='\n'||ch==EOF)break;
            printf(" ");
         }
         else s.push(ch);//Push
      }
      printf("\n");
   }
}

Example: Simple Calculator (Inverse Polish Expression)
- Numbers are put on the stack first, +signs are put on the stack, minus signs are added to the stack, and if they are multiplied, the top element is taken out and multiplied. The division sign is the same. Finally, the sum of all the numbers on the stack is calculated and the answer is given.
The code is as follows:

#include<cstdio>
#include<stack>
#include<algorithm>
int main()
{
   double n,m;
   char c;
   while(~scanf("%lf",&n))
   {
      c=getchar();
      if(c=='\n'&&n==0)break;
      stack<double>s;
      s.push(n);
      scanf("%c",&c);
      while(~scanf("%lf",&n))
      {
         if(c=='*')
         {
            m=s.pop();
            m*=n;
            s.pop();
            s.push(m);
         }
         if(c=='/')
         {
            m=s.pop();
            m/=n;
            s.pop();
            s.push(m);
         }
         if(c=='+')
            s.push(n);
         if(c=='-')
            s.push(0-n);
         if(getchar()=='\n')
            break;
         c=getchar();
      }
      double sum=0;
      while(s.empty())
      {
         sum+=s.top();
         s.pop();
      }
      printf("%.2lf\n",sum);
   }
   return 0;
}

Queues
Features: FIFO
Queue operations:

Example	Explain
queueq;	Define the queue, Type is the data type
q.push(item);	Queue item
q.front();	Returns the first element of the queue, but does not delete it
q.pop();	Delete the first element of the queue
q.back();	Return trailing elements
q.size();	Returns the number of elements
q.empty();	Check if the queue is empty

Example: ACboy needs your help again!
Problem Description
ACboy was kidnapped!!
he miss his mother very much and is very scare now.You can't image how dark the room he was put into is, so poor 😦.
As a smart ACMer, you want to get ACboy out of the monster's labyrinth.But when you arrive at the gate of the maze, the monste say :" I have heard that you are very clever, but if can't solve my problems, you will die with ACboy."
The problems of the monster is shown on the wall:
Each problem's first line is a integer N(the number of commands), and a word "FIFO" or "FILO".(you are very happy because you know "FIFO" stands for "First In First Out", and "FILO" means "First In Last Out").
and the following N lines, each line is "IN M" or "OUT", (M represent a integer).
and the answer of a problem is a passowrd of a door, so if you want to rescue ACboy, answer the problem carefully!

Input
The input contains multiple test cases.
The first line has one integer,represent the number oftest cases.
And the input of each subproblem are described above.

Output
For each command "OUT", you should output a integer depend on the word is "FIFO" or "FILO", or a word "None" if you don't have any integer.

Sample Input
4
4 FIFO
IN 1
IN 2
OUT
OUT
4 FILO
IN 1
IN 2
OUT
OUT
5 FIFO
IN 1
IN 2
OUT
OUT
OUT
5 FILO
IN 1
IN 2
OUT
IN 3
OUT

Sample Output
1
2
2
1
1
2
None
2
3

Source
2007 Provincial Training Team Training Competition (1)

Recommend
lcy

Analog stack and queue, stack is FILO, queue is FIFO.

The code is as follows:

#include<bits/stdc++.h>
using namespace std;
int main()
{
   int t,n,temp;
   cin>>t;
   while(t--)
   {
      string str,str1;
      queue<int>Q;
      stack<int>S;
      cin>>n>>str;
      if(str=="FIFO")//queue
      {
         cin>>str1;
         if(str1=="IN")
         {
            cin>>temp;
            Q.push(temp);
         }
         if(str1=="OUT")
         {
            if(Q.empty())cout<<"None"<<endl;
            else
            {
               cout<<Q.front()<<endl;
               Q.pop();
            }
         }
      }
      else
      {
         cin>>str1;
         if(str1=="IN")
         {
            cin>>temp;
            S.push(temp);
         }
         if(str1=="OUT")
         {
            if(S.empty())cout<<"None"<<endl;
            else
            {
               cout<<S.pop()<<endl;
               S.pop();
            }
         }
      }
   }
}

Priority Queue and priority_queue
Priority Queue: The queue with the highest priority.
A perfect combination of queues and sorting not only stores data, but also sorts it according to set rules.
Each push and pop operation, the priority queue is dynamically adjusted to put the highest priority element first.
priority_queue<int,vector,lessq>
priority_queuei;
priority_queued;
q.top(); //Returns the element with the highest priority without deleting it
q.pop();//Delete the element with the highest priority
q.push(item);//Insert a new element
A priority queue has all the characteristics of a queue, including basic operations, but adds an internal sort to it, which is essentially a heap implementation

#include<cstdio>
#include<queue>
using namespace std;
priority_queue<int>q;
int main()
{
  q.push(10),q.push(8),q.push(12),q.push(14),q.push(6);
  while(!q.empty())
  {
     printf("%d "q.top());
     q.pop();
  } 
}

The output will be sorted from large to small.

#include<cstdio>
#include<queue>
using namespace std;
priority_queue<int,vector<int>,less<int> >p;
priority_queue<int,vector<int>,greater<int> >q;
int a[5]={10,12,14,6,8};
int main()
{
   for(int i=0;i<5;i++)
      p.push(a[i]),q.push(a[i]);
   printf("less<int>:");
   while(!p.empty())
      printf("%d",p.top()),p.pop();
   printf("\ngreater<int>:");
   while(!q.empty())
   {
      printf("%d "q.top()),q.pop();
   }
}

In STL, a priority queue is implemented with a binary heap, push a number or pop a number into the queue, and the complexity is O(logn).

Example: The program implementation of Dijkstra's graph theory algorithm, using STL's priority queue, can greatly simplify the code.

Exercise: hdu 1873 to queue for medical treatment

Title Description
Queuing for medical treatment is a common knowledge known to all on earth.
However, after careful observation of 0068, he found that there were still queues in the hospital. 0068 went to a hospital with three doctors (sweat, so little)Seek a doctor at the same time. Because the patient's condition is important, it can't be based on the principle of simple first-come-first-service. So the hospital sets 10 different priorities for each condition. Level 10 has the highest priority and Level 1 has the lowest. When a doctor visits a doctor, he will choose the person with the highest priority in his team to treat. If he encounters two priorities.For patients with the same rights, choose the first patient to queue.

Now you can help the hospital simulate this process.
input
The input data contains multiple sets of tests, please process to the end of the file.
There is a positive integer N (0<N<2000) in the first row of each set of data to indicate the number of events that occurred.
Next, there are N rows representing what happened.
There are two events:
1:'IN A B', means that a patient with priority B has requested medical attention from Doctor A. (0<A<=3,0<B<=10)
2: "OUT A" means that Doctor A made a diagnosis and treatment, and the patient was discharged after diagnosis and treatment. (0<A<=3)
output
For each "OUT A" event, output the number ID of the person being treated in one line. If no patient needs treatment at the time of the event, output "EMPTY".
The diagnostic and therapeutic ID number is defined as: in a set of tests, the patient ID that comes in is K when the "IN A B" event occurs K. Numbering starts from 1.
Sample Input Copy
7
IN 1 1
IN 1 2
OUT 1
OUT 2
IN 2 1
OUT 2
OUT 1
2
IN 1 1
OUT 1
Sample Output Copy
2
EMPTY
3
1
1

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
struct Node{
	int id;
	int p;
	int doc;
}node[10010];

struct cmp{
	bool operator()(Node a, Node b){
		if(a.p!=b.p)//If the priority is equal and does not change, the pit is here
			return a.p < b.p;//Since the analog function is the opposite of sort, here is the sort from big to small 
		else return a.id > b.id;
	}
};
priority_queue<Node,vector<Node>,cmp> q,q1,q2;
int main(){
	ios::sync_with_stdio(false);
	int n;
	string str;
	while(cin>>n){
		while(!q.empty()){
			q.pop();
		}
		while(!q1.empty()){
			q1.pop();
		}
		while(!q2.empty()){
			q2.pop();
		}
		int cnt = 1;
		for(int i = 0; i < n; i++){
			cin>>str;
			if(str=="IN"){
				cin>>node[i].doc>>node[i].p;
				node[i].id = cnt++;
				if(node[i].doc==1)
					q.push(node[i]);// Doctor 1 
				else if(node[i].doc==2)
					q1.push(node[i]);// Doctor 2 
				else if(node[i].doc==3)
					q2.push(node[i]);// Doctor 3 
			}else{
				int num;
				cin>>num;
				if(num==1){	
					if(q.empty()){
						cout<<"EMPTY"<<endl;
						continue;
					}
					Node node1 = q.top();
					cout<<node1.id<<endl;
					q.pop();
				}
				else if(num==2){
					if(q1.empty()){
						cout<<"EMPTY"<<endl;
						continue;
					}
					Node node1 = q1.top();
					cout<<node1.id<<endl;
					q1.pop();
				}else if(num==3){
					if(q2.empty()){
						cout<<"EMPTY"<<endl;
						continue;
					}
					Node node1 = q2.top();
					cout<<node1.id<<endl;
					q2.pop();
				}
			}
		}
	}
	return 0;
}

map:
Example:shopping

Topic:
dandelion, a girl who often goes shopping, likes a store called memory in particular.
As the Spring Festival is approaching, the prices of all stores are rising every day. She wants to know the daily price rankings of this store.
Input:
The first line is the number n (n <= 10000), which represents the number of stores. The next N lines have a string for each line
(Less than 31, with only lowercase and uppercase letters) indicates the name of the store. The next line is the number m (1 <= m <= 50).
Represents the number of days. Following the m-part, each part has n rows, each line is a number s and a string p, indicating that store P increased its price on that day s.
Output:
Include m rows, row i shows the ranking of store "memory" after day i I. The ranking is defined as:
If there is a store with a price higher than memory, it is ranked t + 1.

The code is as follows:

#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
int main(){
        map<string,int>m;
        int n,M;
        int s;
        string store;
        while(cin>>n){
        for(int i=0;i<n;i++){
            cin>>store;
            m[store]=0;
        }
        cin>>M;
        for(int i=0;i<M;i++){
            for(int j=0;j<n;j++){
                cin>>s>>store;
                m[store]+=s;
            }
        int k=0;
        for(map<string,int>::iterator it=m.begin();it!=m.end();it++)
            if(it->second>m["memory"])k++;
        cout<<k+1<<endl;
        }
    }
    return 0;
}

next_permutation
1.next_permutation(): Require "next" permutation combination
2. For example, a sequence of three characters {a,b,c}, next_permutation() can return six combinations in dictionary order: a B c, a C b, B a c, B C a, C a b, C B a.
3. Return value: Return false if there is no next permutation combination, or return true. Each time next_permutation() is executed, the new permutation is placed in the original space.

Example:
Given n n n n numbers, from 1 to n, the mth smallest sequence is required to be output
Input:
The numbers N and M consist of 1<=n<=1000,1<=m<=10000
Output:
Output mth smallest sequence

The code is as follows:

#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
int a[1001];
int main(){
    int n,m;
    while(cin>>n>>m){
        for(int i=1;i<=n;i++)
            a[i]=i;
        int b=1;
        do{
            if(b==m)break;
            b++;
        }while(next_permutation(a+1,a+n+1));
        for(int i=1;i<n;i++)
            cout<<a[i]<<" ";
        cout<<a[n]<<endl;
    }
    return 0;
}