好用的STL函数集合

Author Avatar
ajcxsu 2018年07月27日
  • 104 次阅读

持续更新~

非特殊说明应该都属于algorithm头文件

二路归并 $inplace\_merge\ O(n)$

同一数组的归并。
inplace_merge(begin, middle, end)

指针begin~middle-1和middle~end-1的归并。

用该函数写成的归并排序样例程序如下:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int arr[N];

void merge_sort(int l,int r) {
    if(l==r) return;
    int mid=(l+r)>>1;
    merge_sort(l,mid), merge_sort(mid+1,r);
    inplace_merge(arr+l, arr+mid+1, arr+r+1);
}

int main() {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>arr[i];
    merge_sort(1,n);
    for(int i=1;i<=n;i++) cout<<arr[i]<<' ';
    return 0;
}

二分查找 $lower\_bound\ O(n \log n)$

主要讲讲自定义函数的用法。

四个参数:lower_bound(begin, end, val, <compare>),第四个是自定义比较函数,等价于重载<运算符。

bool cmp(const int &a, const int &b) { return a<b; }

cmp一般这么写。
需要提醒的一点是,a是数组里的元素,而b是被比较的元素。

快速查找 $nth\_element\ O(n)$

引用 https://blog.csdn.net/dylan_frank/article/details/77893811

找到数组中的第k大元素,将其放在k位置,左边的元素皆比其小,右边的元素皆比其大,且右边一定有序。
nth_element(first, nth, last)

first,last 第一个和最后一个迭代器,也可以直接用数组的位置。
nth,要定位的第n 个元素,能对它进行随机访问.

nth同属于迭代器。
常用于K-DTree或中位数查找。

字符串库函数(C++11)

类型 wstring 宽字符串,可包含非ASCII字符,如Unicode等

stoi stol stoll 字符串转化为有符号整数
stoul stoull 字符串转化为无符号整数
stof stod stold 字符串转化为浮点数
to_string 整数/浮点数化为string

pop_back 移除末尾字符

本文链接:https://acxblog.site/archives/stl_functions.html
文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。