C++ STL(标准模板库)引入及使用 1

2021-08-17

如题目＞▽＜

引用 Reference

是一个别名，相当于给其取个小名（蟑螂和小强都指代一个东东）,可以增强代码可读性
1
2
3
4
5
int zhanglang[3]={1,2,3};
for(int i=0;i<3;i++){
const &p=zhanglang[i];
cout<< p<<endl;
}

函数传参：相当于传入地址

void _swap(int &x,int &y){
    int t=x;
    x=y;
    y=t;
}

类 class struct

一个构造器

// struct是访问权限为public的class
class _class{
    public:
    int num;
    _class(int _num):num(_num){}
};

// struct是访问权限为public的class
struct _class_struct{
    int num;
    _class_struct(int _num):num(_num){}
};

struct node{
    int u,v,w;
    node(int _u=0,int _v=0,int _w=0):u(_u),v(_v),w(_w){}
};

new一个对象

1
2
3

_class a=_class();//先new出对象，再拷贝到新的对象中
_class a(123456);// previous: _class(int _a){a(_a);} 有参构造
_class a;//无参构造

重载运算符

格式：[返回值][operator][运算符][参数列表][const][body]

struct node{
    int u,v,w;
    node(int _u=0,int _v=0,int _w=0):u(_u),v(_v),w(_w){}
    bool operator<(const node&_node) const{// 成员变量重载
        return w<_node.w;
    }
    bool friend operator>(node &node_a,node &node_b){//友元变量重载
        return node_a.w>node_b.w;
    }
};
int operator+(node &_node_a,node &_node_b){// 类外重载
    return _node_a.w+_node_b.w;
}

匿名函数 lambda expressions

可以在函数中定义函数的骚操作（常用于sort中的cmp函数定义）,当然也可以将其实名化

auto func=[](int a,int b){
    return a+b;
}
cout<<func(1,2);

int a[3]={1,2,3};
sort(a,a+3,[](int a,int b){return a>b;});
//也可以使用greater(降序)排序方式进行排序(升序为less)
//sort(a,a+3,greater<>());
for(int i=0;i<3;i++){
    cout<<a[i]<<endl;
}

pair<T1,T2>

//tip1
using pii =pair<int,int>;//常用的int型pair
//or:
typedef pair<int,int> pii;
#define pii pair<int,int>

//tip2
#define x first//在访问pair成员时可以用x，y来直观地引用
#define y second

//ctor(constructor)
pii p(1,2);
pii a=make_pair(3,4);
auto b=a;
cout<<p.x<<"="<<p.first;

pair<int,pii>pill(12345,make_pair(123,234));//可以pair套pair
// 默认重载小于号< 依照first排序
puts(a<b?"less":"greater");

迭代器 Iterator

Container->Iterator->Algorithm(容器通过迭代器调用算法)
类似于指针,通过迭代器访问容器的值
分类
正向迭代器
1
container::iterator it;
反向迭代器
1
container::reverse_iterator it;
使用

使用auto关键帧循环

map<int, int> dsk;
for (auto it : dsk) {
  cout<<it.second<<" ";
}

正常遍历

using Iter=vector<int>::iterator;//迭代器重命名，方便使用
vector<int> dsk = {1, 2, 3, 4, 5};
    for (Iter it = dsk.begin(); it != dsk.end();it++){
        cout << *it << " ";
    }

排序 sort&stable_sort

sort(begin,end,cmp);
begin：头迭代器
end：尾迭代器

cmp：排序方式

int arr[]={1,1,4,5,1,4,114514,-114514,19260817};
int n=sizeof(arr)/sizeof(arr[0]);
sort(arr,arr+n);//默认升序排列
sort(arr,arr+n,greater<>());//降序排列

stable_sort(arr,arr+n);//稳定排序，不会打乱原有相同元素的位置关系，相当于使用归并排序
vector<int> dsk={1,1,4,5,1,4,114514,-114514,19260817};
sort(dsk.begin(),dsk.end());//升序
sort(dsk.rbegin(),dsk.rend());//降序,使用反向迭代器的骚操作

二分查找 lower_bound&upper_bound

在有序容器中，使用二分的方式查找元素
lower_bound:查找到第一个大于等于目标值的元素，返回迭代器

upper_bound:查找到第一个大于目标值的元素，返回迭代器

int arr[]={1,1,4,5,1,4,114514,-114514,19260817};
int n=sizeof(arr)/sizeof(arr[0]);
sort(arr,arr+n);//升序排列
int pos=lower_bound(arr,arr+n,114514)-arr;//获得待查找元素的相对位置
auto acl=lower_bound(arr,arr+n,114514);//获得待查找元素的迭代器
cout<<arr[pos]<<"="<<*acl<<endl;

sort(arr,arr+n,greater<>())//降序排列
int pos=lower_bound(arr,arr+n,114514,greater<>())-arr;//在递减的时候，我们需要greater仿函数龟腚比较方向
auto acl=lower_bound(arr,arr+n,114514);//获得待查找元素的迭代器
cout<<arr[pos]<<"="<<*acl<<endl;

一些简单算法

两级反转 reverse

将能够双向查询的迭代器翻转过来

int arr[]={1,2,3,4,5,6,7,8};
int n=sizeof(arr)/ sizeof(arr[0]);
reverse(arr,arr+n);
//reverse(begin(arr),end(arr));//另一种写法，不常用

string orl="ybbbby";
string rev(orl);//拷贝赋值，效率高一点，也可以写成rev=rel
reverse(rev.begin(),rev.end());
puts(orl==rev?"Yes":"No");//简单回文串判定

填充 fill&fill_n

快速填充一段区间内的值（相当于memset）

int arr[]={1,2,3,4,5,6,7,8};
int n=sizeof(arr)/ sizeof(arr[0]);
fill(arr,arr+n,0);
fill_n(arr,n,0);

最大公约数 gcd

1	cout<<__gcd(2,4);

排列

生成全排列(n!复杂度，少用)

int orl[]={2,1,3};
sort(olr,olr+3);
do{
    cout << orl[0] << orl[1] << orl[2] << endl;
} while (next_permutation(orl, orl + 3));//升序全排列
//} while (prev_permutation(orl, orl + 3));//降序全排列