C++算法中的一些常用库函数

目录

1. 算法库algorithm

​ 1.1 交换函数swap

​ 1.2 最大/小值函数

​ 1.3 排序函数sort

​ 1.4 查找函数find

​ 1.5 逆序函数reverse

​ 1.6 去重函数unique

​ 1.7 二分搜索函数

​ 1.8 全排列next_permutation

2. STL常用容器

​ 2.1 字符串string

​ 2.2 动态数组vector

​ 2.3 双向链表list

​ 2.4 栈stack

​ 2.5 队列queue

​ 2.6 集合set

​ 2.7 字典map

3. 其他函数

3.1 数字与字符串之间的转换

 

1. 算法库algorithm

#include<algorithm>

1.1 交换函数swap

swap(a,b) 交换a,b

int a[3] = { 1, 2, 3 };
swap(a[1], a[2]);
for (int i = 0; i < 3; i++)
    cout << a[i] << " ";//1 3 2 

 

1.2 最大/小值函数

max(a,b) 返回a,b中的较大者

min(a,b) 返回a,b中的较小者

max_element(begin,end) 返回指定范围内指向首个最大值的迭代器（迭代器可以简单理解为指针）

min_element(begin,end) 返回指定范围内指向首个最小值的迭代器

int a[5] = { 5, 9, 8, 1, 6 };
cout << max(a[1], a[2]) << endl;//9
cout << min('A', 'a') << endl;//A 使用ascii码进行比较
cout << "最大值为" << *max_element(a, a + 5) << "，下标为" << max_element(a, a + 5) - a << endl;//最大值为9，下标为1
cout << "最小值为" << *min_element(a, a + 5) << "，下标为" << min_element(a, a + 5) - a << endl;//最小值为1，下标为3

 

1.3 排序函数sort

数组、字符串、容器均可使用

升序：sort(begin, end, less())或sort(begin, end)（第三个参数省略则默认为升序）
降序：sort(begin, end, greater())

int a[5] = { 5, 3, 9, 8, 2 };
sort(a, a + 5);//升序，排序范围从a[0]到a[4]
for (int i = 0; i < 5; i++)
    cout << a[i] << " ";//2 3 5 8 9 
cout << endl;
sort(a, a + 5, greater<int>());//降序
for (int i = 0; i < 5; i++)
    cout << a[i] << " ";//9 8 5 3 2 

 

1.4 查找函数find

find(begin,end,element) 在指定范围内查找元素element，找到返回指向元素的迭代器，找不到返回尾迭代器end（指向最后一个元素的后一位）

这种方法常用来判断数组或容器中是否含有某元素

int a[5] = { 5,9,6,8,2 };
int *res = find(a, a + 5, 8);
if (res != a + 5)
    cout << "找到，元素下标为" << res - a << endl;//找到，元素下标为3
else cout << "没找到" << endl;
res = find(a, a + 5, 4);
if (res != a + 5)
    cout << "找到，元素下标为" << res - a << endl;
else cout << "没找到" << endl;//没找到

 

1.5 逆序函数reverse

reverse(begin,end)

int a[5] = { 5,9,6,8,2 };
reverse(a, a + 5);
for (int i = 0; i < 5; i++)
    cout << a[i] << " ";//2 8 6 9 5 

 

1.6 去重函数unique

使用前需要数据已排序

unique(begin,end) 返回指向首个开始重复元素的迭代器

int a[9] = { 1, 1, 3, 1, 2, 5, 9, 7, 5 };
sort(a, a + 9);
int *p = unique(a, a + 9);
for (int i = 0; i < 9; i++)
    cout << a[i] << " ";//1 2 3 5 7 9 5 7 9 
cout << endl;
for (int i = 0; i < p - a;i++)
    cout << a[i] << " ";//1 2 3 5 7 9 

 

1.7 二分搜索函数

使用前需要数据已排序

binary_search(begin,end,element) 在指定范围内查找是否含有元素element，找到返回true，找不到返回false

lower_bound(begin,end,element) 返回指向首个不小于element的元素的迭代器，若不存在返回尾迭代器end

upper_bound(begin,end,element) 返回指向首个不大于element的元素的迭代器，若不存在返回尾迭代器end

int a[5] = { 5, 9, 8, 1, 6 };
sort(a, a + 5);//a:1 5 6 8 9
if (binary_search(a, a + 5, 1))cout << "找到" << endl;//找到
else cout << "没找到";
if (lower_bound(a, a + 5, 4) != a + 5)cout << "下标为" << lower_bound(a, a + 5, 4) - a << endl;//下标为1
if (upper_bound(a, a + 5, 8) != a + 5)cout << "下标为" << upper_bound(a, a + 5, 8) - a << endl;//下标为4

 

1.8 全排列next_permutation

按字典序进行排列，使用时一般需要原数据已排序

常用结构：

do
{
    
}while(next_permutation(begin,end));

例如求1,2,3三个数的全排列：

int a[3] = { 1, 2, 3 };
do
{
    for (int i = 0; i < 3; i++)
        cout << a[i] << " ";
    cout << endl;
} while (next_permutation(a, a + 3));
//1 2 3
//1 3 2
//2 1 3
//2 3 1
//3 1 2
//3 2 1

 

2. STL常用容器

2.1 字符串string

#include<string>

常用操作：

函数名	功能
at(i)或[i]	返回位置i处的字符
size()或ength()	返回字符串长度
push_back(ch)	在字符串尾部插入字符ch
begin()	返回字符串的头迭代器
end()	返回字符串的尾迭代器
insert(p,ch)	在迭代器p前插入字符ch
append()或+=	连接字符串，类似C库函数strcat
erase(p)	删除迭代器p处的字符
replace(p,n,s0)	将从位置p开始的n个字符替换成字符串s0
find(s0,p)	从位置p处开始查找字符串s0 p省略不写则默认为0（即从开头开始查找） 找到返回首字母位置，找不到返回string::npos
rfind(s0,p)	从位置p开始逆向查找，p省略则从末尾开始查找，返回值同上
substr(p,n)	返回截取的字符串，p为开始位置，n为截取长度
clear()	清空字符串

string s = "Hello";
cout << s.at(1) << endl;//e
cout << s[1] << endl;//e
cout << s.size() << endl;//5
cout << s.length() << endl;//5
s.insert(s.end(), ',');
cout << s << endl;//Hello,
s.append("world");
cout << s << endl;//Hello,world
s += "!";
cout << s << endl;//Hello,world!
s.erase(s.end() - 1);
cout << s << endl;//Hello,world
s.replace(6, 5, "C++");
cout << s << endl;//Hello, C++
if (s.find("llo") != string::npos)
    cout << s.find("llo") << endl;//2
else cout << "Not Found" << endl;
cout << s.rfind("l") << endl;//3
s.clear();
cout << s << endl;//

 

2.2 动态数组vector

#include<vector>

可以在添加元素时增加长度的数组称为动态数组，亦称向量。

常用操作：

函数名	功能
at(i)或[i]	返回位置i处的元素
size()	返回向量的元素数
push_back(x)	在向量末尾添加元素x
pop_back()	删除向量的最后一个元素
begin()	返回向量的头迭代器
end()	返回向量的尾迭代器
insert(p,x)	在迭代器p前插入元素x
erase(p)	删除迭代器p处的元素
clear()	清空向量

vector<int>v;//定义一个空的vector
v.push_back(2);//v:2
v.push_back(1);//v:2 1
v.push_back(3);//v:2 1 3
v.pop_back();//v:2 1
v.insert(v.end(), 3);//v:2 1 3
v.erase(v.begin()+1);//v:2 3
v.push_back(1);//v:2 3 1
sort(v.begin(), v.end());//v:1 2 3

遍历向量的三种方法：

• //普通数组法
  for (int i = 0; i < v.size(); i++)
      cout << v[i] << " ";
  

• //迭代器法
  for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
      cout << *it << " ";
  

• //foreach法，C++11新特性，类似于JAVA中的foreach循环和Python中的for循环
  for (auto x : v)
      cout << x << " ";
  

 

2.3 双向链表list

#include<list>

链表是一种可以灵活插入和删除元素的数据结构。

常用操作：

函数名	功能
size()	返回链表的元素数
begin()	返回链表的头迭代器
end()	返回链表的尾迭代器
push_front(x)	向表头添加元素x
push_back(x)	向表尾添加元素x
pop_front()	删除表头的元素
pop_back()	删除表尾的元素
insert(p,x)	在迭代器p前插入元素x
erase(p)	删除迭代器p处的元素
clear()	清空链表

list<int>l;
l.push_back(2);//l:2
l.push_front(3);//l:3 2
l.insert(l.end(), 5);//l:3 2 5
l.insert(l.begin(), 4);//l:4 3 2 5
l.insert(++l.begin(), 7);//l:4 7 3 2 5 不能使用l.begin()+1，只有连续内存空间容器（如vector、string等）才可以这样用
l.insert(l.begin()++, 6);//l:6 4 7 3 2 5
l.pop_back();//l:6 4 7 3 2
l.pop_front();//l:4 7 3 2
list<int>::iterator it;//声明迭代器it
it = find(l.begin(), l.end(), 3);
if (it != l.end())l.erase(it);//如果找到3则删除它
for (auto x : l)
    cout << x << " ";
//4 7 2 

链表的遍历可以使用迭代器法。

 

2.4 栈stack

#include<stack>

栈是一种后入先出的数据结构。

常用操作：

函数名	功能
size()	返回栈的元素数
top()	返回栈顶的元素
pop()	删除栈顶的元素
push(x)	向栈顶添加元素x
empty()	栈为空时返回true，否则返回false

遍历栈：

stack<int>s;
s.push(1);//s:1
s.push(2);//s:1 2
s.push(3);//s:1 2 3
//while循环法
while (!s.empty())
{
    cout << s.top() << " ";
    s.pop();
}
//3 2 1 

 

2.5 队列queue

#include<queue>

队列是一种先入先出的数据结构。

常用操作：

函数名	功能
size()	返回队列的元素数
front()	返回队首的元素
pop()	删除队首的元素
push(x)	向队尾添加元素x
empty()	队列为空时返回true，否则返回false

遍历队列：

queue<int>q;
q.push(1);//q:1
q.push(2);//q:1 2
q.push(3);//q:1 2 3
//while循环法
while (!q.empty())
{
    cout << q.front() << " ";
    q.pop();
}
//1 2 3 

 

2.6 集合set

#include<set>

set是根据元素值进行排序的集合，所插入的元素在集合中唯一，不存在重复元素。

常用操作：

函数名	功能
size()	返回集合的元素数
begin()	返回集合的头迭代器
end()	返回集合的尾迭代器
insert(x)	向集合中插入元素x
erase(x)	删除元素x
find(x)	查找元素x，找到返回指向元素的迭代器，找不到返回尾迭代器
clear()	清空集合

set<int>s;
s.insert(2);//s:2
s.insert(1);//s:1 2
s.insert(2);//s:1 2
s.insert(3);//s:1 2 3
s.erase(2);//s:1 3
if (s.find(2) != s.end())
    cout << "找到" << endl;
else cout << "没找到" << endl;

set由平衡二叉搜索树实现，因此元素的搜索、插入、删除操作的复杂度在$O(logn)$。

 

2.7 字典map

#include<map>

map由键值对组成，即map中的每个元素有1个键和1个值，为pair结构，各元素的键是唯一的，不允许重复，而值可以重复，map根据键进行排序。

常用操作：

函数名	功能
size()	返回字典的元素数
begin()	返回字典的头迭代器
end()	返回字典的尾迭代器
insert(make_pair(key,value))	插入元素(key,value)
erase(key)	删除键为key的元素
find(key)	查找键为key的元素，找到返回指向元素的迭代器，找不到返回尾迭代器
clear()	清空字典

map<string, int>m;//<string,int>为pair结构
m.insert(make_pair("zhangsan", 18));
m["lisi"] = 18;//可通过此种方式添加元素
m["lisi"] = 19;//可通过此种方式修改元素的值
m["wangwu"] = 20;
m.insert(make_pair("wangwu", 19));//此语句无效，不能通过此种方式修改"wangwu"的值
for (map<string, int>::iterator it = m.begin(); it != m.end(); it++)
    cout << it->first << ":" << it->second << endl;//通过first访问第一个元素（即键），通过second访问第二个元素（即值）
//lisi:19
//wangwu:20
//zhangsan:18

map与set一样通过平衡二叉搜索树实现，因此元素的插入、删除、搜索以及“[ ]”运算的复杂度皆为$O(logn)$。

 

3. 其他函数

3.1 数字与字符串之间的转换

3.1.1 数字转字符串

• C中方法：利用C库函数sprintf

#include<cstdio>

//整型转字符串
int a = 666;
char s1[10];
sprintf(s1, "%d", a);
cout << s1 << endl;//666
//浮点型转字符串
double b = 666.666;
char s2[10];
sprintf(s2, "%.3lf", b);//保留3位小数
cout << s2 << endl;//666.666

//拓展：sprintf可以用于进制转换
char s3[10];
sprintf(s3, "%o", a);//十进制转换为八进制
cout << s3 << endl;//1232
char s4[10];
sprintf(s4, "%x", a);//十进制转换为十六进制 字母大写用"%X"
cout << s4 << endl;//29a

此外，整型转字符串还可以使用itoa函数，但此函数为非标准库函数，部分编译器无法识别，因此不推荐使用。

• C++方法：使用stringstream类

#include<sstream>

//整型转字符串
int a = 666;
stringstream ss;
ss << a;
string s;
ss >> s;
cout << s << endl;
//浮点型转字符串（用法同上）
double b = 666.666;
ss.clear();//清空流的标记
ss << b;
ss >> s;
cout << s << endl;//666.666

此外，C++11提供了to_string函数可以直接将数字转为字符串。

cout << to_string(666) << endl;//666
cout << to_string(666.666) << endl;//666.666000 浮点型会保留6位小数

 

3.1.2 字符串转数字

• C中方法：使用sscanf函数或atoi、atof函数

#include<cstdio>//sscanf头文件
#include<cstdlib>//atoi、atof头文件

//字符串转整型
char s1[] = "666";
int a;
sscanf(s1, "%d", &a);
cout << a << endl;//666
cout << atoi(s1) << endl;//666
//字符串转浮点型
char s2[] = "666.666";
double b;
sscanf(s2, "%lf", &b);
cout << b << endl;//666.666
cout << atof(s2) << endl;

• C++方法：使用stringstream类

#include<sstream>

//字符串转整型
string s1 = "666";
stringstream ss;
ss << s1;
int a;
ss >> a;
cout << a << endl;//666
//字符串转浮点型（用法同上）
string s2 = "666.666";
ss.clear();//清空流的标记
ss << s2;
double b;
ss >> b;
cout << b << endl;//666.666

总结：数字转字符串推荐使用sprintf函数（如果编译器支持C++11，可以使用to_string函数），字符串转数字推荐使用atoi、atof函数。