STL常用库函数复习

pair

• utility
• 示例

#include 
#include 

using namespace std;

int main() {
    pair<int,double> p1(1,3.14);
    pair<char,string> p2('a',"hello");
    cout<<p1.first<<", "<<p1.second<<endl;
    cout<<p2.first<<", "<<p2.second<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

• 嵌套
• 例如：三维坐标

#include 
#include 

using namespace std;

int main() {
    pair<int,int> p1(1,2);
    pair<int,pair<int,int>> p2(3,make_pair(4, 5));
    pair<pair<int,int>,pair<int,int>> p3(make_pair(6, 7),make_pair(3, 5));
    cout<<p1.first<<", "<<p1.second<<endl;
    cout<<p2.first<<", "<<p2.second.first<<", "<<p2.second.second<< endl;
    cout<<p3.first.first<<" ,"<<p3.first.second<<" ,"<<p3.second.first<<" ,"<<p3.second.second<<endl;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

• 示例

#include 
#include 
#include 

using namespace std;
struct Person{
    string name;
    int age;
};
int main() {
    vector<Person> people;
    people.push_back({"Alice",25});
    people.push_back({"Bob",30});
    people.push_back({"Charlie",20});
    vector<pair<Person, int>> scores;
    scores.push_back({people[0],90});
    scores.push_back({people[1],85});
    scores.push_back({people[2],95});
    for(const auto& pair : scores){
        cout<<"Name: "<<pair.first.name<<endl;
        cout<<"Age: "<<pair.first.age<<endl;
        cout<<"Score: "<<pair.second<<endl;
        cout<<endl;
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

vector

• 一般用 i

• push_back()

• pop_back()

• insert()

• erase()

• empty()

• resize()

• begin(),end()

• clear()

• sort()

• unique()

• 排序并去重：vec.erase(unique(vec.begin(),vec.end()),vec.end());

#include 
#include 
#include 

int main() {
    std::vector<int> vec = {2,1,3,2,4,1,5,4};
    std::sort(vec.begin(),vec.end());
    auto last = unique(vec.begin(),vec.end());
    vec.erase(last,vec.end());
    for(const auto& num:vec){
        std::cout<<num<<" ";
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

list

• 用的很少，如果需要链表一般用数组模拟或手写链表
• 如果需要随机访问，一半用 vector(),deque()
• push_back()
• push_front()
• pop_back()
• pop_front()
• size()
• empty()
• clear()
• front()
• back()
• begin()
• end()
• insert()
• erase()

stack

• push()
• pop()
• top()
• empty()
• size()
• 将数组元素依次入栈，再依次出栈，可以将数组翻转。（一般不会这么做）

queue

queue

以下都是 O(1)

• push(x)
• pop()
• front()
• empty()
• size()

priority_queue

• push(x)

• pop()

• top()

• empty()

• size()

• #include

• priority_queue(int，vector,compare/greater) //小根堆

struct Compare{
	bool operator()(int a,int b){
		return a>b;
	}
}
1
2
3
4
5

queue双端队列

• 不常用
• push_back(x)
• push_front(x)
• pop_back()
• pop_front()
• front()
• back()
• empty()
• size()
• clear()
  

#include

using namespace std;

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int m;cin>>m;
    queue<string> V,N;
    while(m--){
        string op;cin>>op;
        if(op=="IN"){
            string name,q;cin>>name>>q;
            if(q=="V")V.push(name);
            else N.push(name);
        }else{
            string q;cin>>q;
            if(q=="V")V.pop();
            else N.pop();
        }
    }
    while (V.size()) {
        cout<<V.front()<<'\n';
        V.pop();
    }
    while(N.size()){
        cout<<N.front()<<"\n";
        N.pop();
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include

using namespace std;
using ll = long long;

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n;cin>>n;
    priority_queue<ll,vector<ll>,greater<ll>> pq;
    for(int i=1;i<=n;++i){
        ll x;cin>>x;
        pq.push(x);
    }
    ll ans = 0;
    while(pq.size()>=2){
        ll x = pq.top();pq.pop();
        ll y = pq.top();pq.pop();
        ans += x+y;
        pq.push(x+y);
    }
    cout<<ans<<"\n";
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

set

✨set集合

• 无重复，默认降序
• insert(x)
• erase(x)
• find(x)

#include
#include
using namespace std;
int main( ){
    set<int,greater<int>> mySet;
    mySet.insert(25);
    mySet.insert(17);
    mySet.insert(39);
    mySet.insert(42);
    for(const auto& elem:mySet)cout<<elem<<" ";
    cout<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

#include
#include
using namespace std;

struct MyCompare{
    bool operator()(const int& a,const int& b)const{
        return a>b;
    }
};

int main( ){
    set<int,MyCompare> mySet;
    mySet.insert(25);
    mySet.insert(17);
    mySet.insert(39);
    mySet.insert(42);
    for(const auto& elem : mySet){
        cout<< elem << " ";
    }
    cout<<endl;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

✨multiset 多重集合

• 允许存储重复元素
• 二分：
  • lower_bound:返回第一个不小于给定值的迭代器
  • upper_bount:返回第一个不大于给定值的迭代器
• st.erase(st.find(x))

了解：unordered_set 无序集合

• 无重复，无顺序

map

🌟map

• 存储键值对

#include   
#include   
using namespace std;  
  
int main() {  
    //创建并初始化multimap  
    multimap<int, string> myMultimap = {{1, "Apple"}, {2, "Banana"}, {3, "Orange"}};  
      
    //判断元素是否存在  
    if (myMultimap.count(2) == 0) {  
        cout << "Key 2 not found." << endl;  
    }  
  
    
    //插入元素  
    myMultimap.insert(make_pair(4, "Grapes"));  
    
  //清空multimap  
    myMultimap.clear();  
  
    //判断multimap是否为空  
    if (myMultimap.empty()) {  
        cout << "Multimap is empty." << endl;  
    } else {  
        //查找和访问元素  
        auto range = myMultimap.equal_range(3);  
        for (auto it = range.first; it != range.second; ++it) {  
            cout << "Key: " << it->first << ", Value: " << it->second << endl;  
        }  
    }  
  
    //遍历并打印multimap中的元素  
    for (const auto& pair : myMultimap) {  
        cout << "Key: " << pair.first << ", Value: " << pair.second << endl;  
    }  
  
    //删除元素  
    myMultimap.erase(3);  
      
    return 0;  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

几乎不用：multimap

一般不用：undered_map