前面我们学习了C++的一些知识点，今天我们就来着重了解一下系统给我们提供的算法包，了解一下较常用的一些api.
引入算法包：#include <algorithm> // 算法包
1、find_if 及函数适配器
说明：
1） find_if 参数说明：第一个参数是开始的位置，第二个参数是结束的位置，第三个是仿函数（equal_to()）
2）函数适配器：bind1st (将第一个参数适配传递给equal_to()函数),
bind2nd(将第二个参数适配传递传递给equal_to函数)
示例代码：
int main(){
set<string, less<string>> setVar;
setVar.insert("AAAA");
setVar.insert("BBBB");
setVar.insert("CCCC");
set<string, less<string>>::iterator iteratorResult =
find_if(setVar.begin(),
setVar.end(),
bind1st(equal_to<string>(), "1111")
/*bind2nd(equal_to<string>(), "BBBB")*/);
if (iteratorResult != setVar.end()) {
cout << "查找到了" << endl;
} else {
cout << "没有查找到" << endl;
}
return 0;
}
2、for_each 遍历
先看看源码：
for_each(_InputIterator __first, _InputIterator __last, _Function __f)
{
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
__glibcxx_requires_valid_range(__first, __last);
for (; __first != __last; ++__first)
__f(*__first);
return __f; // N.B. [alg.foreach] says std::move(f) but it's redundant.
}
说明：
1）源码： for_each(_InputIterator first, _InputIterator last, _Function __f) 前面两个参数是遍历的起始、结束的位置，第三个是一个仿函数
2）推导仿函数：需要一个参数（__first），参数类型是容器迭代器指向的位置的值，也就是集合的元素数据类型，如源码的第7行；*
不需要返回值；
自定义一个仿函数：
class __F {
public:
void operator()(string __first) {
cout << "自定义for_each一元谓词:" << __first << endl;
}
};
示例代码：
int main(){
vector<string> vectorVar;
vectorVar.insert(vectorVar.begin(), "10000");
vectorVar.insert(vectorVar.begin(), "60000");
vectorVar.insert(vectorVar.begin(), "40000");
vectorVar.insert(vectorVar.begin(), "20000");
vectorVar.insert(vectorVar.begin(), "50000");
vectorVar.insert(vectorVar.begin(), "30000");
for_each(vectorVar.begin(), vectorVar.end(), __F());
cout << endl;
return 0;
}
/**
输出结果：
自定义for_each一元谓词:30000
自定义for_each一元谓词:50000
自定义for_each一元谓词:20000
自定义for_each一元谓词:40000
自定义for_each一元谓词:60000
自定义for_each一元谓词:10000
*/
3、transform 变化操作
源码分析：
_OutputIterator
transform(_InputIterator __first, _InputIterator __last,
_OutputIterator __result, _UnaryOperation __unary_op)
{
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
// "the type returned by a _UnaryOperation"
__typeof__(__unary_op(*__first))>)
__glibcxx_requires_valid_range(__first, __last);
for (; __first != __last; ++__first, (void)++__result)
*__result = __unary_op(*__first);
return __result;
}
说明：
1）类似于RxJava中的变化操作符
2）用于将集合的元素修改值；
3） 定义带有返回值的一元仿函数（参数类型和返回值类型需要根据容器元素的数据类型来确定）
4）将修改后的值赋值给当前迭代器的位置(也可以自定义个容器用于接收返回的值)
5) 参数说明：第一个：起始位置；第二个：结束位置；第三个：接受结果的集合；第四个：仿函数（一个参数，一个返回值，参数和返回值的数据类型都是和原始集合的数据类型一致）
自定义仿函数：
class __unary_op {
public:
int operator()(int __first) {
__first += 100;
cout << "自定义transform的仿函数:" << __first << endl;
return __first;
}
};
示例代码：
int main(){
vector<int> vectorVar2;
vectorVar2.insert(vectorVar2.begin(), 10000);
vectorVar2.insert(vectorVar2.begin(), 20000);
vectorVar2.insert(vectorVar2.begin(), 30000);
vectorVar2.insert(vectorVar2.begin(), 40000);
cout << "---在当前容器中进行修改--------" << endl;
transform(vectorVar2.begin(), vectorVar2.end(), vectorVar2.begin(), __unary_op());
cout << "---将修改的结果另外存储--------" << endl;
vector<int> vectorReslut(vectorVar2.size());
transform(vectorVar2.begin(), vectorVar2.end(), vectorReslut.begin(), __unary_op());
cout << endl;
return 0;
}
/**
输出结果：
---在当前容器中进行修改--------
自定义transform的仿函数:40100
自定义transform的仿函数:30100
自定义transform的仿函数:20100
自定义transform的仿函数:10100
---将修改的结果另外存储--------
自定义transform的仿函数:40200
自定义transform的仿函数:30200
自定义transform的仿函数:20200
自定义transform的仿函数:10200
*/
4、find 与自定义find_if 仿函数
源码分析：
template<typename _InputIterator, typename _Tp>
inline _InputIterator
find(_InputIterator __first, _InputIterator __last,
const _Tp& __val)
{
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
__glibcxx_function_requires(_EqualOpConcept<
typename iterator_traits<_InputIterator>::value_type, _Tp>)
__glibcxx_requires_valid_range(__first, __last);
return std::__find_if(__first, __last,
__gnu_cxx::__ops::__iter_equals_val(__val)); // 此处可以看到是调用了find_id 来完成的
}
说明：
1）原理：是对find_if的封装,通过迭代器指针移动来完成查询工作，在find_if的第三个参数中直接默认传入__iter_equals_val 这个仿函数，
2）find_if 是通过对容器迭代器的位置++进行遍历查询
3）参数说明：前面两个参数是容器的起始结束位置的迭代器指针，最后一个参数是一个泛型常量引用
4）find 没有自定义仿函数;find_if有自定义仿函数
示例代码：
//自定义一个find_if的仿函数
class __pred {
public:
int number;
__pred(int number) : number(number) {}
bool operator()(const int value) {
return number = value;
}
};
int main(){
vector<int> vectorVar3;
vectorVar3.insert(vectorVar3.begin(), 10000);
vectorVar3.insert(vectorVar3.begin(), 20000);
vectorVar3.insert(vectorVar3.begin(), 30000);
vectorVar3.insert(vectorVar3.begin(), 40000);
auto findResult = find(vectorVar3.begin(), vectorVar3.end(), 10000);
auto findIfReslut = find_if(vectorVar3.begin(), vectorVar3.end(), __pred(10000));
if (findResult != vectorVar3.end()) {
cout << "findResult找到了" << endl;
} else {
cout << "findResult未找到" << endl;
}
if (findIfReslut != vectorVar3.end()) {
cout << "findIfReslut找到了" << endl;
} else {
cout << "findIfReslut未找到" << endl;
}
return 0;
}
/**
输出结果：
findResult找到了
findIfReslut找到了
*/
5、count与count_if 统计某一个元素在容器中出现的次数
源码分析：
//count源码
inline typename iterator_traits<_InputIterator>::difference_type
count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
{
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
__glibcxx_function_requires(_EqualOpConcept<
typename iterator_traits<_InputIterator>::value_type, _Tp>)
__glibcxx_requires_valid_range(__first, __last);
return std::__count_if(__first, __last,
__gnu_cxx::__ops::__iter_equals_val(__value));
}
//count_if 源码
inline typename iterator_traits<_InputIterator>::difference_type
count_if(_InputIterator __first,
_InputIterator __last,
_Predicate __pred//需要一个仿函数
)
{
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
__glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
typename iterator_traits<_InputIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
return std::__count_if(__first, __last,
__gnu_cxx::__ops::__pred_iter(__pred));
}
typename iterator_traits<_InputIterator>::difference_type
__count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
{
typename iterator_traits<_InputIterator>::difference_type __n = 0;
for (; __first != __last; ++__first)
if (__pred(__first))//仿函数推导的依据：（）运算符重载，返回一个bool值，需要一个容器元素类型的值作为参数，并且保存下来
++__n;
return __n;
}
说明：
1）count 是对count_if的一个封装，默认提供了一个相等的仿函数
2）参数说明与仿函数的推导在上述源码中已经添加；
3）count 不需要仿函数和函数适配器，而count_if 需要仿函数或者函数适配器
自定义count_if 仿函数
class __pred2 {
public:
int number;
__pred2(int number) : number(number) {}
bool operator()(const int value) {
return value < number;
}
};
示例代码：
int main(){
vector<int> vectorVar1;
vectorVar1.push_back(1);
vectorVar1.push_back(2);
vectorVar1.push_back(3);
vectorVar1.push_back(2);
vectorVar1.push_back(4);
vectorVar1.push_back(6);
vectorVar1.push_back(8);
vectorVar1.push_back(1);
int num = count(vectorVar1.begin(), vectorVar1.end(), 2);
cout << "统计元素是2的个数：" << num << endl;
//使用函数适配器
num = count_if(vectorVar1.begin(), vectorVar1.end(), bind2nd(less<int>(), 3));
cout << "函数适配器模式---统计小于元素3的个数：" << num << endl;
num = count_if(vectorVar1.begin(), vectorVar1.end(), __pred2(3));
cout << "自定义仿函数模式---统计小于元素3的个数：" << num << endl;
cout << endl;
return 0;
}
/**
输出结果：
统计元素是2的个数：2
函数适配器模式---统计小于元素3的个数：4
自定义仿函数模式---统计小于元素3的个数：4
*/
6、merge 合并
源码分析：
inline _OutputIterator
merge(_InputIterator1 __first1, //第一个容器的起始位置
_InputIterator1 __last1,//第一个容器的结束位置
_InputIterator2 __first2, //第二个容器的起始位置
_InputIterator2 __last2,//第二个容器的结束位置
_OutputIterator __result//存放合并结果的容器的起始位置
)
{
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
typename iterator_traits<_InputIterator1>::value_type>)
__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
typename iterator_traits<_InputIterator2>::value_type>)
__glibcxx_function_requires(_LessThanOpConcept<
typename iterator_traits<_InputIterator2>::value_type,
typename iterator_traits<_InputIterator1>::value_type>)
__glibcxx_requires_sorted_set(__first1, __last1, __first2);
__glibcxx_requires_sorted_set(__first2, __last2, __first1);
__glibcxx_requires_irreflexive2(__first1, __last1);
__glibcxx_requires_irreflexive2(__first2, __last2);
return _GLIBCXX_STD_A::__merge(__first1, __last1,
__first2, __last2, __result,
__gnu_cxx::__ops::__iter_less_iter()//默认传递了一个比较的仿函数
);
}
//真正的merge实现
template<typename _InputIterator1, typename _InputIterator2,
typename _OutputIterator, typename _Compare>
_OutputIterator
__merge(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2,
_OutputIterator __result, _Compare __comp)
{
while (__first1 != __last1 && __first2 != __last2)
{
if (__comp(__first2, __first1))
{
//先将第一个容器的元素合并到结果容器中
*__result = *__first2;
++__first2;
}
else
{
//再合并第二个容器的元素到结果容器中
*__result = *__first1;
++__first1;
}
++__result;
}
return std::copy(__first2, __last2,
std::copy(__first1, __last1, __result));
}
说明：
1）原理：按照容器的开始与结束位置，循环遍历两个容器的元素，并进行从小到大的排序后，进行拷贝;
2) 参数说明如源码中的注释；
示例代码：
int main(){
vector<int> vectorVar5;
vectorVar5.push_back(10);
vectorVar5.push_back(20);
vectorVar5.push_back(30);
vectorVar5.push_back(40);
vector<int> vectorVar4;
vectorVar4.push_back(50);
vectorVar4.push_back(60);
vectorVar4.push_back(70);
vectorVar4.push_back(80);
vector<int> vectorResult;
vectorResult.resize(vectorVar5.size() - 2 + vectorVar4.size());
merge(++vectorVar4.begin(), --vectorVar4.end(), vectorVar5.begin(), vectorVar5.end(), vectorResult.begin());
for (auto iterator = vectorResult.begin(); iterator != vectorResult.end(); iterator++) {
cout << "合并后的容器元素是：" << *iterator << endl;
}
cout << endl;
return 0;
}
/**
输出结果：
合并后的容器元素是：10
合并后的容器元素是：20
合并后的容器元素是：30
合并后的容器元素是：40
合并后的容器元素是：60
合并后的容器元素是：70
*/
7、sort 排序
源码分析：
inline void
sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
__glibcxx_function_requires(_LessThanComparableConcept<
typename iterator_traits<_RandomAccessIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
__glibcxx_requires_irreflexive(__first, __last);
std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());//真正的排序
}
inline void
sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
{
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
typename iterator_traits<_RandomAccessIterator>::value_type,
typename iterator_traits<_RandomAccessIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
__glibcxx_requires_irreflexive_pred(__first, __last, __comp);
std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));//真正的排序
}
//上面是重载了sort方法，支持可以自定义仿函数或者使用默认的仿函数
inline void
__sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
{
if (__first != __last)
{
std::__introsort_loop(__first, __last,
std::__lg(__last - __first) * 2,
__comp);
std::__final_insertion_sort(__first, __last, __comp);//
}
}
//
void
__final_insertion_sort(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp)
{
if (__last - __first > int(_S_threshold))
{
std::__insertion_sort(__first, __first + int(_S_threshold), __comp);//
std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
__comp);
}
else
std::__insertion_sort(__first, __last, __comp);
}
void
__insertion_sort(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp)
{
if (__first == __last) return;
for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
{
if (__comp(__i, __first))
{
//冒泡排序
typename iterator_traits<_RandomAccessIterator>::value_type
__val = _GLIBCXX_MOVE(*__i);
_GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
*__first = _GLIBCXX_MOVE(__val);
}
else
std::__unguarded_linear_insert(__i,
__gnu_cxx::__ops::__val_comp_iter(__comp));//
}
}
void
__unguarded_linear_insert(_RandomAccessIterator __last,
_Compare __comp)
{
typename iterator_traits<_RandomAccessIterator>::value_type
__val = _GLIBCXX_MOVE(*__last);
_RandomAccessIterator __next = __last;
--__next;
while (__comp(__val, __next))
{
//冒泡排序
*__last = _GLIBCXX_MOVE(*__next);
__last = __next;
--__next;
}
*__last = _GLIBCXX_MOVE(__val);
}
说明：
1）排序可以不需要传入第三个参数，系统默认提供了一个比较从小到大的仿函数；
2）第三个参数也可以传入自定义或内置的模板函数;
3) 内部是冒泡排序算法；
示例代码：
int main(){
vector<int> vectorVar6;
vectorVar6.push_back(10);
vectorVar6.push_back(30);
vectorVar6.push_back(20);
sort(vectorVar6.begin(), vectorVar6.end());
for (auto itVar = vectorVar6.begin(); itVar != vectorVar6.end(); itVar++) {
cout << "容器排序后的结果：" << *itVar << endl;
}
cout << endl;
return 0;
}
8、random_shuffle随机打乱元素的顺序
源码分析：
inline void
random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
__glibcxx_requires_valid_range(__first, __last);
if (__first != __last)
for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
{
// XXX rand() % N is not uniformly distributed 取随机位置
_RandomAccessIterator __j = __first
+ std::rand() % ((__i - __first) + 1);
if (__i != __j)
//交换两个位置
std::iter_swap(__i, __j);
}
}
说明：
原理：通过随机数与（当前位置与起始位置相减+1） 进行 %操作后，找到要切换顺序的位置，然后再将这两个位置的值进行交换
示例代码：
int main(){
vector<int> vectorVar7; // vector默认是没有排序功能的，默认输出： 65 53 84
vectorVar7.push_back(1);
vectorVar7.push_back(2);
vectorVar7.push_back(3);
vectorVar7.push_back(4);
vectorVar7.push_back(5);
vectorVar7.push_back(6);
vectorVar7.push_back(7);
random_shuffle(vectorVar7.begin(), vectorVar7.end());
for (auto iterator = vectorVar7.begin(); iterator != vectorVar7.end(); iterator++) {
cout << "随机打乱顺序后的结果是：" << *iterator << endl;
}
return 0;
}
/**
输出结果：
随机打乱顺序后的结果是：5
随机打乱顺序后的结果是：2
随机打乱顺序后的结果是：7
随机打乱顺序后的结果是：3
随机打乱顺序后的结果是：1
随机打乱顺序后的结果是：6
随机打乱顺序后的结果是：4
*/
9、copy 将1个容器里面的元素复制到另外一个容器里面
源码分析：
inline _OI
copy(_II __first, _II __last, _OI __result)
{
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_II>)
__glibcxx_function_requires(_OutputIteratorConcept<_OI,
typename iterator_traits<_II>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
return (std::__copy_move_a2<__is_move_iterator<_II>::__value>
(std::__miter_base(__first), std::__miter_base(__last),
__result));
}
示例代码：
int main(){
vector<int> vectorVar8;
vectorVar8.push_back(1);
vectorVar8.push_back(2);
vectorVar8.push_back(3);
vector<int> vectorResult8(vectorVar8.size());
copy(vectorVar8.begin(),vectorVar8.end(),vectorResult8.begin());
for (auto it=vectorResult8.begin();it!= vectorResult8.end();it++) {
cout<<"执行copy函数后的 结果容器 元素："<<*it<<endl;
}
cout<<"##################"<<endl;
for (auto it=vectorResult8.begin();it!= vectorResult8.end();it++) {
cout<<"执行copy函数后的 原 容器元素："<<*it<<endl;
}
cout<<endl;
return 0;
}
/**
输出结果：
执行copy函数后的 结果容器 元素：1
执行copy函数后的 结果容器 元素：2
执行copy函数后的 结果容器 元素：3
##################
执行copy函数后的 原 容器元素：1
执行copy函数后的 原 容器元素：2
执行copy函数后的 原 容器元素：3
*/
10、replace 替换元素（指定容器中的指定位置范围内将值为XXX的元素替换值为YYY）
源码分析：
void
replace(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __old_value, const _Tp& __new_value)
{
// concept requirements
__glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
_ForwardIterator>)
__glibcxx_function_requires(_EqualOpConcept<
typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
__glibcxx_function_requires(_ConvertibleConcept<_Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
for (; __first != __last; ++__first)
if (*__first == __old_value)
*__first = __new_value;
}
示例代码：
int main(){
vector<int> vectorVar9;
vectorVar9.push_back(11);
vectorVar9.push_back(23);
vectorVar9.push_back(30);
vectorVar9.push_back(44);
vectorVar9.push_back(55);
replace(vectorVar9.begin()+3,vectorVar9.end(),55,58);
for (auto it=vectorVar9.begin();it!= vectorVar9.end();it++) {
cout<<"执行replace函数后的容器元素："<<*it<<endl;
}
cout<<endl;
return 0;
}
/**
输出结果：
执行replace函数后的容器元素：11
执行replace函数后的容器元素：23
执行replace函数后的容器元素：30
执行replace函数后的容器元素：44
执行replace函数后的容器元素：58
*/
更多算法就各位看官自行研究了。
网友评论