算法初步——C++标准库

本文主要是介绍算法初步——C++标准库，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

文章目录

• • C标准库常用函数
  • C++STL < vector >数组
  • C++STL< string >字符串
  • C++STL < algorithm >算法函数
  • • 1.sort 快排
    • 2.其他algorithm函数
    • • 简单的6个函数
      • `nth_element()`函数
      • `unique()`函数
      • `binary_search()`函数
      • `lower_bound`函数和`upper_bound`函数

C标准库常用函数

<cstring>
strlen()字符串长度
strcmp()字符串比较
strcpy()字符串拷贝
memset()暴力清空数组
memcpy()暴力拷贝

2.<cstdlib>
qsort() C语言快排
rand() 随机数
malloc() free() C语言动态分配内存

3.<ctime>
time(0) 从1970年到现在的秒数，配合随机数
clock() 程序启动到目前位置的毫秒数

4.<cctype>
isdigit() 判断字符是否为数字
isalpha() 判断字符是否为英文字母，小写字母返回2，大写字母返回1，不为字母返回0

C++STL < vector >数组

常见操作：

vector<int>v;
v.begin();  //数组的首元素迭代器 O(1)
v.end();  //数组的最后一个元素的下一个元素的迭代器（该元素不存在） O(1)
v.size(); //数组长度（元素个数） O(1)
v.clear(); //一键清空数组 O(n)
v.empty(); //判断数组是否为空 O(1)
v.erase(it); //删除数组某个迭代器所在的位置的数字 O(n)
v.push_back(5); //往数组后面添加元素 O(1)
v.pop_back(); //删除数组后面最后一个元素 O(1)

C++STL< string >字符串

常见操作：

string s="hello";
string str1="world";
s.length();/s.size(); //求字符串长度 O(n)
s.insert(2,"abc"); //在下标为2处插入一个字符或者字符串 O(n)
s.insert(s.begin(),'a'); ///在迭代器处插入一个字符或者字符串 O(n)
s.c_str(); //返回C语言的字符串，用于输出printf O(n)
s.append(str1); //s+str
s.compare(str); //strcmp(s,str1);
s==str1 //strcmp(s.str1)==0;
s+=str1 //s.append(str1);
s+='a'; //s.push_back('a');
s+="aa";

C++STL < algorithm >算法函数

algorithm和之前两个头文件不同，它没有定义新的类型，只是定义了很多使用的算法，一个函数和传入的若干参数往往可以解决很多问题

1.sort 快排

int arr[]={4,5,2,1,3,6};
vector<int>v={4,5,2,1,3,6};
sort(arr,arr+6);   //排序结果：1 2 3 4 5 6
sort(v.begin();v.end()); //排序结果：1 2 3 4 5 6
//O(nlogn)
//sort函数里面有参数
//第一个参数是数组的头指针
//第二个参数是数组的最后一个元素的下一个元素的指针

//实际上还有第三个参数，如果第三个参数不写，sort将会从小到大排序
//第三个参数可以使用自定义的比较函数，
//第三个参数也可以使用<functional>头文件里面的greater<type>和less<type>
vector<int>v={4,5,2,1,3,6};
bool Mycompare(int a,int b)  //自定义从大到小排序
	return a>b;
int main()
{
	sort(v.begin(),v.end(),Mycompare);  //排序结果：6 5 4 3 2 1
	sort(v.begin(),v.end(),less<int>()) //排序结果：1 2 3 4 5 6
	sort(v.begin(),v.end(),greater<int>()) //排序结果：6 5 4 3 2 1
}

//大部分情况下用greater<type>和less<type>,但是比较的是点的坐标的话就要使用自定义比较函数了
struct Point
{
	int x;
	int y;
};
bool Mycmp(Point a,Point b) //先降序排序点的横坐标，横坐标相同的所有点中降序排序点的纵坐标
{
	if(a.x!=b.x)
		return a.x>b.x;
	else
        return a.y>b.y;
}
int main()
{
    Point arr[1005];
    for(int i=0;i<5;i++)
        cin>>arr[i].x>>arr[i].y;
	sort(arr,arr+5,Mycmp);
	
	for(int i=0;i<5;i++)
        cout<<arr[i].x<<" "<<arr[i].y<<endl;
}

测试案例

2.其他algorithm函数

简单的6个函数

vector<int>v;
min_element(v.begin(),v.end()) //返回第一个元素的指针 O(n)
max_element(v.begin(),v.end()) //返回最后一个元素的指针 O(n)
//这两个函数都是默认升序排序的，不要被 min 和 max 迷惑了
//以上两个函数都可以sort的变形，可以添加第三个参数
//即 greater<type> , less<type> , 自定义函数调整排序顺序

min(a,b); //返回a,b中较小的那个数
max(a,b); //返回a,b中较大的那个数
swap(v[0],v[1]); //交换任意两个同类型变量 O(1)
reverse(v.begin(),v.end()); //将数组翻转 O(n)

nth_element()函数

vector<int>v={2,5,6,1,3,4};
nth_element(v.begin(),v.begin()+3,v.end()); 
//把数组第n小（从0开始算）的数放到第n个位置
//可以理解为快排的简化版，并且左边的数都比它小，右边的数都比它大 
//O(n), sort的复杂度是O(nlogn),必要时刻还是要用这个函数的
//排序结果：2 1 3 4 6 5
//第三号也就是第四个数是4

unique()函数

vector<int>v={2,5,6,1,3,4,5,5};
sort(v.begin(),v.end()); //排序结果: 1 2 3 4 5 5 5 6 
auto it=unique(v.begin(),v.end()); //排序结果 1 2 3 4 5 6 5 5
//使用unique前需要将数组排序
//unique的作用是将多余的数字放在数组的末尾
//返回的是一个数组末尾指针 所以*it=5
//O(n)

int NewSize=unique(v.begin(),v.end())-v.begin();  //NewSize=6
//这是一种去重的方法，和set容器达成的效果一样
//数组里面的也只有 1 2 3 4 5 6这六个数字

binary_search()函数

bool IsEx=binary_search(v.begin(),v.end(),1);
//前提排好序 
//判断对应元素是否存在 O(logn)

lower_bound函数和upper_bound函数

vector<int>v={1,2,3,4,5,6};
auto pos=lower_bound(v.begin(),v.end(),3);
//前提排好序
//从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字
//找到返回该数字的地址，不存在则返回end
//O(logn)

auto pos=upper_bound(v.begin(),v.end(),3);
//前提排好序
//从数组的begin位置到end-1位置二分查找第一个大于(没有等于)num的数字
//找到返回该数字的地址，不存在则返回end
//O(logn)

这篇关于算法初步——C++标准库的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！