秉持着奥卡姆剃刀：如无必要，勿增新知的原则， 本篇只收录使用频率高的内容。

更新

transform转换大小写

transform(word.begin(), word.end(), word.begin(), ::tolower); 对string转换成小写
transform(word.begin(),word.end(),word.begin(),::toupper); 对string转换成大写

STL

迭代器基础使用

    set<int>a = {4,2,3,1,5};
    for(set<int>::iterator it = a.begin();it!=a.end();it++){
        cout << *it << ''; // 1 2 3 4 5
    }

auto神器

编译器自行判断用户定义的变量类型

    //第一种遍历方式
    set<int>a = {4,2,3,1,5};
    for(auto it = a.begin();it!=a.end();it++){
        cout << *it << ' ';
    }
    //第二种，如果容器封装了begin和end就可以用,普通数组也可以
    for(auto x : a){
        cout << x << endl;
    }

Lambda语法

格式: [] () -> return_type {}

如下场景会用就行。

    int arr[5] = {3,4,1,2,7};
    sort(arr,arr+5,[](int a, int b){
        return a>b;
    });

vector

  • 常见声明：
    • vector<int> v1;
    • vector<int> v2(5); 长度为5，其实第二个参数可以传入初始值
    • vector<int> v4 = {4, 5, 6, 7};
  • 访问
    • 下标访问
    • 遍历：
      • 普通for
      • 迭代器 for(auto x : v)
  • 插入push_back 弹出 pop_back
  • 其它
    • size
    • clear O(1)
    • empty
    • front 返回引用类型，可以修改值 -- v.front() = 1;
    • back 返回引用类型，可以修改值
    • erase(v.begin()+1,v.begin()+4); 删除[1,4)
    • resize(size,default_value)
    • 重写了比较运算符，机制类似字符串

string

形式上是字符串，功能上如同 vector<char>，支持+=和+，支持cin，cout

  • 声明
    • string s1;
    • string s2 = "123"; 也可以直接传入一个char[]
  • 访问：同vector
  • 用法：
    • push_back pop_back
    • size,length相同
    • clear empty begin end
    • 运算符+ += ： 尾部拼接一个字符串
  • 常量：string::npos：无穷大，表示无或者不存在
  • str1.compare(str2);
  • str1.insert(begin_index,str2);
  • str1.erase(begin_index，length)
  • c_str 转成 char*字符串

find函数

时间复杂度 O(N)
用于从前往后查找子串或者字符串第一次出现的下标位置，若找到则返回stirng::npos，与其相对的从后往前找的是rfind函数。

    string s = "abcdef";
    cout << s.find('a') << endl; // 0
    //从下标3开始找
    if(s.find('a',3) == string::npos) cout << "not found! " << endl; // not found!

    cout << s.find("bc") << endl; // 1

substr

O(N)
返回子串
string str = s.substr(begin_index);
s.substr(begin_index,length);
s.substr(begin_index,-1); 表示长度为无穷，或者改成string::npos

replace

O(1) 返回替换后的结果

  • s.replace(begin_index,length,string content); 将指定位置子串替换成成新的结果，长度没限制。
  • s.replace(begin_index,length,be_copyed,copyed_begin,copyed_length,)
  • s.replace(begin_index,legnth,num,char content)替换成num个char字符

sstream头文件 stringstream

学校的普通题挺好用的，竞赛可能就不太行，速度慢。
斯坦福CS106L第一节课就是讲的这个，可惜后面没听了。

#include <bits/stdc++.h>
using namespace std;
int main(){
    string str = "what are you doing now",sub;
    stringstream ss1(str);
    while(ss1 >> sub){
        cout << sub << endl;
    }
    /*
    what
    are
    you
    doing
    now
    */
    str = "123 45.6";
    stringstream ss2;
    ss2 << str;

    int x;
    double y;
    ss2 >> x >> y;
    cout << "x = " <<  x << "y = " << y;
    return 0;
}

其它操作

  • int,long long, double 转字符串： to_string(int);
  • string类型转成int 类型 : stoi("123456");
    • 还有stol stof stoll等
  • 整行读取 while(getline(cin,s)){cout << s << endl;}

stack

  • 没有clear，只能暴力pop
  • 养成习惯，先判断不为空再pop

priority_queue 堆

  • 声明
    • priority_queue<int> heap; 大顶堆
    • priority_queue<int, vector<int>, greater<int> > heap1; // 小顶堆
  • 访问方式：只能top，返回的是堆顶元素的引用。
  • 结构体：
#include <bits/stdc++.h>
using namespace std;
struct pii{
    int x;
    //比较谁的优先级小
    bool operator< (const pii& j)const{ // 语法，两个const
        if(this->x > j.x) return true; // 越大优先级越小，那就是小根堆
        return false;
    }
};
int main(){
    priority_queue<pii>heap;
    heap.push({.x=100});
    heap.push({.x=200});
    cout << heap.top().x << endl;
    return 0;
}

pair

  • 排序先比较first，如果不一样再看second
  • 声明：
    • pair<int,string>p = {3,"haha"};
  • 访问：
    • 点运算符，.first,.second
  • 赋值：
    • p = make_pair(3,"123456");

set

集合，内部元素唯一和自动排序，底层是红黑树。
插入O(LogN) 插入

  • 声明：
    • set<int> ass2 = {3, 4, 2, 3};
    • set<int> ass1;
  • 遍历：auto
  • 常用函数：
    • insert(value);
      • 返回一个pair，if (ass.insert(3).second == false) {失败}
    • erase(value/iterator)
    • size empty count（可以用来确定某个元素是否存在）
    • clear O(N)
    • lower_bound
      • O(logn)的时间复杂度内第一个大于等于指定元素的迭代器，找不到返回end()
      • O(logn)的时间复杂度内第一个大于指定元素的迭代器，找不到返回end()
    • find() 返回查找元素的迭代器，找不到返回end()

unordered_set

存放元素，不会排序。底层时哈希。速度更快一点。

multiset

可以重复，不如map

map

关联容器。底层是红黑树。根据first排序。插入查找修改复杂度都是O(logN)

  • 初始化
    • map<double, long long> mp1;
  • 插入
    • mp.insert({"222", 5});
    • mp["222"] = 5; 如果key存在，修改其value值，否则插入
  • 访问
    • 单个：mp["222"]，记得判断其是否存在，用count
    • 遍历：auto就行了，然后x.first x.second
  • 常见函数
    • erase(key/iterator); 成功返回1，否则返回0
    • 其它跟set基本一样

unordered_map

当hashmap用

deque

双端队列，支持头部尾部的插入和删除，效率比vector低。

list

双向链表，不支持随机访问，支持头部尾部的插入和删除

  • 声明
    • list l2(length,default_value);
  • 函数
    • insert(iterator,val);
    • sort(); 升序排序
    • reverse(); 翻转，学校的小题挺好用的。
    • merge(list2) ：用第二个有序的 list 合并一个有序 list
    • erase(iterator)：删除iterator，返回删除前的下一个的迭代器
    • erase(iterator_start, iterator_end)：删除[iterator_start, iterator_end)范围内的元素，返回删除前的iterator_end
    • splice(list.iterator, list2, list2.iterator_start, list2.iterator_end)：在本list的 iterator后插入list2的从 iterator_start 到 iterator_end， 后面两个可填可以不填，当填了iterator_start，可不填最后一个，时间复杂度O(1)

Algorithm库

sort

  • 形式1：sort(arr,arr+10); 范围[0,10)
  • 形式2：sort(arr+1,arr+9,cmp);bool cmp(int a,int b){return a>b;}
    • cmp可以是封装好的 greater<int>()
  • 形式3：lambda

reverse

翻转，传参和sort一样

lower_bound upper_bound

O(logN)
lower_bound(vt.begin(), vt.end(), value);

可以自己二分实现。

unique

用于将去除一个有序序列中指定范围内的重复元素（实际没有去除）,返回去除后的尾指针
一般这么玩：

sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());

next_permutation

生成全排列，结果是排序的

#include <bits/stdc++.h>
using namespace std;
int main(){
    vector<int> v = {1,2,3,4};
    do{
        for(int i=0;i<v.size();i++){
            cout << v[i];  
        }
        cout << endl;
    }while(next_permutation(v.begin(),v.end()));
}

find

暴力查找一个序列中指定范围内的某个值第一次出现的位置，返回其位置的指针
O(N)

random_shuffle

随机打乱给定范围的序列

参考文章

{% link 一位ACM大佬的总结, https://blog.csdn.net/hao_6_6/article/details/118612536, https://g.csdnimg.cn/static/logo/favicon32.ico %}