网站集约化建设困难,网站素材 下载,wordpress移除头部无用,广州专业网站制作哪家专业C提高编程
第五章 STL- 常用算法
三、常用排序算法
算法简介#xff1a;
sort //对容器内元素进行排序random_shuffle //洗牌 指定范围内的元素随机调整次序merge // 容器元素合并#xff0c;并存储到另一容器中reverse // 反转指定范围的元素
1. sort
功能描述#…C提高编程
第五章 STL- 常用算法
三、常用排序算法
算法简介
sort //对容器内元素进行排序random_shuffle //洗牌 指定范围内的元素随机调整次序merge // 容器元素合并并存储到另一容器中reverse // 反转指定范围的元素
1. sort
功能描述
对容器内元素进行排序
函数原型 sort(iterator beg, iterator end, _Pred); // 按值查找元素找到返回指定位置迭代器找不到返回结束迭代器位置 // beg 开始迭代器 // end 结束迭代器 // _Pred 谓词
示例
#include algorithm
#include vectorvoid myPrint(int val)
{cout val ;
}void test01() {vectorint v;v.push_back(10);v.push_back(30);v.push_back(50);v.push_back(20);v.push_back(40);//sort默认从小到大排序sort(v.begin(), v.end());for_each(v.begin(), v.end(), myPrint);cout endl;//从大到小排序sort(v.begin(), v.end(), greaterint());for_each(v.begin(), v.end(), myPrint);cout endl;
}int main() {test01();system(pause);return 0;
}/*10 20 30 40 50 50 40 30 20 10
*/总结 sort属于开发中最常用的算法之一需熟练掌握
2. random_shuffle
功能描述
洗牌 指定范围内的元素随机调整次序
函数原型 random_shuffle(iterator beg, iterator end); // 指定范围内的元素随机调整次序 // beg 开始迭代器 // end 结束迭代器
示例
#include algorithm
#include vector
#include ctimeclass myPrint
{
public:void operator()(int val){cout val ;}
};void test01()
{srand((unsigned int)time(NULL));vectorint v;for(int i 0 ; i 10;i){v.push_back(i);}for_each(v.begin(), v.end(), myPrint());cout endl;//打乱顺序random_shuffle(v.begin(), v.end());for_each(v.begin(), v.end(), myPrint());cout endl;
}int main() {test01();system(pause);return 0;
}/*0 1 2 3 4 5 6 7 8 9 6 0 3 5 7 8 4 1 2 9
*/总结 random_shuffle洗牌算法比较实用使用时记得加随机数种子
3. merge
功能描述
两个容器元素合并并存储到另一容器中
函数原型 merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest); // 容器元素合并并存储到另一容器中 // 注意: 两个容器必须是有序的 // beg1 容器1开始迭代器 // end1 容器1结束迭代器 // beg2 容器2开始迭代器 // end2 容器2结束迭代器 // dest 目标容器开始迭代器
示例
#include algorithm
#include vectorclass myPrint
{
public:void operator()(int val){cout val ;}
};void test01()
{vectorint v1;vectorint v2;for (int i 0; i 10 ; i) {v1.push_back(i);v2.push_back(i 1);}vectorint vtarget;//目标容器需要提前开辟空间vtarget.resize(v1.size() v2.size());//合并 需要两个有序序列merge(v1.begin(), v1.end(), v2.begin(), v2.end(), vtarget.begin());for_each(vtarget.begin(), vtarget.end(), myPrint());cout endl;
}int main() {test01();system(pause);return 0;
}/*0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10
*/总结 merge合并的两个容器必须的有序序列
4. reverse
功能描述
将容器内元素进行反转
函数原型 reverse(iterator beg, iterator end); // 反转指定范围的元素 // beg 开始迭代器 // end 结束迭代器
示例
#include algorithm
#include vectorclass myPrint
{
public:void operator()(int val){cout val ;}
};void test01()
{vectorint v;v.push_back(10);v.push_back(30);v.push_back(50);v.push_back(20);v.push_back(40);cout 反转前 endl;for_each(v.begin(), v.end(), myPrint());cout endl;cout 反转后 endl;reverse(v.begin(), v.end());for_each(v.begin(), v.end(), myPrint());cout endl;
}int main() {test01();system(pause);return 0;
}/*反转前 10 30 50 20 40 反转后 40 20 50 30 10
*/总结 reverse反转区间内元素面试题可能涉及到
四、常用拷贝和替换算法
算法简介
copy // 容器内指定范围的元素拷贝到另一容器中replace // 将容器内指定范围的旧元素修改为新元素replace_if // 容器内指定范围满足条件的元素替换为新元素swap // 互换两个容器的元素
1. copy
功能描述
容器内指定范围的元素拷贝到另一容器中
函数原型 copy(iterator beg, iterator end, iterator dest); // 按值查找元素找到返回指定位置迭代器找不到返回结束迭代器位置 // beg 开始迭代器 // end 结束迭代器 // dest 目标起始迭代器
示例
#include algorithm
#include vectorclass myPrint
{
public:void operator()(int val){cout val ;}
};void test01()
{vectorint v1;for (int i 0; i 10; i) {v1.push_back(i 1);}vectorint v2;v2.resize(v1.size());copy(v1.begin(), v1.end(), v2.begin());for_each(v2.begin(), v2.end(), myPrint());cout endl;
}int main() {test01();system(pause);return 0;
}/*1 2 3 4 5 6 7 8 9 10
*/总结 利用copy算法在拷贝时目标容器记得提前开辟空间
2. replace
功能描述
将容器内指定范围的旧元素修改为新元素
函数原型 replace(iterator beg, iterator end, oldvalue, newvalue); // 将区间内旧元素 替换成 新元素 // beg 开始迭代器 // end 结束迭代器 // oldvalue 旧元素 // newvalue 新元素
示例
#include algorithm
#include vectorclass myPrint
{
public:void operator()(int val){cout val ;}
};void test01()
{vectorint v;v.push_back(20);v.push_back(30);v.push_back(20);v.push_back(40);v.push_back(50);v.push_back(10);v.push_back(20);cout 替换前 endl;for_each(v.begin(), v.end(), myPrint());cout endl;//将容器中的20 替换成 2000cout 替换后 endl;replace(v.begin(), v.end(), 20, 2000);for_each(v.begin(), v.end(), myPrint());cout endl;
}int main() {test01();system(pause);return 0;
}/*替换前20 30 20 40 50 10 20 替换后2000 30 2000 40 50 10 2000
*/总结 replace会替换区间内满足条件的元素
3. replace_if
功能描述:
将区间内满足条件的元素替换成指定元素
函数原型 replace_if(iterator beg, iterator end, _pred, newvalue); // 按条件替换元素满足条件的替换成指定元素 // beg 开始迭代器 // end 结束迭代器 // _pred 谓词 // newvalue 替换的新元素
示例
#include algorithm
#include vectorclass myPrint
{
public:void operator()(int val){cout val ;}
};class ReplaceGreater30
{
public:bool operator()(int val){return val 30;}};void test01()
{vectorint v;v.push_back(20);v.push_back(30);v.push_back(20);v.push_back(40);v.push_back(50);v.push_back(10);v.push_back(20);cout 替换前 endl;for_each(v.begin(), v.end(), myPrint());cout endl;//将容器中大于等于的30 替换成 3000cout 替换后 endl;replace_if(v.begin(), v.end(), ReplaceGreater30(), 3000);for_each(v.begin(), v.end(), myPrint());cout endl;
}int main() {test01();system(pause);return 0;
}/*替换前20 30 20 40 50 10 20 替换后20 3000 20 3000 3000 10 20
*/总结 replace_if按条件查找可以利用仿函数灵活筛选满足的条件
4. swap
功能描述
互换两个容器的元素
函数原型 swap(container c1, container c2); // 互换两个容器的元素 // c1容器1 // c2容器2
示例
#include algorithm
#include vectorclass myPrint
{
public:void operator()(int val){cout val ;}
};void test01()
{vectorint v1;vectorint v2;for (int i 0; i 10; i) {v1.push_back(i);v2.push_back(i100);}cout 交换前 endl;for_each(v1.begin(), v1.end(), myPrint());cout endl;for_each(v2.begin(), v2.end(), myPrint());cout endl;cout 交换后 endl;swap(v1, v2);for_each(v1.begin(), v1.end(), myPrint());cout endl;for_each(v2.begin(), v2.end(), myPrint());cout endl;
}int main() {test01();system(pause);return 0;
}/*交换前 0 1 2 3 4 5 6 7 8 9 100 101 102 103 104 105 106 107 108 109 交换后 100 101 102 103 104 105 106 107 108 109 0 1 2 3 4 5 6 7 8 9
*/总结 swap交换容器时注意交换的容器要同种类型
五、常用算术生成算法
注意
算术生成算法属于小型算法使用时包含的头文件为 #include numeric
算法简介 accumulate // 计算容器元素累计总和 fill // 向容器中添加元素
1. accumulate
功能描述
计算区间内 容器元素累计总和
函数原型 accumulate(iterator beg, iterator end, value); // 计算容器元素累计总和 // beg 开始迭代器 // end 结束迭代器 // value 起始值
示例
#include numeric
#include vector
void test01()
{vectorint v;for (int i 0; i 100; i) {v.push_back(i);}int total accumulate(v.begin(), v.end(), 0);cout total total endl;
}int main() {test01();system(pause);return 0;
}/*total 5050
*/总结 accumulate使用时头文件注意是 numeric这个算法很实用
2. fill
功能描述
向容器中填充指定的元素
函数原型 fill(iterator beg, iterator end, value); // 向容器中填充元素 // beg 开始迭代器 // end 结束迭代器 // value 填充的值
示例
#include numeric
#include vector
#include algorithmclass myPrint
{
public:void operator()(int val){cout val ;}
};void test01()
{vectorint v;v.resize(10);//填充fill(v.begin(), v.end(), 100);for_each(v.begin(), v.end(), myPrint());cout endl;
}int main() {test01();system(pause);return 0;
}/*100 100 100 100 100 100 100 100 100 100
*/总结 利用fill可以将容器区间内元素填充为 指定的值
六、常用集合算法
算法简介 set_intersection // 求两个容器的交集 set_union // 求两个容器的并集 set_difference // 求两个容器的差集
1. set_intersection
功能描述
求两个容器的交集
函数原型 set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest); // 求两个集合的交集 // 注意:两个集合必须是有序序列 // beg1 容器1开始迭代器 // end1 容器1结束迭代器 // beg2 容器2开始迭代器 // end2 容器2结束迭代器 // dest 目标容器开始迭代器
示例
#include vector
#include algorithmclass myPrint
{
public:void operator()(int val){cout val ;}
};void test01()
{vectorint v1;vectorint v2;for (int i 0; i 10; i){v1.push_back(i);v2.push_back(i5);}vectorint vTarget;//取两个里面较小的值给目标容器开辟空间vTarget.resize(min(v1.size(), v2.size()));//返回目标容器的最后一个元素的迭代器地址vectorint::iterator itEnd set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());for_each(vTarget.begin(), itEnd, myPrint());cout endl;
}int main() {test01();system(pause);return 0;
}/*5 6 7 8 9
*/总结
求交集的两个集合必须的有序序列目标容器开辟空间需要从两个容器中取小值set_intersection返回值既是交集中最后一个元素的位置
2. set_union
功能描述
求两个集合的并集
函数原型 set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest); // 求两个集合的并集 // 注意:两个集合必须是有序序列 // beg1 容器1开始迭代器 // end1 容器1结束迭代器 // beg2 容器2开始迭代器 // end2 容器2结束迭代器 // dest 目标容器开始迭代器
示例
#include vector
#include algorithmclass myPrint
{
public:void operator()(int val){cout val ;}
};void test01()
{vectorint v1;vectorint v2;for (int i 0; i 10; i) {v1.push_back(i);v2.push_back(i5);}vectorint vTarget;//取两个容器的和给目标容器开辟空间vTarget.resize(v1.size() v2.size());//返回目标容器的最后一个元素的迭代器地址vectorint::iterator itEnd set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());for_each(vTarget.begin(), itEnd, myPrint());cout endl;
}int main() {test01();system(pause);return 0;
}/*0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
*/总结
求并集的两个集合必须的有序序列目标容器开辟空间需要两个容器相加set_union返回值既是并集中最后一个元素的位置
3. set_difference
功能描述
求两个集合的差集
函数原型 set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest); // 求两个集合的差集 // 注意:两个集合必须是有序序列 // beg1 容器1开始迭代器 // end1 容器1结束迭代器 // beg2 容器2开始迭代器 // end2 容器2结束迭代器 // dest 目标容器开始迭代器
示例
#include vector
#include algorithmclass myPrint
{
public:void operator()(int val){cout val ;}
};void test01()
{vectorint v1;vectorint v2;for (int i 0; i 10; i) {v1.push_back(i);v2.push_back(i5);}vectorint vTarget;//取两个里面较大的值给目标容器开辟空间vTarget.resize( max(v1.size() , v2.size()));//返回目标容器的最后一个元素的迭代器地址cout v1与v2的差集为 endl;vectorint::iterator itEnd set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());for_each(vTarget.begin(), itEnd, myPrint());cout endl;cout v2与v1的差集为 endl;itEnd set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), vTarget.begin());for_each(vTarget.begin(), itEnd, myPrint());cout endl;
}int main() {test01();system(pause);return 0;
}/*v1与v2的差集为 0 1 2 3 4 v2与v1的差集为 10 11 12 13 14
*/总结
求差集的两个集合必须的有序序列目标容器开辟空间需要从两个容器取较大值set_difference返回值既是差集中最后一个元素的位置
