1 常用排序算法

学习目标： 掌握常用的排序算法

算法简介：

• sort //对容器内元素进行排序
• random_shuffle //洗牌 指定范围内的元素随机调整次序
• merge // 容器元素合并，并存储到另一容器中
• reverse // 反转指定范围的元素

1.1 sort

功能描述： 对容器内元素进行排序，默认升序

函数原型： sort(iterator beg, iterator end, _Pred);

// beg 开始迭代器
// end 结束迭代器
// _Pred 谓词 可填 可不填 改变排序规则

sort的使用在之前的学习中也有用到，比如list容器的排序，以下简单展示。

代码示例：

void mtprint(int val)
{cout << val << "  ";
}void test1()
{vector v1;v1.push_back(18);v1.push_back(23);v1.push_back(21);v1.push_back(23);v1.push_back(28);v1.push_back(30);v1.push_back(26);v1.push_back(32);v1.push_back(35);cout << "排序前\nv1：";for_each(v1.begin(), v1.end(), mtprint);cout << endl << endl;sort(v1.begin(), v1.end());cout << "sort排序 默认升序\nv1：";for_each(v1.begin(), v1.end(), mtprint);cout << endl << endl;sort(v1.begin(), v1.end(), greater());cout << "sort排序 加入谓词 降序\nv1：";for_each(v1.begin(), v1.end(), mtprint);cout << endl << endl;
}

在sort源码中，使用谓词less，默认升序

如果是自定义数据类型，可以自己写谓词来定义排序规则。

总结： sort属于开发中最常用的算法之一，需熟练掌握

1.2 random_shuffle

功能描述： 洗牌 指定范围内的元素随机调整次序

函数原型： random_shuffle(iterator beg, iterator end);

// beg 开始迭代器
// end 结束迭代器​

代码示例：

void mtprint(int val)
{cout << val << "  ";
}void test1()
{vector v;for (int i = 0; i < 10; i++){v.push_back(i + 1);}cout << "v：";for_each(v.begin(), v.end(), mtprint);cout << endl << endl;cout << "打乱后\nv：";srand((unsigned int)time(NULL));//产生真实随机种子random_shuffle(v.begin(), v.end());for_each(v.begin(), v.end(), mtprint);cout << endl << endl;
}

总结： random_shuffle洗牌算法比较实用，使用时记得加随机数种子

1.3 merge

功能描述： 两个容器元素合并，并存储到另一容器中，注意: 两个容器必须是有序的

函数原型： merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

// beg1 容器1开始迭代器
// end1 容器1结束迭代器
// beg2 容器2开始迭代器
// end2 容器2结束迭代器
// dest 目标容器开始迭代器​

代码示例：

void mtprint(int val)
{cout << val << "  ";
}void test1()
{vector v1;//有序 顺序一致vector v2;//有序 顺序一致for (int i = 0; i < 10; i++){v1.push_back(i + 1);v2.push_back(i + 11);}cout << "v1：";for_each(v1.begin(), v1.end(), mtprint);cout << endl << endl;cout << "v2：";for_each(v2.begin(), v2.end(), mtprint);cout << endl << endl;vector vtarget;vtarget.resize(v1.size() + v2.size());//必须提前开辟内存空间merge(v1.begin(), v1.end(), v2.begin(), v2.end(), vtarget.begin());cout << "vtarget：";for_each(vtarget.begin(), vtarget.end(), mtprint);cout << endl << endl;
}

总结：

• merge合并的两个容器必须的有序序列，并且顺序要一致，不能一个是升序，一个是降序
• merge后的目标容器必须提前开辟内存空间

1.4 reverse

功能描述： 将容器内元素进行反转，反转指定范围的元素

函数原型： reverse(iterator beg, iterator end);

// beg 开始迭代器
// end 结束迭代器

代码示例：

void mtprint(int val)
{cout << val << "  ";
}void test1()
{vector v;for (int i = 0; i < 10; i++){v.push_back(i + 21);}cout << "反转前" << endl;cout << "v：";for_each(v.begin(), v.end(), mtprint);cout << endl << endl;cout << "反转后" << endl;reverse(v.begin(), v.end());cout << "v：";for_each(v.begin(), v.end(), mtprint);cout << endl << endl;
}

总结： reverse反转区间内元素，面试题可能涉及到

2 常用拷贝和替换算法

学习目标： 掌握常用的拷贝和替换算法

算法简介：

• copy // 容器内指定范围的元素拷贝到另一容器中
• replace // 将容器内指定范围的旧元素修改为新元素
• replace_if // 容器内指定范围满足条件的元素替换为新元素
• swap // 互换两个容器的元素

2.1 copy

功能描述： 容器内指定范围的元素拷贝到另一容器中。

函数原型：

• copy(iterator beg, iterator end, iterator dest);

  // beg 开始迭代器
  // end 结束迭代器
  // dest 目标起始迭代器

代码示例：

void mtprint(int val)
{cout << val << "  ";
}void test1()
{vector v1;for (int i = 0; i < 10; i++){v1.push_back(i + 21);}cout << "v1：";for_each(v1.begin(), v1.end(), mtprint);cout << endl << endl;vector v2;v2.resize(v1.size());copy(v1.begin(), v1.end(), v2.begin());cout << "v2：";for_each(v2.begin(), v2.end(), mtprint);cout << endl << endl;
}

总结： 利用copy算法在拷贝时，目标容器记得提前开辟空间

2.2 replace

功能描述： 将容器内指定范围的旧元素修改为新元素

函数原型： replace(iterator beg, iterator end, oldvalue, newvalue);

// beg 开始迭代器
// end 结束迭代器
// oldvalue 旧元素
// newvalue 新元素

代码示例：

void mtprint(int val)
{cout << val << "  ";
}void test1()
{vector v;for (int i = 0; i < 5; i++){v.push_back(i + 21);}v.push_back(25);v.push_back(25);v.push_back(25);v.push_back(25);cout << "替换前\nv：";for_each(v.begin(), v.end(), mtprint);cout << endl << endl;replace(v.begin(), v.end(), 25, 26);cout << "替换后\nv：";for_each(v.begin(), v.end(), mtprint);cout << endl << endl;
}

总结： replace会替换区间内满足条件的元素

2.3 replace_if

功能描述: 将区间内满足条件的元素，替换成指定元素

函数原型： replace_if(iterator beg, iterator end, _pred, newvalue);

// beg 开始迭代器
// end 结束迭代器
// _pred 谓词
// newvalue 替换的新元素

代码示例：

void mtprint(int val)
{cout << val << "  ";
}class myrepalce
{
public:bool operator()(int val){return val >= 25;}
};void test1()
{vector v;for (int i = 0; i < 5; i++){v.push_back(i + 21);}v.push_back(25);v.push_back(25);v.push_back(25);v.push_back(25);cout << "替换前\nv：";for_each(v.begin(), v.end(), mtprint);cout << endl << endl;replace_if(v.begin(), v.end(), myrepalce(), 26);cout << "替换后\nv：";for_each(v.begin(), v.end(), mtprint);cout << endl << endl;
}

总结： replace_if按条件查找，可以利用仿函数灵活筛选满足的条件

2.4 swap

功能描述： 互换两个容器的元素，容器必须是同种类型

函数原型： swap(container c1, container c2);

// c1容器1
// c2容器2

代码示例：

void mtprint(int val)
{cout << val << "  ";
}void test1()
{vector v1;vector v2;for (int i = 0; i < 10; i++){v1.push_back(i + 1);v2.push_back(i + 21);}cout << "替换前\nv1：";for_each(v1.begin(), v1.end(), mtprint);cout << endl << endl;cout << "v2：";for_each(v2.begin(), v2.end(), mtprint);cout << endl << endl;cout << "替换后\nv1：";swap(v1, v2);for_each(v1.begin(), v1.end(), mtprint);cout << endl << endl;cout << "v2：";for_each(v2.begin(), v2.end(), mtprint);cout << endl << endl;
}

总结： swap交换容器时，注意交换的容器要同种类型

3 常用算术生成算法

学习目标： 掌握常用的算术生成算法

注意： 算术生成算法属于小型算法，使用时包含的头文件为 #include

算法简介：

• accumulate // 计算容器元素累计总和
• fill // 向容器中添加元素

3.1 accumulate

功能描述： 计算区间内 容器元素累计总和

函数原型： accumulate(iterator beg, iterator end, value);

// beg 开始迭代器
// end 结束迭代器
// value 起始值

代码示例：

void mtprint(int val)
{cout << val << "  ";
}void test1()
{vector v;for (int i = 0; i < 100; i++){v.push_back(i + 1);}//参数3 起始累加值int ret = accumulate(v.begin(), v.end(), 0);cout << "起始累加值为0\t\t1 + ... + 100 = " << ret << endl << endl;ret = accumulate(v.begin(), v.end(), 1000);cout << "起始累加值为1000\t1 + ... + 100 = " << ret << endl << endl;
}

总结： accumulate使用时头文件注意是 numeric，这个算法很实用

3.2 fill

功能描述： 向容器中填充指定的元素

函数原型： fill(iterator beg, iterator end, value);

// beg 开始迭代器
// end 结束迭代器
// value 填充的值

代码示例：

void mtprint(int val)
{cout << val << "  ";
}void test1()
{vector v;for (int i = 0; i < 10; i++){v.push_back(i + 1);}cout << "填充前 v：";for_each(v.begin(), v.end(), mtprint);cout << endl << endl;fill(v.begin(), v.end(), 30);cout << "填充后 v：";for_each(v.begin(), v.end(), mtprint);cout << endl;
}

总结： 利用fill可以将容器区间内元素填充为指定的值

4 常用集合算法

学习目标： 掌握常用的集合算法

算法简介：

• set_intersection // 求两个容器的交集

• set_union // 求两个容器的并集

• set_difference // 求两个容器的差集
  

4.1 set_intersection

功能描述： 求两个容器的交集，两个集合必须是有序序列

函数原型： set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

// beg1 容器1开始迭代器
// end1 容器1结束迭代器
// beg2 容器2开始迭代器
// end2 容器2结束迭代器
// dest 目标容器开始迭代器

代码示例：

void mtprint(int val)
{cout << val << "  ";
}void test()
{vector v1;vector v2;vector vtarget;for (int i = 0; i < 10; i++){v1.push_back(i + 1);v2.push_back(i + 6);}cout << "v1：";for_each(v1.begin(), v1.end(), mtprint);cout << endl << endl;cout << "v2：";for_each(v2.begin(), v2.end(), mtprint);cout << endl << endl;vtarget.resize(min(v1.size(), v2.size()));vector::iterator ret = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), vtarget.begin());//返回交集迭代器cout << "目标容器的结束迭代器 vtarget.end()" << endl;cout << "vtarget：";for_each(vtarget.begin(), vtarget.end(), mtprint);//相当于把所有数据都遍历一遍输出cout << endl << endl;cout << "交集迭代器\t     ret" << endl;cout << "vtarget：";for_each(vtarget.begin(), ret, mtprint);//只输出交集部分cout << endl << endl;
}

总结：

• 求交集的两个集合必须的有序序列
• 目标容器必须提前开辟内存空间，开辟空间需要从两个容器中取小值
• set_intersection返回值是交集中最后一个元素的位置

4.2 set_union

功能描述： 求两个集合的并集，两个集合必须是有序序列

函数原型： set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

// beg1 容器1开始迭代器
// end1 容器1结束迭代器
// beg2 容器2开始迭代器
// end2 容器2结束迭代器
// dest 目标容器开始迭代器​

代码示例：

void mtprint(int val)
{cout << val << "  ";
}void test()
{vector v1;vector v2;vector vtarget;for (int i = 0; i < 10; i++){v1.push_back(i + 1);v2.push_back(i + 6);}cout << "v1：";for_each(v1.begin(), v1.end(), mtprint);cout << endl << endl;cout << "v2：";for_each(v2.begin(), v2.end(), mtprint);cout << endl << endl;//提前开辟内存空间，开辟空间是两个容器的size相加vtarget.resize(v1.size() + v2.size());//返回并集中最后一个元素的位置vector::iterator ret = set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), vtarget.begin());cout << "目标容器的结束迭代器 vtarget.end()" << endl;cout << "vtarget：";for_each(vtarget.begin(), vtarget.end(), mtprint);//相当于把所有数据都遍历一遍输出cout << endl << endl;cout << "并集迭代器\t     ret" << endl;cout << "vtarget：";for_each(vtarget.begin(), ret, mtprint);//只输出并集部分cout << endl << endl;
}

总结：

• 求并集的两个集合必须的有序序列
• 目标容器必须提前开辟内存空间，开辟空间需要两个容器相加
• set_union返回值既是并集中最后一个元素的位置

4.3 set_difference

功能描述： 求两个集合的差集，两个集合必须是有序序列

函数原型： set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

// beg1 容器1开始迭代器
// end1 容器1结束迭代器
// beg2 容器2开始迭代器
// end2 容器2结束迭代器
// dest 目标容器开始迭代器​

代码：

void mtprint(int val)
{cout << val << "  ";
}void test()
{vector v1;vector v2;vector vtarget;for (int i = 0; i < 10; i++){v1.push_back(i + 1);v2.push_back(i + 6);}cout << "v1：";for_each(v1.begin(), v1.end(), mtprint);cout << endl << endl;cout << "v2：";for_each(v2.begin(), v2.end(), mtprint);cout << endl << endl;//目标容器需要提前开辟内存空间//最特殊的情况是两个容器没有交集，大与小的差集是小 小与大的差集是大//开辟空间是大容器的sizevtarget.resize(max(v1.size(), v2.size()));cout << "v1与v2的差集为： " << endl;cout << "vtarget：";vector::iterator ret = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), vtarget.begin());for_each(vtarget.begin(), ret, mtprint);//相当于把所有数据都遍历一遍输出cout << endl << endl;cout << "v2与v1的差集为： " << endl;cout << "vtarget：";ret = set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), vtarget.begin());for_each(vtarget.begin(), ret, mtprint);//只输出并集部分cout << endl << endl;
}

总结：

• 求差集的两个集合必须的有序序列
• 目标容器开辟空间需要从两个容器取较大值
• set_difference返回值既是差集中最后一个元素的位置