C++ STL学习笔记

一、C++STL API

1、算法常用模板

include<bits/stdc++.h> //万能头 C++版本4.4以上支持
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    //pass
    return 0;
}

2、algorithm//标准算法库

min(x, y); 
max(x, y);
abs(x); //求绝对值
swap(x, y); //交换x和y的值
reverse(it2, it2); //将数组指针或容器迭代器在[it1,it2)范围内的元素进行翻转
next_permutation(); //给出序列在全排列中的下一个序列
fill(a,b,1); //对数组或容器中某段区间赋值为某个相同的值，样例区间为[a,b)赋值为1
sort(首地址, 尾元素下一个地址, 比较函数(optional)); //比较函数为空时默认递增排序
//实现比较函数的tip: 当cmp(a,b)为true时a放在b之前
//STL标准容器中，vector, string, deque支持sort，内部本身有序的那种不支持排序
lower_bound(first, last, val); //查找数组或容器的[first, last)范围内第一个值大于等于val元素的位置，返回数组指针或容器该位置的迭代器
upper_bound(first, last, val);//查找数组或容器的[first, last)范围内第一个值大于val元素的位置，返回数组指针或容器该位置的迭代器

3、queue//队列

(1)queue

实现先进先出（FIFO）的容器，常用于BFS实现；类似的还有双端队列（deque），首尾均可插入和删除；

定义

queue<typename> instName;

访问

front(); //访问队首元素
back(); //访问队尾元素

常用函数

push(); //入队，复杂度O(1)
pop(); //出队，复杂度O(1)
empty(); //判空，复杂度O(1)
size(); //获取元素个数，复杂度O(1)

常用函数

push_back(); push_front(); //队尾||首入队，复杂度O(1)
pop_back(); pop_front(); //队尾||首出队，复杂度O(1)
front(); back(); //访问队首、队尾
operator[] (size_type n); //访问，复杂度O(1)
empty(); //判空，复杂度O(1)
size(); //获取元素个数，复杂度O(1)

(2)priority_queue//二叉堆

常用：求数组第k个值，

1、二叉堆：

大顶堆：less或自定义用＜操作符
小于号<规定了优先级，表示优先队列后面的元素都要小于优先队列前面的元素，因为优先队列队首的元素优先级最高，优先队列队尾元素的优先级最低，所以小于号<就规定了优先队列后面的元素都要小于优先队列前面的元素（尾部优先级小于首部优先级），也就是形成一个大根堆，降序排序，每次权值最大的会被弹出来。

小顶堆：greater或自定义用＞操作符
这里的大于号>规定了优先级，表示优先队列后面的元素都要大于优先队列前面的元素，因为优先队列队首的元素优先级最高，优先队列队尾元素的优先级最低，所以大于号>就规定了优先队列后面的元素都要大于优先队列前面的元素（尾部优先级小于首部优先级），也就是形成一个小根堆，升序排序，每次权值最小的会被弹出来。

每当插入一个数后，优先队列会根据优先级自动调整好结构。

2、默认是以数字大为优先级

3、可设置优先级

priority_queue<typename, vector<typename>, cmp_fn> instName;
cmp_fn 可使用 less<typename>: 设置大顶堆，以及greater<typename>: 设置小顶堆
push(); //push(x)，将x入队，复杂度O(logN)
pop(); //队首元素出队，复杂度O(logN)
empty(); //判空，复杂度O(1)
size(); //返回元素个数，复杂度O(1)
top();//返回顶部元素

4、自定义队列的比较方式

struct myComparison{//创建结构体
     bool operator()(pair<int,int>&p1,pair<int,int>&p2){
           return p1.second>p2.second;//小顶堆是大于号
        }
     };
//创建优先队列
priority_queue<pair<int,int>,vector<pair<int,int>>,myComparison> q;//最后一个参数放入结构体

4、stack//栈

后进先出的容器，

基本定义方式：

stack<typename> instName;

2.常用函数

push(); //元素入栈，复杂度O(1)
top(); //获得栈顶元素，复杂度O(1)
pop(); //弹出栈顶元素，复杂度O(1)
empty(); //判空，复杂度O(1)

5、utility

常用于将两个元素捆绑成为合成元素，以及用于构造map的键值对；

定义

pair<typename1, typename2> instName;
//example1: 
pair<string, int> p("example",0);
//example2: 
make_pair("example",0);

常用函数

//比较操作数<=、>=等，pair可以直接比较，默认先以first大小作为标准，当fisrt相等时使用second;

6、vector//数组

相当于Java的ArrayList数据结构，可加入泛型。

URL :https://zhuanlan.zhihu.com/p/150118797

1、初始化

一维使用：vector<type> name

直接赋值（C++11支持）：vector<int> name = {1,1,1};
return {-1,-1};//返回数组

直接赋值：利用数组，初始化成vector容器
int i[2] = {0,1};
vector<int> ii(i,i+2);

一维使用并且开空间赋初值：vctor<type> name(size,initValue)

二维使用：vector<vector<type>> name

初始化开空间：vector.resize(capacity)

对于二维数组：

    vector.resize(capacity) //初始化一维空间

    for(int i =0; i<n;i++){//初始化二维空间

      order[i].resize(capacity);

    }

2、函数方法

长度：vector.size()

begin(); end(); rbegin(); rend(); //返回迭代器，r为reversed的缩写

empty(); //判空

front(); back(); //返回vector的首/尾值

push_back(); //尾部添加元素，复杂度O(1)

pop_back(); //尾部删除元素，复杂度O(1)

size(); //获取元素个数

clear(); //清空所有元素，复杂度O(N)

insert(it,value); //向任意迭代器it处插入一个元素value, 复杂度O(N)，功能同emplace()

erase(); //可删除单个元素:erase(it)，或删除区间[first, larst)内所有元素:erase(first_it, last_it)

swap(vector& x); //与另外一个vector container交换数据

3、排序

自定义排序（顺序）：

1、直接使用lambda表达式
自定义按照二维数组
sort(courses.begin(),courses.end(),[](vector<int>& o1,vector<int>& o2){//lambda表达式
      return o1[1] > o2[1];//根据vector[][1]降序排序，大于号 表示数组前面的元素要大于后面的元素。
  });
2、自定义函数（降序排序）
bool cmp_max(int x,int y){
    return x > y;
}

int main() {
    int a[] = {8,6,2,9,3,5,4,1,7,10};
    vector<int> arr(a, a+5);
    sort(arr.begin(),arr.end(),cmp_max);
    for(int i = 0; i <arr.size(); ++i){
        cout <<arr[i] << " ";
    }
    return 0 ;
}
output：9 8 6 3 2
3、vector局部排序
bool cmp_max(int x,int y){
    return x > y;
}
vector<int> array = {1,2,3,4,5};
sort(array.begin(),array.begin()+3,cmp);//对[0,3)下标之间进行逆序排序
output:3 2 1 4 5
    
sort(array.begin()+1,array.begin()+5,cmp);//对[1,5)下标之间进行逆序排序
output:1 5 4 3 2
    
sort(array.begin(),array.end()-2,cmp);//对[0,2)下标之间进行逆序排序
output:3 2 1 4 5

7、string//字符串

定义：

string str;
string str = "example string";

访问：可通过下标或迭代器，与vector基本类似
常用函数：

append()：从后方插入字符串
直接字符串相加：
    string a = "hello";
    string b = "hello";
    for(int i = 0; i < 100; ++i)
    {
        a = b + a;
    }
//operator+=, 用于字符串拼接
//compare operator: ==、!=、<=、>=等，基于字典序比较大小
length()/size(); //返回string长度
insert(); //插入字符串，复杂度O(N)
//insert(pos, string)-->在pos未知插入字符串string
//insert(it, it2, it3)-->迭代器指示的string it位置上插入串[it2,it3]
erase(); //删除单个或区间内元素，与vector中erase用法基本一致，复杂度O(N)
clear(); //清空，复杂度O(1)
substr(); //substr(pos, len)返回pos位置开始长度为len的字串，复杂度O(len)
find(); 
//str.find(str2), 当str2是str的字串时，返回其在str中第一次出现的位置，否则返回string:npos
//str.dinf(pos, str2), 从str的pos位置开始匹配, 复杂度O(mn), m、n为str和str2的长度
string:npos; //常数(=-1, or 4294967295, max value of unsigned_int)，一般作为find函数失配时的返回值
replace(); //replace(pos, len, str2), 把str从pos号位开始长度为len的字串替换为str2; 
//replace(it1, it2, str2), 把str的迭代器[it1, it2)范围的字串替换为str2; 复杂度为O(str.length())

1、string与int互转(C++11不支持)
stoi(str, 0, 2); //将字符串 str 从 0 位置开始到末尾的 2 位置转换为十进制
stoi(str);//将“字符串”转为十进制
stod()//“字符串”转换为double
to_string(char c)//重载方法，将一些整形，浮点型等转换为string类型字符串
2、string与int互转
// int 转 string
  int number = 12;
  string str;
  stringstream ss;
  ss<<number;
  ss>>str;
  cout<<str;
 //注意，此时这个流中还留有之前流入的数据。
 ss.clear();  //清楚这个流中残留的数据

 //string 转 int
  string str2 = "13";
  int num;
  ss<<str2;
  ss>>num;
  cout<<num;
2、char与int互转，string[index]是char类型
'1'-'0'(输出int类型的1)：char转int，使用ASCII码方法
int转char：
    char z1 = 1 +'0';
    cout<<z1<<endl;//'1'
    cout<<char(1 +'0')<<endl;//'1'
    cout<< 1 +'0'<<endl;//'49'，此处输出的是1的ASCII值，而不是字符

8、map//映射

映射，可以将任何基本类型映射到任何基本类型（包含STL容器）；内部由红黑树实现，因此建立映射过程中自动有序（从小到大）；若需要一个key对应多个值，可以使用multimap；C++11中增加了散列实现的unordered_map，速度比红黑树实现的map要快很多.

常用用途为：

需要建立字符串与整数/字符串间的映射；
判断大整数或其他类型数据是否存在时，把map当bool数组使用；

定义

map<typename1, typename2> instName;

访问：通过下标或迭代器

通过迭代器访问时，it->first用来访问key, it->second用来访问value

常用函数

//[]复杂度O(logN)，等价于(*((this->insert(make_pair(k,mapped_type()))).first)).second
operator[] (const key_type& k); //当key k存在时返回value的reference，否则构造新的k-v对，并初始化v
insert(const value_type& val); //插入新k-v pair，一般需要通过std::pair构造，如: std::pair<char,int>('a',100)
find(const key_type& k); //find(key)返回键为key的映射迭代器，时间复杂度O(logN)
count(const key_type& k); //只能为1或者0，功能等价于find();
erase(); //可删除单个元素:erase(it)，复杂度O(1);erase(key),删除键为key的键值对，复杂度O(logN)
size(); //获取元素个数，复杂度O(1)
empty(); //判空
clear(); //清空元素，复杂度O(N)
lower_bound (const value_type& val); //参考https://gendml.oss-cn-hangzhou.aliyuncs.com/picgo头文件下常用函数

9、set//集合

set，集合，为内部自动有序(note: 增序)且不含重复元素的容器，内部由红黑树实现。相似的容器为multiset，内部可以允许有重复元素；unordered_set，可以去重但是无序，内部由散列实现，速度比set要快很多。

定义：

set<typename> instName;

访问：一般通过迭代器访问

set<typename>::iterator it; //通过*it访问set的元素，但注意只能使用for-loop枚举，不支持*(it+i)的方式访问
//NOTE: 只有vector和string支持*(it+i)的访问方式

常用函数：

begin(); end(); rbegin(); rend(); //返回迭代器，r为reversed的缩写
// Capacity
size(); //获取set内元素个数，复杂度O(1)
empty(); //判空
// Modifiers
insert(); //insert(x)将x插入容器中，时间复杂度O(logN)
erase(); //可删除单个元素:erase(it)，复杂度O(1);或删除区间[first, larst)内所有元素:erase(first_it, last_it),复杂度O(logN)
clear(); //清空set中所有元素，复杂度O(N)
// Operations
find(); //返回set中对应值为value的迭代器，时间复杂度O(logN)
count(); //Count elements with a specific value
lower_bound (const value_type& val); //参考https://gendml.oss-cn-hangzhou.aliyuncs.com/picgo头文件下常用函数

10、cmath//数学函数库

int abs(int n) 求n的绝对值
double cos/sin/tan(double x) 求x的三角函数值（x为弧度值）
double exp(double x) 求e的x次方
double pow(double x,double y) 求x的y次方
double sqrt(double x) 求x的平方根

11、cstdio//IO（C）

scanf("%d", &a);//格式化输入
printf("%.2f\n", b);//格式化输出

12、cstdlib//工具库（C）

/*
    C语言中的字符串为char *temp
    C++为string
*/

atoi(const char* str)//将一串“字符”转换为int型（注意参数类型是const char*）
atof(const char* str)//同上，转换为double型（注意参数类型是const char*）
string1.c_str()：string转const char*
abs(int n)//取绝对值
fill()//区域赋值
/*    int a[10];
      vector<int> vt;
      fill(a, a+10, 100000);
      fill(vt.begin(), vt.end(), -100000);
*/
sort(vt.begin(), vt.end(), cmp);//时间复杂度n*log(n)的排序算法，默认升序
max(int a, int b)//取最大值
min(int a, int b)//取最小值
strcmp(char* str1, char* str2)//比较两个字符串，前一个小返回<0，前一个大返回>0，否则返回0
strcpy(char* destination, char* source)//将后一个字符串拷贝到前一个字符串
strlen(char* str)//返回字符串str的有效长度
isalnum()//判断一个字符是不是alphanumeric，即大小写英文字母或是数字
isalpha()//判断一个字符是不是alphabetic，即英文字母
isdigit()//判断一个字符是不是数字
tolower()//将大写转换为小写
toupper()//将小写转换为大写

13、cstring（C）

c语言的字符串库

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。