C++STL算法_c++ stl 算法

1. STL查找算法

基本查找：

   find：区间查找

   find_if：条件查找

   find_first_of：查找区间第一次出现值

   adjacent_find：查找第一次重复的数

   search：子序列查找

   search_n：子序列查找出现次数

统计查找：

   count：区间统计

   count_if：条件统计个数

   equal：比较

有序查找：

   binary_search：二分查找

   upper_bound：查找在最后一个大于查找的值

   lower_bound：大于等于查找的值

   equal_range：区间比较——有序序列

#include <iostream>
#include <algorithm>//基本算法的头文件
#include <functional>//算法一般结合仿函数
#include <string>
#include <vector>
#include <list>
using namespace std;
 
int main()
{
	//1 find查找
	int array[] = { 9,8,7,4,5,6,3,2,1 };
	vector<int> vec;
	vec.assign(array, array + 9);
	auto result = find(vec.begin(), vec.end(), 5);
	cout << *result;//在vec容器的开头和结尾找5，没找到就返回容器结束w位置
	//2 find_if条件查找
	auto findif = find_if(vec.begin(), vec.end(), [](int x) {return x > 3;});
	cout << *findif;
	//3 find_first_of查找区间第一次出现值
	int temp[] = { 8,9,7 };
	auto findfirstof = find_first_of(vec.begin(), vec.end(), temp, temp + 3);
	cout << *findfirstof;//8,9,7都能找到，返回找到的第一个
	//4 adjacent_find：查找第一次重复的数
	vector<int> rvec = { 1,2,2,3,3,4,4,5,5,6 };
	auto reIter = adjacent_find(rvec.begin(), rvec.end());
	cout << *reIter;
	//5 search：子序列查找
	int searchData[] = { 5,7,8 };
	auto it = search(rvec.begin(), rvec.end(), searchData, searchData + 3);
	cout << *it;//5
	//6 search_n：子序列查找出现次数
	auto sn = search_n(rvec.begin(), rvec.end(), 4, 5);
	cout << *sn;
	//7 count：区间统计
	cout << count(rvec.begin(), rvec.end(), 4);//4出现的次数
	//8 count_if：条件统计个数
	cout << count_if(rvec.begin(), rvec.end(), [](int x) {return x > 3; });
	//9 equal：比较,两个容器的值是否相同
	list<int> mylist = { 0,1,2,3,6,5,4,7,8,9 };
	cout << boolalpha << equal(rvec.begin(), rvec.end(), mylist.begin(), mylist.end());
	//10 binary_search：二分查找//必须是有序数列
	vector<int> testdata = { 1,2,3,4,5,6,7,8,9 };
	cout << boolalpha << binary_search(testdata.begin(), testdata.end(), 3);
	//11 upper_bound：查找在最后一个大于查找的值
	auto uper = upper_bound(testdata.begin(), testdata.end(), 6);
	//12 lower_bound：大于等于查找的值
	auto lower = lower_bound(testdata.begin(), testdata.end(), 7);
	//13 equal_range：区间比较——有序序列
	auto pair = equal_range(testdata.begin(), testdata.end(), 6);
	cout << *pair.first << " " << *pair.second;
	return 0;
}

2 STL排序算法

merge：归并排序，存于新容器

inplace_merge：归并排序，覆盖原区间

sort：排序，更改原容器顺序

stable_sort：排序，保存原容器数据顺序

nth_element：关键字排序

partition：范围排序

partial_sort：范围排序

partial_sort_copy：范围排序外加复制操作

stable_partition：范围排序，保存原容器顺序

random_shuffle：随机排序

reverse：逆序原容器

reverse_copy：逆序容器保存到新容器

rotate：移动元素到容器末尾

rotate_copy：移动元素到新容器

#include <iostream>
#include <algorithm>//基本算法的头文件
#include <functional>//算法一般结合仿函数
#include <string>
#include <vector>
#include <list>
using namespace std;
template <class T>
void print(T data)
{
	for (auto v : data)
	{
		cout << v << "\t";
	}
	cout << endl;
}
class student
{
public:
	student(string name, int age) :name(name), age(age) {}
	void print()
	{
		cout << name << " " << age;
	}
protected:
	string name;
	int age;
};
void testsort()
{
	vector<student> Sdata;
	Sdata.push_back(student("kjshf", 18));
	Sdata.push_back(student("dfjds", 19));
	Sdata.push_back(student("sdoif", 20));
	sort(Sdata.begin(), Sdata.end(), [](auto a, auto b) {return a.name, b.name; });
	for (auto v : Sdata)
	{
		v.print();
	}
}
bool com_as_int(double a, double b)
{
	return int(a) < int(b);
}
void testStable()
{
	vector<double> num = { 1.33,1.34,1.32,1.35,1.335,1.334,1.342 };
	stable_sort(num.begin(), num.end(), com_as_int);
	print(num);
}
void testMergeinplace()
{//不会更改原容器的顺序
	vector<int> vec = { 1,2,9,8,7,6,5,4 };
	vector<int> result(vec.size());
	merge(vec.begin(), vec.begin() + 2, vec.begin() + 2, vec.end(), result.begin());
	print(result);
	//会改变原容器
	inplace_merge(vec.begin(), vec.begin() + 2, vec.end());
	print(vec);
}
int main()
{
	//1 sort：排序，更改原容器顺序
	vector<int> vec = { 1,2,4,3,9,7,6,8,5,0 };
	sort(vec.begin(), vec.end());
	//print(vec);//0，1，2，3，4，5，6，7，8，9
	testsort();
	//2 stable_sort：排序，保存原容器数据顺序
	testStable();
	//3 merge：归并排序，存于新容器
	testMergeinplace();
	//4 inplace_merge：归并排序，覆盖原区间
	testMergeinplace();
	//5 nth_element：关键字排序
	vector<int> test = { 1,2,3,4,5,9,8,7,6 };
	nth_element(test.begin(), test.begin() + 5, test.end());
	print(test);
	//6 partition：范围排序
	partition(test.begin(), test.end(), 6);
	print(test);
	//7 stable_partition：范围排序，保存原容器顺序
	vector<int> result(test.size());
	stable_partition(test.begin(), test.end(), com_as_int);
	print(result);
	//8 partital_sort：范围排序
	partial_sort(test.begin(), test.begin() + 5, test.end());
	//9 partial_sort_copy：范围排序外加复制操作
	partial_sort_copy(test.begin(), test.begin() +5, test.end(), result.begin());
	//10 random_shuffle：随机排序
	random_shuffle(test.begin(), test.end());
	//11 reverse：逆序原容器
	reverse(test.begin(), test.end());
	//12 reverse_copy：逆序容器保存到新容器
	reverse_copy(test.begin(), test.end(), result.begin());
	//13 rotate：移动元素到容器末尾
	rotate(test.begin(), test.begin() + 2, test.end());
	//14 rotate_copy：移动元素到新容器
	rotate_copy(test.begin(), test.begin() + 5, test.end(), result.begin());
	return 0;
}