STL标准模版库之算法（algorithm）

STL（Standard Template Library，标准模板库)是惠普实验室开发的一系列软件的统称。它是由Alexander Stepanov、Meng Lee和David R Musser在惠普实验室工作时所开发出来的。现在虽说它主要出现在C++中，但在被引入C++之前该技术就已经存在了很长的一段时间。

STL的代码从广义上讲分为三类：algorithm（算法）、container（容器）和iterator（迭代器），几乎所有的代码都采用了模板类和模版函数的方式，这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。

在C++标准中，STL被组织为下面的13个头文件：<algorithm>、<deque>、<functional>、<iterator>、<vector>、<list>、<map>、<memory>、<numeric>、<queue>、<set>、<stack>和<utility>.

目录

1. 算法(algorithm)基本概念

1.1 非修正序列算法

1.2 修正序列算法

1.3 排序算法

1.4 数值算法

1. 算法(algorithm)基本概念

算法(algorithm)是STL的中枢，STL提供了算法库，算法库中都是模版函数，迭代器主要负责从容器中获取一个对象，算法与具体对象在容器中的位置等细节无关，每种算法都是参数化一个或多个迭代器类型的函数模版。‘

标准算法分为4类：非修正序列算法、修正序列算法、排序算法和数值算法。

1.1 非修正序列算法

非修改序列算法：不修改它们所作用的容器，如计算元素个数或查找元素的函数。STL中提供的非修正序列算法有adjacent_find(first,last),count、equal等。

代码示例如下：

adjacent_find：搜索相邻的重复元素

    multiset<int, less<int>> intSet;
	intSet.insert(1);
	intSet.insert(3);
	intSet.insert(6);
	intSet.insert(3);
	intSet.insert(6);
	//intSet.insert(3);

	cout << "Set:" << " ";
	multiset<int, less<int>>::iterator it = intSet.begin();
	for (int i = 0; i < intSet.size(); i++)
	{
		cout << *it++ << ' ';
	}

	cout << endl;
	cout << "第一次匹配:";
	//查找重复的元素
	it = adjacent_find(intSet.begin(),intSet.end());
	cout << *it++ << ' ';
	cout << *it << endl;
	cout << "第二次匹配:";
	it = adjacent_find(it,intSet.end());
	cout << *it++ << ' ';
	cout << *it << endl;

count：计数

    multiset<int, less<int>> intSet;
	intSet.insert(1);
	intSet.insert(3);
	intSet.insert(6);
	intSet.insert(3);
	intSet.insert(6);
	//intSet.insert(3);

	cout << "Set:" << " ";
	multiset<int, less<int>>::iterator it = intSet.begin();
	for (int i = 0; i < intSet.size(); i++)
	{
		cout << *it++ << ' ';
	}

	int num = count(intSet.begin(),intSet.end(),3);
	cout << "相同元素数据:" << num << endl;

for_each（first,last,func）:对first到last范围的各个元素执行函数func定义的操作

void Output(int val)
{
	cout << val << ' ';
}

void test_algorithm_03(void)
{
	multiset<int, less<int>> intSet;
	intSet.insert(1);
	intSet.insert(3);
	intSet.insert(6);

	cout << "Set:" << " ";
	for_each(intSet.begin(), intSet.end(),Output);
	cout << endl;

}

1.2 修正序列算法

修正序列算法：有一些 操作会改变容器的内容，例如把一个容器的部分内容复制到同一个容器的另一部分，或者用指定值填充容器，例如copy、fill、reverse、remove等。

代码示例如下：

fill:改填元素值

vector<int> intVect;
for (int i = 0; i < 10; i++)
{
	intVect.push_back(i);
}
cout << "Vect:";
for_each(intVect.begin(), intVect.end(), Output);
fill(intVect.begin(), intVect.begin() + 5, 0);
cout << endl;
cout << "Vect:";
for_each(intVect.begin(),intVect.end(), Output);
cout << endl;

rotate:旋转

    vector<char> charVect;
	charVect.push_back('C');
	charVect.push_back('B');
	charVect.push_back(' ');
	charVect.push_back('H');
	charVect.push_back('R');
	charVect.push_back(' ');
	charVect.push_back('G');

	cout << "Vect:";
	for_each(charVect.begin(), charVect.end(), Output);
	rotate(charVect.begin(),charVect.begin()+6,charVect.end());
	cout << endl;
	cout << "Vect:";
	for_each(charVect.begin(), charVect.end(), Output);
	cout << endl;

1.3 排序算法

排序算法：是对容器的内容进行不同方式的排序，例如sort等。

代码示例如下：

sort:排序从大到小

    vector<char> charVect;
	charVect.push_back('C');
	charVect.push_back('B');
	charVect.push_back('D');
	charVect.push_back('H');
	charVect.push_back('R');
	charVect.push_back('A');
	charVect.push_back('G');

	cout << "Vect:";
	for_each(charVect.begin(), charVect.end(), Output);
	sort(charVect.begin(), charVect.end());
	cout << endl;
	cout << "Vect:";
	for_each(charVect.begin(), charVect.end(), Output);
	cout << endl;

1.4 数值算法

数值算法：是对容器的内容进行计算，STL的数值算法实现了4中类型的计算，可以在一个值序列上进行这些计算。

示例代码如下：

accumulate:元素累加

	vector<int> intVect;
	for (int i = 0; i < 5; i++)
	{
		intVect.push_back(i);
	}
	cout << "Vect:";
	for_each(intVect.begin(), intVect.end(), Output);
	int result = accumulate(intVect.begin(),intVect.end(),5);
	cout << endl;
	cout << "Result:" << result << endl;