STL基本使用

STL六大组件：

  1. 容器
  2. 适配器
  3. 空间分配器：malloc
  4. 迭代器：高级指针
  5. 算法库：sort
  6. 仿函数：一个类重载一个括号

1.string类

string常用方法
find(what, start)
substr(start, length)
insert(start, what)
replace(start, length, what)
size()\length()

注意：find()返回值为第一个目标出现的下标值，若没有找到将返回string::npos(-1)

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
#include <iostream>
#include <string>
using namespace std;

int main(){
    string str = "ABCDEF";
    //1.输出字符串长度
    cout << str.size() << endl;
    //2.查找字符串DE的位置
    cout << str.find("DE") << endl;
    //3.输出没有查找到的结果
    cout << (int)str.find("DE", 5) << endl;
    //4.字符串截取
    cout << str.substr(3, 2) << endl;
    //5.字符串插入
    str.insert(1, "abc");
    cout << str << endl;
    //6.字符串替换
    str.replace(2, 5, "000");
    cout << str << endl;
    //7.一次性读入一行包含空格的字符串
    string str1;
    getline(cin, str1);
    cout << str1 << endl;
    
    return 0;
}

2.vector动态数组

vector常用方法 说明
v.size() 获取vector中元素数量
v.push_back(x) 向vector末尾插入值为x的元素

（1）一维数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
#include<vector>
using namespace std;

int main(){
    //初始化一个10个元素都为88的一维数组
    vector<int> v(10, 88);
    v.push_back(99);
    v.push_back(8);
    v.push_back(56);
    for(int i = 0; i < v.size(); ++i){
        cout << v[i] << "\n";
    }
    
    return 0;
}

（2）二维数组：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<vector>
#include<string>
using namespace std;

int main(){
    //初始化一位10*10元素都为9的二维数组
    vector<vector<int> > v(10, vector<int>(10, 9));
    //(1)外层循环次数:v.size
    for(int i = 0; i < v.size(); ++i){
        //(2)内层循环次数:v[i].size
        for(int j = 0; j < v[i].size(); ++j){
            cout << v[i][j] << " ";
        }
        cout << endl;
    }
    
    return 0;
}

3.deque双端队列

deque常用方法
push_front()
pop_front()
push_back()
pop_back()
size()\empty() 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
#include<deque>
using namespace std;

int main(){
    deque<int> que;
    que.push_back(3);
    que.push_back(4);
    que.push_back(5);
    que.push_front(6);
    que.push_front(7);
    while(!que.empty()){
        cout << que.front() << " " << que.back() << endl;
        que.pop_back();
    }

    return 0;
}

4.stack栈

stack栈本质上不是容器属于适配器，是由双端队列进行二次封装得到

stack常用方法
push()
pop()
top()
empty()
size() 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<stack>
using namespace std;

int main(){
    stack<string> sta;
    sta.push("1234567890");
    sta.push("abc");
    sta.push("909090");
    sta.push("T");
    cout << sta.size() << endl;
    cout << sta.top() << endl;
    while(!sta.empty()){
        cout << sta.top() << endl;
        sta.pop();
    }

    return 0;
}

5.queue队列

queue常用方法
push()
pop()
front()
back()
empty()
size()

（1）基本使用：

queue队列本质上不是容器属于适配器，大部分情况下是由双端队列进行二次封装得到

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
#include<queue>
using namespace std;

int main(){
    queue<int> que;
    que.push(6);
    que.push(7);
    que.push(1);
    cout << que.size() << endl;
    while(!que.empty()){
        cout << que.front() << " " << que.back() << endl;
        que.pop();
    }
    return 0;
}

（2）自定义类型：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<queue>
using namespace std;

struct node{
    int num, cnt;
};

int main(){
    queue<node> que;
    que.push((node){5, 6});
    que.push((node){1, 10});
    que.push((node){6, -1});
    cout << que.size() << endl;
    while(!que.empty()){
        cout << que.front().num << " " << que.front().cnt << endl;
        que.pop();
    }

    return 0;
}

6.priority_queue优先队列

priority_queue底层实现为堆，且建立后默认为大顶堆

priority_queue常用方法
push()
pop()
top()
empty()
size()

（1）大顶堆：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<queue>
using namespace std;

int main(){
    priority_queue<int> que;
    que.push(5);
    que.push(9);
    que.push(-1);
    que.push(999);
    que.push(72);
    cout << que.size() << endl;
    while(!que.empty()){
        cout << que.top() << endl;
        que.pop();
    }
    
    return 0;
}

（2）小顶堆：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<queue>
using namespace std;

int main(){
    /*
    priority_queue<int, vector<int>, greater<int> > que;
    priority_queue<类型（装的是什么）, 容器（用什么装）, 比较规则（greater<int>） > que;
    */
    priority_queue<int, vector<int>, greater<int> > que;
    que.push(5);
    que.push(9);
    que.push(-1);
    que.push(999);
    que.push(72);
    cout << que.size() << endl;
    while(!que.empty()){
        cout << que.top() << endl;
        que.pop();
    }
    
    return 0;
}

（3）队列自定义类型：运算符重载

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
#include<iostream>
#include<queue>
using namespace std;

/*
	容器存储自定义类型必须重载小于号：
	bool operator< (const node &b)const{
        return this->num < b.num;    
    } 
*/

struct node{
    int num, cnt;
    bool operator< (const node &b)const{
        return this->num < b.num;    
    }
};

int main(){
    priority_queue<node> que;
    que.push((node){1, 2});
    que.push((node){4, -2});
    que.push((node){3, -9});
    cout << que.size() << endl;
    while(!que.empty()){
        cout << que.top().num << " " << que.top().cnt << endl;
        que.pop();
    }
    return 0;
}

总结：自定义类型自定义输出顺序规则为按照第一个数字从大到小输出

（4）队列自定义类型：仿函数

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
#include<iostream>
#include<queue>
using namespace std;

struct node{
    int num, cnt;
};

/*
自定义仿函数：
struct func{
    bool operator() (const node &a, const node &b){
        return a.num < b.num;    
    }
};
*/

struct func{
    bool operator() (const node &a, const node &b){
        return a.num < b.num;    
    }
};

int main(){
    priority_queue<node, vector<node>, func> que;
    que.push((node){1, 2});
    que.push((node){4, -2});
    que.push((node){3, -9});
    cout << que.size() << endl;
    while(!que.empty()){
        cout << que.top().num << " " << que.top().cnt << endl;
        que.pop();
    }
    return 0;
}

7.set集合

set集合特点：

  1. 无重复元素
  2. 元素是有序的
  3. 插入、查找、删除操作的时间复杂度为log(N)

（1）基本使用：

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
#include<iostream>
#include<set>
using namespace std;

int main(){
    set<int> s;
    s.insert(7);
    s.insert(5);
    s.insert(99);
    s.insert(128);
    s.insert(-1);
    cout << s.size() << endl;
    if(s.count(128) == 1){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
    s.erase(128);
    if(s.count(128) == 1){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
    //迭代器遍历set集合中的元素
    for(auto it = s.begin(); it != s.end(); it++){
        cout << *it << endl; 
    }

    return 0;
}

（2）自定义类型：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<set>
using namespace std;

struct node{
    int num,cnt;
    bool operator< (const node &b)const {
        return this->num < b.num;
    }
};

int main(){
    set<node> s;
    s.insert((node){8, 9});
    s.insert((node){-99, 128});
    s.insert((node){2, 73});
    for(auto it = s.begin(); it != s.end(); it++){
        cout << it->num << " " << it->cnt << endl;
    }

    return 0;
}

8.map键值对

除了map中存储的为键值对，其他与set集合基本一致

（1）基本使用：

注意：在使用[]查询键值对时，若键值对不存在将自动创建，int类型将初始化值为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
#include<iostream>
#include<map>
#include<string>
#include<utility>
using namespace std;

int main(){
    map<string, int> m;
    m.insert(make_pair("12345", 789));
    m.insert(make_pair("abcdefg", 111111));
    m.insert(make_pair("T", 99));
    if(m.count("abcdefg") == 1){
        cout << "YES" << endl;
        cout << m["abcdefg"] << endl;
    }else{
        cout << "NO" << endl;
    }
    m["999999"] = 56789;
    cout << m["999999"] << endl;
    
   	//使用count()查询与使用[]查询的区别
    m.erase("999999");
    cout << m.count("999999") << endl;
    cout << m["999999"] << endl;
    cout << m.count("999999") << endl;
    
	//遍历输出map中的键值对
    for(auto it = m.begin(); it != m.end(); it++){
        cout << it->first << " " << it->second << endl;
    }

    return 0;
}

（2）unordered_map:

对于无序map/set其内部的结构是一个哈希表（利用哈希查找函数），

  1. 所以如果在unordered_map/set中使用自定义类型，就必须要自己手写哈希函数。
  2. 在容器选择时，如果需要容器有序时才使用map/set，若无序有序则使用unordered_map/set以尽可能提升运行速度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
#include<unordered_map>
#include<string>
using namespace std;

int main(){
    unordered_map<string, int> m;
    m["1234567890"] = 67890;
    m["abcdefg"] = 12345;
    m["(+_+)"] = 666666;
    cout << m.size() << endl;
    for(auto it = m.begin(); it != m.end(); it++){
        cout << it->first << " " << it->second << endl;
    }
    return 0;
}

unordered_set

unordered_map

unordered_multiset

unordered_multimap