STL_常用的演算法

一、常用的查找演算法

adjacent_find()

adjacent_find(iterator beg, iterator end, _callback);

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

	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，注意：在無序序列中，不可使用，

	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);

利用等于運算子，把標志范圍內的元素與輸入值比較，回傳相等的個數，

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);
//此時iCount == 4

find()

find(iterator beg, iterator end, value)

find: 利用底層元素的等于運算子，對指定范圍內的元素與輸入值進行比較，當匹配時，結束搜索，回傳該元素的迭代器，

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);
//此時 *it==3, *(it+1)==5, *(it+2)==3, *(it+3)==9

二、常用的排序演算法

merge()

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

merge: 合并兩個有序序列，存放到另一個序列，

//例如：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());
//此時vecIntC就存放了按順序的1,2,3,4,5,6,7,8,9九個元素

sort()

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

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

//學號比較函式
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);
	// 此時，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演算法 將容器內指定范圍滿足條件的元素替換為新元素
	@param beg 容器開始迭代器
	@param end 容器結束迭代器
	@param callback函式回呼或者謂詞(回傳Bool型別的函式物件)
	@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: 交換兩個容器的元素

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); //交換

四、常用的算術和生成演算法

accumulate()

accumulate: 對指定范圍內的元素求和，然后結果再加上一個由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: 構造一個有序序列，包含兩個有序序列的并集，

set_intersection: 構造一個有序序列，包含兩個有序序列的交集，

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

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 開始迭代器
	@param end 結束迭代器
	@param _callback  函式回呼或者函式物件
	@return 函式物件
*/
for_each(iterator beg, iterator end, _callback);

for_each: 用指定函式依次對指定范圍內所有元素進行迭代訪問，該函式不得修改序列中的元素，

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 不會給目標容器分配記憶體，所以需要我們提前分配好記憶體
	@param beg1 源容器開始迭代器
	@param end1 源容器結束迭代器
	@param beg2 目標容器開始迭代器
	@param _cakkback 回呼函式或者函式物件
	@return 回傳目標容器迭代器
*/
transform(iterator beg1, iterator end1, iterator beg2, _callbakc)

transform: 與for_each類似，遍歷所有元素，但可對容器的元素進行修改

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}
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/253397.html

標籤：其他

上一篇：FastJson 處理json資料中物件相互參考,最后轉為json字串出現占位符("$ref"標識回圈參考)"的問題

下一篇：陣列及Arrays類