C++ STL 常用容器用法总结

2. unordered_map 用法

定义

unordered_map 内部实现了一个哈希表 （也叫散列表，通过把关键码值映射到 Hash 表中一个位置来访问记录，查找的时间复杂度可达到 O(1)，其在海量数据处理中有着广泛应用）。因此，其元素的排列顺序都是无序的。

因为内部实现了哈希表，因此其查找速度非常的快。

函数方法

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    unordered_map<int,string>mymap{{5,"张大"},{6,"李四"}};//使用{}赋值
    mymap[2]="张三";//使用 [] 进行单个插入，若已存在键值 2，则赋值修改，若无则插入。
    mymap.insert(pair<int ,string>(3,"陈二"));//使用 insert 插入
    //遍历输出 + 迭代器的使用
    auto iter=mymap.begin();//auto 自动识别为迭代器类型 unorder_map<int,string>::iterator
    while(iter!=mymap.end()){
        cout<<iter->first<<','<<iter->second<<endl;
        ++iter;
    }
    //查找元素并输出
    auto iterator = mymap.find(2);//find() 返回一个指向 2 的迭代器
    if (iterator != mymap.end()) cout << endl<< iterator->first << "," << iterator->second << endl;
    //迭代器
    unordered_map<key,t>::iterator it;
    (*it).first;
    (*it).second;
    (*it)
    return 0;
}

3. stack 用法

定义

stack 栈函数，实现先进后出的数据结构。

函数方法

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    stack<int>s;
    for(int i=0;i<5;i++){
        s.push(i);
    }
    while(!s.empty()){
        int t=s.top();
        cout<<t<<" ";
        s.pop();
    }
    //4 3 2 1 0
    return 0;
}

4. vector 用法

定义

vector 是 STL 中的一种常用的容器，长度可变（size），类似数组，可以代替长度未知的数组。

函数方法

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    vector<int>a;
    a.push_back(200);
    a.push_back(20);
    a.push_back(300);
    a.push_back(50);
    a.push_back(60);
    a.push_back(100);
    vector<int>::iterator it;
    //删除单个元素
    for(it=a.begin();it!=a.end();it++){
        if (*it==300){
            a.erase(it);
        }
    }
    for(it=a.begin();it!=a.end();it++){
        cout<<*it<<endl;
    }
    printf("\n");
    //删除一段元素
    auto it_begin=a.begin()+1;
    vector<int>::const_iterator it_end=a.end()-1;
    a.erase(it_begin,it_end);
    for(it=a.begin();it!=a.end();it++){
        cout<<*it<<endl;
    }
    printf("\n");
    //删除最后一个元素
    vector<int>::iterator it_last=a.end()-1;
    a.erase(it_last);
    for(it=a.begin();it!=a.end();it++){
        cout<<*it<< " ";
    }
    return 0;
}

5. queue 用法

定义

队列是先进先出的数据结构，可以在队尾添加元素，队首删除元素。

函数方法

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    //创建一个队列
    queue<int>q;
    //向队列添加元素
    q.push(10);
    q.push(15);
    q.push(6);
    q.push(9);
    //返回队首元素、队尾元素和队列长度 10 9 4
    cout<<q.front()<<" "<<q.back()<<" "<<q.size()<<endl;
    //输出队列中的元素
    while(!q.empty()){//队列不为空
        cout<<q.front()<<" ";
        q.pop();//删除队首元素
    }
    // 10 15 6 9
    cout<<endl;
    return 0;
}

6. deque 用法

定义

deque 是双端队列，允许在两端进行插入和删除操作的线性数据结构。适合用于频繁插入和删除元素的场景。

函数方法

代码

#include<bits/stdc++.h>
using namespace std;
deque<int>q1,q2;
int main(){
    //插入元素
    for(int i=0;i<5;i++){
        q1.push_front(i);//队列前端添加
        q2.push_back(i);//队列末尾添加
    }
    // q1:4 3 2 1 0
    // q2:0 1 2 3 4
    //返回队首和队尾元素
    cout<<q1.front()<<" "<<q1.back()<<endl;//4 0
    q1.pop_front();//q1:3 2 1 0
    q1.pop_back();//q1:3 2 1
    //查找元素
    auto iter = find(q2.begin(), q2.end(), 1);
    if (iter != q2.end()) cout << *iter << endl;//1
    else cout << "没找到" << endl;
    //删除
    q2.erase(iter);//q2:0 2 3 4
    for(int i=0;i<q1.size();i++){
        cout<<q1[i]<<" ";
    }
    cout<<endl;
    for(int i=0;i<q2.size();i++){
        cout<<q2[i]<<" ";
    }
    cout<<endl;
    return 0;
}

7. priority_queue 用法

定义

优先队列是一种特殊的队列，它允许我们快速访问队列中具有最高（或最低）优先级的元素，内部会自动按照规则排列。默认情况下队列顶部元素是最大值，不能随机访问，只能从队首访问元素。

函数方法

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    //对于基础类型 默认是大顶堆，递减
    priority_queue<int>a;
    priority_queue<int,vector<int>,less<int> >b;
    //这样就是小顶堆，递增
    priority_queue<int, vector<int>, greater<int> > c;
    //插入
    for(int i=0;i<5;i++){
        a.push(i);
        b.push(i);
        c.push(i);
    }
    while(!a.empty()){
        int t=a.top();
        a.pop();
        printf("%d ",t);
    }
    //4 3 2 1 0
    puts("");
    while(!b.empty()){
        int t=b.top();
        b.pop();
        printf("%d ",t);
    }
    //4 3 2 1 0
    puts("");
    while(!c.empty()){
        int t=c.top();
        c.pop();
        printf("%d ",t);
    }
    //0 1 2 3 4
    puts("");
    //pari 的比较，先比较第一个元素，第一个相等比较第二个
    priority_queue<pair<int,int> >d;
    d.push({1,2});
    d.push({1,3});
    d.push({2,5});
    while (!d.empty()){
        cout << d.top().first << ' ' << d.top().second << '\n';
        d.pop();
    }
    /* 2 5 1 3 1 2 */
    return 0;
}

如果要自定义类型

#include<bits/stdc++.h>
using namespace std;
//方法 1
struct tmp1{
    //运算符重载<
    int x;
    tmp1(int a) {x = a;}
    bool operator<(const tmp1& a) const {
        return x < a.x; //大顶堆
    }
};
//方法 2
struct tmp2{
    //重写仿函数
    //相当于是在定义优先级
    bool operator() (tmp1 a, tmp1 b) {
        return a.x < b.x; //大顶堆
    }
};
int main(){
    tmp1 a(1);
    tmp1 b(2);
    tmp1 c(3);
    priority_queue<tmp1> d;
    d.push(b);
    d.push(c);
    d.push(a);
    while (!d.empty()) {
        cout << d.top().x <<" ";
        d.pop();
    }
    cout << endl;
    //3 2 1
    priority_queue<tmp1, vector<tmp1>, tmp2> f;
    f.push(c);
    f.push(b);
    f.push(a);
    while (!f.empty()) {
        cout << f.top().x <<" ";
        d.pop();
    }
    //3 2 1
    return 0;
}

8. set 用法

定义

set 容器中元素有序且不会重复，可以进行元素的快速查找、插入和删除。set 是基于红黑树实现的，事件复杂度 log n。

函数方法

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    //初始化定义
    set<int>s;
    set<int>a={1,2,3};
    for(int i=10;i>=0;i--){
        s.insert(i);
    }
    int mmin=*s.begin();
    int mmax=*(--s.end());
    printf("%d %d\n",mmin,mmax);// 0 10 返回首尾元素
    set<int>::iterator it;
    for(it=s.begin();it!=s.end();it++){
        printf("%d ",*it);
    }
    //0 1 2 3 4 5 6 7 8 9 10
    printf("\n");
    //删除：erase
    //直接删除
    s.erase(5);
    s.erase(s.begin());
    for(auto it:s){
        printf("%d ",it);
    }
    //1 2 3 4 6 7 8 9 10
    printf("\n");
    s.erase(--s.end());
    for(auto it:s){
        printf("%d ",it);
    }
    // 1 2 3 4 6 7 8 9
    printf("\n");
    s.clear();
    printf("%d\n",s.size());// 0
    return 0;
}

9. multiset 用法

multiset 与 set 类似，但允许元素重复。

10. bitset 用法

bitset 用于处理位运算，空间效率高。

补充知识：随机数

1. rand()

rand() 产生的是伪随机数字，每次执行时是相同。rand() 产生的随机数在每次运行的时候都是与上一次相同的。若要不同，用函数 srand() 初始化它。可以利用 srand((unsigned int)(time(NULL)) 的方法，产生不同的随机数种子，因为每一次运行程序的时间是不同的。

int rand(void)

2. srand()

srand() 用来设置 rand() 产生随机数时的随机数种子。参数 seed 必须是个整数，如果每次 seed 都设相同值，rand() 所产生的随机数值每次就会一样。

1. 给 srand() 提供一个种子，它是一个 unsigned int 类型；
2. 调用 rand()，它会根据提供给 srand() 的种子值返回一个随机数 (在 0 到 RAND_MAX 之间)；
3. 根据需要多次调用 rand()，从而不间断地得到新的随机数；
4. 无论什么时候，都可以给 srand() 提供一个新的种子，从而进一步"随机化"rand() 的输出结果。

//0~RAND_MAX 之间的随机数程序
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
int main() {
    srand((unsigned)time(NULL));
    for(int i = 0; i < 10;i++ ) cout << rand() << '/t';
    cout << endl;
    return 0;
}
/* 要取得 [a,b) 的随机整数，使用 (rand() % (b-a))+ a;
   要取得 [a,b] 的随机整数，使用 (rand() % (b-a+1))+ a;
   要取得 (a,b] 的随机整数，使用 (rand() % (b-a))+ a + 1; */