C++ STL函数总结

STL 函数

accumulate

accumulate(begin, end, init)
复杂度：O(N)

对序列元素求和，begin 和 end 是始末位置的迭代器（左闭右开），init 是加上的初始值。返回求和结果，数据类型与 init 相同。

基础累加求和

int a[]={1,3,5,9,10};
//对[0,2]区间求和，初始值为0，结果为0+1+3+5=9
int res1 = accumulate(a, a + 3, 0);
//对[0,3]区间求和，初始值为5，结果为5+1+3+5+9=23
int res2 = accumulate(a, a + 4, 5);

自定义二元对象求和

使用 lamda表达式

typedef long long ll;
struct node {
    ll num;
} st[10];
for(int i = 1; i <= n; i++)
    st[i].num = i + 10000000000;
//返回值类型与init一致，同时注意参数类型（a）也要一样
//初始值为1，累加1+10000000001+10000000002+10000000003=30000000007
ll res = accumulate(st + 1, st + 4, 1ll, [](ll a,node b) {
    return a + b.num;
});

atoi

atoi(const char*)，将字符串转换为 int 类型。

注意参数为 char 型数组，如果需要将 string 类型转换为 int 类型，可以使用 stoi 函数，或者将 string 类型转换为 const char * 类型。

关于输出数字的范围：

atoi 不做范围检查，如果超出上界，输出上界，超出下界，输出下界。
stoi 会做范围检查，默认必须在 int 范围内，如果超出范围，会出现 RE（Runtime Error）错误。

string s = "1234";
int a = atoi(s.c_str());
cout << a << endl; // 1234
// 或者
char s[] = "1234";
int a = atoi(s);
cout << a << endl;

stoi 同理

fill

fill(beg, end, num)，复杂度 O(N)，对一个序列进行初始化赋值。

//对a数组的所有元素赋1
int a[5];
fill(a,a+5,1);
for(int i=0; i<5; i++)
    cout << a[i] << endl;
//1 1 1 1 1

memset() 是按字节进行赋值，对于初始化赋 0 或 -1 有比较好的效果，如果赋某个特定的数会出错，赋值特定的数建议使用fill()

is_sorted

is_sorted(beg, end)，复杂度 O(N)，判断序列是否有序，返回 bool 值。

1
2
3

//如果序列有序，输出YES
if(is_sorted(a, a+n))
    cout << "YES" << endl;

iota

iota(beg, end, init)，让序列递增赋值。

vector<int> a(10);
iota(a.begin(), a.end(), 0);
for(auto i : a)
    cout << i << " ";
// 0 1 2 3 4 5 6 7 8 9

lower_bound

lower_bound(beg, end, x)，复杂度 O(logN)，二分查找。

//在a数组中查找第一个大于等于x的元素，返回该元素的地址
lower_bound(a, a + n, x);
//在a数组中查找第一个大于x的元素，返回该元素的地址
upper_bound(a, a + n, x);
//如果未找到，返回尾地址的下一个位置的地址

min_element

min_element(beg, end)，复杂度 O(N)，返回序列最小值的地址。

1
2
3

//函数都是返回地址，需要加*取值
int mx = *max_element(a, a + n);
int mn = *min_element(a, a + n);

min

复杂度 O(1)，找多个元素的最大值最小值。

//找a，b的最大值和最小值
mx = max(a, b);
mn = min(a, b);
//找到a,b,c,d的最大值和最小值
mx = max({a, b, c, d});
mn = min({a, b, c, d});
// minmax，输入两个值，返回 pair 类型，头文件<algorithm>
pair<int, int> t = minmax(4, 2);
// t.first = 2, t.second = 4

minmax_element

minmax_element(beg, end)，复杂度 O(N)，返回序列中的最小和最大值组成 pair 的对应的地址。

int n = 10;
vector<int> a(n);
iota(a.begin(), a.end(), 1);
auto t = minmax_element(a.begin(), a.end());
// *t.first = 1, *t.second = 10 输出对应最小最大值时需要使用指针

nth_element

nth_element(beg, nth, end)，平均复杂度 O(N)，寻找序列第 n 小的值。

nth 为一个迭代器，指向序列中的一个元素。第 n 小的值恰好在 nth 位置上。执行 nth_element() 之后，序列中的元素会围绕 nth 进行划分：nth之前的元素都小于等于它，而之后的元素都大于等于它。

1
2
3

// 求序列中的第3小的元素
nth_element(a, a + 2, a + n);
cout << a[2] << endl;

next_permutation

next_permutation(beg, end)，复杂度 O(N)，求序列的下一个排列，下一个排列是字典序大一号的排列。返回 bool 值，如果是最后一个排列，返回 false ,否则求出下一个序列后，返回 true。

求 a 所有的排列。

// 数组a不一定是最小字典序序列，所以将它排序
sort(a, a + n);
do {
    for(int i = 0; i < n; i++)
        cout << a[i] << " ";
    cout << endl;
} while(next_permutation(a, a + n));

同理有 prev_permutation(beg, end)

partial_sort

partial_sort(beg, mid, end)，复杂度大概 O(NlogM)，M 为距离。部分排序，排序 mid-beg 个元素，mid 为要排序区间元素的尾后的一个位置，从 beg 到 mid 前的元素都排好序。

int a[] = {1,2,5,4,7,9,8,10,6,3};
partial_sort(a, a + 5, a + 10);
for(int i = 0; i < 10; i++) 
    cout << a[i] << " ";
//1 2 3 4 5 9 8 10 7 6 前五个元素都有序

也可以添加自定义排序规则：

partial_sort(beg, mid, end, cmp)

int a[] = {1,2,5,4,7,9,8,10,6,3};
partial_sort(a, a + 5, a + 10, greater<int>());
for(int i = 0; i < 10; i++) 
    cout << a[i] << ' ';
//10 9 8 7 6 1 2 4 5 3
//前五个元素降序有序

shuffle

shuffle(beg, end)，复杂度 O(N)，随机打乱。

1
2
3

vector<int> b(n);
iota(b.begin(), b.end(), 1);
shuffle(b.begin(), b.end());

reverse

reverse(beg, end)，复杂度 O(N)，翻转序列。

1
2
3

string s = "abcde";
reverse(s.begin(), s.end());//对s进行翻转
cout << s << endl;//edcba

sort

sort(beg, end)，复杂度 O(NlogN)，对序列排序。

//对a数组的[0,n-1]位置从大到小排序
sort(a, a + n, greater<int>());
//对a数组的[0,n-1]位置从小到大排序
sort(a, a + n);
//自定义排序，定义比较函数
bool cmp(node a, node b) {
    return a.x > b.x;
}
sort(node, node + n, cmp);

stable_sort 不会改变相等元素的相对位置

transform

transform(beg, end, dest, unaryOp)，复杂度 O(N)，使用给定操作，结果写入 dest。

1
2
3

//大小写转换，把结果存到起始地址为dest的序列中
transform(beg, end, dest, ::tolower);
transform(beg, end, dest, ::toupper);

to_string

将数字转化为字符串，支持小数（double）

1 2	int a = 12345678; cout << to_string(a) << endl;

unique

unique(beg, end)，复杂度 O(N)，消除重复元素，返回消除完重复元素的下一个位置的地址。

如：a[] = {1,2,3,3,4}，unique 之后 a 数组为 {1,2,3,4,3} 前面为无重复元素的数组，后面则是重复元素移到后面，返回 a[4] 位置的地址（不重复元素的尾后地址）

消除重复元素一般需要原序列是有序序列

离散化

for(int i = 0; i < n; i++) {
    cin >> a[i];
    b[i] = a[i]; //将a数组复制到b数组
}
sort(b, b + n);
unique(b, b + n);//消除b重复元素
for(int i = 0; i < n; i++) {
    //因为b有序，查找到的下标就是对应的相对大小（离散化后的值）
    int pos = lower_bound(b, b + n, a[i]) - b;
    a[i] = pos;//赋值
}