5.3 迭代器?
- 前置式遞增比后置式遞增效率更高,因為后者需要一個額外的臨時對象,因為他需要存儲一個迭代器原本的位置并將其進行返還,因此最好使用++pos,而不是pos++;
5.3.1 關聯式容器的運用實例
- 修改map默認的遞增的方式,將內部排序修改為 遞減方式
- ? ? std::map<int,int,std::greater<int>>map{};
- greater是一個預先定義的仿函數
- 關聯式容器使用自己的默認規則進行元素位置的存放,因此相較于序列式容器取消了push_back()和push_front()函數
- std::greater - C++中文 - API參考文檔
#include <list>
#include <iostream>
#include <set>
#include <map>int main(){std::map<int,int,std::greater<int>>map{};map.insert(std::make_pair(1,1));map.insert(std::make_pair(2,2));map.insert(std::make_pair(3,3));map.insert(std::make_pair(4,4));for (auto temp=map.begin();temp!=map.end();++temp) {std::cout << temp->first << " " << temp->second << std::endl;}
}
- multimap包含在map頭文件內部,允許key和value是1對多的關系
#include <list>
#include <iostream>
#include <set>
#include <map>int main(){std::multimap<int,int,std::greater<int>>map{};map.insert(std::make_pair(1,1));map.insert(std::make_pair(1,1));map.insert(std::make_pair(1,1));map.insert(std::make_pair(1,1));map.insert(std::make_pair(2,2));map.insert(std::make_pair(3,3));map.insert(std::make_pair(4,4));for (auto temp=map.begin();temp!=map.end();++temp) {std::cout << temp->first << " " << temp->second << std::endl;}
}
- 迭代器訪問 元素的時候,可以使用 迭代器->first? 或者? (*迭代器).first 使用*解除引用,再對元素進行訪問
- 類名 變量名;將創建一個對象將其存儲在棧上,使用 變量名.成員? 進行使用
- 類名 變量名 = new 類名();??將創建一個對象將其存儲在堆上,使用 變量名->成員? 進行使用
- map 鍵值/實值 所形成的群集中,如果所有的鍵值是唯一的,將其作為一個關聯式數組;這里想表達的意思是我們可以像使用數組一樣進行元素的訪問,數組通過數組下標訪問對應的數值,map可以通過指定key,訪問對應的value。通過map[key]訪問對應的數值
5.3.2 迭代器分類
- 雙向迭代器 Bidirectional iterator:雙向行進,采用遞增進行前進運算,使用遞減進行后退運算,list、set、multiset、map和undered_map 都使用這個迭代器
- 隨機存儲迭代器Random access iterator:在雙向迭代器的基礎上還具備了隨機訪問的特性,因此可以對迭代器增加或者減少一個偏移量,處理迭代器之間的距離,或者使用<和>之類的relational相對關系的操作符來比較兩個迭代器。vector、deque和string均采用此迭代器
- 盡量使用 != 這個的適配性更好,但是如果pos位于了end的后面,發生錯誤很難發現
for(pos = coll.begin();pos != coll.end();++pos){}operator !=for(pos = coll.begin();pos < coll.end();++pos){}//operator < Random access iterator
5.4 算法
- 算法不是容器類別的成員函數,而是搭配迭代器使用的全局函數,采用的是泛型函數編程的思維,數據和操作進行分離
5.4.2 處理多個區間
- copy將第一區間的數據拷貝到目標區域,第一區間的起點和第一區間的終點確定了第一區間的元素的數量,因此第二區間只需要提供一個起點即可。
- 但是copy函數使用的是覆寫操作,不是插入操作,因此需要第二區間具備足夠的內存空間,如下例子所示,會產生未定義的行為
#include <list>
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <vector>int main(){std::list<int>coll1;std::vector<int>coll2;for (int i = 1; i <= 9; ++i) {coll1.push_back(i);}std::copy(coll1.begin(),coll1.end(),coll2.begin());
}
- 對上述錯誤代碼的修改:1,確認目標區域具備足夠的內存;2,采用insert iterator
std::list<int>coll1;std::vector<int>coll2;for (int i = 1; i <= 9; ++i) {coll1.push_back(i);}coll2.resize(coll1.size());std::copy(coll1.begin(),coll1.end(),coll2.begin());
5.5 迭代器配接器
- Insert iterator 安插型迭代器
- Stream iterator 流迭代器
- reverse iterator 逆向迭代器
Insert iterator 安插型迭代器
- 采用安插方式而不是覆寫的方式運作,解決目標區域不足的問題? 3種方式
- Back inserters 安插在容器的最尾端:內部調用push_back() 采用追加的操作,只能適用于具備push_back()成員函數的容器中? 適用于vector list deque
- ? ? std::copy(coll1.begin(),coll1.end(),std::back_inserter(coll2));
- Front inserters 安插在容器最前端,內部調用的是push_front() ,這種操作會逆轉被插元素的次序,比如插入1 再次插入 2,輸出的時候2會在1 的前面打印輸出? 這個適用于 list 和 deque
- ? ? std::copy(coll1.begin(),coll1.end(),std::insert_iterator<>(coll2));
- General inserters一般性安插器: 將元素插入到初始化時接受的第二個參數指向的前方。內部調用的是insert函數,并按照新值和新的位置作為參數。適用于關聯式容器
?流迭代器
- stream iterator是一種用來讀取stream流的迭代器。提供了必要的抽象性,使得鍵盤的輸入像一個群集,使得程序員可以從中讀取內容,也可以把算法的輸出重新導向某個文件或者屏幕
- 代碼沒有跑通
#include <list>
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <vector>using namespace std;
int main(){std::vector<std::string>coll{};copy(std::istream_iterator<string>(cin),istream_iterator<string>(),back_inserter(coll));sort(coll.begin(),coll.end());unique_copy(coll.begin(),coll.end(),ostream_iterator<string>(cout,"\n"));
}
5.5.3 reverse iterators 逆向迭代器
- coll.rbegin()指向的是逆向遍歷的起點,也就是先前的end()-1 的位置?
5.6.1 移除元素
- ?remove移除元素,是使用刪除元素位置之后的元素對刪除位置上的元素進行替代,不會是將其所有的3全部刪除
- 但是群集末尾未被覆蓋的元素原封不動,但是從邏輯層面上講,他們已經不屬于這個群集了
#include <list>
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <vector>using namespace std;
int main(){std::list<int>coll{};for(int i=1;i<=6;i++){coll.push_back(i);coll.push_front(i);}std::cout << "pre: ";copy(coll.begin(),coll.end(),ostream_iterator<int>(cout," "));std::cout << std::endl;std::remove(coll.begin(),coll.end(),3);std::cout << "post: ";copy(coll.begin(),coll.end(),ostream_iterator<int>(cout," "));std::cout << std::endl;
}
- pre: 6 5 4 3 2 1 1 2 3 4 5 6
- post: 6 5 4 2 1 1 2 4 5 6 5 6?
- 實際上 算法會產生一個新的終點,需要更新新的終點的位置,獲得新的區間,也就是縮減元素之后的容器的大小,亦或是刪除元素的個數
?改進如下
- ? ? std::list<int>::iterator end = std::remove(coll.begin(),coll.end(),3);
- 這個end也就是經過刪除之后邏輯上新的終點
- 或者獲取徐亞刪除的元素的個數,利用distance函數,返回兩個迭代器之間的距離
#include <list>
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <vector>using namespace std;
int main(){std::list<int>coll{};for(int i=1;i<=6;i++){coll.push_back(i);coll.push_front(i);}std::cout << "pre: ";copy(coll.begin(),coll.end(),ostream_iterator<int>(cout," "));std::cout << std::endl;std::list<int>::iterator end = std::remove(coll.begin(),coll.end(),3);std::cout << "post: ";copy(coll.begin(),end,ostream_iterator<int>(cout," "));std::cout << std::endl;std::cout << "number of removed elements: "<< std::distance(end,coll.end()) << std::endl;coll.erase(end,coll.end());copy(coll.begin(),coll.end(),ostream_iterator<int>(cout," "));std::cout << std::endl;
}
5.6.2 更易型算法和關聯式容器
- 更易型算法是指 移除、重排、修改元素的算法,這些算法不適用于關聯型算法,因為這些操作會修改位置上的數值,破壞排序
- 因此,關聯式容器的所有迭代器都被聲明為指向常量
#include <list>
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <vector>using namespace std;
int main(){set<int>coll{};for (int i = 0; i <= 9; ++i) {coll.insert(i);}copy(coll.begin(),coll.end(),ostream_iterator<int>(cout," "));std::cout << std::endl;int num = coll.erase(3);cout << "number os removed elements:" << num << std::endl;copy(coll.begin(),coll.end(),ostream_iterator<int>(cout," "));
}
5.6.3 算法 VS 成員函數
- 如果容器提供了功能相似但是性能更佳的成員函數,優先使用成員函數
- 成員函數 對其進行了優化,相較于函數功能相似的算法
- 成員函數?remove(coll.begin(),coll.end(),4)
- 算法:? ? coll.remove(4);
#include <list>
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <vector>using namespace std;
int main(){list<int>coll{};for (int i = 1; i <= 6; ++i) {coll.push_front(i);coll.push_back(i);}coll.erase(remove(coll.begin(),coll.end(),3),coll.end());coll.remove(4);
}
5.8.1 以函數作為算法的參數
- 算法接收用戶定義的輔助性函數 ,在算法的內部被調用
- for_each函數對coll的begin到end區間內的每一個元素都調用print函數進行輸出
#include <list>
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <vector>using namespace std;void print(int elem){std::cout << elem << " ";
}
int main(){std::vector<int>coll{};for (int i = 1; i <= 9; ++i) {coll.push_back(i);}std::for_each(coll.begin(),coll.end(),print);
}
- 算法以🌲種態度來面對輔助函數,1,將其視為可有可無;2,視為必要;
- 利用他們指定搜尋的規則、排序的規則或者定義某種操作,從而將某個容器內 的元素轉換到另外一個容器
#include <list>
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <vector>using namespace std;void print(int elem){std::cout << elem << " ";
}int square(int value){return value*value;
}
int main(){std::set<int>coll{};std::vector<int>coll2{};for (int i = 1; i <= 9; ++i) {coll.insert(i);}std::transform(coll.begin(),coll.end(),std::back_inserter(coll2),square);std::for_each(coll2.begin(),coll2.end(),print);
}
5.8.2 判斷式
- 潘端師就是返還結果是布爾數值的函數,常用于指定排序準則和搜尋準則,可能有一個或者兩個操作數
- 判斷式 對于相同的輸入返還相同的輸出結果,且程序執行不可以改變內部狀態?
一元判斷式
?二元判斷式
?
5.9 仿函數
- 泛型編程強大威力和存粹抽象的一個例證。仿函數就是行為像函數,比如定義一個對象,他具備類似函數的一些特性,就可以當做函數來使用;比如使用小括號傳遞參數,如果指望定義的對象也可以實現 使用小括號傳遞參數,比如定義operator()???
#include <list>
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <vector>using namespace std;class X{
public:int operator()(int v1,int v2)const;
};
int X::operator()(int v1, int v2) const {std::cout << v1 << " "<< v2<< std::endl;
}
int main(){X fo;fo(4,5);fo.operator()(4,5);
}
class PrintInt{
public:void operator()(int elem)const{std::cout << elem << std::endl;}
};
int main(){std::vector<int>coll{};for (int i = 1; i <= 6; ++i) {coll.push_back(i);}std::for_each(coll.begin(),coll.end(),PrintInt());
}
?
void add10(int & elem){elem += 10;
}
int main(){std::vector<int>coll{};for (int i = 1; i <= 6; ++i) {coll.push_back(i);}for_each(coll.begin(),coll.end(),add10);std::for_each(coll.begin(),coll.end(),PrintInt());
}
- 如果需要數個不同的固定數值? 而且他們在編譯期 都已經確認,可以使用template?
- 使用模板傳參,需要在函數被調用之前將數值傳遞給函數?
- ?具體的代碼如下面所示,? ? for_each(coll.begin(),coll.end(),AddValue(10));這種方式,使用AddValue(10)生成一個AddValue的組件,并且賦予了初值為10,構造函數就會把10保存在成員theValue中,在for_each之內,針對coll的每一個元素調用 () ,實際上就是對傳入的那個AddValue對象 暫時調用 operator()操作,并以容器的元素作為參數
class AddValue{
private:int theValue;
public:AddValue(int v):theValue(v){};void operator()(int& elem)const{elem += theValue;}
};
class PrintInt{
public:void operator()(int elem)const{std::cout << elem << " ";}
};
int main(){std::vector<int>coll{};for (int i = 1; i <= 6; ++i) {coll.push_back(i);}for_each(coll.begin(),coll.end(),AddValue(10));std::for_each(coll.begin(),coll.end(),PrintInt());std::cout << std::endl;for_each(coll.begin(),coll.end(),AddValue(*coll.begin()));std::for_each(coll.begin(),coll.end(),PrintInt());
}
- ?? ? for_each(coll.begin(),coll.end(),AddValue(*coll.begin()+5));這種方式,傳入的參數
- 使用這個技術就可以實現先前所說的 一個函數,兩種狀態的問題,用兩個不同的仿函數實現
class AddValue{
private:int theValue;
public:AddValue(int v):theValue(v){};void operator()(int& elem)const{elem += theValue;}
};
class PrintInt{
public:void operator()(int elem)const{std::cout << elem << " ";}
};
int main(){std::vector<int>coll{};for (int i = 1; i <= 6; ++i) {coll.push_back(i);}AddValue addx(4);for_each(coll.begin(),coll.end(),addx);std::for_each(coll.begin(),coll.end(),PrintInt());std::cout << std::endl;AddValue addy(5);for_each(coll.begin(),coll.end(),addy);std::for_each(coll.begin(),coll.end(),PrintInt());
}
?5.9.2 預先定義的仿函數
- C++標準庫 包含了一些預定義的仿函數 涵蓋了部分的基礎運算
- 比如排序默認的排序是從小到大,也就是operator < 的缺省排序準則就是 less<>
- 默認的 std::set<int>coll? ->? set<int,less<int>>coll
- 反向排列?? set<int,greater<int>>coll
- negate<int>()? 將傳入的int數值設置為 負數
- transform()算法 將第一群集的所有元素處理之后轉移到第二群集,如果第二群集的起始地址是自身,就相當于對第一群集的元素進行操作覆蓋
- transform的另外一種形式,按照某種特定的運算,將兩個群集內的元素處理之后將其結果寫入到第三群集;如下所示,設定 第一群集、第二群集 將兩個群集的元素進行計算,將結果寫回到第三群集
?
class PrintInt{
public:void operator()(int elem)const{std::cout << elem << " ";}
};
int main(){std::set<int,std::greater<int>>coll1;std::deque<int>coll2;for (int i = 1; i <= 9; ++i) {coll1.insert(i);}std::for_each(coll1.begin(),coll1.end(),PrintInt());transform(coll1.begin(),coll1.end(), //sourceback_inserter(coll2), //destinationbind2nd(multiplies<int>(),10)); //operationstd::cout << std::endl;std::for_each(coll2.begin(),coll2.end(),PrintInt());//replace value equals to 70 with 42replace_if(coll2.begin(),coll2.end(), //rangebind2nd(equal_to<int>(),70), //replace criterion42); //new valuestd::cout << std::endl;std::for_each(coll2.begin(),coll2.end(),PrintInt());//remove all elements with values less than 50coll2.erase(remove_if(coll2.begin(),coll2.end(), //rangebind2nd(less<int>(),50)), //remove criterioncoll2.end());std::cout << std::endl;std::for_each(coll2.begin(),coll2.end(),PrintInt());
- ? ? transform(coll1.begin(),coll1.end(), //source
? ? ? ? ? ? ? back_inserter(coll2), //destination
? ? ? ? ? ? ? bind2nd(multiplies<int>(),10)); //operation - bind2nd 就是? 進行multiplies<int>()運算的時候,將源群集的元素作為第一參數,將10 作為第二參數
- 所有的仿函數通常都聲明為inline,一方面使用類似函數的表示法或者抽象性,一方面又可以獲得出色的效能
- 還有一些仿函數可以調用群集內的每個元素的成員函數?
?
?
?
?
- 智能指針:是一種對象,有著類似指針的接口,但是內部實現了一些額外的檢查和處理工作?
?
?
?
?