当前位置：网站首页>[STL programming] [common competition] [Part 2]

[STL programming] [common competition] [Part 2]

2022-06-27 20:31:00 【Eternity_ GQM】

List of articles

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

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

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

6. pair Containers

Definition	explain
pair<T1, T2> p1;	Create an empty pair object , Its two elements are T1 and T2 type , Initialize with a value
pair<T1, T2>p1(v1,v2):	Create a pair object , among first Members are initialized to v1, and second Members are initialized to v2
make_pair(v1.v2)	With v1 and v2 Value to create a new pair object , The element types are v1 and v2 The type of
p1<p2	Two pair Less than operation between objects , Its definition follows dictionary order ： If `p1.first＜p2.first` perhaps `!(p2.first＜p1.first)&&(p1.second＜p2. second)`, Then return to `true`
p1==p2	If two pair Object's `first` and `second` The members are equal in turn , Then the two objects are equal
p.first	return p Middle name is first Of （ public ） Data member
p.second	return p The name is second Of （ public ） Data member

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

int main(){
    
    pair<int, double> p1; // Use the default constructor 
    p1.first = 10;
    p1.second = 12.5;
    cout << p1.first << ' ' << p1.second << endl;
    return 0;
}
/* 10 12.5 */

#include <bits/stdc++.h>
using namespace std;
typedef pair<string, double> psd; // typedef simplify pair The statement of is Record

int main(){
    
    psd p1 = make_pair("yjr", 100);
    psd p2;
    p2 = p1; // Overload operator "="
    cout << p2.first << ' ' << p2.second << endl;
    return 0;
}
/* yjr 100 */

pair The comparison of is in dictionary order , Compare according to first Size comparison of , If equal , Press again second Size comparison of ：

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

int main(){
    
    pair<int, char> A(10, 'z');
    pair<int, char> B(90, 'a');
    if (A == B)
        cout << " equal \n";
    if (A != B)
        cout << " It's not equal \n";
    if (A < B)
        cout << "A<B\n";
    if (A > B)
        cout << "A>B\n";
    if (A <= B)
        cout << "A<=B\n";
    if (A >= B)
        cout << "A>=B\n";
    return 0;
}
/*  It's not equal  A<B A<=B */

7. set Assembly containers

set The collection container is in the header file <set> In a statement , Use a tree like structure （ Balanced binary search tree based on red black tree ）, Store data and automatically transfer data （ No repetition value ） From small to large . structure set The main purpose of a collection container is to quickly retrieve （ The time complexity is O(logN)）, The retrieval efficiency is higher than vector、deque And list Equal container .

visit set Elements in the collection container , It needs to be iterated . Iterators are like pointers , It can be used to point to the address of an element in the container . for example set<int>::iterator ii; Defined a set<int> The iterator of type is ii.

Method	explain
s.begin()	return set The first element of the container
s.end()	return set The last element of the container
s.clear()	Delete set All the elements in the container
s.empty()	Judge set Whether the container is empty
s.insert()	Insert an element
s.erase()	Delete an element
s.size()	Returns the current set The number of elements in the container

s.lower_bound()	Returns the first element greater than or equal to the given key value
s.upper_bound()	Returns the first element greater than the given key value
s.equal_range()	Returns a pair of locators , respectively The first element greater than or equal to the given key value and The first element greater than the given key value , The return value is a pair type , If one of the pair of locators returns a failure , It will be equal to s.end()

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

int main(){
    
    set<int> s;
    for (int i = 10; i > 0; --i) // Here, the value is assigned from large to small 
        s.insert(i);             // Insert elements 
    set<int> s2(s);              // Copy s Generate s2
    s.erase(s.begin());          // Delete operation 
    s.erase(6);
    s.insert(5);                              // It doesn't insert repeatedly 
    set<int>::iterator ii;                    // ii Is a forward iterator 
    for (ii = s.begin(); ii != s.end(); ii++) // Traverse 
        cout << *ii << ' ';
    cout << "\n The number of elements is " << s.size(); // Statistics set The number of elements in , Time complexity O(1)
    ii = s.find(10);                    // Find element value , And return the iterator pointing to the element 
    if (ii != s.end())                  // If the element does not exist in the container , The return value is equal to s.end()
        cout << "\n lookup =" << *ii;
    if (s.count(5)) // return set The median is 5 Number of elements of , The time complexity is O(log n)
        cout << "\n The element of being 5";
    s.clear(); // Empty all elements 
    cout << "\n Whether the element is empty :" << s.empty();
    return 0;
}

/* 2 3 4 5 7 8 9 10  The number of elements is 8  lookup =10  The element of being 5  Whether the element is empty :1 */

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

int main(){
    
    set<int> myset;
    for (int i = 1; i < 11; i++){
    
		myset.insert(i);
	}
	cout << "lower_bound & upper_bound test:" << endl;
	cout << " The first is greater than or equal to 3 The elements of :" << *myset.lower_bound(3) << endl; // The function actually returns the address value 
	cout << " The first one is greater than 3 The elements of :" << *myset.upper_bound(3) << endl;	
	cout << "equal_range test:" << endl;
	cout << " The first is greater than or equal to 2 The elements of : " << *myset.equal_range(2).first << endl;
	cout << " The first one is greater than 2 The elements of : " << *myset.equal_range(2).second << endl;
	if (myset.equal_range(20).first == myset.end())
		cout << " There is no greater than or equal to 20 The elements of " << endl;
	myset.clear();
    return 0;
}
/*  The first is greater than or equal to 3 The elements of :3  The first one is greater than 3 The elements of :4 equal_range test:  The first is greater than or equal to 2 The elements of : 2  The first one is greater than 2 The elements of : 3  There is no greater than or equal to 20 The elements of  */

Use insert() Insert elements into set When collecting containers , By default, collection containers insert elements in descending order , But in many cases （ For example, you need to sort from large to small ） You need to write your own comparison function .

// set The comparison function of 
#include <bits/stdc++.h>
using namespace std;

struct Comp{
    
    bool operator()(const int &a, const int &b){
    
        return a > b; // Sort from large to small 
        // return a < b; // Sort from small to large 
    }
}; // The comparison function needs to be defined in the structure 

int main(){
    
    set<int, Comp> s;             // set The comparison function called is Comp
    for (int i = 1; i <= 10; ++i) // Here is the assignment from small to 
        s.insert(i);
    set<int>::iterator ii;
    for (ii = s.begin(); ii != s.end(); ii++) // Traverse 
        cout << *ii << ' ';
    return 0;
}
/* 10 9 8 7 6 5 4 3 2 1 */

Overload operators You can make user-defined types support addition like basic data types 、 reduce 、 ride 、 except 、 Self adding 、 Self reduction and other operations .operator yes C++ Key words of , It and the operator （ for example “ () ”） Use it together , Indicates that the operator overloads the function , In understanding, we can put operator And operators （ for example “operator()”） Treat as function name .

The parameter is defined as const int &a and const int &b This form , One is to prevent a and b Be modified , The second is to reduce the system overhead by referencing variables . Last const Also to prevent modification .

actually , quite a lot C++ The operator has been overloaded , for example “*” Used between two numbers , What you get is their product ; Used before an address , What you get is the value stored at this address .cin>>x and cout<<x Medium “>>” and “<<” Operators are also overloaded .

For example, customize a structure Time type , And want to achieve two Time Type addition operation （ That is, the hours are added to the hours , Add minutes to minutes , Add seconds to seconds ）, The procedure may be as follows .

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

struct Time{
    
    int H, M, S;                        // when , branch , second 
    Time operator+(const Time &b) const // Overload operator "+"
    {
    
        return Time{
    H + b.H, M + b.M, S + b.S}; // Just for demonstration , Don't think about carry 
    }
} T1 = {
    3, 2, 4}, T2 = {
    5, 20, 30}, T3;

int main(){
    
    T3 = T1 + T2;
    cout << T3.H << ":" << T3.M << ":" << T3.S << endl;
    return 0;
}
/* 8:22:34 */

C++ Existing operators can only be overloaded . The following table lists the operators that can be overloaded .

Insert picture description here
When an element is a structure , Operator must be overloaded “<”：

// set Structure Sorting of 
#include <bits/stdc++.h>
using namespace std;

struct Info{
    
    string name;
    double score;
    bool operator<(const Info &a) const  {
    // heavy load "<" The operator , Just copy 
        return a.score < score; // Sort from large to small 
     // return a.score >score; // Sort from small to large 
    }
} info;

int main(){
    
    set<Info> s;
    info = {
    "A", 90.0};
    s.insert(info);
    info = {
    "B", 92.0};
    s.insert(info);
    info = {
    "C", 96.0};
    s.insert(info);

    set<Info>::iterator ii;
    for (ii = s.begin(); ii != s.end(); ii++) // Traverse 
        cout << (*ii).name << ' ' << (*ii).score << endl;
    return 0;
}
/* C 96 B 92 A 90 */

8. multiset Multiple collection container

multiset Multiple collection containers in header files <set> In the definition of , It can be seen as a sequence , The number of repeats can exist in the sequence .multiset It can always ensure that the numbers in the sequence are ordered （ The default order is from small to large ）, Inserting a number or deleting a number can be done in O(logn) In time to complete .

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

int main(){
    
    multiset<int> m;
    m.insert(11); // insert data 
    m.insert(21);
    m.insert(10);
    m.insert(12);
    m.insert(12);
    m.insert(11);
    m.insert(11);
    m.insert(11);
    m.insert(9);
    cout << "11 The number of " << m.count(11) << endl; // Output multiset in 11 The number of 
    cout << " The first is greater than or equal to 10 The element of is ：" << *m.lower_bound(10) << endl;
    cout << " The first one is greater than 11 The element of is :" << *m.upper_bound(11) << endl;
    multiset<int>::iterator it;
    for (it = m.begin(); it != m.end(); it++)
        cout << *it << endl;                            // From small to large output 
    cout << " Delete 12, Yes " << m.erase(12) << " individual " << endl; // Delete equals 12 The elements of 
    cout << " lookup 9\n";
    multiset<int>::iterator i = m.find(9); // lookup v, Returns the iterator position of the element 
    if (i != m.end())                      // Output if found , otherwise i by end() Iterator location 
        cout << *i << endl;
    pair<multiset<int>::iterator, multiset<int>::iterator> p;
    int v = 11;
    // equal_range: The last bit in an ordered container that represents the first occurrence and the last occurrence of a value 
    p = m.equal_range(v); // Find all the same elements 
    cout << " Greater than or equal to " << v << " The first element of is " << *p.first << endl;
    cout << " Greater than " << v << " The first element of is " << *p.second << endl;
    cout << " The key value is " << v << " All elements of are ";
    for (it = p.first; it != p.second; it++) // Print duplicate key value elements 11
        cout << *it << " ";
    m.clear(); // Empty all elements 
    return 0;
}

11 The number of 4
 The first is greater than or equal to 10 The element of is ：10
 The first one is greater than 11 The element of is :12     
9
10
11
11
11
11
12
12
21
 Delete 12, Yes 2 individual 
 lookup 9
9
 Greater than or equal to 11 The first element of is 11
 Greater than 11 The first element of is 21
 The key value is 11 All elements of are 11 11 11 11

9. map Mapping containers

map Mapping container in header file <map> In the definition of , Its element data is composed of key values and mapping data , There is a one-to-one correspondence between key values and mapping data .

map Mapping containers and set Like the collection container, it is implemented with red and black trees , The element inserting the key value cannot be repeated , By default, elements are sorted by key value from small to large . If you define a comparison function , The comparison function can only compare the key values of elements , The data of the element can be retrieved through the key value .
map And set Is the difference between the ：map It is a quick insert for processing record type element data with key value 、 Delete and retrieve , and set It is the processing of single data .

Method	explain
begin()	Return to point map The iterator of the head
end()	Return to point map Iterator at the end
rbegin()	Return a point map The backward iterator of the tail
rend()	Return a point map The reverse iterator of the head

clear(）	Delete all elements
count()	Returns the number of occurrences of the specified element ( because key Values don't repeat , So it can only be 1 or 0)
empty()	If map If it is blank, return true
equal_range()	Returns the iterator pair for a particular entry
erase()	Delete an element
find()	Find an element
insert()	Insert elements
size()	return map The number of elements in
swap()	Two exchanges map

get_allocator()	return map Configurator for
key_comp()	Returns the comparison element key Function of
value_comp()	Returns the comparison element value Function of
lower_bound()	Return key value >= Given the first position of the element
upper_bound()	Return key value > Given the first position of the element
max_size()	Returns the maximum number of elements that can be accommodated
size()	return map The number of elements in
swap()	Two exchanges map

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

int main(){
    
    map<int, string> ms;
    ms[1] = "student_one";
    ms[1] = "student_two"; // id identical , Coverage 
    ms[2] = "student_three";
    map<int, string>::iterator iter;
    ms.insert(make_pair(3, "student_four")); // Insert new elements 
    for (iter = ms.begin(); iter != ms.end(); iter++)
        cout << iter->first << " " << iter->second << endl;
    cout << endl;
    iter = ms.lower_bound(1); // The first is greater than or equal to 1 The elements of 
    cout << iter->second << endl;
    iter = ms.upper_bound(1); // First greater than 1 The elements of 
    cout << iter->second << endl;
    iter = ms.find(1); // The search key value is 1 Element location of 
    ms.erase(iter);    // The delete key value is 1 The elements of 
    for (iter = ms.begin(); iter != ms.end(); iter++)
        cout << iter->first << " " << iter->second << endl;
    ms.erase(ms.begin(), ms.end()); // Delete all elements 
    cout <<"size: "<< ms.size() << endl;
    cout <<"empty: "<< ms.empty() << endl;// empty() Judge map Is it empty 
    return 0;
}

result ：

1 student_two
2 student_three
3 student_four

student_two
student_three
2 student_three
3 student_four
size: 0
empty: 1

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

struct Info{
     // Student information structure 
    char *xm; // full name 
    int y;    // year 
    char *d;  // Address 
};

struct Record {
    // Student record structure 
    int id;  // Student ID as key value 
    Info sf; // Student information as mapping data 
};

int main(){
    
    Record srArray[] ={
    
            {
    4, "Li", 21, "beijing"},
            {
    2, "wang", 29, "shanghai"},
            {
    3, "zhang", 30, "shengzheng"}};
    map<int, Info, greater<int>> m; // Key values are sorted from large to small 
    for (int j = 0; j < 3; j++)     // Load three student information 
        m[srArray[j].id] = srArray[j].sf;
    Record s1 = {
    5, "Ling", 23, "XINJIANG"};
    m.insert(make_pair(s1.id, s1.sf)); // Insert new student information 
    map<int, Info>::iterator i;
    for (i = m.begin(); i != m.end(); i++) // Positive traversal 
        cout << (*i).first << ' ' << (*i).second.xm << ' ' << (*i).second.d << '\n';
    i = m.find(2); // The search key value is 2 Record and output 
    cout << "Key value 2: " << (*i).second.xm << ' ' << (*i).second.d;
    return 0;
}

result ：

5 Ling XINJIANG
4 Li beijing
3 zhang shengzheng
2 wang shanghai
Key value 2：wang shanghai

10. multimap Multiple mapping container

multimap And map The functions of are basically the same , The only difference is multimap Allow to insert elements with duplicate key values , Since it is allowed to insert elements with duplicate key values , therefore multimap The elements of insert 、 Delete and find and map Different .

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

int main(){
    
    multimap<string, double> mp;                    // Definition map object , There are currently no elements 
    mp.insert(pair<string, double>("Jack", 300.5)); // Insert elements a
    mp.insert(pair<string, double>("Kity", 200));
    mp.insert(pair<string, double>("Memi", 500));
    mp.insert(pair<string, double>("Jack", 306)); // Insert key values repeatedly "Jack"

    multimap<string, double>::iterator it;
    mp.erase("Jack");                           // Delete key value equals "Jack" The elements of 
    for (it = mp.begin(); it != mp.end(); it++) // Forward iterator traversal in sequence multimap
        cout << (*it).first << " " << (*it).second << endl;

    it = mp.find("Nacy"); // Element search 
    if (it != mp.end())   // find 
        cout << (*it).first << " " << (*it).second << endl;
    else // Did not find 
        cout << "Not find it!" << endl;
    return 0;
}