[STL programming] [common competition] [Part 3]

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

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

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

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

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

11. list Two way list container

list The bidirectional linked list container declares in the header file , It looks for elements at any location 、 Both insertion and deletion have high time complexity of constant order algorithm .

#include <bits/stdc++.h> // Use universal header files , No need to write #include <list>
using namespace std;

int main(){
    
    list<int> l;
    l.push_back(2); // Insert new elements at the end , Automatic expansion of linked list 
    l.push_back(2);
    l.push_back(9);
    l.push_back(12);
    l.push_back(12);
    l.push_back(4);
    l.push_back(4);
    l.push_back(6);
    // l.clear();// Empty the list 
    l.push_front(9); // Insert a new element in the header , Automatic expansion of linked list 
    list<int>::iterator it;
    it = l.begin();
    it++;             // Linked list iterators can only ++ or -- operation , Cannot be +n operation , because list Node is not contiguous memory 
    l.insert(it, 20); // Insert new element at current position 
    it++;
    l.erase(it);                              // Delete the element at the iterator location 
    for (it = l.begin(); it != l.end(); it++) // Positive traversal 
        cout << *it << " ";
    cout << endl;
    l.remove(12);                     // Delete all values as 12 The elements of 
    l.pop_front();                    // Delete the first element of the linked list 
    l.pop_back();                     // Delete the end of the list 
    it = find(l.begin(), l.end(), 4); // Find element value as 4
    if (it != l.end())
        cout << "find " << *it << endl;
    l.sort();                                 // Ascending order 
    l.unique();                               // Delete consecutive elements （ Keep only one ）
    for (it = l.begin(); it != l.end(); it++) // Positive traversal 
        cout << *it << " ";
    cout << endl;
    return 0;
}
/* 9 20 2 9 12 12 4 4 6 find 4 2 4 9 20 */

Structure ：

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

struct student{
    
    char *name;
    int age;
    char *city;
};

int main(){
    
    student s[] = {
    
            {
    " Zhang San ", 18, " Zhejiang "},
            {
    " Li Si ", 19, " Beijing "},
            {
    " The king 2 ", 18, " Shanghai "}};
    list<student> l;
    l.push_back(s[0]); // Insert elements 
    l.push_back(s[1]);
    l.push_back(s[2]);
    student x = {
    " Liu Si ", 19, " xinjiang "};
    l.push_front(x);        // Insert to first , The complexity is O(1)
    l.insert(l.begin(), x); // Insert anywhere , Time complexity O(1)
    // l.pop_front();// Delete first element 
    // l.pop_back();// Delete tail element 
    l.erase(l.begin());
    // l.erase(l.begin(),l.end());// Delete element of interval 
    for (list<student>::iterator i = l.begin(); i != l.end(); i++)
        cout << (*i).name << " " << (*i).age << " " << (*i).city << "\n";
    return 0;
}
/*  Liu Si  19  xinjiang   Zhang San  18  Zhejiang   Li Si  19  Beijing   The king 2  18  Shanghai  */

list Linked list merging routine

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

void print(list<int> l){
    
    list<int>::iterator i;
    for (i = l.begin(); i != l.end(); i++)
        cout << *i << " ";
    cout << endl;
}

int main(){
    
    list<int> l1;
    for (int j = 10; j >= 0; j--)
        l1.push_back(j);

    list<int> l2;
    list<int>::iterator ii;
    l2.splice(l2.begin(), l1); // take l1 All elements of are merged into L2,L1 Empty 
    ii = l2.begin()++;
    l1.splice(l1.begin(), l2, ii); // take l2 Of ii The elements of position are merged into l1,l2 The original element is deleted 
    print(l1);
    print(l2);
    // swap(l1,l2);// In exchange for l1,l2
    l1.push_back(8);
    l1.push_back(8);
    l1.push_back(35);
    l1.unique(); // Remove consecutive repeating elements 
    l2.push_back(30);
    l1.sort(); // Sort 
    l2.sort();
    print(l1);
    l2.merge(l1); // L1 Merge into l2, Two linked lists need to be sorted , See the following merging algorithm for details merge
    print(l2);
    return 0;
}

12. stack Stack container

Stack Similar to an opening at one end 、 A container closed at one end , The open end is called the top of the stack （Stack Top）, The closed end is called the bottom of the stack （Stack Bottom）, The insertion and deletion of elements can only be performed at the top of the stack . The insertion of elements into the stack is called pushing , The deletion of elements is called out of stack . The main feature of the stack is “ Last in, first out ”（Last In First Out）, That is, the elements that are put on the stack later are put out of the stack first . Every time the element is put into the stack, it will be placed on the original top element of the current stack , Become a new stack top element , Every time the element out of the stack is the original top element of the current stack

Refer to my data structure tutorial ：
2021-9-22【 data structure / YanWeiMin 】【 Order of the stack & Chain stack & Maze solution & Expression evaluation 】【 Code implementation algorithm 3.1-3.5】

Method	explain
empty()	If the stack is empty, return true
pop()	Remove the top element
push()	Add elements at the top of the stack
size()	Returns the number of elements in the stack
top()	Back to top of stack element

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

int main(){
    
    stack<string> s;
    s.push("aaa"); // Push 
    s.push("bbb");
    s.push("ccc");
    if (s.size() < STACK_SIZE) // Can be limited in size 
        s.push("68");
    cout << s.size() << endl; // Output the number of elements in the stack 
    while (!s.empty()) {
       // When the stack is not empty 
        cout << s.top() << endl; // Out of the stack 
        s.pop();                 // Out of the stack 
    }
    return 0;
}

result ：

4
68
ccc
bbb
aaa

13. queue Queue container

Method	explain
push()	Insert an element at the end of the team
pop()	Delete the first element of the queue
size()	Return the number of elements in the queue
empty()	If the queue is empty, return true
front()	Returns the first element in the queue
back()	Returns the last element in the queue

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

int main(){
    
    queue<int> q;
    q.push(3); // The team 
    q.push(5);
    q.push(2);
    cout << "The number of elements is:" << q.size() << endl;
    cout << q.back();  // Take the last element of the team 
    while (!q.empty())  {
     // When the queue is not empty 
        cout << q.front() << endl; // Print the first element of the team 
        q.pop();                   // Out of the team 
    }
    return 0;
}

result ：

The number of elements is:3      
23
5
2

14. deque Double ended queue container

deque In the header file <deque> In a statement , It is a continuous linear space with two-way openings , Can be efficiently in the head 、 Insert and delete elements at both ends of the tail . Its time complexity is O(1), When considering the memory allocation strategy and operation performance of container elements ,deque Than vector There are advantages .

Method	explain
push_back(element);	Add a data at the end of the container
push_front(element);	Insert a data into the head of the container
pop_back();	Delete the last data in the container
pop_front();	Delete the first data of the container
begin();	Returns the iterator of the first element in the container .
end();	Returns the iterator after the last element in the container .
rbegin();	Returns the iterator of the penultimate element in the container .
rend();	Returns the iterator after the last element in the container .
cbegin();	Returns the constant iterator of the first element in the container .
cend();	Returns the constant iterator after the last element in the container .
size();	Returns the number of elements in the container
empty();	Judge whether the container is empty
insert(pos,elem);	stay pos Insert a elem Copies of elements , Return new data The location of .
insert(pos,n,elem);	stay pos Position insert n individual elem data , No return value .
insert(pos,beg,end);	stay pos Position insert [beg,end) Interval data , No return value
clear();	Remove all data from the container
erase(beg,end);	Delete [beg,end) Interval data , Return to the next data location .
erase(pos);	Delete pos Location data , Return to the next data location .

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

int main(){
    
    deque<string> d;  // Define an inclusion string Type of deque
    d.push_back("A"); // Tail-insert element 
    d.push_back("B");
    d.push_back("C");
    d.push_front("X"); // Header insert element 
    d.push_front("Y");
    // d.pop_front();// Delete first element 
    // d.pop_back();// Delete tail element 
    // d.erase(d.begin()+1);// Delete the specified location element 
    // d.clear();// Delete all elements 
    d.insert(d.end() - 2, "O"); // Insert... At specified location 

    reverse(d.begin(), d.end());       // Reverse the order of elements 
    for (int i = 0; i < d.size(); i++) // Array access 
        cout << d[i] << " ";
    cout << endl;

    swap(d[1], d[2]);          // Two element exchange 
    deque<string>::iterator i; // Iterators access 
    for (i = d.begin(); i != d.end(); i++)
        cout << *i << " ";
    cout << endl;

    cout << "\nDeque is empty " << d.empty();
    cout << "\nDeque element number is " << d.size();
    cout << "\nDeque's first element is " << d.front();
    cout << "\nThe last element of Deque is " << d.back();
    return 0;
}

result ：

C B O A X Y 
C O B A X Y

Deque is empty 0
Deque element number is 6
Deque's first element is C
The last element of Deque is Y

15. priority_queue Priority queue container

priority_queue Priority queue container in header file <queue> In a statement , Same as queue container , You can only insert elements from the end of the team , Remove element from team leader . Its general form is priority_queue<Type,Container, Functional>, among Type Is the data type ,Container A container for storing data ,Functional It is the way of element comparison .

Container Must be a container implemented in an array , for example vector、deque etc. , But it can't be used. list,STL The default is vector. If the following two parameters are set by default , The priority queue container is Big pile top （ Descending ）, The team head element is the largest . Operators can be overloaded to redefine comparison rules .

From smallest to largest , The basic way to get small elements out of the team first is as follows .
priority_queue<int,vector<int>,greater<int> >q;
From large to small , The basic way to get big elements out of the team first is as follows .( Default )
priority_queue<int,vector<int>,less<int> >q;

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

struct cmp{
    
    bool operator()(const int &a, const int &b) {
    // heavy load "()" The operator 
        return a > b; // Arrange from small to large ">", Otherwise, use "<"
    }
};

int main(){
    
    priority_queue<int, vector<int>, cmp> que1;
    //priority_queue<int, vector<int>, greater<int>> que1;
    priority_queue<int, vector<int>> que2;
    int a[] = {
    1, 3, 4, 2, 5, 0, 6};
    for (int i = 0; i < 7; i++){
    
        que1.push(a[i]);
        que2.push(a[i]);
    }
    cout << "que1:";
    while (!que1.empty()){
    
        cout << que1.top() << " ";
        que1.pop();
    }
    cout << endl
         << "que2:";
    while (!que2.empty()){
    
        cout << que2.top() << " ";
        que2.pop();
    }
    return 0;
}
/* que1:0 1 2 3 4 5 6 que2:6 5 4 3 2 1 0 */