C++ STL 标准模板库(非变易/变易)算法

C++ STL模板是惠普实验室开发的标准开发模板，STL是C++的一部分，STL可分为容器(containers)、迭代器(iterators)、空间配置器(allocator)、配接器(adapters)、算法(algorithms)、仿函数(functors)六个部分，以下案例是针对算法中的非变易与变易算法的总结知识点。

STL 非变易算法(查找遍历)

C++ 非变易算法是一组不破坏操作数据的模板函数,用来对序列数据进行逐个处理,元素查找,统计等,并通过迭代器实现元素的遍历,由于迭代器与算法是分离的,因此非变易算法本身具有极为广泛的通用性,基本上可以应用于各种容器上.

逐个遍历容器元素 for_each: 该函数用于对容器的元素进行循环操作,常用于元素遍历.

#include 
#include 
#include 
using namespace std;

struct MyPrint{
	int count;                   // 设置元素计数
	MyPrint(){ count = 0; }      // 初始化元素
	void operator()(int x)       // 重载小括号
	{
		cout << x << endl;
		count++;
	}
};

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

	MyPrint p = for_each(ls.begin(), ls.end(), MyPrint());
	cout << "Link Count: " << p.count << endl;
	system("pause");
	return 0;
}

普通查找容器元素 find: 该算法用于查找某个值等于某值得元素,它在迭代区间是(frist,last)之间寻找value值.

#include 
#include 
#include 
using namespace std;

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

	list::iterator it = find(ls.begin(), ls.end(),6);
	if (it != ls.end())
	{
		cout << "找到了元素" << endl;
		cout << "前一个元素: " << *(--it) << endl;
	}

	system("pause");
	return 0;
}

类查找容器元素 find: 该算法不仅可以查询普通数据结构,还可以查询结构与类中数据.

#include 
#include 
#include 
#include 
using namespace std;

class Person
{
public:
	string m_name;
	int m_age;
public:Person(string name, int age){
		this->m_name = name;
		this->m_age = age;
	}
public: bool operator==(const Person &p){
	// 重载 == 实现遍历数据
		if (this->m_name == p.m_name && this->m_age == p.m_age)
			return true;
		return false;
	}
};

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

	Person p1("aaa", 10);
	Person p2("bbb", 20);
	Person p3("ccc", 30);
	var.push_back(p1);
	var.push_back(p2);
	var.push_back(p3);

	vector::iterator pos = find(var.begin(), var.end(), p1);
	if (pos != var.end())
		cout << "找到姓名: " << (*pos).m_name << endl;
	system("pause");
	return 0;
}

条件查找容器元素 find_if: 该查询与上方的普通查找相比,该查找可以添加回调函数,用于对查到的数据进行筛选.

#include 
#include 
#include 
using namespace std;

bool MyFunction(int x) { return x % 5 ? 0 : 1; }

int main(int argc, char* argv[])
{
	vector var(20);

	// 循环生成数据
	for (unsigned int x = 0; x < var.size(); x++)
		var[x] = (x + 1) * (x + 3);

	// 循环遍历,并判断是否符合条件
	vector::iterator it = find_if(var.begin(),var.end(),MyFunction);
	if (it != var.end())
	{ // 寻找第一个被5整除的元素
		cout << *it << endl;
		cout << "元素索引: " << it - var.begin() << endl;
	}
	system("pause");
	return 0;
}

条件查找类容器元素 find_if: 查找ptr类中的数据,是否存在于我们的结构中.

#include 
#include 
#include 
#include 
#include 
using namespace std;

class Person
{
public:
	string m_name;
	int m_age;
public:Person(string name, int age){
		   this->m_name = name;
		   this->m_age = age;
}
public: bool operator==(const Person &p){
		// 重载 == 实现遍历数据
		if (this->m_name == p.m_name && this->m_age == p.m_age)
			return true;
		return false;
	}
};
// 使用binary_function适配函数实现传递两个Person数据
class MyCompare:public binary_function
{
public: bool operator()(Person *p1,Person *p2) const {
		// 对比函数,重载() 用于实现指针元素的对比
		if (p1->m_name == p2->m_name && p1->m_age == p2->m_age)
			return true;
		return false;
	}
};

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

	Person p1("aaa", 10);
	Person p2("bbb", 20);
	Person p3("ccc", 30);
	var.push_back(&p1);
	var.push_back(&p2);
	var.push_back(&p3);

	Person *ptr = new Person("bbb", 20);   // 查找这个属性的类成员
	// 通过使用bind2nd绑定事件,将ptr传递给MyCompare() 即可实现两个类属性的对比查找
	vector::iterator pos = find_if(var.begin(), var.end(), bind2nd(MyCompare(),ptr));
	if (pos != var.end())
		cout << "找到姓名: " << (*pos)->m_name << endl;
	system("pause");
	return 0;
}

邻近查找容器元素 adjacent_find:用于查找相等或满足条件的相邻的重复的元素,找到了返回第一个位的迭代器.

#include 
#include 
#include 
using namespace std;

bool MyFunction(int x,int y) { return (x - y) % 2 == 0 ? 1 : 0; }

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

	// 查找链表中邻接相等的元素
	list::iterator it = adjacent_find(ls.begin(), ls.end());
	if (it != ls.end())
		cout << *it << endl;

	// 查找基偶性相同的邻接元素
	it = adjacent_find(ls.begin(), ls.end(), MyFunction);
	if (it != ls.end())
	{
		cout << *it << endl;
		it++;
		cout << *it << endl;
	}
	system("pause");
	return 0;
}

范围查找容器元素 find_first_of: 该算法可用于查找位于某个范围之内的元素.

#include 
#include 
#include 
using namespace std;

int main(int argc, char* argv[])
{
	char * str1 = "hello";
	char * str2 = "lyshark This is a test case. Thank you for using it lyshark.";

	char * result = find_first_of(str1, str1 + strlen(str1), 
									str2, str2 + strlen(str2));
	// 字符串str1的第一个字符,第一次出现在str2中的字符为.
	cout << *result << endl;
	system("pause");
	return 0;
}

普通元素计数统计 count: 该算法用于计算容器中某个给定值得出现次数.

#include 
#include 
#include 
using namespace std;

int main(int argc, char* argv[])
{
	list ls;
	
	// 批量插入测试数据
	for (int x = 0; x < 100; x++)
	{
		ls.push_back(x % 20);
	}
	// 统计元素value出现次数,将次数放入num中.
	int num = 0; int value = 9;
	num = count(ls.begin(), ls.end(), value);
	cout << "The number of occurrences is: " << num << endl;

	system("pause");
	return 0;
}

条件元素计数统计 count_if: 与Count算法类似,该算法可以在统计前增加判断条件.

#include 
#include 
#include 
using namespace std;

struct Student{
	struct Info{
		char *name; // 学生姓名
		int year;   // 学生年龄
	};
	int id;    // 学号
	Info stu;  // 学生Info数据

	Student(int _id, char *_name, int _year)
	{
		id = _id;
		stu.name = _name;
		stu.year = _year;
	}
};

// 获取学生年龄大于20岁并且小于30岁的人
bool GetRange(pair s)
{
	if (s.second.year > 20 && s.second.year < 30)
		return 1;
	return 0;
}

int main(int argc, char* argv[])
{
	// 初始化学生数据
	Student stu1 = Student(1, "admin", 10);
	Student stu2 = Student(2, "guest", 21);
	Student stu3 = Student(3, "lyshark", 35);

	// 映射Map结构数据,并将上方的数据插入到Map中
	map mp;
	pair pairSt1(stu1.id, stu1.stu);
	mp.insert(pairSt1);
	pair pairSt2(stu2.id, stu2.stu);
	mp.insert(pairSt2);
	pair pairSt3(stu3.id, stu3.stu);
	mp.insert(pairSt3);

	// 条件统计,统计出年龄大于20岁并且小于30岁的人有多少个= num
	int num = 0;
	num = count_if(mp.begin(), mp.end(), GetRange);
	cout << num << endl;
	system("pause");
	return 0;
}

二分法查找算法 binary_search: 该算法就是折半查找法,查找的元素集合必须是一个有序的序列.

#include 
#include 
#include 
using namespace std;

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

	bool ret = binary_search(var.begin(), var.end(), 4);
	if (ret)
		cout << "found ok" << endl;
	else
		cout << "not found" << endl;

	system("pause");
	return 0;
}

元素不匹配查找 mismatch: 该算法函数比较两个序列,并从中找出首个不匹配元素的位置.

#include 
#include 
#include 
#include 
using namespace std;

bool StrEqual(const char* x, const char* y)
{
	return strcmp(x, y) == 0 ? 1 : 0;
}

int main(int argc, char* argv[])
{
	vector var1{ 2, 0, 0, 6 };
	vector var2{ 2, 0, 0, 7 };

	// 检测var1与var2中不匹配元素数,并输出
	pair::iterator, vector::iterator> result;
	result = mismatch(var1.begin(), var1.end(), var2.begin());
	if (result.first == var1.end() && result.second == var1.end())
		cout << "var1 与var2完全一致" << endl;
	else
		// var1 和var2不相同,不匹配的数是
		cout << "var1 = " << *result.first << " --> var2= " << *result.second << endl;

	// ---------------------------------------------------------------------------------
	// 针对字符串的不匹配检测
	char * str1[] = { "apple", "pear", "banana", "grape" };
	char * str2[] = { "apple", "pear", "banana", "zoops" };

	pair result2 = mismatch(str1, str1 + 4, str2, StrEqual);
	if (result2.first != str1 + 4 && result2.second != str2 + 4)
	{ // 成立则说明两个str子串有不同的地方,并输出他们之间的不同点
		cout << "str1 = > " << str1[result2.first - str1] << endl << endl;
		cout << "str2 = > " << str2[result2.second - str2] << endl;
	}
	system("pause");
	return 0;
}

元素相等的判断 equal: 该算法实现逐一比较两个序列的元素是否相等,该函数不返回迭代器.

#include 
#include 
#include 
using namespace std;

bool absEqual(const int x,const int y)
{
	return (x == abs(y) || abs(x) == y) ? 1 : 0;
}

int main(int argc, char* argv[])
{
	vector var1;
	vector var2;

	// 初始化向量
	for (unsigned int x = 0; x < var1.size(); x++)
	{
		var1[x] = x;
		var2[x] = -1 * x;
	}

	// 判断v1和v2元素的绝对值是否完全相等
	if (equal(var1.begin(), var1.end(), var2.begin(), absEqual))
	{
		cout << "完全相等" << endl;
	}
	system("pause");
	return 0;
}

子序列搜索算法 search: 该算法实现了在一个序列中搜索与另一个序列匹配的子序列.

#include 
#include 
#include 
using namespace std;

int main(int argc, char* argv[])
{
	vector var1 = { 5, 6, 7, 8, 9 };
	vector var2 = { 7, 8 };

	// 检查var2是否构成var1的子序列
	vector::iterator it;
	it = search(var1.begin(), var1.end(), var2.begin(),var2.end());
	if (it != var1.end())
	{ // 输出var2元素包含在var1中,的起始元素为
		cout << "Offset = " << it - var1.begin() << endl;
	}

	system("pause");
	return 0;
}

重复元素子序列搜索 search_n: 该算法搜索序列中是否有一系列元素值均为某个给定值得子序列.

#include 
#include 
#include 
using namespace std;

int main(int argc, char* argv[])
{
	vector var1 = { 5, 6, 7, 8,8,8,9 };

	// 查找var1中存在三个连续是8的数据
	vector::iterator it;
	it = search_n(var1.begin(), var1.end(), 3, 8);
	if (it != var1.end())
	{
		cout << "var1中存在三连8" << endl;
	}

	system("pause");
	return 0;
}

最后一个子序列搜索 find_end: 该算法在一个序列中搜索出最后一个与另一个序列匹配的子序列.

#include 
#include 
#include 
using namespace std;

int main(int argc, char* argv[])
{
	vector var1 = { -5,1,2,-6,-8,1,2,-11 };
	vector var2 = { 1, 2 };

	// var1中查找最后一个子序列var2
	vector::iterator it;

	it = find_end(var1.begin(), var1.end(), var2.begin(), var2.end());
	// 打印子序列在var1的起始位置,输出起offset
	if (it != var1.end())
		cout << "offset = [" << it - var1.begin() << "]" << endl;

	system("pause");
	return 0;
}

STL 变易算法(复制与拷贝)

C++ 变易算法是一组能够修改容器元素数据的模板函数,可进行序列数据的复制,交换,替换,分割,等特殊需求,这些算法对迭代器有较高的要求,具体的迭代器类型随各个算法而定,使用变易算法时应先要检查容器的迭代器是否符合要求,避免出现错误.

元素复制算法 copy: 实现容器之间元素的拷贝复制操作,将两个迭代器进行互相拷贝.

#include 
#include 
#include 
using namespace std;

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

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

	// 复制var1到var2 此时var2中的内容将被覆盖
	copy(var1.begin(), var1.end(), var2.begin());
	// var1 -> 覆盖到 --> var2
	for_each(var2.begin(), var2.end(), MyPrint);
	cout << endl;

	// 复制var1中的前3个元素,并输出
	copy_backward(var1.begin(), var1.begin() + 2, var1.end());
	for_each(var1.begin(), var1.end(), MyPrint);

	system("pause");
	return 0;
}

元素交换算法 swap: 该算法可用于实现两个数或两个结构之间数据的互换,使用非常方便.

#include 
#include 
#include 
using namespace std;

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

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

	swap(var1, var2);        // 两个容器之间数值互换
	for_each(var1.begin(), var1.end(), MyPrint);

	iter_swap(&var1, &var2); // 通过迭代的方式实现数值互换
	for_each(var2.begin(), var2.end(), MyPrint);

	swap_ranges(var1.begin(), var1.end(), var2.begin()); // 区间选择交换
	for_each(var2.begin(), var2.end(), MyPrint);

	system("pause");
	return 0;
}

元素搬运算法 transform: 该算法用于实现容器元素的变换操作,例如两个容器相加等操作.

#include 
#include 
#include 
using namespace std;

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

class TransForm
{
	// 在搬运的过程中每次+10写入到vTarget;
public: int operator()(int val)
	{ 
		return val + 10;
	}
};
class New_TransForm
{
	// 使用仿函数,将两个数组中的值相加
public: int operator()(int val1, int val2)
	{
		return val1 + val2;
	}
};

int main(int argc, char* argv[])
{
	vector var = { 1,2,3,4,5 };    // 原容器
	vector vTarget;               // 目标容器

	// 第一种形式：将var中的数据每次+10后搬运到vTarget中
	vTarget.resize(5);    // transform 不会自动开辟内存,需要我们手动开辟
	transform(var.begin(), var.end(), vTarget.begin(), TransForm());
	// 循环输出 此处的 [](int val){cout << val << " ";  其实是 MyPrint 不过是匿名了
	for_each(vTarget.begin(), vTarget.end(), [](int val){cout << val << " "; });
	cout << endl;
	
	// 第二种形式：将var1,var2两个容器中的值相加,相加后搬运到new_vTarget容器中
	vector var1 = { 1, 2, 3, 4, 5 };  // 原容器
	vector var2 = { 6, 7, 8, 9, 10 }; // 原容器
	vector new_vTarget;               // 目标容器
	new_vTarget.resize(5);
	transform(var1.begin(), var1.end(), var2.begin(), new_vTarget.begin(), New_TransForm());
	for_each(new_vTarget.begin(), new_vTarget.end(), MyPrint);

	system("pause");
	return 0;
}

元素替换算法 replace: 该算法的作用是将指定元素的旧值替换为新值.

#include 
#include 
#include 
using namespace std;

void MyPrint(int x) { cout << x << " "; }
class MyCompart
{
public: bool operator()(int val){
	// 将大于5的数据替换
		return val > 5;
	}
};

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

	// 全部替换: 将var中的4全部替换为4000
	replace(var.begin(), var.end(), 4, 4000);  
	for_each(var.begin(), var.end(), MyPrint);

	// 条件替换:将所有的大于5的数替换为0
	replace_if(var.begin(), var.end(), MyCompart(), 0);
	for_each(var.begin(), var.end(), MyPrint);

	system("pause");
	return 0;
}

容器元素初始化算法 fill: 该函数将同一个值填充到容器的指定位置,可用于初始化操作.

#include 
#include 
#include 
using namespace std;

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

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

	// 将前3个元素填充为0
	fill_n(var.begin(), 3, 0);
	for_each(var.begin(), var.end(), MyPrint);

	// 全部填充为0
	fill_n(var.begin(), var.size(), 0);
	for_each(var.begin(), var.end(), MyPrint);

	// 全部填充为10
	fill(var.begin(), var.end(), 10);
	for_each(var.begin(), var.end(), MyPrint);

	system("pause");
	return 0;
}

普通条件移除 remove_if: 该算法可以将容器中不等于某个值的元素移除出容器.

#include 
#include 
#include 
using namespace std;

void MyPrint(int x) { cout << x << " "; }
bool even(int val) { return val % 2 ? 0 : 1; }

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

	// 移除var里面的所有的4
	vector::iterator result;
	result = remove(var.begin(), var.end(), 4);
	for_each(var.begin(), var.end(), MyPrint);
	cout << endl;
	
	// 移除var里面所有的偶数
	vector::iterator result1;
	result1 = remove_if(var.begin(), var.end(), even);
	for_each(var.begin(), var.end(), MyPrint);

	system("pause");
	return 0;
}

条件移除复制 remove_copy: 该算法将原容器中不等于某个给定值的元素复制到新容器中.

#include 
#include 
#include 
using namespace std;

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

bool even(int val){ return val % 2 ? 0 : 1; }

int main(int argc, char* argv[])
{
	vector var { 4,3,4,8,9,5 };
	int iarray[6] = { 0, 0, 0, 0, 0, 0, };

	// 移除复制,将var中的数据的前4个数据复制到iarray中,var中数据保持不变
	remove_copy(var.begin(), var.end(), iarray, 4);
	for_each(iarray, iarray+6, MyPrint);
	cout << endl;

	// 移除var中的偶数,剩余元素复制到iarray中
	remove_copy_if(var.begin(), var.end(), iarray, even);
	for_each(iarray, iarray + 6, MyPrint);
	system("pause");
	return 0;
}

容器元素去重算法 unique: 提供两个算法,unique_copy实现邻近元素去重,unique去除连续重复元素.

#include 
#include 
#include 
using namespace std;

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

int main(int argc, char* argv[])
{
	vector var { 2,5,5,5,5,5,6,7,5,9,5};
	int iarray[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };

	// 实现邻近元素去重,只能去除相邻元素中重复的
	unique_copy(var.begin(), var.end(), iarray);
	for_each(iarray, iarray + 10, MyPrint);
	cout << endl;
	// 另一种邻近元素去重算法
	vector::iterator result;
	result = unique(var.begin(), var.end());
	for_each(var.begin(),result,MyPrint);

	system("pause");
	return 0;
}

元素反向拷贝算法 reverse: 该算法实现了对容器中元素的反向排列,和反向复制容器中的数据.

#include 
#include 
#include 
using namespace std;

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

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

	// 将元素反向排列后输出
	reverse(var.begin(), var.end());
	for_each(var.begin(), var.end(), MyPrint);
	cout << endl;

	// 将元素反向复制到iarray数组中存储
	int iarray[10] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
	reverse_copy(var.begin(), var.end(), iarray);
	for_each(iarray,iarray+10, MyPrint);
	system("pause");
	return 0;
}

容器旋转复制算法 rotate: 该算法用于旋转数值,需要指定一个中心数.

#include 
#include 
#include 
using namespace std;

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

int main(int argc, char* argv[])
{
	vector var { 1,2,3,4,5,6,7,8,9,10 };
	for_each(var.begin(), var.end(), MyPrint);

	// 以元素6为中心,将两边数据旋转后输出
	cout << "middle => " << *(var.begin() + 5) << endl;
	rotate(var.begin(), var.begin() + 5, var.end());
	for_each(var.begin(), var.end(), MyPrint);
	cout << endl;

	// 旋转后复制到iarray数组中存储
	int iarray[10] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
	rotate_copy(var.begin(), var.begin() + 5, var.end(), iarray);
	for_each(iarray,iarray+10, MyPrint);

	system("pause");
	return 0;
}

随机数相关算法 random: 算法generate_n用于生成随机数,random_shuffle用于打乱数组.

#include 
#include 
#include 
#include 
using namespace std;

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

int main(int argc, char* argv[])
{
	// 增加此方法,每次都可以随机打乱
	srand((unsigned int)time(NULL));
	vector var(10);

	// 生成随机数：生成5个随机数,并存入var
	generate_n(var.begin(), 5, rand);
	for_each(var.begin(), var.end(), MyPrint);
	cout << endl;

	// 随机抖动: 随机的打乱一个数组
	int iarray[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	random_shuffle(iarray, iarray + 10);
	for_each(iarray, iarray + 10, MyPrint);

	system("pause");
	return 0;
}

容器元素分割算法 partition: 该算法用于重新分割排列容器的元素,第一种无序分割,第二种为有序分割.

#include 
#include 
#include 
using namespace std;

void MyPrint(int x) { cout << x << " "; }
bool Less(int y){ return y < 10 ? 1 : 0; } // 判断是否小于10

int main(int argc, char* argv[])
{
	int iarray[10] = { 12,45,2,6,8,-5,-12,-78,-4,3 };

	// 按照小于10对容器进行分割
	int * result = partition(iarray, iarray + 10, Less);
	for_each(iarray, result , MyPrint);  // 输出小于10的元素
	cout << endl;

	// 按照小于10对容器分割,但保持原来的次序
	int * new_ret = stable_partition(iarray, iarray + 10, Less);
	for_each(iarray, iarray + 10, MyPrint);
	cout << " --> 分界元素 Mid:" << *new_ret << endl;

	system("pause");
	return 0;
}

C++ STL 标准模板库(非变易/变易)算法

C/C++/C#相关栏目本月热门文章