C++STL标准模板库(排序/集合/适配器)算法

C++ 标准模板库STL,是一个使用模板技术实现的通用程序库,该库由容器container,算法algorithm,迭代器iterator,容器和算法之间通过迭代器进行无缝连接,其中所包含的数据结构都是目前最优解,该库既能保证软件代码的高可复用性,又能保证代码具有相当高的执行效率,STL库是ANSI/ISO的C++标准的具体实现,任何标准库的实现都是以源码形式释出的.

STL是C++的一部分，STL可分为容器(containers)、迭代器(iterators)、空间配置器(allocator)、配接器(adapters)、算法(algorithms)、仿函数(functors)六个部分，以下案例主要是在学习时对容器的总结笔记，基本上涵盖了关于容器之间，能够想到的任何操作，一次性全部涵盖其中。

STL 排序/算数/集合算法

C++ 的排序算法是一组将无序序列排列成有序序列的模板函数或与排序相关的模板函数,排序算法一般要求容器提供随机访问迭代器,这里将分别学习常用的排序算法,集合中/交集/并集/差集/的使用技巧.

堆排序 sort_heap: 该算法通过利用堆进行排序,首先需要将向量容器转坏为堆容器,然后再利用堆排序算法排序.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

void MyPrint(int val){ cout << val << "  "; }

int main(int argc, char* argv[])
{
	vector<int> var {45,76,89,32,11,23,45,9,0,3};

	for_each(var.begin(), var.end(), MyPrint);
	cout << endl;

	make_heap(var.begin(), var.end());     // 建立堆
	if (is_heap(var.begin(), var.end()))   // 如果堆建立成功,则执行排序
	{
		sort_heap(var.begin(), var.end()); // 开始对堆排序
	}
	for_each(var.begin(), var.end(), MyPrint);

	system("pause");
	return 0;
}

局部排序与复制 partial_sort: 该算法可实现对容器中部分元素进行排序,还可以将结果拷贝到其他容器中.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

void MyPrint(int val){ cout << val << "  "; }

int main(int argc, char* argv[])
{
	int iArray[] = { 3, 4, 8, 23, 56, 3, 89, 0, 32, 6 };
	const int len = sizeof(iArray) / sizeof(int);
	// 输出排序前的顺序
	for_each(iArray, iArray + len, MyPrint);
	cout << endl;

	// 局部排序,将数组中的前6个元素进行排序,后面的不排列
	int middle = 5;  // 指定排序索引,索引从0开始
	partial_sort(iArray, iArray + middle, iArray + len);
	for_each(iArray, iArray + len, MyPrint);
	cout << endl;

	// 排序并拷贝元素,将iArray中前5个元素排序后拷贝到var中
	vector<int> var(6);
	partial_sort_copy(iArray, iArray + 5, var.begin(), var.end());
	for_each(iArray, iArray + 5, MyPrint);

	system("pause");
	return 0;
}

常用排序算法 sort: 该算法与堆排序相同,也要求使用随机访问迭代器进行排序,相比于堆排序速度更快.

#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
using namespace std;

void MyPrint(int val){ cout << val << " "; }

int main(int argc, char* argv[])
{
	// 从小到大排序
	int iArray[] = { 56, 43, 22, 1, 34, 7, 89, 0, 43, 56 };
	const int len = sizeof(iArray) / sizeof(int);
	sort(iArray, iArray + len);
	for_each(iArray, iArray + len, [](int val){cout << val << " "; });
	cout << endl;

	// 从大到小排序
	vector<int> var = { 45, 76, 33, 21, 7, 89, 0, 34, 5, 7 };
	sort(var.begin(), var.end(), greater<int>());
	for_each(var.begin(), var.end(), MyPrint);

	system("pause");
	return 0;
}

稳定排序算法 stable_sort: 该算法与sort算法类似,也是将区间元素排序,但可保持等介元素的相对顺序稳定不变.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct Student{
	int id;
	char *name;
	int score;
	Student(int _id, char* _name, int _score)
	{
		id = _id; name = _name; score = _score;
	}
};

void MyPrint(Student val)
{
	cout << val.id << val.name << val.score << endl;
}

bool CompByScore(Student x, Student y)
{ // 按照学生的成绩从小到大进行排序
	return x.score < y.score ? 1 : 0;
}

int main(int argc, char* argv[])
{
	vector<Student> var;

	var.push_back(Student(1, "keey", 90));
	var.push_back(Student(2, "marry", 82));
	var.push_back(Student(3, "lisa", 70));

	stable_sort(var.begin(), var.end(), CompByScore);
	for_each(var.begin(), var.end(), MyPrint);

	system("pause");
	return 0;
}

容器归并算法 merge: 该算法可以实现将两个具有相同升降方向的有序序列(必须有序),合并成另一个有序序列.

#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;

void MyPrint(int val){ cout << val << " "; }

int main(int argc, char* argv[])
{
	// 按照升序方式将两个序列合并
	int iArray1[3] = { 1, 2, 3 };
	int iArray2[7] = { 4, 5, 6, 7, 8, 9, 10 };
	int result[10];

	merge(iArray1, iArray1 + 3, iArray2, iArray2 + 7, result);
	for_each(result, result + 10, MyPrint);
	cout << endl;

	// 按照降序方式将两个序列合并
	int iArray3[5] = { 30, 20, 15, 9, 2 };
	int iArray4[4] = { 10, 5, 3, 1 };
	int result2[9];

	merge(iArray3, iArray3 + 5, iArray4, iArray4 + 4, result2, greater<int>());
	for_each(result2, result2 + 9, MyPrint);
	cout << endl;

	// 内部归并排序,这里只给出降序排列代码,升序排列与第一个案例相同
	int iArray5[] = { 100, 80, 60, 40, 20, 10, 90, 70, 50, 30 };
	const int len = sizeof(iArray5) / sizeof(int);  // 数组元素总长度
	int middle = 6;                                 // 选择一个切割中位数下标
	inplace_merge(iArray5, iArray5 + middle, iArray5 + len, greater<int>());
	for_each(iArray5, iArray5 + len, MyPrint);

	system("pause");
	return 0;
}

容器区间查找算法 bound: 该算法由于在有序的容器中查找首/尾/中区间里面不同的取值范围.

#include <iostream>
#include <algorithm>
using namespace std;

int main(int argc, char* argv[])
{
	int iArray[] = { 3, 6, 9, 12, 13, 18, 20, 27, 55, 44};
	const int len = sizeof(iArray) / sizeof(int);

	// lower_bound 找出不小于某值的有序数组下确界元素
	int *result1 = lower_bound(iArray, iArray + len, 16);
	cout << "lower_bound = " << *result1 << endl;

	// upper_bound 找出大于某值的有序数组上确界元素
	int *result2 = upper_bound(iArray, iArray + len, 20);
	cout << "upper_bound = " << *result2 << endl;

	// equal_range 找出可插入某值的区间元素
	pair<int*, int*> range = equal_range(iArray, iArray + len, 5);
	cout << "lower_bound = " << *range.first << endl;
	cout << "upper_bound = " << *range.second << endl;
	
	system("pause");
	return 0;
}

求最大/最小值算法: 该max/min函数分别实现统计一个序列中最大和最小元素并返回.

#include <iostream>
#include <algorithm>
#include <list>
using namespace std;

int main(int argc, char* argv[])
{
	list<int> ls = { 1, 4, 5, 6, 7, 2, 3, 4, 9, 7, 6 };

	// 返回链表最小元素
	cout << *min_element(ls.begin(), ls.end()) << endl;

	// 返回链表最大元素
	cout << *max_element(ls.begin(), ls.end()) << endl;

	// 剩余 max /min 比较
	cout << max(100, 30) << endl;
	cout << min(1, -10) << endl;

	system("pause");
	return 0;
}

交集/并集/差集/算法: 下面的算法分别演示了对数组或容器求交并差集的运算.

#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>
using namespace std;

int main(int argc, char* argv[])
{
	vector<int> var1 = { 1,2,3,4,5,23 };
	vector<int> var2 = { 1,2,3,4,5,6,7,8,9,10 };
	vector<int> vTarget;

	// 求 var1 与 var2 的交集
	vTarget.resize(min(var1.size(), var2.size()));  // 分配最小空间
	vector<int>::iterator itEnd;
	itEnd = set_intersection(var1.begin(), var1.end(), var2.begin(), var2.end(), vTarget.begin());
	copy(vTarget.begin(), itEnd, ostream_iterator<int>(cout, " ")); // 拷贝与打印出来
	cout << endl;

	// 求 var1 与 var2 的并集
	vTarget.resize(var1.size()+var2.size());        // 分配最大空间
	vector<int>::iterator itEnd1;
	itEnd1 = set_union(var1.begin(), var1.end(), var2.begin(), var2.end(), vTarget.begin());
	copy(vTarget.begin(), itEnd1, ostream_iterator<int>(cout, " ")); // 拷贝与打印出来
	cout << endl;

	// 求 var1 与 var2 的差集
	vTarget.resize(max(var1.size(),var2.size()));  // 分配最大数组的空间
	vector<int>::iterator itEnd2;
	itEnd2 = set_difference(var1.begin(), var1.end(), var2.begin(), var2.end(), vTarget.begin());
	copy(vTarget.begin(), itEnd2, ostream_iterator<int>(cout, " ")); // 拷贝与打印出来

	system("pause");
	return 0;
}

求容器上/下排列组合: 该算法用于对区间元素进行组合排列,选择一个字典顺序更大/更小的排列.

#include <iostream>
#include <algorithm>
using namespace std;

void MyPrint(int x) { cout << x << " "; }

// 排序函数
template <class BidirectionalIter>
void nextPermu_sort(BidirectionalIter first, BidirectionalIter last)
{
	while (next_permutation(first, last)){} // 利用较大的组合返回true
}

int main(int argc, char* argv[])
{
	int iArray[] = { 3, 5, 8, 1, 8, 9, 3, 2, 1, 9 };
	const int len = sizeof(iArray) / sizeof(int);

	// 下一排列组合
	next_permutation(iArray, iArray + len);
	for_each(iArray, iArray + len, MyPrint);
	cout << endl;

	// 上一排列组合
	prev_permutation(iArray, iArray + len);
	for_each(iArray, iArray + len, MyPrint);

	system("pause");
	return 0;
}

容器元素求和算法: 该算法中包括了求数组元素想加之和,求内积,求阶乘,等常用的数学算法.

#include <iostream>
#include <numeric>
#include <algorithm>
using namespace std;

void MyPrint(int x) { cout << x << " "; }

int multiply(int x, int y) { return x*y; }

int main(int argc, char* argv[])
{
	// 求数组元素相加之和
	int iArray[5] = {1,2,3,4,5};
	cout << accumulate(iArray, iArray + 5, 0) << endl;

	// 求数组元素的内积
	int iArray1[3] = { 2, 5, 4 };
	int iArray2[3] = { 10, 6, 5 };
	cout << inner_product(iArray1, iArray1 + 3, iArray2, 0) << endl;

	// 部分元素求和
	int iArray3[5] = { 1, 2, 3, 4, 5 };
	int result[5];

	partial_sum(iArray3, iArray3 + 5, result);
	for_each(iArray3, iArray3 + 5, MyPrint);
	cout << endl;

	// 求阶乘
	int result1[5];
	partial_sum(iArray3, iArray3 + 5, result1,multiply);
	for_each(result1, result1 + 5, MyPrint);

	system("pause");
	return 0;
}

STL 模板适配器与迭代器

输入输出流迭代器是架构在流之上的一种迭代器,如同容器的迭代器与容器的关系一样,对流的数据提供迭代器的操作支持,通过输入输出流的迭代器,你就可以在输入输出流上使用STL算法,使得应用能应用到更广泛的数据流上,其实迭代器也是一种特殊的适配器,这里会先学习适配器的概念,然后在研究流迭代器.

函数对象适配器: 通过绑定参数实现对函数对象的适配,使之可以传递参数.

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

// binary_function (val= > 参数类型1 start=> 参数类型2 void=> 返回值类型)
class MyPrint :public binary_function<int,int,void>
{
public:void operator()(int val, int start) const {
		cout << val + start << endl;
	}
};

int main(int argc, char* argv[])
{
	vector<int> var = {1,2,3,4,5,6,7,8,9,10};

	int num;
	cin >> num;

	// 让MyPrint函数绑定num参数,传参是传递到MyPrint中
	for_each(var.begin(), var.end(), bind2nd(MyPrint(),num));
	system("pause");
	return 0;
}

函数指针适配器: 函数则无法直接绑定参数,但可以将函数指针适配为函数对象,然后再传递参数.

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

void MyPrint(int val,int start)
{
	cout << val + start << " ";
}

int main(int argc, char* argv[])
{
	vector<int> var = {1,2,3,4,5,6,7,8,9,10};

	for_each(var.begin(), var.end(),bind2nd(ptr_fun(MyPrint),100) );
	system("pause");
	return 0;
}

容器取反适配器: 首先我们想要找到第一个大于5的数是多少,但由于加上了not1取反则输出的数据则小于5.

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

class MyPrint : public unary_function<int,bool>
{
public:bool operator()(int val) const {
		   return val > 5; // 找大于5的数
	}
};

int main(int argc, char* argv[])
{
	vector<int> var = {1,2,3,4,5,6,7,8,9,10};

	// 寻找第一个大于5的数,并遍历出来
	vector<int>::iterator pos = find_if(var.begin(), var.end(), not1(MyPrint()));
	if (pos != var.end())
		cout << *pos << endl;

	system("pause");
	return 0;
}

文件流对象拷贝文件: 通过绑定istream输入流对象,实现了向前迭代动态拷贝文件到指定目录下.

#include <iostream>
#include <iterator>
#include <fstream>
#include <string>
#include <algorithm>
using namespace std;

void Copy_Log(string src_path, string dst_path)
{
	ifstream read_file;
	ofstream write_file;

	read_file.open(src_path, ios::in);
	read_file >> noskipws;
	write_file.open(dst_path, ios::out);

	istream_iterator<char> iter_iFile(read_file);
	ostream_iterator<char> iter_oFile(write_file);

	copy(iter_iFile, istream_iterator<char>(), iter_oFile);
}

int main(int argc, char* argv[])
{
	Copy_Log("c:\\lyshark.txt", "c:\\new.txt");
	system("pause");
	return 0;
}

向前/向后/插入迭代器: 通过使用插入迭代器我们可以将一组数据插入到容器中的前或后等位置.

#include <iostream>
#include <iterator>
#include <set>
#include <deque>
#include <vector>
#include <algorithm>
using namespace std;

int main(int argc, char* argv[])
{
	// 插入迭代器: 将两个数组合并,并插入到集合容器st中
	int iArray1[] = { 1, 3, 5, 7, 9 };
	int iArray2[] = { 2, 4, 6, 8, 10, 12, 14, 16 };
	set<int> st;

	merge(iArray1, iArray1 + 5, iArray2, iArray2 + 8, insert_iterator<set<int>>(st,st.begin()));
	copy(st.begin(), st.end(), ostream_iterator<int>(cout, " "));  // 输出 st 内部的元素结果
	cout << endl;

	// 向前插入迭代器
	deque<int> deq = {1,2,3};
	front_insert_iterator<deque<int>> fii(deq);  // 向前插入
	*fii++ = 0;
	*fii++ = -1;
	copy(deq.begin(), deq.end(), ostream_iterator<int>(cout, " "));  // 输出 deq 内部的元素结果
	cout << endl;

	// 向后插入迭代器
	int iArray3[] = { 1, 2, 3, 4 };
	int len = sizeof(iArray3) / sizeof(int);
	vector<int> ve = {5,6};
	// 将数组元素从后插入到ve容器中
	copy(iArray3,iArray3+len,back_insert_iterator<vector<int>>(ve));
	copy(ve.begin(), ve.end(), ostream_iterator<int>(cout, " "));  // 输出 deq 内部的元素结果

	system("pause");
	return 0;
}

容器反向迭代器: 该迭代器是一个用随机访问迭代器构造出来的迭代器,用于反向迭代容器元素.

#include <iostream>
#include <iterator>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;

int main(int argc, char* argv[])
{
	vector<int> var;
	back_insert_iterator< vector<int>> bii(var);
	*bii++ = 3;
	*bii++ = 9;
	*bii++ = 10;

	// 反向迭代器定义
	reverse_iterator<vector<int>::iterator> rfirst(var.end());
	reverse_iterator<vector<int>::iterator> rend(var.begin());

	// 从尾到头打印
	copy(rfirst, rend, ostream_iterator<int>(cout, " "));

	system("pause");
	return 0;
}