算法主要由頭文件<algorithm> <function> <numeric>組成
這里只是將這三個(gè)頭文件里面的常用算法，不是算法結(jié)構(gòu)
- <algorithm>是所有STL頭文件中最大的一個(gè)伴网，其中常用的功能設(shè)計(jì)到比較蓬推、交換、查找澡腾、遍歷沸伏、賦值糕珊、修改、反轉(zhuǎn)毅糟、排序红选、合并等
- <numeric>體積很小，只包括在幾個(gè)序列容器上進(jìn)行的簡(jiǎn)單運(yùn)算的模板函數(shù)
- <functional>定義了一些模板類留特，用以聲明函數(shù)對(duì)象
STL算法分為：質(zhì)變函數(shù)和非質(zhì)變函數(shù)
所有的STL算法都作用在由迭代器(first,end)所標(biāo)示出來的區(qū)間上.
質(zhì)變算法纠脾，是指運(yùn)算過程中會(huì)改變區(qū)間內(nèi)的(迭代器所指)的元素內(nèi)容。比如蜕青，拷貝(copy)苟蹈、互換(swap)、替代(replace)右核、填寫(fill)慧脱、刪除(remove)、排序(sort)等算法都屬于此類.
非質(zhì)變算法贺喝，是指在運(yùn)算過程中不會(huì)更改區(qū)間內(nèi)(迭代器所指)的元素內(nèi)容菱鸥，比如查找(find)、計(jì)數(shù)(count)躏鱼、遍歷(for_each)氮采、尋找極值等(max,min)，都屬于此類染苛。但是如果你在for_each遍歷每個(gè)元素的時(shí)候試圖應(yīng)用一個(gè)會(huì)改變?cè)貎?nèi)容的仿函數(shù)鹊漠，那么元素當(dāng)然也會(huì)改變
1.常用遍歷算法
#include <iostream>
#include <vector>
#include <algorithm> //for_each
#include <functional>
#include <numeric>
using namespace std;
//for_each算法
class print{
public:
print():count(0){}
void operator()(int v){
count++;
cout<<" "<<v;
}
int count;
}
void test01(){
vector<int> v;
for(int i = 0 ; i < 10;i++){
v.push_back(i);
}
print p1;
//for_each(v.begin(),v.end(),print());
print p2 = for_each(v.begin(),v.end(),p1);
cout<<endl;
cout<<"count:"<<p1.count<<endl;//0
cout<<"count:"<<p2.count<<endl;//10
}
//transform算法
class myplus100{
public:
int operator()(int v){
return v + 100;
}
};
class myminute{
public:
int operator()(int v1,int v2){
return v1 - v2;
}
};
void test02(){
vector<int> v1,v2;
for(int i = 0 ; i < 10;i++){
v1.push_back(i);
}
v2.resize(v1.size());
//第一種情況，一個(gè)容器中的元素經(jīng)過運(yùn)算 把結(jié)果放進(jìn)目標(biāo)容器中 v2
transform(v1.begin(),v1.end(),v2.begin(),myplus100());//把v1的所有值對(duì)位加100放到v2中
print p1;
for_each(v2.begin(),v2.end(),p1);
cout<<endl;
//-------------------------------------------------------------
//第二種方式
vector<int> v1,v2,v3;
for(int i = 0;i<10;i++){
v1.push_back(i);
v2.push_back(i+1);
}
v3.resize(v1.size());
transform(v1.begin(),v1.end(),v2.begin(),v3.begin(),myminute());
}
int main(){
//test01();
test02();
return 0;
}
2.常用查找算法
iterator find(iterator beg,iterator end,value);
/*
find 算法 查找元素
@param beg 容器開始迭代器
@param end 容器結(jié)束迭代器
@param value 查找的元素
@return 返回元素的位置
*/
iterator adjacent_find(iterator beg,iterator end,_callback);
/*
adjacent_find 算法 查找相鄰重復(fù)元素
@param beg 容器開始迭代器
@param end 容器結(jié)束迭代器
@param _callback 回調(diào)函數(shù)或者謂詞(返回Bool類型的函數(shù)對(duì)象)
@return 返回相鄰元素的第一個(gè)位置的迭代器
*/
bool binary_find(iterator beg,iterator end,TYPE & value);
/*
binary_find 算法 二分查找法
注意： 在無(wú)序序列中不可用
@param beg 容器開始迭代器
@param end 容器結(jié)束迭代器
@param value 查找的元素
@return bool 查找返回true 否則false
*/
iterator find_if(iterator beg,iterator end,_callback);
/*
find_if 算法 條件查找
@param beg 容器開始迭代器
@param end 容器結(jié)束迭代器
@param _callback 回調(diào)函數(shù)或者謂詞(返回Bool類型的函數(shù)對(duì)象)
@return iterator 返回迭代器
*/
int count(iterator beg,iterator end,TYPE & value)
/*
count 算法 統(tǒng)計(jì)元素出現(xiàn)次數(shù)
@param beg 容器開始迭代器
@param end 容器結(jié)束迭代器
@param value 要統(tǒng)計(jì)的值
@return int 返回元素個(gè)數(shù)
*/
int count_if(iterator beg,iterator end,_callback);
/*
count_if 算法 統(tǒng)計(jì)指定元素的個(gè)數(shù)
@param beg 容器開始迭代器
@param end 容器結(jié)束迭代器
@param _callback 回調(diào)函數(shù)或者謂詞(返回Bool類型的函數(shù)對(duì)象)
@return bool 查找返回true 否則false
*/
//-----------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <numeric>
using namespace std;
//find算法
void test01(){
vector<int> v;
v.push_back(8);
v.push_back(2);
v.push_back(5);
v.push_back(6);
/*
template<class _InIt,
class _Ty> inline
_InIt find(_InIt _First, _InIt _Last, const _Ty& _Val)
{ // find first matching _Val
_DEBUG_RANGE(_First, _Last);
return (_Rechecked(_First,
_Find(_Unchecked(_First), _Unchecked(_Last), _Val)));
}
*/
vector<int>::itertaor pos = find(v.begin(),v.end(),5);
if (pos == v.end())
{
cout<<"沒有找到"<<endl;
}
else{
cout<<"找到了:"<<*pos<<endl;
}
}
//查找對(duì)象
class Student{
public:
Student(int id,int age):id(id),age(age){}
int id;
int age;
bool operator==(const Student &s){
if (this->id = s.id && this->age == s.age)return true;
else return false;
}
};
void test02(){
vector<Student> v;
Student s1(1,2),s2(3,4),s3(5,6);
v.push_back(s1);
v.push_back(s2);
v.push_back(s3);
vector<Student>::iterator pos = find(v.begin(),v.end(),s1);
if (pos == v.end())
{
cout<<"沒有找到"<<endl;
}
else{
cout<<"找到了:"<<pos->id<<" "<<pos->age<<endl;
}
}
/*
找對(duì)象必然報(bào)錯(cuò)茶行，因?yàn)樵谡业倪^程中
看原代碼躯概，兩個(gè)對(duì)象的比較不是只是單純地根據(jù) == 號(hào)進(jìn)行判斷，編譯器為了防止這種不嚴(yán)謹(jǐn)?shù)膶懛ㄅ鲜Γ苯訄?bào)錯(cuò)
所以 我們需要重載Student的 == 號(hào)運(yùn)算符
*/
//find_if函數(shù)
class mycompare03{
public:
bool operator()(int v){
if (v > 6)
{
return true;
}else{
return false;
}
}
};
void test03(){
vector<int> v;
v.push_back(8);
v.push_back(2);
v.push_back(5);
v.push_back(6);
/*
template<class _InIt,
class _Pr> inline
_InIt find_if(_InIt _First, _InIt _Last, _Pr _Pred)
{ // find first satisfying _Pred
_DEBUG_RANGE(_First, _Last);
_DEBUG_POINTER(_Pred);
return (_Rechecked(_First,
_Find_if(_Unchecked(_First), _Unchecked(_Last), _Pred)));
}
template<class _InIt,
class _Pr> inline
_InIt _Find_if(_InIt _First, _InIt _Last, _Pr _Pred)
{ // find first satisfying _Pred
for (; _First != _Last; ++_First)
if (_Pred(*_First))
break;
return (_First);
}
*/
vector<int>::iterator pos = find_if(v.begin(),v.end(),mycompare03());
if (pos == v.end())
{
cout<<"沒有找到"<<endl;
}
else
{
cout<<"找到了:"<<*pos<<endl;
}
}
//adjacent_find 查找相鄰重復(fù)元素 并返回第一個(gè)重復(fù)的元素出現(xiàn)的位置
void test04(){
vector<int> v;
v.push_back(8);
v.push_back(2);
v.push_back(2);
v.push_back(5);
v.push_back(6);
/*
template<class _FwdIt> inline
_FwdIt adjacent_find(_FwdIt _First, _FwdIt _Last)
{ // find first matching successor
return (_STD adjacent_find(_First, _Last, equal_to<>()));
}
*/
vector<int>::iterator pos = adjacent_find(v.begin(),v.end());
if (pos == v.end())
{
cout<<"沒有找到"<<endl;
}
else
{
cout<<"找到了:"<<*pos<<endl;
}
}
//binary_search 二分查找法 需要容器內(nèi)元素有序
void test05(){
vector<int> v;
v.push_back(8);
v.push_back(2);
v.push_back(2);
v.push_back(5);
v.push_back(6);
greater<int> mygreater;
sort(v.begin(),v.end(),mygreater);
//sort(v.begin(),v.end());
/*
template<class _FwdIt,
class _Ty> inline
bool binary_search(_FwdIt _First, _FwdIt _Last, const _Ty& _Val)
{ // test if _Val equivalent to some element, using operator<
return (_STD binary_search(_First, _Last, _Val, less<>()));
}
*/
bool flag = binary_search(v.begin(),v.end(),5,mygreater);
//bool flag = binary_search(v.begin(),v.end(),5);
//默認(rèn)是從小到大二分查找娶靡，如果你排序過程中變成了從大到小，這里就必須申明
if (flag)
{
cout<<"找到了看锉！"<<endl;
}
else
{
cout<<"沒有查找到"<<endl;
}
}
//count count_if
class mycompare06{
public:
bool operator()(int v){
return v > 2;
}
}
void test06(){
vector<int> v;
v.push_back(8);
v.push_back(2);
v.push_back(2);
v.push_back(5);
v.push_back(6);
//count 算法
int n = count(v.begin(),v.end(),2);
cout<<"n:"<<n<<endl;
//count_if
/*
template<class _InIt,
class _Pr> inline
typename iterator_traits<_InIt>::difference_type
count_if(_InIt _First, _InIt _Last, _Pr _Pred)
{ // count elements satisfying _Pred
_DEBUG_RANGE(_First, _Last);
_DEBUG_POINTER(_Pred);
return (_Count_if(_Unchecked(_First), _Unchecked(_Last), _Pred));
}
*/
n = count_if(v.begin(),v.end(),mycompare06());
cout<<"n:"<<n<<endl;
}
int main(){
//test01();
//test02();
//test03();
//test04();
//test05();
test06();
return 0;
}
3.常用排序算法
merge(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator dest);
/*
merge 算法 容器元素合并姿锭，并存儲(chǔ)到另一容器中
兩個(gè)容器內(nèi)元素必須有序！
而且必須都從大到小 或 一起從小到大伯铣！不然就報(bào)錯(cuò)了
@param beg1 容器1開始迭代器
@param end1 容器1結(jié)束迭代器
@param beg2 容器2開始迭代器
@param end2 容器2結(jié)束迭代器
@param dest 目標(biāo)容器開始迭代器
@
*/
sort(iterator beg,iterator end,_callback);
/*
sort 算法 容器元素排序
注意：兩個(gè)容器必須是有序的
list容器不支持隨機(jī)訪問艾凯，所以不能用sort
@param beg 容器開始迭代器
@param end 容器結(jié)束迭代器
@param _callback 回調(diào)函數(shù)或者謂詞（返回bool類型的函數(shù)對(duì)象)
@
*/
random_shuffle(iterator beg,iterator end);
/*
sort 算法 指定范圍內(nèi)的元素隨機(jī)調(diào)整次序
@param beg 容器開始迭代器
@param end 容器結(jié)束迭代器
*/
//-----------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <numeric>
using namespace std;
//merge算法
void print(int v){
cout<<v<<" ";
}
void test01(){
vector<int> v1,v2,v3;
v1.push_back(6);
v1.push_back(2);
v1.push_back(8);
v1.push_back(4);
v2.push_back(1);
v2.push_back(2);
v2.push_back(6);
v2.push_back(4);
/*
template<class _InIt1,
class _InIt2,
class _OutIt> inline
_OutIt merge(_InIt1 _First1, _InIt1 _Last1,
_InIt2 _First2, _InIt2 _Last2,
_OutIt _Dest)
{ // copy merging ranges, both using operator<
return (_STD merge(_First1, _Last1, _First2, _Last2, _Dest,
less<>()));
}
*/
sort(v1.begin(),v1.end(),greater<int>());//參數(shù)三可不寫 默認(rèn)less 從小到大
sort(v2.begin(),v2.end(),greater<int>());
v3.resize(v1.size() + v2.size());//v1 v2不排序 必然報(bào)錯(cuò)
merge(v1.begin(),v1.end(),v2.begin(),v2.end(),v3.begin(),greater<int>());//參數(shù)6可不寫 默認(rèn)less 從小到大
for_each(v3.begin(),v3.end(),print);
cout<<endl;
}
//sort 算法
void test02(){
vector<int> v;
v.push_back(6);
v.push_back(2);
v.push_back(8);
v.push_back(4);
sort(v.begin(),v.end(),greater<int>());//從大到小排序 默認(rèn)從小到大
}
//random_shuffle 洗牌 將容器中的元素 順序打亂
void test03(){
vector<int> v;
for (int i = 0; i < 10; ++i)
{
v.push_back(i);
}
for_each(v.begin(),v.end(),print);
cout<<endl;
random_shuffle(v.begin(),v.end());
for_each(v.begin(),v.end(),print);
cout<<endl;
}
//reverse 反轉(zhuǎn)容器中的元素
void test04(){
vector<int> v;
for (int i = 0; i < 10; ++i)
{
v.push_back(i);
}
for_each(v.begin(),v.end(),print);
cout<<endl;
reverse(v.begin(),v.end());
for_each(v.begin(),v.end(),print);
cout<<endl;
}
int main(){
//test01();
//test02();
//test03();
test04();
return 0;
}
4.常用的拷貝和替換算法
copy(iterator beg,iterator end,iterator dest);
/*
copy 算法 將容器內(nèi)指定范圍的元素拷貝到另一個(gè)容器中
@param beg 容器開始迭代器
@param end 容器結(jié)束迭代器
@param dest 目標(biāo)容器開始迭代器
@
*/
replace(iterator beg,iterator end,TYPE &oldvalue,TYPE &newvalue);
/*
replace 算法 將容器內(nèi)指定范圍的舊元素修改為新元素
@param beg 容器開始迭代器
@param end 容器結(jié)束迭代器
@param oldvalue 就元素
@param newvalue 新元素
@
*/
replace_if(iterator beg,iterator end,_callback,TYPE & newvalue);
/*
replace_if 算法 將容器內(nèi)指定范圍滿足條件的元素修改為新元素
@param beg 容器開始迭代器
@param end 容器結(jié)束迭代器
@param _callback 函數(shù)回調(diào)或者謂詞(返回Bool類型的函數(shù)對(duì)象)
@param newvalue 新元素
@
*/
swap(container c1,container c2);
/*
swap 算法 互換兩個(gè)容器的元素
@param c1 容器1
@param c2 容器2
@
*/
//-----------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <numeric>
using namespace std;
//copy算法
void print(int v){
cout<<v<<" ";
}
void test01(){
vector<int> v1,v2;
for (int i = 0; i < 10; ++i)
{
v1.push_back(i);
}
v2.reszie(v1.size());
copy(v1.begin(),v1.end(),v2.begin());
for_each(v2.begin(),v2.end(),print);
}
//replace replace_if算法
class mycompare02{
public:
bool operator()(int v){
return v>5;
}
}
void test02(){
vector<int> v;
for (int i = 0; i < 10; ++i)
{
v.push_back(i);
}
replace(v.begin(),v.end(),6,100);
for_each(v.begin(),v.end(),print);
cout<<endl;
//replace_if
replace_if(v.begin(),v.end(),mycompare02(),50);
for_each(v.begin(),v.end(),print);
cout<<endl;
//swap
vector<int> v2;
for (int i = 0; i < 10; ++i)
{
v2.push_back(i);
}
for_each(v1.begin(),v1.end(),print);
cout<<endl;
for_each(v2.begin(),v2.end(),print);
cout<<endl;
cout<<"-----------------------------"<<endl;
swap(v1,v2);
for_each(v1.begin(),v1.end(),print);
cout<<endl;
for_each(v2.begin(),v2.end(),print);
cout<<endl;
}
int main(){
//test01();
test02();
return 0;
}
