概述:
<algorithm> <functional> <numeric> 组成。<algorithm> 是所有STL头文件中最大的一个,范围涉及到比较、交换、查找、遍历操作、复制、修改等等。<numeric> 体积很小,只包括几个在序列上面进行简单数学运算的模板函数。<functional> 定义了一些模板类,用以声明函数对象。学习目标:
算法简介:
for_each 遍历容器
* transform 搬运容器到另一个容器中功能描述:
函数原型:
for_each(iterator beg, iterator end, _func); // 遍历算法 遍历容器元素 // beg 开始迭代器 // end 结束迭代器 // _func 函数或者函数对象
功能描述:
函数原型:
transform(iterator beg1, iterator end1, iterator beg2, _func); // beg1 源容器开始迭代器 // end1 源容器结束迭代器 // beg2 目标容器开始迭代器 // _func 函数或者函数对象
学习目标:
算法简介:
find 查找元素
* findif 按条件查找元素
* adjacentfind 查找相邻重复元素
* binarysearch 二分查找法
* count 统计元素个数
* countif 按条件统计元素个数
==== find ====
功能描述:
* 查找指定元素,找到返回指定元素的迭代器,找不到返回结束迭代器end()
函数原型:
<code cpp>
find(iterator beg, iterator end, value);
按值查找元素,找到返回指定位置迭代器,找不到返回结束迭代器位置
beg 开始迭代器
end 结束迭代器
value 查找的元素
</code>
==== find_if ====
功能描述:
* 按条件查找元素
函数原型:
<code cpp>
find_if(iterator beg, iterator end, _Pred);
按值查找元素,找到返回指定位置迭代器,找不到返回结束迭代器位置
beg 开始迭代器
end 结束迭代器
_Pred 函数或者谓词(返回bool类型的仿函数)
</code>
==== adjacent_find ====
功能描述:
* 查找相邻重复元素
函数原型:
<code cpp>
adjacent_find(iterator beg, iterator end);
查找相邻重复元素,返回相邻元素的第一个位置的迭代器
beg 开始迭代器
end 结束迭代器
</code>
总结: 面试题中如果出现查找相邻重复元素,记得用STL中的adjacent_find算法
==== binary_search ====
功能描述:
* 查找指定元素是否存在
函数原型:
<code cpp>
bool binary_search(iterator beg, iterator end, value);
查找指定的元素,查到 返回true 否则false
注意: 在无序序列中不可用
beg 开始迭代器
end 结束迭代器
value 查找的元素
</code>
==== count ====
功能描述:
* 统计元素个数
函数原型:
<code cpp>
count(iterator beg, iterator end, value);
统计元素出现次数
beg 开始迭代器
end 结束迭代器
value 统计的元素
</code>
==== count_if ====
功能描述:
* 按条件统计元素个数
函数原型:
<code cpp>
count_if(iterator beg, iterator end, _Pred);
按条件统计元素出现次数
beg 开始迭代器
end 结束迭代器
_Pred 谓词
</code>
===== 常用排序算法 =====
学习目标:
* 掌握常用的排序算法
算法简介:
* sort 对容器内元素进行排序
* random_shuffle 洗牌 指定范围内的元素随机调整次序
* merge 容器元素合并,并存储到另一容器中
* reverse 反转指定范围的元素
==== sort ====
功能描述:
* 对容器内元素进行排序
函数原型:
<code cpp>
sort(iterator beg, iterator end, _Pred);
按值查找元素,找到返回指定位置迭代器,找不到返回结束迭代器位置
beg 开始迭代器
end 结束迭代器
_Pred 谓词
</code>
总结: sort属于开发中最常用的算法之一,需熟练掌握
==== random_shuffle ====
功能描述:
* 洗牌 指定范围内的元素随机调整次序
函数原型:
<code cpp>
random_shuffle(iterator beg, iterator end);
指定范围内的元素随机调整次序
beg 开始迭代器
end 结束迭代器
</code>
==== merge ====
功能描述:
* 两个容器元素合并,并存储到另一容器中
函数原型:
<code cpp>
merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
容器元素合并,并存储到另一容器中
注意: 两个容器必须是有序的
beg1 容器1开始迭代器 end1 容器1结束迭代器 beg2 容器2开始迭代器 end2 容器2结束迭代器 dest 目标容器开始迭代器
</code>
==== reverse ====
功能描述:
* 将容器内元素进行反转
函数原型:
<code cpp>
reverse(iterator beg, iterator end);
反转指定范围的元素
beg 开始迭代器
end 结束迭代器
</code>
===== 常用拷贝和替换算法 =====
学习目标:
* 掌握常用的拷贝和替换算法
算法简介:
* copy 容器内指定范围的元素拷贝到另一容器中
* replace 将容器内指定范围的旧元素修改为新元素
* replace_if 容器内指定范围满足条件的元素替换为新元素
* swap 互换两个容器的元素
==== copy ====
功能描述:
* 容器内指定范围的元素拷贝到另一容器中
函数原型:
<code cpp>
copy(iterator beg, iterator end, iterator dest);
按值查找元素,找到返回指定位置迭代器,找不到返回结束迭代器位置
beg 开始迭代器
end 结束迭代器
dest 目标起始迭代器
</code>
==== replace ====
功能描述:
* 将容器内指定范围的旧元素修改为新元素
函数原型:
<code cpp>
replace(iterator beg, iterator end, oldvalue, newvalue);
将区间内旧元素 替换成 新元素
beg 开始迭代器
end 结束迭代器
oldvalue 旧元素
newvalue 新元素
</code>
==== replace_if ====
功能描述:
* 将区间内满足条件的元素,替换成指定元素
函数原型:
<code cpp>
replace_if(iterator beg, iterator end, _pred, newvalue);
按条件替换元素,满足条件的替换成指定元素
beg 开始迭代器
end 结束迭代器
_pred 谓词
newvalue 替换的新元素
</code>
==== swap ====
功能描述:
* 互换两个容器的元素
函数原型:
<code cpp>
swap(container c1, container c2);
互换两个容器的元素
c1容器1
c2容器2
</code>
===== 常用算术生成算法 =====
学习目标:
* 掌握常用的算术生成算法
注意:
* 算术生成算法属于小型算法,使用时包含的头文件为 #include <numeric>
算法简介:
* accumulate 计算容器元素累计总和
* fill 向容器中添加元素
==== accumulate ====
功能描述:
* 计算区间内 容器元素累计总和
函数原型:
<code cpp>
accumulate(iterator beg, iterator end, value);
计算容器元素累计总和
beg 开始迭代器
end 结束迭代器
value 起始值
</code>
==== fill ====
功能描述:
* 向容器中填充指定的元素
函数原型:
<code cpp>
fill(iterator beg, iterator end, value);
向容器中填充元素
beg 开始迭代器
end 结束迭代器
value 填充的值
</code>
===== 常用集合算法 =====
学习目标:
* 掌握常用的集合算法
算法简介:
* setintersection 求两个容器的交集
* setunion 求两个容器的并集
* setdifference 求两个容器的差集
==== set_intersection ====
功能描述:
* 求两个容器的交集
函数原型:
<code cpp>
set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
求两个集合的交集
注意:两个集合必须是有序序列
beg1 容器1开始迭代器 end1 容器1结束迭代器 beg2 容器2开始迭代器 end2 容器2结束迭代器 dest 目标容器开始迭代器
</code>
总结:
* 求交集的两个集合必须的有序序列
* 目标容器开辟空间需要从两个容器中取小值
* set_intersection返回值既是交集中最后一个元素的位置
==== set_union ====
功能描述:
* 求两个集合的并集
函数原型:
<code cpp>
set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
求两个集合的并集
注意:两个集合必须是有序序列
beg1 容器1开始迭代器 end1 容器1结束迭代器 beg2 容器2开始迭代器 end2 容器2结束迭代器 dest 目标容器开始迭代器
</code>
总结:
* 求并集的两个集合必须的有序序列
* 目标容器开辟空间需要两个容器相加
* set_union返回值既是并集中最后一个元素的位置
==== set_difference ====
功能描述:
* 求两个集合的差集
函数原型:
<code cpp>
set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
求两个集合的差集
注意:两个集合必须是有序序列
beg1 容器1开始迭代器 end1 容器1结束迭代器 beg2 容器2开始迭代器 end2 容器2结束迭代器 dest 目标容器开始迭代器
</code>
总结:
* 求差集的两个集合必须的有序序列
* 目标容器开辟空间需要从两个容器取较大值
* set_difference返回值既是差集中最后一个元素的位置