C++之STL（四）

痛定思痛。 2022-01-06 12:15 152阅读 0赞

**目录**

1、遍历算法

2、查找算法

3、排序算法

4、拷贝和替换算法

5、生成算法

6、集合算法

--------------------

算法主要是由头文件<algorithm> <functional> <numeric>组成。

*  <algorithm>是所有STL头文件中最大的一个,其中常用的功能涉及到比较，交换，查找,遍历，复制，修改，反转，排序，合并等...
 *  <numeric>体积很小，只包括在几个序列容器上进行的简单运算的模板函数.
 *  <functional> 定义了一些模板类,用以声明函数对象。

### 1、遍历算法 ###

*  for\_each 可有返回值
 *  可以绑定参数进行输出
 *  transform 将容器中的数据进行搬运到另一个容器中
 *  注意：目标容器需要开辟空间！！！！！

#define _CRT_SECURE_NO_WARNINGS
    #include<iostream>
    #include<vector>
    #include<algorithm>
    #include<functional>
    using namespace std;
    
    /*
    遍历算法 遍历容器元素
    @param beg 开始迭代器
    @param end 结束迭代器
    @param _callback  函数回调或者函数对象
    @return 函数对象
    
    
    */
    
    //void myPrint(int v)
    //{
    //	cout << v << endl;
    //}
    
    //class myPrint01
    //{
    //public:
    //	void operator()(int v)
    //	{
    //		cout << v << endl;
    //	}
    //};
    
    struct myPrint01
    {
    	void operator()(int v)
    	{
    		cout << v << endl;
    	}
    };
    
    void test01()
    {
    	vector<int>v;
    	for (int i = 0; i < 10; i++)
    	{
    		v.push_back(i);
    	}
    
    	//for_each(v.begin(), v.end(), myPrint);
    	for_each(v.begin(), v.end(), myPrint01());
    }
    
    struct myPrint02
    {
    	void operator()(int v)
    	{
    		cout << v << endl;
    		m_Count++;
    	}
    	int m_Count;
    };
    
    //for_each有返回值
    void test02()
    {
    	vector<int>v;
    	for (int i = 0; i < 10; i++)
    	{
    		v.push_back(i);
    	}
    
    	//for_each(v.begin(), v.end(), myPrint);
    	myPrint02 print2 = for_each(v.begin(), v.end(), myPrint02());
    	cout << print2.m_Count << endl;
    }
    
    //for_each可以绑定参数进行输出
    struct myPrint03 :public binary_function<int, int, void>
    {
    	void operator()(int v, int start) const
    	{
    		cout << v + start << endl;
    	}
    };
    
    void test03()
    {
    	vector<int>v;
    	for (int i = 0; i < 10; i++)
    	{
    		v.push_back(i);
    	}
    
    	for_each(v.begin(), v.end(), bind2nd(myPrint03(), 10000));
    }
    
    /*
    transform算法 将指定容器区间元素搬运到另一容器中
    !!!注意 : transform 不会给目标容器分配内存，所以需要我们提前分配好内存
    @param beg1 源容器开始迭代器
    @param end1 源容器结束迭代器
    @param beg2 目标容器开始迭代器
    @param _cakkback 回调函数或者函数对象
    @return 返回目标容器迭代器
    */
    
    class TransForm
    {
    public:
    	int operator()(int val)
    	{
    		return val + 10;
    	}
    };
    
    
    void test04()
    {
    	vector<int>v;  //原容器
    	for (int i = 0; i < 10; i++)
    	{
    		v.push_back(i);
    	}
    
    	vector<int>vTarget;  //目标容器
    	vTarget.resize(v.size());
    	transform(v.begin(), v.end(), vTarget.begin(), TransForm());
    
    	for_each(vTarget.begin(), vTarget.end(), [](int val){cout << val << " "; });
    }
    
    //transform 第二种用法  将两个容器数据相加搬运到目标容器
    class TransForm2
    {
    public:
    	int operator()(int val1, int val2)
    	{
    		return val1 + val2;
    	}
    };
    
    void test05()
    {
    	vector<int>v1;
    	vector<int>v2;
    
    	for (int i = 0; i < 10; i++)
    	{
    		v1.push_back(100 + i);
    		v2.push_back(200 + i);
    	}
    
    	vector<int>vTarget;
    	vTarget.resize(v1.size());  //两个容器大小一致，也可以使用v2.size()，效果等同
    	transform(v1.begin(), v1.end(), v2.begin(), vTarget.begin(), TransForm2());
    
    	//300  302   304
    	for_each(vTarget.begin(), vTarget.end(), [](int val){cout << val << " "; });
    }
    
    
    int main()
    {
    	//test01();
    	//test02();
    
    	//test03();
    	//test04();
    	test05();
    	system("pause");
    	return 0;
    }

### 2、查找算法 ###

*  find 按值查找
 *  find\_if 按条件查找 Person\*
 *  adjacent\_find算法 查找相邻重复元素 返回第一个重复元素的迭代器位置
 *  binary\_search算法 二分法查找 必须容器是有序数列

#define _CRT_SECURE_NO_WARNINGS
    #include<iostream>
    #include<vector>
    #include<algorithm>
    #include<functional>
    #include<string>
    using namespace std;
    
    /*
    find算法 查找元素
    @param beg 容器开始迭代器
    @param end 容器结束迭代器
    @param value 查找的元素
    @return 返回查找元素的位置
    */
    
    void test01()
    {
    	vector<int> v;
    	for (int i = 0; i < 10; i++)
    	{
    		v.push_back(i);
    	}
    	vector<int>::iterator pos = find(v.begin(), v.end(), 5);
    	if (pos != v.end())
    	{
    		cout << "找到了数据 " << *pos << endl;
    	}
    	else
    	{
    		cout << "未找到" << endl;
    	}
    }
    
    class Person
    {
    public:
    	Person(string name, int age)
    	{
    		this->m_Name = name;
    		this->m_Age = age;
    	}
    
    	bool operator==(const Person&p)
    	{
    		if (this->m_Name == p.m_Name&& this->m_Age == p.m_Age)
    		{
    			return true;
    		}
    		else
    		{
    			return false;
    		}
    	}
    	string m_Name;
    	int m_Age;
    };
    
    //利用find查找自定义的数据类型
    void test02()
    {
    	vector<Person>v;
    
    	Person p1("aaa", 10);
    	Person p2("bbb", 20);
    	Person p3("ccc", 30);
    	Person p4("ddd", 40);
    
    	v.push_back(p1);
    	v.push_back(p2);
    	v.push_back(p3);
    	v.push_back(p4);
    
    	vector<Person>::iterator pos = find(v.begin(), v.end(), p2);
    	if (pos != v.end())
    	{
    		cout << "找到了姓名数据 " << (*pos).m_Name << "  年龄 " << (*pos).m_Age << endl;
    	}
    	else
    	{
    		cout << "未找到" << endl;
    	}
    }
    
    /*
    find_if算法 条件查找
    @param beg 容器开始迭代器
    @param end 容器结束迭代器
    @param  callback 回调函数或者谓词(返回bool类型的函数对象)
    @return bool 查找返回true 否则false
    */
    
    class MyCompare : public binary_function<Person*, Person*, bool>
    {
    public:
    	bool operator()(Person *p1, Person *p2) const
    	{
    		if (p1->m_Name == p2->m_Name && p1->m_Age == p2->m_Age)
    		{
    			return true;
    		}
    		else
    		{
    			return false;
    		}
    	}
    };
    
    void test03()
    {
    	vector<Person*>v;
    
    	Person p1("aaa", 10);
    	Person p2("bbb", 20);
    	Person p3("ccc", 30);
    	Person p4("ddd", 40);
    
    	v.push_back(&p1);
    	v.push_back(&p2);
    	v.push_back(&p3);
    	v.push_back(&p4);
    
    	Person * p = new Person("bbb", 21);
    	
    	vector<Person*>::iterator pos = find_if(v.begin(), v.end(), bind2nd(MyCompare(),p));
    	if (pos != v.end())
    	{
    		cout << "找到了姓名数据 " << (*pos)->m_Name << "  年龄 " << (*pos)->m_Age << endl;
    	}
    	else
    	{
    		cout << "未找到" << endl;
    	}
    }
    
    /*
    adjacent_find算法 查找相邻重复元素
    @param beg 容器开始迭代器
    @param end 容器结束迭代器
    @param  _callback 回调函数或者谓词(返回bool类型的函数对象)
    @return 返回相邻元素的第一个位置的迭代器
    */
    
    void test04()
    {
    	vector<int>v;
    	v.push_back(2);
    	v.push_back(3);
    	v.push_back(4);
    	v.push_back(5);
    	v.push_back(5);
    	v.push_back(6);
    	v.push_back(2);
    
    	vector<int>::iterator pos = adjacent_find(v.begin(), v.end());
    
    	if (pos != v.end())
    	{
    		cout << "找到了相邻重复元素为：" << *pos << endl;
    	}
    	else
    	{
    		cout << "没找到" << endl;
    	}
    }
    
    /*
    binary_search算法 二分查找法
    注意: 在无序序列中不可用
    @param beg 容器开始迭代器
    @param end 容器结束迭代器
    @param value 查找的元素
    @return bool 查找返回true 否则false
    */
    
    void test05()
    {
    	vector<int>v;
    	for (int i = 0; i < 10; i++)
    	{
    		v.push_back(i);
    	}
    
    	bool ret = binary_search(v.begin(), v.end(), 4);
    
    	if (ret)
    	{
    		cout << "找到了4" << endl;
    	}
    	else
    	{
    		cout << "未找到" << endl;
    	}
    
    }
    
    /*
    count算法 统计元素出现次数
    @param beg 容器开始迭代器
    @param end 容器结束迭代器
    @param  value回调函数或者谓词(返回bool类型的函数对象)
    @return int返回元素个数
    */
    
    /*
    count_if算法 统计元素出现次数
    @param beg 容器开始迭代器
    @param end 容器结束迭代器
    @param  callback 回调函数或者谓词(返回bool类型的函数对象)
    @return int返回元素个数
    */
    
    class GreaterThan4
    {
    public:
    	bool operator()(int v)
    	{
    		return v >= 4;
    	}
    };
    
    void test06()
    {
    	vector<int>v;
    	for (int i = 0; i < 10; i++)
    	{
    		v.push_back(i);
    	}
    
    	v.push_back(4);
    	v.push_back(4);
    	v.push_back(4);
    	v.push_back(4);
    
    	int num = count(v.begin(), v.end(), 4);
    	cout << "4的个数为：" << num << endl;
    
    	num = count_if(v.begin(), v.end(), GreaterThan4());
    	cout << "大于等于4的个数为：" << num << endl;
    }
    
    int main()
    {
    	//test01();
    	//test02();
    	//test03();
    	//test04();
    	//test05();
    	test06();
    	system("pause");
    	return 0;
    }

### 3、排序算法 ###

*  merge算法容器元素合并，并存储到另一容器中，两容器要有序，并且顺序一致。
 *  sort排序（常用）
 *  random\_shuffle 洗牌 随机 自己提供随机种子（常用）
 *  reverse反转

#define _CRT_SECURE_NO_WARNINGS
    #include<iostream>
    #include<algorithm>
    #include<vector>
    #include<functional>
    #include<ctime>
    using namespace std;
    
    /*
    merge算法 容器元素合并，并存储到另一容器中,这两个容器必须也是有序的
    @param beg1 容器1开始迭代器
    @param end1 容器1结束迭代器
    @param beg2 容器2开始迭代器
    @param end2 容器2结束迭代器
    @param dest  目标容器开始迭代器
    */
    
    void test01()
    {
    	vector<int>v1;
    	vector<int>v2;
    
    	for (int i = 0; i < 10; i++)
    	{
    		v1.push_back(i);
    		v2.push_back(i + 1);
    	}
    
    	vector<int>vTarget;
    	vTarget.resize(v1.size() + v2.size());
    	merge(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());
    
    	for_each(vTarget.begin(), vTarget.end(), [](int v){cout << v << " "; });
    }
    
    //重点：sort
    /*
    sort算法 容器元素排序
    注意:两个容器必须是有序的
    @param beg 容器1开始迭代器
    @param end 容器1结束迭代器
    @param _callback 回调函数或者谓词(返回bool类型的函数对象)
    */
    
    void test02()
    {
    	vector<int>v1;
    
    	v1.push_back(10);
    	v1.push_back(40);
    	v1.push_back(20);
    	v1.push_back(30);
    
    	sort(v1.begin(), v1.end());
    	for_each(v1.begin(), v1.end(), [](int val){cout << val << " "; });
    	cout << endl;
    
    	//降序
    	sort(v1.begin(), v1.end(), greater<int>());
    	for_each(v1.begin(), v1.end(), [](int val){cout << val << " "; });
    	cout << endl;
    }
    
    /*
    random_shuffle算法 对指定范围内的元素随机调整次序   洗牌算法
    @param beg 容器开始迭代器
    @param end 容器结束迭代器
    */
    
    void test03()
    {
    	vector<int>v;
    	for (int i = 0; i < 10; i++)
    	{
    		v.push_back(i);
    	}
    	random_shuffle(v.begin(), v.end());
    	for_each(v.begin(), v.end(), [](int val){cout << val << " "; });
    }
    
    /*
    reverse算法 反转指定范围的元素
    @param beg 容器开始迭代器
    @param end 容器结束迭代器
    */
    
    void test04()
    {
    	vector<int>v;
    	for (int i = 0; i < 10; i++)
    	{
    		v.push_back(i);
    	}
    	reverse(v.begin(), v.end());
    	for_each(v.begin(), v.end(), [](int val){cout << val << " "; });
    }
    
    
    
    int main()
    {
    	srand((unsigned int)time(NULL));
    	//test01();
    	//test02();
    	//test03();
    	test04();
    	system("pause");
    	return 0;
    }

### 4、拷贝和替换算法 ###

*  copy复制
 *  replace replace\_if （常用）
 *  reverse
 *  swap

#define _CRT_SECURE_NO_WARNINGS
    #include<iostream>
    #include<vector>
    #include<algorithm>
    #include<functional>
    #include<iterator>
    using namespace std;
    
    /*
    copy算法 将容器内指定范围的元素拷贝到另一容器中
    @param beg 容器开始迭代器
    @param end 容器结束迭代器
    @param dest 目标起始迭代器
    */
    
    void test01()
    {
    	vector<int>v;
    	for (int i = 0; i < 10; i++)
    	{
    		v.push_back(i);
    	}
    	vector<int>vTarget;
    	vTarget.resize(v.size());
    
    	copy(v.begin(), v.end(), vTarget.begin());
    
    	//for_each(vTarget.begin(), vTarget.end(), [](int val){cout << val << " "; });
    
    	copy(vTarget.begin(), vTarget.end(), ostream_iterator<int>(cout, " "));
    }
    
    /*
    replace算法 将容器内指定范围的旧元素修改为新元素
    @param beg 容器开始迭代器
    @param end 容器结束迭代器
    @param oldvalue 旧元素
    @param oldvalue 新元素
    */
    
    
    /*
    replace_if算法 将容器内指定范围满足条件的元素替换为新元素
    @param beg 容器开始迭代器
    @param end 容器结束迭代器
    @param callback函数回调或者谓词(返回Bool类型的函数对象)
    @param oldvalue 新元素
    */
    class myCompare
    {
    public:
    	bool operator()(int v)
    	{
    		return v > 3;
    	}
    };
    
    void test02()
    {
    	vector<int>v;
    	for (int i = 0; i < 10; i++)
    	{
    		v.push_back(i);
    	}
    
    	//需求  把容器中的3替换成300
    	replace(v.begin(), v.end(), 3, 300);
    	copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
    	cout << endl;
    
    	//需求  把所有大于3的数字替换成30000
    
    	replace_if(v.begin(), v.end(), myCompare(), 30000);
    	copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
    }
    
    /*
    swap算法 互换两个容器的元素
    @param c1容器1
    @param c2容器2
    */
    
    void test03()
    {
    	vector<int>v1;
    	for (int i = 0; i < 10; i++)
    	{
    		v1.push_back(i);
    	}
    
    	vector<int>v2;
    	v2.push_back(10);
    	v2.push_back(30);
    	v2.push_back(20);
    	v2.push_back(40);
    
    	cout << "交换前数据：" << endl;
    	copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
    	cout << endl;
    	copy(v2.begin(), v2.end(), ostream_iterator<int>(cout, " "));
    	cout << endl;
    
    	cout << "交换后的数据：" << endl;
    	swap(v1, v2);
    	copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
    	cout << endl;
    	copy(v2.begin(), v2.end(), ostream_iterator<int>(cout, " "));
    	cout << endl;
    
    }
    
    int main()
    {
    	//test01();
    	//test02();
    	test03();
    	system("pause");
    	return 0;
    }

### 5、生成算法 ###

*  头文件 numeric
 *  accumulate 累加
 *  fill 填充

#define _CRT_SECURE_NO_WARNINGS
    #include<iostream>
    #include<algorithm>
    #include<numeric>
    #include<vector>
    #include<iterator>
    using namespace std;
    
    /*
    accumulate算法 计算容器元素累计总和
    @param beg 容器开始迭代器
    @param end 容器结束迭代器
    @param value累加值
    */
    //accumulate(iterator beg, iterator end, value)
    
    
    void test01()
    {
    	vector<int>v;
    	for (int i = 0; i <= 100; i++)
    	{
    		v.push_back(i);
    	}
    
    	//0~100累计和  5050  第三个参数是起始值
    	int sum = accumulate(v.begin(), v.end(), 0);
    	cout << "总和为：" << sum << endl;
    }
    
    /*
    fill算法 向容器中添加元素
    @param beg 容器开始迭代器
    @param end 容器结束迭代器
    @param value t填充元素
    */
    //fill(iterator beg, iterator end, value)
    
    void test02()
    {
    	vector<int>v;
    
    	v.resize(10);
    
    	fill(v.begin(), v.end(), 1000);
    	copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
    }
    
    int main()
    {
    	//test01();
    	test02();
    	system("pause");
    	return 0;
    }

### 6、集合算法 ###

*  交集 set\_intersection
 *  并集 set\_union
 *  差集 set\_difference

#include<iostream>
    #include<vector>
    #include<algorithm>
    #include<iterator>
    using namespace std;
    
    /*
    set_intersection算法 求两个set集合的交集
    注意:两个集合必须是有序序列
    @param beg1 容器1开始迭代器
    @param end1 容器1结束迭代器
    @param beg2 容器2开始迭代器
    @param end2 容器2结束迭代器
    @param dest  目标容器开始迭代器
    @return 目标容器的最后一个元素的迭代器地址
    */
    
    void test01()
    {
    	vector<int>v1;
    	vector<int>v2;
    
    	for (int i = 0; i < 10; i++)
    	{
    		v1.push_back(i);
    		v2.push_back(i + 5);
    	}
    
    	vector<int>vTarget;
    	vTarget.resize(min(v1.size(), v2.size()));
    	vector<int>::iterator itEnd = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());
    
    	copy(vTarget.begin(), itEnd, ostream_iterator<int>(cout, " "));
    }
    
    /*
    set_union算法 求两个set集合的并集
    注意:两个集合必须是有序序列
    @param beg1 容器1开始迭代器
    @param end1 容器1结束迭代器
    @param beg2 容器2开始迭代器
    @param end2 容器2结束迭代器
    @param dest  目标容器开始迭代器
    @return 目标容器的最后一个元素的迭代器地址
    */
    
    void test02()
    {
    	vector<int>v1;
    	vector<int>v2;
    
    	for (int i = 0; i < 10; i++)
    	{
    		v1.push_back(i);
    		v2.push_back(i + 5);
    	}
    
    	vector<int>vTarget;
    	vTarget.resize(v1.size() + v2.size());
    	vector<int>::iterator itEnd = set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());
    
    	copy(vTarget.begin(), itEnd, ostream_iterator<int>(cout, " "));
    }
    
    /*
    set_difference算法 求两个set集合的差集
    注意:两个集合必须是有序序列
    @param beg1 容器1开始迭代器
    @param end1 容器1结束迭代器
    @param beg2 容器2开始迭代器
    @param end2 容器2结束迭代器
    @param dest  目标容器开始迭代器
    @return 目标容器的最后一个元素的迭代器地址
    */
    
    void test03()
    {
    	vector<int>v1;
    	vector<int>v2;
    
    	for (int i = 0; i < 10; i++)
    	{
    		v1.push_back(i);
    		v2.push_back(i + 5);
    	}
    
    	vector<int>vTarget;
    	vTarget.resize(max(v1.size(),v2.size()));
    	//v1差v2
    	vector<int>::iterator itEnd = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());
    
    	copy(vTarget.begin(), itEnd, ostream_iterator<int>(cout, " "));
    
    	cout << endl;
    	//v2差v1
    	itEnd = set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), vTarget.begin());
    
    	copy(vTarget.begin(), itEnd, ostream_iterator<int>(cout, " "));
    }
    
    int main()
    {
    	//test01();
    	//test02();
    
    	test03();
    	system("pause");
    	return 0;
    }