C++ Primer 第11章 泛型算法 学习总结
生活随笔
收集整理的這篇文章主要介紹了
C++ Primer 第11章 泛型算法 学习总结
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
文章目錄
- 11.2 算法
- 11.2.1 只讀算法
- **1.find函數**
- **2.accumulate函數**
- **3.find_first_of 函數**
- 11.2.2 寫容器元素算法
- 1.fill函數
- 2.fill_n函數
- 3.back_inserter插入迭代器
- 4.copy函數
- 5.算法的 _copy 版本
- 11.2.3 排序算法
- sort（起始，結束）；
- unique（起始，結束）--刪除相鄰重復元素，返回迭代器（無重復范圍的下一位）
- stable_sort（起始，結束）--穩定排序，相等情況下，保持原始順序
- sort（起始，結束，謂詞函數<寫函數名即可>）--按照謂詞函數規則排序
- 11.3 迭代器
- 11.3.1 插入迭代器
- a. back_inserter--使用push_back實現的插入迭代器
- b.front_inserter--使用push_front實現插入，若容器不支持push_front，不可用
- c.inserter（容器對象，插入起始位置迭代器）總是在該迭代器---前面---位置插入
- 11.3.2 iostream迭代器
- istream_iterator迭代器
- ostream_iterator迭代器
- 在類類型上使用istream_iterator
- 流迭代器限制
- a. 不能從 ostream_iterator 對象讀入，也不能寫到istream_iterator 對象中
- b. 一旦給 ostream_iterator 對象賦了一個值，寫入就提交了。賦值后，沒有辦法再改變這個值。此外，ostream_iterator 對象中每個不同的值都只能正好輸出一次
- c. ostream_iterator 沒有 -> 操作符
- 與算法一起使用流迭代器
- 11.3.3 反向迭代器
- 11.3.4 const迭代器
- 11.3.5 五種迭代器
- 11.4泛型算法的結構
- 11.4.1 算法的形參模式
- a. 帶有單個目標迭代器的算法
- b. 帶第二個輸入序列的算法
- 11.4.2 算法命名規范
- a. 區別帶有一個值或一個謂詞函數參數的算法版本
- b. 區別是否實現復制的算法版本
- 11.5容器特有的算法
標準容器定義的操作比較少，我們需要其他的一些函數來操作容器，比如查找，排序，這些算法不依賴容器類型。
11.2 算法
11.2.1 只讀算法
1.find函數
find（起始迭代器，終止迭代器，搜索值）
搜索范圍不包含終止迭代器位置，函數返回迭代器類型
find 找到了第一個出現的搜索值，并返回迭代器（指針）
注意：不加 using namespace std; 則需要寫 std::find
2.accumulate函數
需要包含頭文件，accumulate（起始迭代器，終止迭代器，初始value）；
返回范圍內的值和初始value的總和；也可以連接字符串；
3.find_first_of 函數
find_first_of（a.起始迭代器，a.終止迭代器，b.起始迭代器，b.終止迭代器）
返回值：迭代器（指向第一個a中的元素，該元素也在b中存在）
11.2.2 寫容器元素算法
1.fill函數
fill（起始迭代器，終止迭代器，填充值）
使得范圍內存在的元素進行寫入（填充值）
2.fill_n函數
fill_n（起始迭代器，計數器n，value）
需要保證要寫入的元素存在！！！不然，可能導致嚴重的錯誤
3.back_inserter插入迭代器
需要iterator頭文件
back_inserter（容器對象）在容器尾部添加元素，返回的是一個迭代器
4.copy函數
copy（a.起始迭代器，a.終止迭代器，b.迭代器）
#include<iostream> #include<algorithm> #include<vector> #include<list> using namespace std; int main() {vector<int> ivec;ivec.push_back(9);list<int> ilist;ilist.push_back(1);ilist.push_back(2);ilist.push_back(3);copy(ilist.begin(),ilist.end(),back_inserter(ivec));for(vector<int>::iterator it = ivec.begin();it != ivec.end();++it){cout << *it << " ";}cout << endl; } #include<iostream> #include<algorithm> #include<vector> #include<list> using namespace std; int main() {list<int> ilist;ilist.push_back(1);ilist.push_back(2);ilist.push_back(3);copy(ilist.begin(),ilist.end(),back_inserter(ilist));for(list<int>::iterator it = ilist.begin();it != ilist.end();++it){cout << *it << " ";}cout << endl; }以上代碼無結果，內存撐爆！
int main() {vector<int> ivec;ivec.push_back(9);copy(ivec.begin(),ivec.end(),back_inserter(ivec));for(vector<int>::iterator it = ivec.begin();it != ivec.end();++it){cout << *it << " ";}cout << endl; } int main() {vector<int> ivec;ivec.push_back(9);ivec.push_back(9);ivec.push_back(9);list<int> ilist;ilist.push_back(1);ilist.push_back(2);ilist.push_back(3);vector<int>::iterator it = ivec.begin();copy(ilist.begin(),ilist.end(),it+1);for(vector<int>::iterator it = ivec.begin();it != ivec.end();++it){cout << *it << " ";}cout << endl; }
copy函數沒有添加元素個數，只是改寫了元素。
5.算法的 _copy 版本
_copy版本不改變輸入元素，會創建新序列存儲處理的結果
list<int> ilist;ilist.push_back(1);ilist.push_back(2);ilist.push_back(2);ilist.push_back(3);replace(ilist.begin(),ilist.end(),2,6);for(list<int>::iterator it = ilist.begin();it != ilist.end();++it){cout << *it << " ";}cout << endl;
原輸入改變了
原輸入list沒有改變，把處理后的list追加到vector中了
11.2.3 排序算法
sort（起始，結束）；
unique（起始，結束）–刪除相鄰重復元素，返回迭代器（無重復范圍的下一位）
stable_sort（起始，結束）–穩定排序，相等情況下，保持原始順序
sort（起始，結束，謂詞函數<寫函數名即可>）–按照謂詞函數規則排序
編寫程序統計一個文檔中長度不小于 4 的單詞，并輸出輸入序列中不重復的單詞。
#include<iostream> #include<vector> #include<fstream> #include<algorithm> #include<string> using namespace std; bool isshorter(const string &s1, const string &s2) {return s1.size() < s2.size(); } bool gt4(const string &s) {return s.size() >= 4; } string make_end_s(size_t ctr, const string &word, const string &ending) {return (ctr == 1)?word:word+ending; //多個單詞，后綴加s } int main(int argc, char **argv) {if(argc < 2){cerr << "No input file!" << endl;return EXIT_FAILURE;}ifstream infile;infile.open(argv[1]);if(!infile){cerr << "can not open input file!" << endl;return EXIT_FAILURE;}vector<string> words;string word;while(infile >> word)words.push_back(word);sort(words.begin(),words.end());//sort按照字典順序排序words.erase(unique(words.begin(),words.end()),words.end());//unique指向無重復的末端的下一位，erase刪除重復的stable_sort(words.begin(),words.end(),isshorter);//按照isshorter規則，長度從小到大排序，stable排序，長度一樣的話不改變之前的字典序vector<string>::size_type wc = count_if(words.begin(),words.end(),gt4);//count_if if判斷每個元素是否滿足gt4函數，true則wc+1cout << wc << " " << make_end_s(wc,"word","s")<< " 4 characters or longer!" << endl;cout << "unique words:" << endl;for(vector<string>::iterator iter = words.begin();iter != words.end();++iter)cout << *iter << endl;cout << endl;return 0; }
調試過程如下：
11.3 迭代器
11.3.1 插入迭代器
a. back_inserter–使用push_back實現的插入迭代器
b.front_inserter–使用push_front實現插入，若容器不支持push_front，不可用
在vector或其他沒有push_front運算的容器上，不可以使用，將產生錯誤
c.inserter（容器對象，插入起始位置迭代器）總是在該迭代器—前面—位置插入
#include<list> #include<vector> #include<iostream> #include<algorithm> using namespace std; int main() {list<int> ilist;ilist.push_back(1);ilist.push_back(2);vector<int> ivec;ivec.push_back(6);ivec.push_back(7);list<int>::iterator it = find(ilist.begin(),ilist.end(),2);replace_copy(ivec.begin(),ivec.end(),inserter(ilist,it),6,5);for(it = ilist.begin(); it != ilist.end(); ++it){cout << *it << " ";}cout << endl;return 0; }
!!!在容器begin首位置inserter，不能跟front_inserter一樣產生反序，看下面例子
11.3.2 iostream迭代器
| istream_iterator in; | istream_iterator 對象的超出末端迭代器 |
| ostream_iterator in(strm); | 創建將 T 類型的對象寫到輸出流 strm 的ostream_iterator 對象 |
| ostream_iterator in(strm, delim); | 創建將 T 類型的對象寫到輸出流 strm 的ostream_iterator 對象，在寫入過程中使用 delim作為元素的分隔符。delim 是以空字符結束的字符數組 |
istream_iterator迭代器
#include<vector> #include<iterator> #include<iostream> #include<fstream> #include<exception> using namespace std; int main(int argc, char** argv) {vector<int> ivec;ifstream openfile;openfile.open(argv[1]);if(!openfile)throw runtime_error("open file failure!");istream_iterator<int> int_iter(openfile);istream_iterator<int> end;while(int_iter != end){ivec.push_back(*int_iter++);openfile.clear();}for(vector<int>::iterator it = ivec.begin(); it != ivec.end(); ++it){cout << *it << " ";}cout << endl;return 0; }
以下代碼與上面效果相同，用一對迭代器指向的內容初始化vector
ostream_iterator迭代器
int main(int argc, char** argv) {ifstream openfile;openfile.open(argv[1]);if(!openfile)throw runtime_error("open file failure!");ostream_iterator<string> out_iter(cout,"\n");istream_iterator<string> int_iter(openfile),end;while(int_iter != end){*out_iter++ = *int_iter++;}return 0; }在類類型上使用istream_iterator
提供了>>操作的任何類類型都可以使用istream_iterator
#include<vector> #include<iterator> #include<iostream> #include<fstream> #include<exception> #include<Sales_item.h> using namespace std; int main(int argc, char** argv) {ifstream openfile;openfile.open(argv[1]);if(!openfile)throw runtime_error("open file failure!");istream_iterator<Sales_item> item_iter(openfile),end;Sales_item sum;sum = *item_iter++;while(item_iter != end){if(item_iter->same_isbn(sum))sum += *item_iter;else{cout << sum << endl;sum = *item_iter;}++item_iter;}cout << sum << endl;return 0; }流迭代器限制
a. 不能從 ostream_iterator 對象讀入，也不能寫到istream_iterator 對象中
b. 一旦給 ostream_iterator 對象賦了一個值，寫入就提交了。賦值后，沒有辦法再改變這個值。此外，ostream_iterator 對象中每個不同的值都只能正好輸出一次
c. ostream_iterator 沒有 -> 操作符
與算法一起使用流迭代器
#include<vector> #include<iterator> #include<algorithm> #include<iostream> using namespace std; int main() {istream_iterator<int> cin_iter(cin),end;vector<int> ivec(cin_iter,end);sort(ivec.begin(),ivec.end());ostream_iterator<int> print(cout," ");unique_copy(ivec.begin(),ivec.end(),print);return 0; }11.3.3 反向迭代器
反向遍歷容器的迭代器
如果是字符串呢？反向迭代器有什么問題？
11.3.4 const迭代器
find_first_of(it, roster1.end(),roster2.begin(), roster2.end())如果該容器是 const 對象，則返回的迭代器是 const_iterator 類型；否則，就是普通的 iterator 類型。
roster1 不是 const 對象，因而 end 返回的只是一個普通的迭代器。
如果將 it 定義為 const_iterator，那么 find_first_of 的調用將無法編譯。
because 用來指定范圍的兩個迭代器的類型不相同。
it 是 const_iterator 類型的對象，而 rotser1.end() 返回的則是一個 iterator 對象。
11.3.5 五種迭代器
| Output iterator（輸出迭代器） | 寫，不能讀；只支持自增運算 |
| Forward iterator（前向迭代器） | 讀和寫；只支持自增運算 |
| Bidirectional iterator（雙向迭代器） | 讀和寫；支持自增和自減運算 |
| Random access iterator（隨機訪問迭代器） | 讀和寫；支持完整的迭代器算術運算 |
11.4泛型算法的結構
11.4.1 算法的形參模式
| alg (beg, end, dest, other parms); |
| alg (beg, end, beg2, other parms); |
| alg (beg, end, beg2, end2, other parms); |
alg 是算法名稱；
beg，end 是算法的輸入范圍（操作的元素范圍）；
dest，beg2，end2，都是迭代器；
other parms 是算法的特有其他參數。
a. 帶有單個目標迭代器的算法
dest 形參是一個迭代器，用于指定存儲輸出數據的目標對象。算法假定無論需要寫入多少個元素都是安全的。必須確保輸出容器有足夠大的容量存儲輸出數據
如果 dest 是容器上的迭代器，則算法將輸出內容寫到容器中已存在的元素上。
更普遍的用法是，將 dest 與某個插入迭代器（第 11.3.1 節）或者ostream_iterator 綁定在一起。插入迭代器在容器中添加元素，以確保容器有足夠的空間存儲輸出。ostream_iterator 則實現寫輸出流的功能，無需要考慮所寫的元素個數。
b. 帶第二個輸入序列的算法
算法同時使用 beg2 和 end2 時，這些迭代器用于標記完整的第二個范圍。
帶有 beg2 而不帶 end2 的算法將 beg2 視為第二個輸入范圍的首元素，但沒有指定該范圍的最后一個元素。這些算法假定以 beg2 開始的范圍至少與 beg和 end 指定的范圍一樣大。
11.4.2 算法命名規范
a. 區別帶有一個值或一個謂詞函數參數的算法版本
很多算法通過檢查其輸入范圍內的元素實現其功能。這些算法通常要用到標準關系操作符：== 或 <
sort (beg, end); -----默認升序排序 // use < operator to sort the elements
sort (beg, end, comp); -----用滿足comp函數的規則排序// use function named comp to sort theelements
檢查指定值的算法默認使用 == 操作符。系統為這類算法提供另外命名的（而非重載的）版本，帶有謂詞函數形參。帶有謂詞函數形參的算法，其名字帶有后綴 _if：
find(beg, end, val); // find first instance of val in the input range
------find 算法查找一個指定的值
find_if(beg, end, pred); // find first instance for which pred is true
------find_if 算法則用于查找一個使謂詞函數 pred 返回非零值True的元素
b. 區別是否實現復制的算法版本
_copy的版本，將元素寫到指定的輸出目標
reverse(beg, end); 將自己的輸入序列中的元素反向重排reverse_copy(beg, end, dest); 復制輸入序列的元素，并將它們逆序存儲到 dest 開始的序列中。11.5容器特有的算法
list 容器上的迭代器是雙向的，而不是隨機訪問類型。
由于 list 容器不支持隨機訪問，因此，在此容器上不能使用需要隨機訪問迭代器的算法。
這些算法包括 sort 及其相關的算法。
還有一些其他的泛型算法，如 merge、remove、reverse 和 unique，雖然可以用在 list 上，但卻付出了性能上的代價。
| lst.remove(val); lst.remove_if(unaryPred) | 調用 lst.erase 刪除所有等于指定值或使指定的謂詞函數返回非零值的元素。返回 void 類型 |
| lst.reverse() | 反向排列 lst 中的元素 |
| lst.sort | 對 lst 中的元素排序 |
| lst.splice(iter, lst2) | 將 lst2 的元素移到 lst 中迭代器 iter 指向的元素前面。在 lst2 中刪除移出的元素;-------第一個版本將 lst2 的所有元素移到 lst 中；合并后，lst2 為空。lst 和 lst2 不能是同一個 list 對象 |
| lst.splice(iter, lst2, iter2) | 第二版本只移動 iter2 所指向的元素，這個元素必須是 lst2 中的元素。在這種情況中，lst 和lst2 可以是同一個 list 對象。也就是說，可在一個 list對象中使用 splice 運算移動一個元素。 |
| lst.splice(iter, beg, end) | 第三版本移動迭代器 beg 和 end 標記的范圍內的元素。beg 和 end 必須指定一個有效的范圍。這兩個迭代器可標記任意 list 對象內的范圍，包括 lst。當它們指定 lst 的一段范圍時，如果 iter 也指向這個范圍的一個元素，則該運算未定義（iter 應不屬于beg,end范圍內） |
與對應的泛型算法不同，list 容器特有的操作能添加和刪除元素。
list 容器特有的算法與其泛型算法版本之間有兩個至關重要的差別。
一個差別是 remove 和 unique 的 list 版本修改了其關聯的基礎容器：真正刪除了指定的元素。
例如，list::unique 將 list 中第二個和后續重復的元素刪除出該容器。
另一個差別是 list 容器提供的 merge 和 splice 運算會破壞它們的實參。
使用 merge 的泛型算法版本時，合并的序列將寫入目標迭代器指向的對象，而兩輸入序列保持不變。
但是，使用 list 容器的 merge 成員函數時，則會破壞它的實參 list 對象------當實參對象的元素合并到調用 merge 函數的list 對象時，實參對象的元素被移出并刪除。
list.unique(); 直接刪除了重復的元素！
總結
以上是生活随笔為你收集整理的C++ Primer 第11章 泛型算法 学习总结的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： NumPy快速入门--形状操作
- 下一篇： db2 脚本运行错误返回错误原因_电脑运