好用的STL函数集合

Author Avatar
空気浮遊 2018年07月27日
  • 在其它设备中阅读本文章
  • STL
  • 分享到 Facebook
  • 分享到 Telegram
  • 分享到 Twitter
  • 分享到微博

持续更新~

非特殊说明应该都属于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://pst.iorinn.moe/archives/stl_functions.html
许可: https://pst.iorinn.moe/license.html
若无特别说明,博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆

      新篇
旧篇      
    • fingerprint Login
  • home 主页
  • inbox 归档
    • December 2024 1
    • August 2024 1
    • June 2024 1
    • April 2024 3
    • March 2024 1
    • February 2024 2
    • January 2024 1
    • November 2023 1
    • August 2023 1
    • May 2023 1
    • February 2023 2
    • January 2023 2
    • July 2022 1
    • June 2022 1
    • April 2022 1
    • March 2022 1
    • February 2022 2
    • December 2021 1
    • November 2021 1
    • August 2021 3
    • July 2021 3
    • April 2021 2
    • March 2021 1
    • February 2021 4
    • January 2021 2
    • December 2020 1
    • November 2020 1
    • October 2020 3
    • September 2020 1
    • August 2020 1
    • July 2020 1
    • March 2020 1
    • December 2019 1
    • September 2019 1
    • July 2019 1
    • April 2019 2
    • March 2019 13
    • February 2019 15
    • January 2019 11
    • December 2018 3
    • November 2018 6
    • October 2018 28
    • September 2018 32
    • August 2018 19
    • July 2018 13
    • June 2018 27
    • May 2018 11
    • April 2018 12
    • March 2018 19
    • February 2018 8
    • January 2018 7
    • December 2017 2
    • November 2017 2
  • apps 分类
    • 笔记
    • 题解
    • 杂文
    • 技术
    • 游戏
    • 小说
  • 留言板
  • 关于
  • 友链
  • 文章总数 282
主题 - Material i
expand_less
Copyright © 2025 雪屋
Float in air.
Powered by Typecho
Theme - Material