STL算法部分主要由头文件<algorithm>,<numeric>,<functional>组成.要使用 STL中的算法函数必须包含头文件<algorithm>,对于数值算法须包含<numeric>,<functional>中则定义了一些模板类,用来声明函数对象.
STL中算法大致分为四类:
1、非可变序列算法:指不直接修改其所操作的容器内容的算法.
2、可变序列算法:指可以修改它们所操作的容器内容的算法.
3、排序算法:包括对序列进行排序和合并的算法、搜索算法以及有序序列上的集合操作.
4、数值算法:对容器内容进行数值计算.
<一>查找算法(13个)：判断容器中是否包含某个值
adjacent_find :在 iterator 对标志的元素范围内,查找一对相邻的重复元素,如果找到返回一个 ForwardIterator,指向这对元素的第一个元素.否则返回 last .重载版本使用输入的二元操作符代替相等的判断.
参数:first
:last
返回:forwardItr
template<class forwardItr>
forwardItr adjacent_find(forwardItr first, forwardItr last);
参数:first
:last
:op
返回:forwardItr
template<class forwardItr, class binaryPredicate>
forwardItr adjacent_find(forwardItr first, forwardItr last, binaryPredicate op);
#include "stdafx.h"
#include <string>
#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional> //x,y为依次相邻的两个元素
bool isequal(int x, int y)
{
return x / == y;
} int main()
{ {
std::vector<int> vec = { , , , , , };
auto pos1 = adjacent_find(vec.begin(), vec.end());
std::cout << *pos1 << std::endl; //输出:33 auto pos2 = adjacent_find(vec.begin(), vec.end(), isequal);
std::cout << *pos2 << std::endl; //输出:22 getchar();
return ;
}
}
search :在一个序列中搜索与另一序列匹配的子序列,找到则返回第一次出现子序列的位置,否则返回last1.重载版本使用自定义的比较操作.
//search是在一个集合中搜索另一个子集，find只搜索单个元素
参数:first1
:last1
:first2
:last2
返回：forwardItr1
template <class forwardItr1, class forwardItr2>
forwardItr1 search(forwardItr1 first1, forwardItr1 last1,forwardItr2 first2,forwardItr2 last2);
参数:first1
:last1
:first2
:last2
:op
返回：forwardItr1
template <class forwardItr1, class forwardItr2,class binaryPredicate>
forwardItr1 search(forwardItr1 first1, forwardItr1 last1,forwardItr2 first2,forwardItr2 last2,binaryPredicate op);
search_n :在指定范围内查找 value 出现 n 次的子序列.找到则返回第一次出现的位置，找不到则返回last,重载版本使用自定义的比较操作.
参数:first
:last
:count
:value
返回：forwardItr
template <class forwardItr, class size,class Type>
forwardItr search_n(forwardItr first, forwardItr last,size count,const Type& value);
参数:first
:last
:count
:value
:op
返回：forwardItr
template <class forwardItr, class size,class Type,class binaryPredicate>
forwardItr search_n(forwardItr first, forwardItr last,size count,const Type& value,binaryPredicate op);
binary_search :在有序序列中查找 value ,如果找到返回 true .重载的版本使用指定的比较函数对象或者函数指针来判断相等.
参数:first
:last
:searchValue
返回：bool
template<class forwardItr,class Type>
bool binary_search(forwardItr first,forwardItr last,const Type& searchValue);
参数:first
:last
:searchValue
:op
返回：bool
template<class forwardItr,class Type,class compare>
bool binary_search(forwardItr first, forwardItr last, const Type& searchValue,compare op);
#include "stdafx.h"
#include <string>
#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional> bool equal(std::string str1, std::string str2)
{
//将字符串转换为大写
transform(str1.begin(), str1.end(), str1.begin(), ::toupper);
transform(str2.begin(), str2.end(), str2.begin(), ::toupper); return str1 == str2 ? true : false;
} bool checkequal(int num1, int num2)
{
bool is = (num1 == num2) ? true : false;
return is;
} int main()
{
{
std::vector<std::string> vec1 = { "", "", "", "Abc", "abc" };
std::vector<std::string> vec2 = { "", "Abc" };
auto result1 = search(vec1.begin(), vec1.end(), vec2.begin(), vec2.end());
if (result1 != vec1.end())
{
std::cout << *result1 << std::endl; //输出:789
} else {
std::cout << "no found" << std::endl;
} //调用自定义的equal函数将字符串转换为大写在比较
auto result2 = search(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), equal);
if (result2 != vec1.end())
{
std::cout << *result2 << std::endl; //输出:789
} else {
std::cout << "no found" << std::endl;
} auto result3 = search_n(vec1.begin(), vec1.end(), , "");
if (result3 != vec1.end())
{
std::cout << *result3 << std::endl; //输出:789
} else {
std::cout << "no found" << std::endl;
} auto result4 = search_n(vec1.begin(), vec1.end(), , "abc", equal);
if (result4 != vec1.end())
{
std::cout << *result4 << std::endl; //输出:Abc
} else {
std::cout << "no found" << std::endl;
} auto result5 = binary_search(vec1.begin(), vec1.end(), "");
if (result5)
{
std::cout << "found" << std::endl;
} else {
std::cout << "no found" << std::endl;
} std::vector<int> vec3 = { , , , , };
//这个binary_search找不到也会返回true,是bug还是什么？
auto result6 = binary_search(vec3.begin(), vec3.end(), , checkequal);
if (result6)
{
std::cout << "found" << std::endl;
} else {
std::cout << "no found" << std::endl;
} getchar();
return ;
}
}
find :find算法用于查找等于某值的元素.它在迭代器区间[first , last)上查找等于value值的元素,如果迭代器iter所指的元素满足 *iter == value ,则返回迭代器iter,未找则返回last
参数:first
:last
:searchValue
返回:inputItr 如果迭代器iter所指的元素满足 *iter == value ,则返回迭代器iter,未找则返回last
template <class inputItr,class size,class Type>
inputItr find(inputItr first, inputItr last, const Type& searchValue);
find_if :利用返回布尔值的谓词判断pred,检查迭代器区间[first, last)上的每一个元素,如果迭代器iter满足pred(*iter) == true,表示找到元素并返回迭代器值iter；未找到元素,则返回last
参数:first
:last
:op
返回:inputItr 迭代器iter满足pred(*iter) == true,表示找到元素并返回迭代器值iter；未找到元素,则返回last
template <class inputItr, class unaryPredicate>
inputItr find_if(inputItr first, inputItr last, UnaryPredicate op);
find_end :在一个序列中搜索出最后一个与另一序列匹配的子序列.有如下两个函数原型,在迭代器区间[first1, last1)中搜索出与迭代器区间[first2, last2)元素匹配的子序列,返回首元素的迭代器或last1
//[first2,last2)被看做一个原子,在first1中必须满足元素数量和first2相同并且连续出现才表示找到，而search被搜索的元素在first1中可以不连续
参数:first1
:last1
:first2
:last2
返回:forwardItr1 在迭代器区间[first1, last1)中搜索出与迭代器区间[first2, last2)元素匹配的子序列,找到则返回首元素的迭代器未找到则返回last1
template <class forwardItr1,class forwardItr2>
forwardItr1 find_end(forwardItr1 first1, forwardItr1 last1,forwardItr2 first2,forwardItr2 last2);
参数:first1
:last1
:first2
:last2
:op
返回:forwardItr1 在迭代器区间[first1, last1)中搜索出与迭代器区间[first2, last2)元素匹配的子序列,返回首元素的迭代器或last1
template <class forwardItr1,class forwardItr2,class binaryPredicate>
forwardItr1 find_end(forwardItr1 first1, forwardItr1 last1,forwardItr2 first2,forwardItr2 last2,binaryPredicate op);
find_first_of :用于查找位于某个范围之内的元素.它有两个使用原型,均在迭代器区间[first1, last1)上查找元素*i,使得迭代器区间[first2, last2)有某个元素*j,满足*i ==*j或满足二元谓词函数comp(*i, *j)==true的条件.元素找到则返回迭代器i,否则返回last1
//这里和find_end不一样，[first2,last2)被看作可以拆开的集合，和search有点像
参数:first1
:last1
:first2
:last2
返回:forwardItr1 元素找到则返回迭代器i,否则返回last1
template <class forwardItr1,class forwardItr2>
forwardItr1 find_first_of(forwardItr1 first1, forwardItr1 last1,forwardItr2 first2,forwardItr2 last2);
参数:first1
:last1
:first2
:last2
:op
返回:forwardItr1 元素找到则返回迭代器i,否则返回last1
template <class forwardItr1,class forwardItr2,class binaryPredicate>
forwardItr1 find_first_of(forwardItr1 first1, forwardItr1 last1,forwardItr2 first2,forwardItr2 last2,binaryPredicate op);
#include <string>
#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional> int main()
{
{
std::vector<int> vec1 = { , , , , , };
std::vector<int> vec2 = { , };
std::vector<int> vec3 = { , }; auto result1 = find(vec1.begin(), vec1.end(), );
std::cout << *result1 << " " << result1 - vec1.begin() << std::endl; auto resutl2 = find_if(vec1.begin(), vec1.end(), find_func);
std::cout << *resutl2 << " " << resutl2 - vec1.begin() << std::endl; auto result3 = find_end(vec1.begin(), vec1.end(), vec2.begin(), vec2.end());
if (result3 != vec1.end())
{
std::cout << *result3 << " " << result3 - vec1.begin() << std::endl;
} auto result4 = find_first_of(vec1.begin(), vec1.end(), vec3.begin(), vec3.end());
if (result4 != vec1.end())
{
std::cout << *result4 << " " << result4 - vec1.begin() << std::endl;
} getchar();
return ;
}
}
count :利用等于操作符,把[first,last)范围内的元素与value进行比较,并返回相等元素的个数.
参数:first
:last
:value
返回:满足条件元素的个数
template <class inputItr,class Type>
iterator_traits<inputItr>::difference_type count(inputItr first,inputItr last,const Type& value);
count_if :统计容器指定范围[first,last)内满足op条件元素的个数.
参数:first
:last
:op
返回:满足条件元素的个数
template<class InputIterator, class Predicate>
typename iterator_traits<InputIterator>::difference_type count_if( InputIterator _First, InputIterator _Last, Predicate _Pred );
#include "stdafx.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <iterator>
#include <ostream> bool greater10(int num)
{
return num % ? true : false;
} int main()
{
{
std::vector<int> arr = { , , , , , , , ,, }; auto num1 = count(arr.begin(), arr.end(), );
std::cout << num1 << std::endl; //
std::cout << "arr.begin() + 8:" << *(arr.begin() + ) << std::endl; // auto num2 = count_if(arr.begin(), arr.end(), greater10);
std::cout << num2 << std::endl; // getchar();
return ;
}
}
equal_range :equal_range是C++ STL中的一种二分查找的算法,试图在已排序的[first,last)中寻找value,它返回一对迭代器i和j,其中i是在不破坏次序的前提下,value可插入的第一个位置(亦即lower_bound),j则是在不破坏次序的前提下,value可插入的最后一个位置(亦即upper_bound),因此,[i,j)内的每个元素都等同于value,而且[i,j)是[first,last)之中符合此一性质的最大子区间
参数:first
:last
:val
返回:返回一个pair的键值对,内容为：first:value可插入的第一个位置(亦即lower_bound)second:value可插入的最后一个位置(亦即upper_bound)
template<class ForwardIterator, class Type>
pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first,ForwardIterator last, const Type& val);
参数:first
:last
:val
:comp
返回:返回一个pair的键值对,内容为：first:value可插入的第一个位置(亦即lower_bound)second:value可插入的最后一个位置(亦即upper_bound)
template<class ForwardIterator, class Type, class Predicate>
pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first,ForwardIterator last, const Type& val, Predicate comp);
#include "stdafx.h"
#include <string>
#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional> //x为value,y为元素
bool isGreater(int x, int y)
{
return x < y ? true : false;
} int main()
{
{
std::vector<int> vec = {, , , , };
//返回的值要添加判断，否则使用指向last的指针会引起程序中断
//使用pair1.first - first.begin()即可获得指向元素的索引
auto pair1 = equal_range(vec.begin(), vec.end(), );
std::cout << *pair1.first << " " << pair1.first - vec.begin() << std::endl; //输出:21 1
std::cout << *pair1.second << " " << pair1.second - vec.begin() << std::endl; //输出:22 2 auto pair2 = equal_range(vec.begin(), vec.end(), , isGreater);
if (pair2.first == vec.end() || pair2.second == vec.end())
{
return ;
} std::cout << *pair2.first << std::endl; //输出:21
std::cout << *pair2.second << std::endl; //输出:22 getchar();
return ;
}
}
一个序列中可能会有很多重复或相同的元素,使用下面两个函数可以查找满足条件的第一个或最后一个的位置,STL中的lower_bound,upper_bound算法使用了二分查找的方法
lower_bound :返回一个非递减序列[first, last)中的第一个大于等于值val的位置.如果所有元素都小于val,则返回last的位置.重载函数使用了自定义的比较操作.
参数:first
:last
:val
返回:ForwardIterator 满足条件的元素索引
ForwardIterator lower_bound( ForwardIterator first, ForwardIterator last, const Type& val );
upper_bound :返回一个非递减序列[first, last)中最后一个大于等于val的位置.重载版本使用了输入的比较操作.
参数:first
:last
:val
返回:ForwardIterator 满足条件的元素索引
ForwardIter upper_bound(ForwardIter first, ForwardIter last, const _Tp& val)
#include "stdafx.h"
#include <string>
#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional> int main()
{
{
std::vector<int> vec = { , , , , };
//lower的意义是对于给定的已经排好序的vec，key最早能插入的那个位置
auto result1 = lower_bound(vec.begin(), vec.end(), );
std::cout << *result1 << std::endl; //输出:22 //upper的意义是对于给定的已经排好序的vec，key最晚能插入的那个位置
auto result2 = upper_bound(vec.begin(), vec.end(), );
std::cout << *result2 << std::endl; //输出:23 getchar();
return ;
}
}
<二>排序和通用算法(14个)：提供元素排序策略,会改变原始数据顺序
random_shuffle :对指定范围内的元素随机调整次序.重载版本输入一个随机数产生操作.
参数:first
:last
返回：无
template <class randomAccessItr>
void random_shuffle(randomAccessItr first, randomAccessItr last);
参数:first
:last
:rand
返回：无
template <class randomAccessItr, class randomAccessGenerator>
void random_shuffle(randomAccessItr first,randomAccessItr last,randomAccessGenerator rand);
#include "stdafx.h"
#include <random>
#include <ctime>
#include <string>
#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional> int myrandom(int i)
{
return std::rand() % i;
} int main()
{
{
std::vector<int> vec1 = { , , , , , };
sort(vec1.begin(), vec1.end());
for (int i = ; i < vec1.size(); i++)
{
std::cout << vec1[i] << " "; //输出:2 11 32 33 33 43
}
std::cout << std::endl; default_random_engine defaultEngine(time());
shuffle(vec1.begin(), vec1.end(), defaultEngine);
for (int i = ; i < vec1.size(); i++)
{
std::cout << vec1[i] << " "; //输出:每次都不一样
}
std::cout << std::endl; random_shuffle(vec1.begin(), vec1.end());
for (int i = ; i < vec1.size(); i++)
{
std::cout << vec1[i] << " "; //输出:每次都一样
}
std::cout << std::endl; std::srand(unsigned(std::time()));
random_shuffle(vec1.begin(), vec1.end(), myrandom);
for (int i = ; i < vec1.size(); i++)
{
std::cout << vec1[i] << " "; //输出:每次都不一样
}
std::cout << std::endl; getchar();
return ;
}
}
reverse :将范围内元素重新按反序排列. 会改变原始数据在容器中的顺序
参数:first
:last
返回：无
template <class biDirectionalItr>
void reverse(biDirectionalItr first, biDirectionalItr last);
reverse_copy :类似与 reverse ,不改变原始数据在容器中的顺序，不过将内容倒置写入另外一个容器.
参数:first
:last
:destFirst
返回：outputItr
template <class biDirectionalItr, class outputItr>
outputItr reverse_copy(biDirectionalItr first, biDirectionalItr last,outputItr destFirst);
#include "stdafx.h"
#include <string>
#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional> int main()
{
{
std::vector<int> vec1 = { , , , , , }; reverse(vec1.begin(), vec1.end());
for (int i = ; i < vec1.size(); i++)
{
std::cout << vec1[i] << " "; //输出:43 33 33 11 32 2
}
std::cout << std::endl; std::vector<int> vec2(vec1.size());
reverse_copy(vec1.begin(), vec1.end(), vec2.begin());
for (int i = ; i < vec1.size(); i++)
{
std::cout << vec1[i] << " "; //输出:43 33 33 11 32 2
}
std::cout << std::endl; for (int i = ; i < vec2.size(); i++)
{
std::cout << vec2[i] << " "; //输出:2 32 11 33 33 43
}
std::cout << std::endl; getchar();
return ;
}
}
rotate :由newFirst指向的元素成为容器第一个元素,并且将first到newFirst之间的元素移到newFirst指向元素的后面填充，其他元素位置不变.
参数:first
:newFirst
:last
返回：无
template <class forwardItr>
void rotate(forwardItr first, forwardItr newFirst, forwardItr last);
rotate_copy :类似与 rotate ,不过将结果写入另外一个容器.
参数:first
:middle
:last
:destFirst
返回：outputItr
template <class forwardItr, class outputItr>
outputItr rotate_copy(forwardItr first, forwardItr middle, forwardItr last,outputItr destFirst);
#include <string>
#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional> int main()
{
{
std::vector<int> vec1 = { , , , , , };
auto it1 = vec1.begin() + ;
rotate(vec1.begin(), it1, vec1.begin() + );
for (int i = ; i < vec1.size(); i++)
{
std::cout << vec1[i] << " "; //输出:33 2 32 11 33 43
}
std::cout << std::endl; std::vector<int> vec2(vec1.size());
auto it2 = vec1.begin() + ;
rotate_copy(vec1.begin(), it2, vec1.end(), vec2.begin());
for (int i = ; i < vec2.size(); i++)
{
std::cout << vec2[i] << " "; //输出:11 33 43 33 2 32
}
std::cout << std::endl; getchar();
return ;
}
}
merge :将两个有序序列合并为一个有序序列,元素个数不变，并存放到另外一个序列中.重载版本使用自定义的比较.
参数:first1
:last1
:first2
:last2
:destFirst
返回:outputItr
template<class inputItr1,class inputItr2,class outputItr, class binaryPredicate>
outputItr merge(inputItr1 first1,inputItr1 last1, inputItr2 first2, inputItr2 last2,outputItr destFirst);
参数:first1
:last1
:first2
:last2
:destFirst
:op
返回:outputItr
template<class inputItr1,class inputItr2,class outputItr>
outputItr merge(inputItr1 first1,inputItr1 last1, inputItr2 first2, inputItr2 last2,outputItr destFirst, binaryPredicate op);
inplace_merge :合并两个排过序的连续序列,结果序列覆盖了两端范围,重载版本使用输入的操作进行排序.
参数:first1
:middle
:last
返回:void
template <class BidirectionalIterator>
void inplace_merge ( BidirectionalIterator first, BidirectionalIterator middle,BidirectionalIterator last );
参数:first1
:middle
:last
:comp
返回:void
template <class BidirectionalIterator, class Compare>
void inplace_merge ( BidirectionalIterator first, BidirectionalIterator middle,BidirectionalIterator last, Compare comp );
#include "stdafx.h"
#include <random>
#include <ctime>
#include <string>
#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional> int main()
{ {
std::vector<int> vec1 = { , , , , };
std::vector<int> vec2 = { , , , , };
std::vector<int> vec3(vec1.size() + vec2.size());
auto result = merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), vec3.begin());
for (int i = ; i < vec3.size(); i++)
{
std::cout << vec3[i] << " ";
}
std::cout << std::endl; std::vector<int> vec4 = { , , , , , , , , , };
inplace_merge(vec4.begin(), vec4.begin() + , vec4.end());
for (int i = ; i < vec4.size(); i++)
{
std::cout << vec4[i] << " ";
} getchar();
return ;
}
}
nth_element :将指定范围内的序列重新排序,使第n大元素处于第n位置(从0开始,其位置是下标为 n的元素),并且比这个元素小的元素都排在这个元素之前，比这个元素大的元素都排在这个元素之后,但不能保证他们是有序的,重载版本使用了自定义的比较操作.
参数:_First
:_Nth
:_Last
返回:void
template<class _RanIt>
void nth_element(_RanIt _First, _RanIt _Nth, _RanIt _Last);
参数:_First
:_Nth
:_Last
:_Pred
返回:void
template<class _RanIt, class _Pr>
void nth_element(_RanIt _First, _RanIt _Nth, _RanIt _Last, _Pr _Pred);
#include "stdafx.h"
#include <random>
#include <ctime>
#include <string>
#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional> int main()
{ {
std::vector<int> vec5 = { , , , , , , , , , };
nth_element(vec5.begin(), vec5.begin() + , vec5.begin() + );
for (int i = ; i < vec5.size(); i++)
{
std::cout << vec5[i] << " "; //输出:1 2 3 4 5 6 7 8 5 7
}
std::cout << std::endl; getchar();
return ;
}
}
sort :以升序重新排列范围内的元素,重载版本使用了自定义的比较操作.
参数:first
:last
返回：void
template<class randomAccessItr>
void sort(randomAccessItr first,randomAccessItr last);
参数:first
:last
:op
返回：void
template<class randomAccessItr, class compare>
void sort(randomAccessItr first, randomAccessItr last, compare op);
is_sorted:检查指定范围内元素是否排序
参数:first
:last
返回：bool 已排序返回true,未排序返回false
template <class ForwardIterator>
bool is_sorted (ForwardIterator first, ForwardIterator last);
template <class ForwardIterator, class Compare>
bool is_sorted (ForwardIterator first, ForwardIterator last, Compare comp);
partion :对指定范围内元素重新排序,根据自定义函数,把计算结果为 true 的元素放在结果为 false 的元素之前.
参数:first
:last
:pred
返回：ForwardIterator 排序后返回首个不满足条件元素迭代器
template <class ForwardIterator, class Predicate>
ForwardIterator partition(ForwardIterator first, ForwardIterator last, Predicate pred);
partial_sort :对整个序列做部分排序,被排序元素的个数正好可以被放到范围内.重载版本使用自定义的比较操作.
参数:first
:middle
:last
返回：void
template <class RandomAccessIterator>
void partial_sort ( RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last );
参数:first
:middle
:last
:comp
返回：void
template <class RandomAccessIterator, class Compare>
void partial_sort ( RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp );
partial_sort_copy :与 partial_sort 相同,除了将经过排序的序列复制到另外一个容器.
参数:first
:last
:result_first
:result_last
返回：RandomAccessIterator
template <class InputIterator, class RandomAccessIterator>
RandomAccessIterator partial_sort_copy ( InputIterator first,InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last );
参数:first
:last
:result_first
:result_last
:comp
返回：RandomAccessIterator
template <class InputIterator, class RandomAccessIterator, class Compare>
RandomAccessIterator partial_sort_copy ( InputIterator first,InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp );
所谓稳定排序，是指对一个序列进行排序之后，如果两个元素的值相等，则原来乱序时在前面的元素现在（排好序之后）仍然排在前面
stable_sort :类似与 sort ,不过保留容器中相等元素之间的顺序关系.
参数:first
:last
返回:void
template <class RandomAccessIterator>
void stable_sort ( RandomAccessIterator first, RandomAccessIterator last );
参数:first
:last
:comp
返回:void
template <class RandomAccessIterator, class Compare>
void stable_sort ( RandomAccessIterator first, RandomAccessIterator last, Compare comp );
stable_partition :与 partition 类似,不过保留容器中相等元素之间的相对顺序.
参数:first
:last
:pred
返回:BidirectionalIterator
template <class BidirectionalIterator, class UnaryPredicate>
BidirectionalIterator stable_partition (BidirectionalIterator first, BidirectionalIterator last, UnaryPredicate pred);
#include "stdafx.h"
#include <random>
#include <ctime>
#include <string>
#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional> int main()
{
{
std::vector<int> vec1 = { , , , , };
sort(vec1.begin(), vec1.end());
for (int i = ; i < vec1.size(); i++)
{
std::cout << vec1[i] << " "; //输出:5 11 22 33 43
}
std::cout << std::endl; sort(vec1.begin(), vec1.end(), [](int x, int y)->bool { return x > y; });
for (int i = ; i < vec1.size(); i++)
{
std::cout << vec1[i] << " "; //输出:43 33 22 11 5
}
std::cout << std::endl; std::vector<int> vec2 = { , , , , };
auto result2 = partition(vec2.begin(), vec2.end(), [](int x)->bool { return x % == ? true : false; });
std::cout << *result2 << std::endl; //输出:33 注意是33说明5和10是调换位置
for (int i = ; i < vec2.size(); i++)
{
std::cout << vec2[i] << " "; //输出:22 10 33 43 5
}
std::cout << std::endl; std::vector<int> vec3 = { , , , , , , , , };
partial_sort(vec3.begin(), vec3.begin() + , vec3.end());
for (int i = ; i < vec3.size(); i++)
{
std::cout << vec3[i] << " "; //输出:1 2 9 7 6 5 8 4 3
}
std::cout << std::endl; std::vector<int> vec4(vec3.size());
partial_sort_copy(vec3.begin(), vec3.end(), vec4.begin(), vec4.end());
for (int i = ; i < vec4.size(); i++)
{
std::cout << vec4[i] << " "; //输出:1 2 3 4 5 6 7 8 9
}
std::cout << std::endl; getchar();
return ;
}
}
<三>删除和替换算法(15个)
copy :用于容器之间元素的拷贝,即将迭代器区间[first,last)的元素复制到目标容器中
参数:_First 指出被复制的元素的区间范围[ _First,_Last).
:_Last
:_DestBeg 指出复制到的目标区间起始位置
返回:OutputIterator 返回一个迭代器,指向目标容器中拷贝元素区间的下一个位置(因为是左必右开,也就是目标容器的_DestBeg位置)
template<class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator _First, InputIterator _Last, OutputIterator _DestBeg);
copy_backward :其复制过程是从最后的元素开始复制,直到首元素复制出来.也就是说,复制操作是从last-1开始,直到first结束.这些元素也被从后向前复制到目标容器中
参数:_First
:_Last
:_Dest
返回:_BidIt2 返回一个迭代器,指出已被复制元素区间的起始位置
template<class _BidIt1, class _BidIt2> inline
_BidIt2 copy_backward(_BidIt1 _First, _BidIt1 _Last,_BidIt2 _Dest);
copy_if:将满足条件的元素(对元素调用pred返回true的元素)复制到目标容器中
参数:_First
:_Last
:_Dest
:_Pred
返回:_BidIt2 返回一个迭代器,指向目标容器中最后一个拷贝元素的下一个位置
template<class InputIterator, class OutputIterator, class BinaryPredicate>
OutputIterator copy_if(InputIterator _First, InputIterator _Last,OutputIterator _Dest,Predicate _Pred);
copy_n:从first开始复制count个元素到result的容器中
参数:first
:count
:dest
返回:OutputIterator 返回一个迭代器,指向目标容器中最后一个拷贝元素的下一个位置
template<class InputIterator, class Size, class OutputIterator>
OutputIterator copy_n(InputIterator first, Size count, OutputIterator dest);
#include "stdafx.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <iterator>
#include <ostream> bool greater10(int num)
{
return num % ? true : false;
} int main()
{
{
std::vector<int> arr = { , , , , , , , ,, };
std::vector<int> arr1();
std::vector<int> arr2();
std::vector<int> arr3();
std::vector<int> arr4(); auto var1 = copy(arr.begin() + , arr.begin() + , arr1.begin());
for (int i = ; i < arr1.size(); i++)
{
std::cout << arr1[i] << " ";
}
std::cout << std::endl; auto var2 = copy_backward(arr.begin(), arr.begin() + , arr2.end());
for (int i = ; i < arr2.size(); i++)
{
std::cout << arr2[i] << " ";
}
std::cout << std::endl; auto var3 = copy_if(arr.begin(), arr.begin() + , arr3.begin(), greater10);
for (int i = ; i < arr3.size(); i++)
{
std::cout << arr3[i] << " ";
}
std::cout << std::endl; auto var4 = copy_n(arr.begin(), , arr4.begin());
for (int i = ; i < arr4.size(); i++)
{
std::cout << arr4[i] << " ";
}
std::cout << std::endl; getchar();
return ;
}
}
vector中的remove的作用是将等于value的元素放到vector的尾部，但并不减少vector的size(尾部为无效数据)
移除容器里面的元素应该使用容器自带的remove,不应该使用remove算法
remove :删除在范围内的所有等于指定的元素,注意,该函数并不真正删除元素.内置数组不适合使用 remove 和 remove_if 函数.
参数:first
:last
:value
返回：forwardItr 指向容器中第一个无效数据的迭代器
template <class forwardItr,class Type>
forwardItr remove(forwardItr first, forwardItr last, const Type& value);
remove_copy :将所有不匹配的元素都复制到一个指定容器,
参数:first1
:last1
:destFirst
:value
返回：outputItr 指向被拷贝最后元素的下一个位置的迭代器
template <class inputItr,class outputItr,class Type>
outputItr remove_copy(inputItr first1, inputItr last1, outputItr destFirst, const Type& value);
remove_if :删除指定范围内输入操作结果为 true 的元素.
参数:first
:last
:destFirst
:op
返回：forwardItr
template <class forwardItr, class unaryPredicate>
forwardItr remove_if(forwardItr first, forwardItr last, unaryPredicate op);
remove_copy_if :将所有不匹配的元素拷贝到一个指定容器.
参数:first1
:last1
:destFirst
:op
返回：outputItr 指向被拷贝最后元素的下一个位置的迭代器
template <class inputItr,class outputItr, class unaryPredicate>
outputItr remove_copy_if(inputItr first1, inputItr last1, outputItr destFirst, unaryPredicate op)
#include "stdafx.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <iterator>
#include <ostream> bool remove_func(int x)
{
return x % == ? true : false;
} int main()
{
{
//如果为1234 remove 2 = 1344 3被复制到2的位置，4被复制到3的位置,后面的原来是什么就是什么
std::vector<int> vec1 = { , , , , , , , ,, };
auto result1 = remove(vec1.begin(), vec1.end(), );
std::cout << *result1 << std::endl; //输出:55 指向首个无效数据的迭代器
for (int i = ; i < vec1.size(); i++)
{
std::cout << vec1[i] << " "; //输出:43 65 23 55 56 2 55 56 2 34
}
std::cout << std::endl; std::vector<int> vec2 = { , , , , , , , ,, };
std::vector<int> vec3(vec2.size());
auto result2 = remove_copy(vec2.begin(), vec2.end(), vec3.begin(), );
std::cout << *result2 << std::endl; //输出:0 指向最后一个拷贝元素下一个位置的迭代器
for (int i = ; i < vec3.size(); i++)
{
std::cout << vec3[i] << " "; //输出:43 65 23 55 56 2 0 0 0 0
}
std::cout << std::endl; //同remove一样，将不要删除的元素往前移，后面的元素是无效数据
std::vector<int> vec4 = { , , , , , , , ,, };
remove_if(vec4.begin(), vec4.end(), remove_func);
for (int i = ; i < vec4.size(); i++)
{
std::cout << vec4[i] << " "; //输出:43 65 23 55 34 23 55 56 2 34
}
std::cout << std::endl; std::vector<int> vec5 = { , , , , , , , ,, };
std::vector<int> vec6(vec5.size());
auto result5 = remove_copy_if(vec5.begin(), vec5.end(), vec6.begin(), remove_func);
std::cout << *result5 << std::endl; //输出:0 指向最后一个拷贝元素下一个位置的迭代器
for (int i = ; i < vec6.size(); i++)
{
std::cout << vec6[i] << " "; //输出:43 65 23 55 0 0 0 0 0 0
}
std::cout << std::endl; getchar();
return ;
}
}
replace :将范围内的所有等于 old_value 的元素都用 new_value 替代.
参数:first
:last
:oldValue
:newValue
返回：无
template <class forwardItr,class Type>
void replace(forwardItr first, forwardItr last,const Type& oldValue, const Type& newValue);
replace_copy :与 replace 类似,不过将结果写入另外一个容器.
参数:first1
:last1
:destFirst
:oldValue
:newValue
返回：outputItr 指向dest最后拷贝元素的下一个位置
template <class inputItr,class outputItr,class Type>
outputItr replace_copy(inputItr first1, inputItr last1, outputItr destFirst,const Type& oldValue, const Type& newValue);
replace_if :将范围内的所有操作结果为 true 的元素用新值替代.
参数:first
:last
:op
:newValue
返回：无
template <class forwardItr, class unaryPredicate,class Type>
void replace_if(forwardItr first, forwardItr last, unaryPredicate op,const Type& newValue);
replace_copy_if :类似与 replace_if ,不过将结果写入另外一个容器.
参数:first1
:last1
:destFirst
:op
:newValue
返回：outputItr 指向dest拷贝最后元素的下一个位置的迭代器
template <class inputItr,class outputItr, class unaryPredicate>
outputItr replace_copy_if(inputItr first1, inputItr last1, outputItr destFirst, unaryPredicate op,const Type& newValue);
#include "stdafx.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <iterator>
#include <ostream> bool replace_func(int x)
{
return x % == ? true : false;
} int main()
{
{
std::vector<int> vec1 = { , , , , , };
replace(vec1.begin(), vec1.end(), , );
for (int i = ; i < vec1.size(); i++)
{
std::cout << vec1[i] << " "; //输出:12 22 3 33 3 4
}
std::cout << std::endl; std::vector<int> vec2 = { , , , , , };
std::vector<int> vec3(vec2.size());
auto result1 = replace_copy(vec2.begin(), vec2.end(), vec3.begin(), , );
result1--;
std::cout << *result1 << std::endl; //输出:4
for (int i = ; i < vec3.size(); i++)
{
std::cout << vec3[i] << " "; //输出:12 22 3 33 3 4
}
std::cout << std::endl; std::vector<int> vec4 = { , , , , , };
replace_if(vec4.begin(), vec4.end(), replace_func, );
for (int i = ; i < vec4.size(); i++)
{
std::cout << vec4[i] << " "; //输出:7 7 11 33 11 7
}
std::cout << std::endl; std::vector<int> vec5 = { , , , , , };
std::vector<int> vec6(vec5.size());
replace_copy_if(vec5.begin(), vec5.end(), vec6.begin(), replace_func, );
for (int i = ; i < vec6.size(); i++)
{
std::cout << vec6[i] << " "; //输出:5 5 11 33 11 5
}
std::cout << std::endl; getchar();
return ;
}
}
swap :交换存储在两个对象中的值.
template<class Type>
void swap(Type& objcet1, Type& objec2);
swap_range :将在范围内的元素与另外一个序列的元素值进行交换.
template<class forwardItr1, class forwardItr2>
forwardItr2 swap_ranges(forwardItr1 first,forwardItr1 last, forwardItr2 first2);
iter_swap :交换两个 ForwardIterator 的值.
template<class forwardItr1,class forwardItr2>
void iter_swap(forwardItr1 first,forwardItr2 scecod);
#include "stdafx.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <iterator>
#include <ostream> int main()
{
{
std::vector<int> vec1 = { , , , , };
std::vector<int> vec2 = { , , , , };
swap(vec1, vec2);
for (int i = ; i < vec1.size(); i++)
{
std::cout << vec1[i] << " "; //输出:3 4 23 11 7
}
std::cout << std::endl; for (int i = ; i < vec2.size(); i++)
{
std::cout << vec2[i] << " "; //输出:12 22 11 33 4
}
std::cout << std::endl; std::vector<int> vec3 = { , , , , };
std::vector<int> vec4 = { , , , , };
swap_ranges(vec3.begin(), vec3.begin() + , vec4.begin() + );
for (int i = ; i < vec3.size(); i++)
{
std::cout << vec3[i] << " "; //输出:23 11 7 33 4
}
std::cout << std::endl; for (int i = ; i < vec4.size(); i++)
{
std::cout << vec4[i] << " "; //输出:3 4 12 22 11
}
std::cout << std::endl; std::vector<int> vec5 = { , , , , };
iter_swap(vec5.begin() + , vec5.begin() + );
for (int i = ; i < vec5.size(); i++)
{
std::cout << vec5[i] << " "; //输出:12 33 11 22 4
}
std::cout << std::endl; getchar();
return ;
}
}
unique :unique的功能是去除相邻的重复元素(只保留一个),其实它并不真正把重复的元素删除,只是把重复的元素移到后面去了,然后依然保存到了原数组中,然后返回去重后最后一个元素的地址,因为unique去除的是相邻的重复元素,所以一般用之前都会要排一下序.
注意,unique并不直接改变容器的大小,只改变容器元素的顺序.调用unique“删除”了相邻的重复值.给“删除”加上引号是因为unique实际上并没有删除任何元素,而是将无重复的元素复制到序列的前段,从而覆盖相邻的重复元素.unique返回的迭代器如果需要添加或删除元素,则必须使用容器操作.原理与remove类似
参数:_First
:_Last
返回：ForwardIterator 指向超出无重复的元素范围末端的下一个位置.
template<class ForwardIterator>
ForwardIterator unique(ForwardIterator _First, ForwardIterator _Last);
template<class ForwardIterator, class Predicate>
ForwardIterator unique(ForwardIterator _First, ForwardIterator _Last,Predicate _Comp);
unique_copy :类似与 unique ,不过它把结果输出到另外一个容器.
template<class InputIterator, class OutputIterator>
OutputIterator unique_copy(InputIterator _First, InputIterator _Last, OutputIterator _Result);
template<class InputIterator, class OutputIterator, class BinaryPredicate>
OutputIterator unique_copy(InputIterator _First, InputIterator _Last, OutputIterator _Result,BinaryPredicate _Comp,);
#include "stdafx.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <iterator>
#include <ostream> int main()
{
{
std::vector<int> vec1 = { , , , , , };
auto result1 = unique(vec1.begin(), vec1.end());
std::cout << *result1 << std::endl;
for (int i = ; i < vec1.size(); i++)
{
std::cout << vec1[i] << " "; //输出:12 22 33 44 33 44
}
std::cout << std::endl; std::vector<int> vec2 = { , , , , , };
std::vector<int> vec3(vec2.size());
auto result2 = unique_copy(vec2.begin(), vec2.end(), vec3.begin());
result2--;
std::cout << *result2 << std::endl;
for (int i = ; i < vec3.size(); i++)
{
std::cout << vec3[i] << " "; //输出:12 22 33 44 0 0
}
std::cout << std::endl; getchar();
return ;
}
}
<四>排列组合算法(2个)：提供计算给定集合按一定顺序的所有可能排列组合
next_permutation :取出当前范围内的排列,并将其重新排序为下一个排列.重载版本使用自定义的比较操作.
prev_permutation :取出范围内的序列并将它重新排序为上一个序列.如果不存在上一个序列则返回 false .重载版本使用自定义的比较操作.
#include "stdafx.h"
#include <stdio.h>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <iterator>
#include <ostream>
#include <numeric> int main()
{
{
int myints[] = { ,, };
std::sort(myints, myints + );
std::cout << "The 3! possible next_permutations with 3 elements:\n"; do {
std::cout << myints[] << ' ' << myints[] << ' ' << myints[] << '\n';
} while (std::next_permutation(myints, myints + )); std::cout << "After loop: " << myints[] << ' ' << myints[] << ' ' << myints[] << '\n'; std::cout << "The 3! possible prev_permutations with 3 elements:\n"; do {
std::cout << myints[] << ' ' << myints[] << ' ' << myints[] << '\n';
} while (std::prev_permutation(myints, myints + )); std::cout << "After loop: " << myints[] << ' ' << myints[] << ' ' << myints[] << '\n'; getchar();
return ;
}
}
<五>算术算法(4个)
主要是对容器的数据元素进行数值计算,所在头文件为：<numeric>
accumlate :函数将第三个实参用作累加的初始值(init),然后在此初值上累加输入范围内所有元素的值.accumulate算法返回累加的结果,其返回类型就是第三个实参的类型.容器内的元素类型必须与第三个实参的类型匹配,或者可转换为第三个实参的类型.
参数:first
:last
:init 累加初始值
返回:Type
template <class inputItr, class Type>
Type accumulate(inputItr first, inputItr last, Type init);
参数:first
:last
:init
:op 函数第一个参数总为初始值(会变化),第二个参数依次为集合的每一元素
返回:Type
template <class inputItr, class Type, class binaryOperation>
Type accumulate(inputItr first, inputItr last, Type init,binaryOperation op);
template<class _InIt, class _Ty, class _Fn2>
inline _Ty _Accumulate_unchecked(_InIt _First, _InIt _Last, _Ty _Val, _Fn2& _Func)
{ // return sum of _Val and all in [_First, _Last), using _Func
for (; _First != _Last; ++_First)
_Val = _Func(_Val, *_First);
return (_Val);
}
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric> using namespace std; int multiply(int x, int y)
{
return x - y;
} int main()
{
{
//用accumulate统计vector<int>容器对象中的元素之和
std::vector<int> vec = {, , , , };
int sum = accumulate(vec.begin(), vec.end(), );
std::cout << sum << std::endl; //可以使用accumulate把string型的vector容器中的元素连接起来
std::vector<std::string> vec2 = { "", "", "", "", "" };
string str = accumulate(vec2.begin(), vec2.end(), string(" "));
std::cout << str << std::endl; int total = accumulate(vec.begin(), vec.end(), , multiply);
std::cout << total << std::endl;
} getchar();
return EXIT_SUCCESS;
}
adjacent_difference :创建一个新序列,该序列的每个新值都代表了当前元素与上一个元素的差.重载版本用指定的二元操作计算相邻元素的差.
参数:first
:last
:destFirst 输出集合
template<class inputItr, class outputItr, class binaryOperation>
outputItr adjacent_difference(inputItr first,inputItr last, outputItr destFirst);
参数:first
:last
:destFirst 输出集合
:op
template<class inputItr, class outputItr>
outputItr adjacent_difference(inputItr first,inputItr last, outputItr destFirst,binaryOperation op);
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric> //x为当前元素，y为上一个元素
int sub(int x, int y)
{
return x + (x - y);
} int main()
{
{
std::vector<int> vec = { , , , , , };
std::vector<int> vec2(); auto it = adjacent_difference(vec.begin(), vec.end(), vec2.begin());
for (int i = ; i < vec2.size(); i++)
{
std::cout << vec2[i] << " "; //输出：12 10 -11 22 0 10
} auto it2 = adjacent_difference(vec.begin(), vec.end(), vec2.begin(), sub);
for (int i = ; i < vec2.size(); i++)
{
std::cout << vec2[i] << " "; //输出：12 32 0 55 33 53
} getchar();
return ;
}
}
inner_product :对两个序列做内积 ( 对应的元素相乘,再求和 ) ,并将内积加到一个输入的的初始值上.重载版本使用了用户定义的操作.
参数:first1
:last1
:first2
:init
template<class inputItr1, class inputItr2,class Type>
Type inner_product(inputItr1 first1,inputItr1 last1,inputItr2 first2,Type init);
参数:first1
:last1
:first2
:last2
:init
:op1
:op2
template<class inputItr1, class inputItr2,class Type, class binaryOperation1, class binaryOperation2>
Type inner_product(inputItr1 first1,inputItr1 last1,inputItr2 first2,inputItr2 last2,Type init,binaryOperation1 op1,binaryOperation2 op2);
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric> using namespace std; int main()
{
{
std::vector<int> vec = { , , , , , };
std::vector<int> vec2 = { , , , , , }; //vec[i]*vec2[i] + vec[i+1]*vec2[i+1]
auto value = inner_product(vec.begin(), vec.end(), vec2.begin(), );
std::cout << value << std::endl; auto value2 = inner_product(vec.begin(), vec.end(), vec2.begin(), , plus<int>(), minus<int>());
std::cout << value2 << std::endl; getchar();
return ;
}
}
partial_sum :创建一个新的元素序列,其中每个元素的值代表了范围内该位置之前所有元素之和.重载版本使用了自定义操作替代加法.
参数:first
:last
:destFirst
template<class inputItr, class outputItr>
outputItr partial_sum(inputItr first,inputItr last,outputItr destFirst);
参数:first
:last
:destFirst
:op
template<class inputItr, class outputItr, class binaryOperation>
outputItr partial_sum(inputItr first,inputItr last,outputItr destFirst,binaryOperation op);
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric> using namespace std; int sum(int x, int y)
{
return x + (y - );
} int main()
{
{
std::vector<int> vec = { , , , , , };
std::vector<int> sum_vec();
auto pos = partial_sum(vec.begin(), vec.end(), sum_vec.begin());
for (int i = ; i < sum_vec.size(); i++)
{
std::cout << sum_vec[i] << " ";
} auto pos2 = partial_sum(vec.begin(), vec.end(), sum_vec.begin(), sum);
for (int i = ; i < sum_vec.size(); i++)
{
std::cout << sum_vec[i] << " ";
} getchar();
return ;
}
}
<六>生成和异变算法(6个)
fill :将容器中指定位置[first, last)元素的值赋值为value.
参数:first
:last
:value
返回:无
template <class forwardItr, class Type>
void fill(forwardItr first, forwardItr last, const Type& value);
fill_n :将容器中指定位置[first, frist+n) 范围内的元素赋值为value.
参数:first
:n
:value
返回:无
template <class forwardItr, class size, class Type>
void fill_n(forwardItr first, size n, const Type& value);
#include "stdafx.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <iterator>
#include <ostream> int main()
{
{
std::vector<int> arr = { , , , , , , , ,, };
fill(arr.begin(), arr.end(), );
for (int i = ; i < arr.size(); i++)
{
std::cout << arr[i] << " ";
}
std::cout << std::endl; fill_n(arr.begin(), , );
for (int i = ; i < arr.size(); i++)
{
std::cout << arr[i] << " ";
}
std::cout << std::endl; getchar();
return ;
}
}
for_each :依次对范围内的所有元素执行输入的函数.
参数:first
:last
:func
返回:Function 返回f函数的首地址
template <class inputItr,class function>
Function for_each(InputIterator first, InputIterator last, Function f) {
for ( ; first != last; ++first) f(*first);
return f;
}
#include "stdafx.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <iterator>
#include <ostream> int main()
{
{
std::vector<int> vec1 = { , , , , , };
for_each(vec1.begin(), vec1.end(), [](int x)->void { std::cout << x << " "; }); //输出:12 22 33 33 33 44 getchar();
return ;
}
}
generate :用指定函数对象产生的值去给容器指定范围内元素赋值
参数:first
:last
:gen
返回:无
template <class forwardItr, class function>
void generate(forwardItr first, forwardItr last, function gen);
generate_n :一个函数对象产生的值给一定的范围内指定数目的容器元素赋值
参数:first
:n
:gen
返回:无
template <class forwardItr, class size, class function>
void generate_n(forwardItr first, size n, function gen);
#include "stdafx.h"
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <iterator>
#include <ostream> int generate_func()
{
return std::rand() % ;
} int main()
{
{
std::vector<int> vec1();
std::srand(unsigned(std::time()));
generate(vec1.begin(), vec1.end(), generate_func);
for_each(vec1.begin(), vec1.end(), [](int x)->void { std::cout << x << " "; }); //输出:9 0 4 1 1
std::cout << std::endl; std::vector<int> vec2();
generate_n(vec2.begin(), , generate_func);
for_each(vec2.begin(), vec2.end(), [](int x)->void { std::cout << x << " "; }); //输出:7 0 6 0 0 getchar();
return ;
}
}
transform :将要执行的操作作用在指定范围内的每个元素上,并产生一个新的序列.重载版本将操作作用在一对元素上,另外一个元素来自输入的另外一个序列.结果输出到指定的容器.
参数:first
:last
:destFirst
:op
返回：outputItr
template <class inputItr, class outputItr, class unaryOperation>
outputItr transform(inputItr first,inputItr last, outputItr destFirst,unaryOperation op);
参数:first1
:last1
:first2
:destFirst
:bop
返回：outputItr
template <class inputItr1, class inputItr2, class outputItr, class binaryOperation>
outputItr transform(inputItr1 first1, inputItr1 last, inputItr2 first2, outputItr destFirst,binaryOperation bop);
#include "stdafx.h"
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <iterator>
#include <ostream> int transfrom_func1(int x)
{
return x + ;
} int transfrom_func2(int x, int y)
{
return x + y;
} int main()
{
{
std::vector<int> vec1 = { , , , , , };
std::vector<int> vec2(vec1.size());
/////将first容器的元素加1赋值给second容器
transform(vec1.begin(), vec1.end(), vec2.begin(), transfrom_func1);
for_each(vec2.begin(), vec2.end(), [](int x)->void { std::cout << x << " "; }); //输出:13 5 12 6 2 9
std::cout << std::endl; std::vector<int> vec3 = { , , , , , };
std::vector<int> vec4 = { , , , , , };
/////将first容器的元素与second容器的元素相加，并将得到的结果重新赋值给first
transform(vec3.begin(), vec3.end(), vec4.begin(), vec3.begin(), transfrom_func2);
for_each(vec3.begin(), vec3.end(), [](int x)->void { std::cout << x << " "; }); //输出:15 17 55 12 13 13 getchar();
return ;
}
}
<七>关系算法(8个)
max:判断两个数值中的较大值
参数:aVal
:bVal
返回:Type&
template <class Type>
const Type& max(const Type& aVal, const Type&bVal);
参数:aVal
:bVal
:comp
返回:Type&
template <class Type,class compare>
const Type& max(const Type& aVal,const Type& bVal,compare comp);
max_element:查找指定区间的最大元素
参数:first
:last
返回:forwardItr
template <class forwardItr>
forwardItr max_element(forwardItr first,forwardItr last);
参数:first
:last
:comp
返回:forwardItr
template <class forwardItr, class compare>
forwardItr max_element(forwardItr first,forwardItr last, compare comp);
min:判断两个数值中的较小值
参数:aVal
:bVal
返回:Type&
template <class Type>
const Type& min(const Type& aVal, const Type&bVal);
参数:aVal
:bVal
:comp
返回:Type&
template <class Type,class compare>
const Type& min(const Type& aVal,const Type& bVal,compare comp);
min_element:查找指定区间的最小元素
参数:first
:last
返回:forwardItr
template <class forwardItr>
forwardItr min_element(forwardItr first,forwardItr last);
参数:first
:last
:comp
返回:forwardItr
template <class forwardItr, class compare>
forwardItr min_element(forwardItr first,forwardItr last, compare comp);
minmax_element:查找指定区间的最大和最小元素
参数:first
:last
返回:pair<ForwardIterator,ForwardIterator> 返回指定范围内的最大最小值的元素的迭代器组成的一个pair
template <class ForwardIterator>
pair<ForwardIterator,ForwardIterator> minmax_element (ForwardIterator first, ForwardIterator last);
参数:first
:last
:comp
返回:pair<ForwardIterator,ForwardIterator> 返回指定范围内的最大最小值的元素的迭代器组成的一个pair
template <class ForwardIterator, class Compare>
pair<ForwardIterator,ForwardIterator> minmax_element (ForwardIterator first, ForwardIterator last, Compare comp);
mismatch :并行的比较两个序列的指定范围,指出第一个不匹配的位置.重载版本使用自定义的比较操作.
参数:_First1
:_Last1
:_First2
返回:pair<InputIterator1, InputIterator2> 它返回一对 iterator,first,second分别指向两个集合不同元素的位置,如相同，则返回每个容器的last
template<class InputIterator1, class InputIterator2>
pair<InputIterator1, InputIterator2> mismatch(InputIterator1 _First1, InputIterator1 _Last1,InputIterator2 _First2);
template<class InputIterator1, class InputIterator2, class BinaryPredicate>
pair<InputIterator1, InputIterator2> mismatch(InputIterator1 _First1, InputIterator1 _Last1,InputIterator2 _First2BinaryPredicate _Comp);
#include "stdafx.h"
#include <stdio.h>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <iterator>
#include <ostream>
#include <numeric> int main()
{
{
std::vector<int> vec1 = { , , , , , };
auto result1 = std::max(vec1.begin() + , vec1.begin() + );
std::cout << *result1 << std::endl; //输出:22
auto result3 = std::min(vec1.begin() + , vec1.begin() + );
std::cout << *result3 << std::endl; //输出:4 auto result2 = max_element(vec1.begin(), vec1.end());
std::cout << *result2 << std::endl; //输出:22
auto result4 = min_element(vec1.begin(), vec1.end());
std::cout << *result4 << std::endl; //输出:1 std::vector<int> vec3 = { , , , , , };
std::vector<int> vec4 = { , , , , , };
auto result5 = mismatch(vec3.begin(), vec3.end(), vec4.begin(), vec4.end());
std::cout << *result5.first << " " << *result5.second << std::endl; //输出:4 15 getchar();
return ;
}
}
equal :如果两个序列在指定范围内的元素都相等,则 equal 返回 true .重载版本使用输入的操作符代替了默认的等于操作符.
equal是两个集合对应位置元素的比，includes是集合和子集包含关系
参数:First1
:Last1
:First2
返回:true 标识容器元素相等,false容器元素不相等
template<class InputIterator1, class InputIterator2>
bool equal(InputIterator1 First1, InputIterator1 Last1,InputIterator2 First2);
参数:First1
:Last1
:First2
:Comp 比较条件
返回:true 标识容器元素相等,false容器元素不相等
template<class InputIterator1, class InputIterator2, class BinaryPredicate>
bool equal(InputIterator1 First1,InputIterator1 Last1,InputIterator2 First2,BinaryPredicate Comp);
参数:First1
:Last1
:First2
:Last2
返回:true 标识容器元素相等,false容器元素不相等
template<class InputIterator1, class InputIterator2>
bool equal(InputIterator1 First1, InputIterator1 Last1,InputIterator2 First2,InputIterator2 Last2);
参数:First1
:Last1
:First2
:Last2
:Comp 比较条件比如：判断两个容器中元素绝对值相等
返回:true 标识容器元素相等,false容器元素不相等
template<class InputIterator1, class InputIterator2, class BinaryPredicate>
bool equal(InputIterator1 First1,InputIterator1 Last1,InputIterator2 First2,InputIterator2 Last2,BinaryPredicate Comp);
#include "stdafx.h"
#include <stdio.h>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <iterator>
#include <ostream>
#include <numeric> int main()
{
{
std::vector<int> vec1 = { , , , , , };
std::vector<int> vec2 = { , };
auto result1 = equal(vec1.begin(), vec1.begin(), vec2.begin(), vec2.end());
std::cout << result1 << std::endl; //输出false 是一个元素对应一个元素的比，includes是集合和子集包含关系 auto result2 = equal(vec1.begin() + , vec1.begin() + , vec2.begin(), vec2.end());
std::cout << result2 << std::endl; //输出true getchar();
return ;
}
}
includes :判断 [first1, last1) 的一个元素是否被包含在另外一个序列中.使用底层元素的 <= 操作符,重载版本使用用户输入的函数.
参数:first1
:last1
:first2
:last2
返回:bool
template <class inputItr1, class inputItr2>
bool includes(inputItr1 first1, inputItr1 last1, inputItr2 first2, inputItr2 last2);
参数:first1
:last1
:first2
:last2
:op
返回:bool
template <class inputItr1, class inputItr2, class binaryPredicate>
bool includes(inputItr1 first1, inputItr1 last1, inputItr2 first2, inputItr2 last2, binaryPredicate op);
#include "stdafx.h"
#include <random>
#include <ctime>
#include <string>
#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional> int main()
{
{
std::vector<int> vec1 = { , , , , };
std::vector<int> vec2 = { , }; bool result1 = includes(vec1.begin(), vec1.end(), vec2.begin(), vec2.end());
if (result1)
{
std::cout << "includes" << std::endl;
} else {
std::cout << "not includes" << std::endl;
} getchar();
return ;
}
}
lexicographical_compare :比较两个序列.重载版本使用了用户自定义的比较操作.
如果[first1, last1)按字典序列小于[first2, last2)，返回true，否则返回false,使用opeartor<或者是comp进行比较,可以使用opeartor<进行比较的对象都可以使用该函数
首先逐一比较集合中的元素，那个元素大，则那个集合大，集合中元素相同(个数，内容)，则比较集合长度，那个长度大则那个集合大
template <class InputIterator1, class InputIterator2>
bool lexicographical_compare (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
template <class InputIterator1, class InputIterator2, class Compare>
bool lexicographical_compare (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);
#include "stdafx.h"
#include <stdio.h>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <iterator>
#include <ostream>
#include <numeric> int main()
{
{
std::vector<int> vec1 = { , , , , };
std::vector<int> vec2 = { , , };
bool result1 = lexicographical_compare(vec1.begin(), vec1.end(), vec2.begin(), vec2.end());
if (result1)
{
std::cout << "vec1 < vec2" << std::endl;
} else {
std::cout << "vec1 > vec2" << std::endl;
} std::vector<int> vec3 = { , , , , };
std::vector<int> vec4 = { , , };
bool result2 = lexicographical_compare(vec3.begin(), vec3.end(), vec4.begin(), vec4.end());
if (result2)
{
std::cout << "vec3 < vec4" << std::endl;
}
else {
std::cout << "vec3 > vec4" << std::endl;
} std::vector<int> vec5 = { , , , , };
std::vector<int> vec6 = { , , , , , };
bool result3 = lexicographical_compare(vec5.begin(), vec5.end(), vec6.begin(), vec6.end());
if (result3)
{
std::cout << "vec5 < vec6" << std::endl;
}
else {
std::cout << "vec5 > vec6" << std::endl;
} getchar();
return ;
}
}
<八>条件判断算法(3个)
all_of:在指定范围中判断容器中是否所有元素满足条件
template <class InputIterator, class UnaryPredicate>
bool any_of (InputIterator first, InputIterator last, UnaryPredicate pred);
any_of:在指定范围中判断容器中是否有元素满足条件
template <class InputIterator, class UnaryPredicate>
bool any_of (InputIterator first, InputIterator last, UnaryPredicate pred);
none_of:在指定范围中判断容器中是否没有任何元素满足条件
template <class InputIterator, class UnaryPredicate>
bool any_of (InputIterator first, InputIterator last, UnaryPredicate pred);
#include "stdafx.h"
#include <random>
#include <ctime>
#include <string>
#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional> int main()
{
{
std::vector<int> vec1 = { , , , , }; bool all1 = all_of(vec1.begin(), vec1.end(), [](int x)->bool { return x % == ? true : false; });
std::cout << "ele is all " << all1 << std::endl; //输出:0 bool all2 = any_of(vec1.begin(), vec1.end(), [](int x)->bool { return x % == ? true : false; });
std::cout << "ele is any " << all2 << std::endl; //输出:1 bool all3 = none_of(vec1.begin(), vec1.end(), [](int x)->bool { return x % == ? true : false; });
std::cout << "ele is none " << all3 << std::endl; //输出:0 getchar();
return ;
}
}
<九>集合算法(4个)
以下是STL algorithm的几个函数，使用的条件是有序容器，所以 vector在被sort了之后是可以使用的，set也是可以使用的。
set_difference 这个是求得在第一个容器中有，第二个容器中没有的。set_intersection 求两个容器的交集， set_union 求两个容器的并集，set_symmetric_difference 求两个容器的差集。
set_difference :构造一个排过序的序列,其中的元素出现在第一个序列中,但是不包含在第二个序列中.重载版本使用自定义的比较操作.
set_intersection :构造一个排过序的序列,其中的元素在两个序列中都存在.重载版本使用自定义的比较操作.
set_symmetric_difference :构造一个排过序的序列,其中的元素在第一个序列中出现,但是不出现在第二个序列中.重载版本使用自定义的比较操作.
set_union :构造一个排过序的序列,它包含两个序列中的所有的不重复元素.重载版本使用自定义的比较操作.
#include "stdafx.h"
#include <stdio.h>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <iterator>
#include <ostream>
#include <numeric> int main()
{
{
std::vector<int> vec1 = { , , , , , };
std::vector<int> vec2 = { , , , , , };
std::vector<int> vec3(vec1.size() + vec2.size()); auto result1 = set_symmetric_difference(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), vec3.begin());
for_each(vec3.begin(), vec3.end(), [](int x)->void { std::cout << x << " "; }); //7 13 15 19 20 26 0 0 0 0 0 0
std::cout << std::endl; std::vector<int> vec33(vec1.size() + vec2.size());
auto result3 = set_difference(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), vec33.begin());
for_each(vec33.begin(), vec33.end(), [](int x)->void { std::cout << x << " "; });//7 13 26 0 0 0 0 0 0 0 0 0
std::cout << std::endl; std::vector<int> vec4(vec1.size() + vec2.size());
auto result4 = set_union(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), vec4.begin());
for_each(vec4.begin(), vec4.end(), [](int x)->void { std::cout << x << " "; }); //4 7 11 13 15 19 20 21 26 0 0 0
std::cout << std::endl; std::vector<int> vec5(vec1.size() + vec2.size());
auto result5 = set_intersection(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), vec5.begin());
for_each(vec5.begin(), vec5.end(), [](int x)->void { std::cout << x << " "; }); //4 11 21 0 0 0 0 0 0 0 0 0 getchar();
return ;
}
}
<十>堆算法(4个)
下面介绍STL中与堆相关的4个函数,建立堆make_heap()，在堆中添加数据push_heap()，在堆中删除数据pop_heap()和堆排序sort_heap()
make_heap :把范围内的元素生成一个堆.重载版本使用自定义的比较操作.
pop_heap :并不是真正的把最大元素从堆中弹出,而是重新排序堆.它把 first 和 last-1 交换,然后重新做成一个堆.可以使用容器的 back 来访问被“弹出“的元素或者使用 pop_back 来真正的删除.重载版本使用自定义的比较操作.
push_heap :假设 first 到 last-1 是一个有效的堆,要被加入堆的元素在位置 last-1 ,重新生成堆.在指向该函数前,必须先把元素插入容器后.重载版本使用指定的比较.
sort_heap :对范围内的序列重新排序,它假设该序列是个有序的堆.重载版本使用自定义的比较操作.
#include "stdafx.h"
#include <stdio.h>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <iterator>
#include <ostream>
#include <numeric> int main()
{
{
int ia[] = { ,,,,,,,, };
std::vector<int> ivec(ia, ia + ); //底层我们使用vector来实现，可以动态添加元素。 make_heap(ivec.begin(), ivec.end());
for (int i = ; i != ivec.size(); i++)std::cout << ivec[i] << " ";
std::cout << std::endl; ivec.push_back();
push_heap(ivec.begin(), ivec.end());//这里可以用make_heap替换。
for (int i = ; i != ivec.size(); i++)std::cout << ivec[i] << " ";
std::cout << std::endl; pop_heap(ivec.begin(), ivec.end());
std::cout << ivec.back() << std::endl;
ivec.pop_back();
for (int i = ; i != ivec.size(); i++)std::cout << ivec[i] << " ";
std::cout << std::endl; sort_heap(ivec.begin(), ivec.end());
for (int i = ; i != ivec.size(); i++)std::cout << ivec[i] << " ";
std::cout << std::endl; getchar();
return ;
}
}