[STL programming] [common competition] [Part 1]

【STL Programming 】【 Commonly used in competitions 】【part 1】

Standard template library （Standard Template Library ,STL） Broadly speaking, it can be divided into algorithms （Algorithm）、 Containers （Container） And iterators （Iterator）3 class , Contains many basic data structures and basic algorithms .

standard C++ In language ,STL Organized as 13 Head file ：<algorithm> 、<deque>、<functional>、<vector>、<iterator>、<list>、<map>、<memory>、<numeric>、<queue>、<set>、<stack> And <utiity>.

1. sort Sorting algorithm

STL Inside sort Sorting algorithm in header file <algorithm> In a statement , Fast sort adopted , The time complexity can be guaranteed to be $O(nlogn)$. Than C In language qsort It is better to .

#include<bits/stdc++.h>
using namespace std;
void Print(int a[],int n){
    
    for (int i = 0; i < n;i++){
    
        cout << a[i] << " ";
    }
    cout << endl;
}
int main(){
    
    int a[] = {
    1, 5, 3, 2, 65, 2, 76};
    int len = sizeof(a) / sizeof(int);
    sort(a, a + len);
    Print(a, len);
    sort(a, a + len, greater<int>());// From big to small 
    Print(a, len);
    return 0;
}

 Running results ：
1 2 2 3 5 65 76
76 65 5 3 2 2 1

Or you can write by yourself cmp() Compare function to compare array elements ：

bool cmp(int a,int b){
    
    return a > b;
}
int main(){
    
    int a[] = {
    1, 5, 3, 2, 65, 2, 76};
    int len = sizeof(a) / sizeof(int);
    sort(a, a + len);
    Print(a, len);
    sort(a, a + len, cmp); // From big to small 
    Print(a, len);
    return 0;
}

 The same as above 

Sort characters ：

#include<bits/stdc++.h>
using namespace std;
int main(){
    
    char a[11] = {
    "dfjksaldwq"};
    sort(a,a+10);
    for (int i = 0; i < 10;i++){
    
        cout << a[i];
    }
    cout << endl;
    sort(a, a + 10, greater<char>());
    for (int i = 0; i < 10;i++){
    
        cout << a[i];
    }
    cout << endl;
    return 0;
}

 Running results ：
addfjklqsw
wsqlkjfdda

Sorting of structures , In fact, it's about writing cmp() function ：

#include<bits/stdc++.h>
using namespace std;

struct Node{
    
    int x, y;
} p[1001];

int cmp(Node a,Node b){
    
    if(a.x!=b.x)
        return a.x < b.x;
    return a.y < b.y;
}

int main(){
    
    int n;
    cin >> n;
    for (int i = 1; i <= n;++i){
    
        cin >> p[i].x >> p[i].y;
    }
    sort(p + 1, p + 1 + n, cmp);
    for (int i = 1; i <= n;++i){
    
        cout << p[i].x << " " << p[i].y << endl;
    }
    return 0;
}

2. stable_sort Stable sequencing

stable_sort and sort The difference is that the former can be used after sorting “ identical ” The relative position of the value of in the sequence does not change , For example, there are two elements in the initial sequence A and B The values are equal , And A stay B front , After ordering A Still in B front , This sort is called stable sort .

#include <bits/stdc++.h> 
using namespace std;

struct stu{
    
  int id;
  string name;
  int score;
};

bool comByscore(stu s1, stu s2){
    
  return s1.score < s2.score ? 1 : 0;
}

bool comByid(stu s1, stu s2){
    
  return s1.id > s2.id ? 1 : 0;
}

int main(){
    
    vector<stu> v;
    struct stu master;
    master.id = 3;
    master.name = "clare";
    master.score = 60;
    v.push_back(master);
    master.id = 2;
    master.name = "Liqiang";
    master.score = 99;
    v.push_back(master);
    master.id = 1;
    master.name = "qiangYi";
    master.score = 88;
    v.push_back(master);
    stable_sort(v.begin(), v.end(), comByscore); // Sort by score 
    for (int i = 0; i < v.size(); i++)
        cout << v[i].id << ' ' << v[i].name << ' ' << v[i].score << endl;
    stable_sort(v.begin(), v.end(), comByid); // Reverse sort by student number 
    for (int i = 0; i < v.size(); i++)
        cout << v[i].id << ' ' << v[i].name << ' ' << v[i].score << endl;
    return 0;
}

3 clare 60
1 qiangYi 88
2 Liqiang 99
3 clare 60
2 Liqiang 99
1 qiangYi 88

3. Permutation and combination relation algorithm

next_permutation() Produce an arrangement in dictionary order , And start from the current dictionary order in the array Increase to the maximum Dictionary order .
prev_permutation() Produce an arrangement in dictionary order , And start from the current dictionary order in the array Decrease to the minimum Dictionary order .

#include <bits/stdc++.h>
using namespace std;

void print(int a[]){
    
    for (int i = 0; i < 5; i++)
        cout << a[i] << " ";
    cout << endl;
}

int main(){
    
    int a[] = {
    1, 2, 6, 7, 9};
    // Generate all next combinations , The time complexity is n!, Slower 
    while (next_permutation(a, a + 5)) // Next combination 
        print(a);
    int b[] = {
    5, 4, 3, 2, 1};
    while (prev_permutation(b, b + 5)) // Previous combination 
        print(b);
    return 0;
}

result ：

1 2 6 9 7 
1 2 7 6 9
1 2 7 9 6
1 2 9 6 7
...
9 7 6 2 1

5 4 3 1 2
5 4 2 3 1
5 4 2 1 3
...
1 2 3 4 5

4. lower_bound/upper_bound

lower_bound( Initial address first, End address last, The value to find val): stay first and last Before closed after open interval in binary search , Returns greater than or equal to val The address of the first element of . If all elements in the interval are less than val, Then return to last The address of , And last Your address is out of bounds .
upper_bound( Initial address first, End address last, The value to find val): stay first and last Before closed after open interval in binary search , Return is greater than the val The address of the first element of . If val Greater than all elements in the interval , Then return to last The address of , And last Your address is out of bounds .
Particular attention :lower_bound/upper_bound The interval of binary search must be an ordered sequence , As shown in the figure ：

Ascending array use lower_bound/upper_bound：

#include <bits/stdc++.h>
using namespace std;

int main(){
    
    int a[] = {
    1, 1, 2, 2, 3, 3, 3, 4, 4, 4};
    cout << lower_bound(a, a + 10, 0) - a << endl; // Output subscript 0
    cout << lower_bound(a, a + 10, 1) - a << endl; // Output subscript 0
    cout << lower_bound(a, a + 10, 3) - a << endl; // Output subscript 4
    cout << lower_bound(a, a + 10, 4) - a << endl; // Output subscript 7
    cout << lower_bound(a, a + 10, 5) - a << endl; // Output subscript 10

    cout << upper_bound(a, a + 10, 0) - a << endl; // Output subscript 0
    cout << upper_bound(a, a + 10, 1) - a << endl; // Output subscript 2
    cout << upper_bound(a, a + 10, 3) - a << endl; // Output subscript 7
    cout << upper_bound(a, a + 10, 4) - a << endl; // Output subscript 10
    cout << upper_bound(a, a + 10, 5) - a << endl; // Output subscript 10
    return 0;
}

Descending arrays are used directly lower_bound/upper_bound： It's wrong. ：

#include <bits/stdc++.h>
using namespace std;

int main(){
    
    int a[] = {
    4, 4, 3, 3, 2, 2, 1, 1};
    cout << lower_bound(a, a + 8, 4) - a << endl; //  Output  8
    cout << upper_bound(a, a + 8, 4) - a << endl; //  Output  8
    cout << lower_bound(a, a + 8, 1) - a << endl; //  Output  0
    cout << upper_bound(a, a + 8, 1) - a << endl; //  Output  0
    cout << lower_bound(a, a + 8, 3) - a << endl; //  Output  8
    cout << upper_bound(a, a + 8, 3) - a << endl; //  Output  8
    return 0;
}

This is because lower_bound / upper_bound The default binary search interval is an ascending sequence . To find the value 4 For example , The first step starts from the middle , Median value a [(0+8)/2] = a [4]=2, Than 4 Small , So we continue to approach the larger value , Which way to go , On the right , Because it thinks the sequence is ascending , This is obviously wrong .

therefore , In the descending sequence, we should pay attention to the following two points .

(1) lower_bound The correct expression of is lower_bound ( first , last , val , greater<int>() ), Or something like sort Sort , Use custom comparison functions . if val In the sequence , Then return to val First occurrence , Otherwise, return to the first insert val The position that does not affect the order of the original sequence .

(2) upper_bound The correct expression of is upper_bound ( first , last , val , greater<int>() ), Or something like sort Sort , Use custom comparison functions . if val In the sequence , Returns the first less than val The location of , Otherwise, return to the first insert val The position that does not affect the order of the original sequence .

#include <bits/stdc++.h>
using namespace std;

int main(){
    
    int a[] = {
    4, 4, 3, 3, 2, 2, 1, 1};
    cout << lower_bound(a, a + 8, 0, greater<int>()) - a << endl; //  Output  8
    cout << lower_bound(a, a + 8, 4, greater<int>()) - a << endl; //  Output  0
    cout << lower_bound(a, a + 8, 1, greater<int>()) - a << endl; //  Output  6
    cout << lower_bound(a, a + 8, 3, greater<int>()) - a << endl; //  Output  2
    cout << lower_bound(a, a + 8, 5, greater<int>()) - a << endl; //  Output  2

    cout << upper_bound(a, a + 8, 0, greater<int>()) - a << endl; //  Output  8
    cout << upper_bound(a, a + 8, 4, greater<int>()) - a << endl; //  Output  2
    cout << upper_bound(a, a + 8, 1, greater<int>()) - a << endl; //  Output  8
    cout << upper_bound(a, a + 8, 3, greater<int>()) - a << endl; //  Output  4
    cout << upper_bound(a, a + 8, 5, greater<int>()) - a << endl; //  Output  4
    return 0;
}

STL There is also a binary search function in binary_search(first,last,val), The usage is similar to lower_bound / upper_bound , But it can only judge val Whether in first and last In the ordered interval of , If there is a return true , Otherwise return to false .

int a[] = {
    4, 4, 3, 3, 2, 2, 1, 1};
cout << binary_search(a, a + 8, 2, greater<int>()) << endl; 
// Output  1

5. vector Vector containers

Can replace array a[], Common operations are as follows ：

（1） Array vector

Method	effect
v.push_back()	Insert an element at the end
v.pop_back()	Delete an element from the tail
v.insert()	Insert an element... In a certain location
v.erase()	Delete some / Some elements
v.clear()	Remove all elements
v.empty()	Sentenced to empty
v.size()	The actual size of the container
v.front()	Access the first element
v.back()	Access the last element

(*￣(oo)￣)：

• For containers c , expression c.front() Equivalent to *c.begin().
• For non empty containers c , expression c.back() Equivalent to *std::prev(c.end()) .

#include <bits/stdc++.h>
using namespace std;

int main(){
    
    vector<int> v;   // Defines a storage int Type of vector Containers 
    v.reserve(30);   // Resize data space 
    v.push_back(20); // Insert a new element at the end 
    v.push_back(26);
    v.push_back(12);
    v.push_back(52);
    v.insert(v.begin(), 2);            // begin() by vector Head , Insert... Here 2
    v.insert(v.end(), 43);             // end() by vector The tail , Insert... Here 43
    v.insert(v.begin() + 2, 15);       // In the 2 Insert before elements 15
    v.erase(v.begin() + 1);            // Delete the first 2 Elements 
    v.erase(v.begin(), v.begin() + 2); // Delete the first three elements 
    v.pop_back();                      // Delete the last element 
    for (int i = 0; i < v.size(); ++i) // size() by v The number of elements in 
        cout << v[i] << ' ';
    cout << "\n  The first element is :" << v.front() << '\n'; // First element reference 
    cout << " The last element is :" << v.back() << '\n';     // End element reference 
    reverse(v.begin(), v.end());                 // Reverse entire vector Elements 
    for (int i = 0; i < v.size(); ++i)
        cout << v[i] << ' ';
    v.clear();                                    // Empty all elements 
    cout << "\n v Is it empty :" << v.empty() << '\n'; // Determine whether it is null 
    return 0;
}

（2） Of a structural container vector

#include <bits/stdc++.h>
using namespace std;

struct stu{
    
    int x, y;
};

int main(){
    
    int j;
    vector<stu> v1; // Structural container 
    vector<stu> v2;
    struct stu a = {
    1, 2};
    struct stu b = {
    2, 3};
    struct stu c = {
    4, 5};
    v1.push_back(a);
    v1.push_back(b);
    v1.push_back(c);
    v2.push_back(c);
    v2.push_back(b);
    v2.push_back(a);
    swap(v1, v2);                       // The elements of the two structures are exchanged 
    for (int i = 0; i < v1.size(); i++) // Output v1 All the elements 
        cout << v1[i].x << " " << v1[i].y << endl;
    cout << "\n";
    for (int i = 0; i < v2.size(); i++) // Output v2 All the elements 
        cout << v2[i].x << " " << v2[i].y << endl;
    return 0;
}

result ：

4 5
2 3
1 2

1 2
2 3
4 5

（3） Iterators access vector

#include <bits/stdc++.h>
using namespace std;

int main(){
    
    int j;
    vector<int> v;
    v.reserve(30); // Resize data space 
    for (int i = 0; i < 10; i++)
        v.push_back(i);                    // Insert a new element at the end 
    vector<int>::iterator i;               // Definition vector The iterator i
    for (i = v.begin(); i != v.end(); i++) // Iterator traversal 
        cout << *i << " ";
    cout << "\n v The number of elements in :" << v.size() << '\n'; // Actual number of elements 
    reverse(v.begin(), v.end());                     // reverse 
    for (i = v.begin(); i != v.end(); i++)           // Iterator traversal 
        cout << *i << " ";
    v.clear();                                    // Empty all elements 
    cout << "\n v Is it empty :" << v.empty() << '\n'; // Determine whether it is null 
    return 0;
}
/* 0 1 2 3 4 5 6 7 8 9 v The number of elements in :10 9 8 7 6 5 4 3 2 1 0 v Is it empty :1 */

---

【part 2】【part3】 Coming soon ！！

6. pair Containers

7. set Assembly containers

8. multiset Multiple collection container

9. map Mapping containers

10. multimap Multiple mapping container

11. list Two way list container

12. stack Stack container

13. queue Queue container

14. deque Double ended queue container

15. priority_queue Priority queue container