STL_常用的算法

一、常用的查找算法

adjacent_find()

adjacent_find(iterator beg, iterator end, _callback);

在iterator對標識元素范圍內，查找一對相鄰重復元素，找到則返回指向這對元素的第一個(gè)元素的迭代器。

vector<int> vecInt;
vecInt.push_back(1);
vecInt.push_back(2);
    vecInt.push_back(2);
    vecInt.push_back(4);
    vecInt.push_back(5);
vecInt.push_back(5);
vector<int>::iterator it = adjacent_find(vecInt.begin(), vecInt.end()); 
    //*it = 2

binary_search（）

bool binary_search(iterator beg, iterator end, value);

在有序序列中查找value,找到則返回true。注意：在無(wú)序序列中，不可使用。

set<int> setInt;
setInt.insert(3);
    setInt.insert(1);
setInt.insert(7);
setInt.insert(5);
setInt.insert(9);
bool bFind = binary_search(setInt.begin(), setInt.end(), 5);//nFind=true

count()

count(iterator beg, iterator end, value);

利用等于操作符，把標志范圍內的元素與輸入值比較，返回相等的個(gè)數。

vector<int> vecInt;
vecInt.push_back(1);
vecInt.push_back(2);
vecInt.push_back(2);
vecInt.push_back(4);
vecInt.push_back(2);
vecInt.push_back(5);
int iCount = count(vecInt.begin(),vecInt.end(),2);  //iCount==3

?

count_if()

count_if(首迭代器，未迭代器，搜索值（要比較的值的結果）)(條件計數)

//假設vector<int> vecIntA，vecIntA包含1,3,5,7,9元素

//先定義比較函數
bool GreaterThree(int iNum){
     if(iNum>=3){
     return true;
     }
     else{
    return false;
     }
} 

int iCount = count_if(vecIntA.begin(), vecIntA.end(), GreaterThree);
//此時(shí)iCount == 4

find()

find(iterator beg, iterator end, value)

find: 利用底層元素的等于操作符，對指定范圍內的元素與輸入值進(jìn)行比較。當匹配時(shí)，結束搜索，返回該元素的迭代器。

vector<int> vecInt;
vecInt.push_back(1);
vecInt.push_back(3);
vecInt.push_back(5);
vecInt.push_back(7);
vecInt.push_back(9);

vector<int>::iterator it = find(vecInt.begin(), vecInt.end(), 5);        //*it == 5

find_if()

find_if(iterator beg, iterator end, _callback);（條件查找）

find_if: 使用輸入的函數代替等于操作符執行find。返回被找到的元素的迭代器。

//假設vector<int> vecIntA，vecIntA包含1,3,5,3,9元素 
vector<int>::it = find_if(vecInt.begin(),vecInt.end(),GreaterThree);
//此時(shí) *it==3, *(it+1)==5, *(it+2)==3, *(it+3)==9 

二、常用的排序算法

merge()

以下是排序和通用算法：提供元素排序策略

merge: 合并兩個(gè)有序序列，存放到另一個(gè)序列。

//例如：vecIntA,vecIntB,vecIntC是用vector\<int>聲明的容器，vecIntA已包含1,3,5,7,9元素，vecIntB已包含2,4,6,8元素
vecIntC.resize(9); //擴大容量
merge(vecIntA.begin(),vecIntA.end(),vecIntB.begin(),vecIntB.end(),vecIntC.begin());
//此時(shí)vecIntC就存放了按順序的1,2,3,4,5,6,7,8,9九個(gè)元素

sort()

sort: 以默認升序的方式重新排列指定范圍內的元素。若要改排序規則，可以輸入比較函數。

//學(xué)生類(lèi)
Class CStudent:
{
public:
    CStudent(int iID, string strName)
    {
m_iID=iID; 
m_strName=strName; 
}
public:      
    int m_iID;
    string m_strName;
}

//學(xué)號比較函數
bool Compare(const CStudent &stuA,const CStudent &stuB)
{
return (stuA.m_iID<strB.m_iID);
}
void main()
{
    vector<CStudent> vecStu;
    vecStu.push_back(CStudent(2,"老二"));
vecStu.push_back(CStudent(1,"老大"));
vecStu.push_back(CStudent(3,"老三"));
vecStu.push_back(CStudent(4,"老四"));
sort(vecStu.begin(),vecStu.end(),Compare);
// 此時(shí)，vecStu容器包含了按順序的"老大對象","老二對象","老三對象","老四對象"
}

random_shuffle()

random_shuffle: 對指定范圍內的元素隨機調整次序。

srand(time(0));             //設置隨機種子
vector<int> vecInt;
vecInt.push_back(1);
vecInt.push_back(3);
vecInt.push_back(5);
vecInt.push_back(7);
vecInt.push_back(9);
string str("itcastitcast ");
random_shuffle(vecInt.begin(), vecInt.end());  //隨機排序，結果比如：9,7,1,5,3
random_shuffle(str.begin(), str.end());        //隨機排序，結果比如：" itstcasticat "

reverse()

reverse：反轉指定范圍的元素

vector<int> vecInt;
vecInt.push_back(1);
vecInt.push_back(3);
vecInt.push_back(5);
vecInt.push_back(7);
vecInt.push_back(9);
reverse(vecInt.begin(), vecInt.end());       //{9,7,5,3,1}

三、常用的拷貝和替換算法

copy()

copy算法 將容器內指定范圍的元素拷貝到另一容器中

vector<int> vecIntA;
vecIntA.push_back(1);
vecIntA.push_back(3);
vecIntA.push_back(5);
vecIntA.push_back(7);
vecIntA.push_back(9);
vector<int> vecIntB;
vecIntB.resize(5);           //擴大空間
copy(vecIntA.begin(), vecIntA.end(), vecIntB.begin());  //vecIntB: {1,3,5,7,9}

replace()

replace(beg,end,oldValue,newValue): 將指定范圍內的所有等于oldValue的元素替換成newValue。

vector<int> vecIntA;
vecIntA.push_back(1);
vecIntA.push_back(3);
vecIntA.push_back(5);
vecIntA.push_back(3);
vecIntA.push_back(9);
replace(vecIntA.begin(), vecIntA.end(), 3, 8);     //{1,8,5,8,9}

replace_if()

/*
replace_if算法 將容器內指定范圍滿(mǎn)足條件的元素替換為新元素
@param beg 容器開(kāi)始迭代器
@param end 容器結束迭代器
@param callback函數回調或者謂詞(返回Bool類(lèi)型的函數對象)
@param oldvalue 新元素
*/
replace_if(iterator beg, iterator end, _callback, newvalue)

replace_if : 將指定范圍內所有操作結果為true的元素用新值替換。

//把大于等于3的元素替換成8
vector<int> vecIntA;
vecIntA.push_back(1);
vecIntA.push_back(3);
vecIntA.push_back(5);
vecIntA.push_back(3);
vecIntA.push_back(9);
replace_if(vecIntA.begin(), vecIntA.end(), GreaterThree, 8);     // GreaterThree的定義在上面。

swap()

swap: 交換兩個(gè)容器的元素

vector<int> vecIntA;
vecIntA.push_back(1);
vecIntA.push_back(3);
vecIntA.push_back(5);
vector<int> vecIntB;
vecIntB.push_back(2);
vecIntB.push_back(4);
swap(vecIntA, vecIntB); //交換

四、常用的算術(shù)和生成算法

accumulate()

accumulate: 對指定范圍內的元素求和，然后結果再加上一個(gè)由val指定的初始值。

include<numeric>

vector<int> vecIntA;
vecIntA.push_back(1);
vecIntA.push_back(3);
vecIntA.push_back(5);
vecIntA.push_back(7);
vecIntA.push_back(9);
int iSum = accumulate(vecIntA.begin(), vecIntA.end(), 100);     //iSum==125

fill()

fill: 將輸入值賦給標志范圍內的所有元素。

vector<int> vecIntA;
vecIntA.push_back(1);
vecIntA.push_back(3);
vecIntA.push_back(5);
vecIntA.push_back(7);
vecIntA.push_back(9);
fill(vecIntA.begin(), vecIntA.end(), 8);       //8, 8, 8, 8, 8

五、常用的集合算法

set_union(),set_intersection(),set_difference()

set_union: 構造一個(gè)有序序列，包含兩個(gè)有序序列的并集。

set_intersection: 構造一個(gè)有序序列，包含兩個(gè)有序序列的交集。

set_difference: 構造一個(gè)有序序列，該序列保留第一個(gè)有序序列中存在而第二個(gè)有序序列中不存在的元素。

vector<int> vecIntA;
vecIntA.push_back(1);
vecIntA.push_back(3);
vecIntA.push_back(5);
vecIntA.push_back(7);
vecIntA.push_back(9);
 
vector<int> vecIntB;
vecIntB.push_back(1);
vecIntB.push_back(3);
vecIntB.push_back(5);
vecIntB.push_back(6);
vecIntB.push_back(8);

vector<int> vecIntC;
vecIntC.resize(10);

//并集
set_union(vecIntA.begin(), vecIntA.end(), vecIntB.begin(), vecIntB.end(), vecIntC.begin());       
//vecIntC : {1,3,5,6,7,8,9,0,0,0}

//交集
fill(vecIntC.begin(),vecIntC.end(),0);
set_intersection(vecIntA.begin(), vecIntA.end(), vecIntB.begin(), vecIntB.end(), vecIntC.begin());   
//vecIntC: {1,3,5,0,0,0,0,0,0,0}

//差集
fill(vecIntC.begin(),vecIntC.end(),0);
set_difference(vecIntA.begin(), vecIntA.end(), vecIntB.begin(), vecIntB.end(), vecIntC.begin());     
//vecIntC: {7,9,0,0,0,0,0,0,0,0}

六、常用的遍歷算法

for_each()

/*
    遍歷算法 遍歷容器元素
@param beg 開(kāi)始迭代器
@param end 結束迭代器
@param _callback  函數回調或者函數對象
@return 函數對象
*/
for_each(iterator beg, iterator end, _callback);

for_each: 用指定函數依次對指定范圍內所有元素進(jìn)行迭代訪(fǎng)問(wèn)。該函數不得修改序列中的元素。

void show(const int &iItem){
    cout << iItem;
}

main()
{
    int iArray[] = {0,1,2,3,4};
    vector<int> vecInt(iArray,iArray+sizeof(iArray)/sizeof(iArray[0]));
for_each(vecInt.begin(), vecInt.end(), show);
//結果打印出0 1 2 3 4
} 

transform()

/*
transform算法 將指定容器區間元素搬運到另一容器中
注意 : transform 不會(huì )給目標容器分配內存，所以需要我們提前分配好內存
@param beg1 源容器開(kāi)始迭代器
@param end1 源容器結束迭代器
@param beg2 目標容器開(kāi)始迭代器
@param _cakkback 回調函數或者函數對象
@return 返回目標容器迭代器
*/
transform(iterator beg1, iterator end1, iterator beg2, _callbakc)

transform: 與for_each類(lèi)似，遍歷所有元素，但可對容器的元素進(jìn)行修改

int increase (int i){ 
    return i+1;  
} 
main()
{
vector<int> vecIntA;
    vecIntA.push_back(1)；
    vecIntA.push_back(3);
vecIntA.push_back(5);
    vecIntA.push_back(7);
    vecIntA.push_back(9);

    transform(vecIntA.begin(),vecIntA.end(),vecIntA.begin(),increase);   
    //vecIntA : {2,4,6,8,10}
}