STL -set

轉載自：http://blog.csdn.net/LYHVOYAGE/article/details/22989659

set集合容器實現了紅黑樹（Red-Black Tree）的平衡二叉檢索樹的的數據結構， 在插入元素時，它會自動調整二叉樹的排列，把該元素放到適當的位置，以確保每個子樹根節點的鍵值大于左子樹所有節點的鍵值，而小于右子樹所有節點的鍵值； 另外，還得確保根節點的左子樹的高度與有字數的高度相等，這樣，二叉樹的高度最小，從而檢索速度最快。要注意的是，它不會重復插入相同鍵值的元素，而采取 忽略處理。

? ? ? ? 平衡二叉檢索樹的檢索使用中序遍歷算法，檢索效率高于vector、deque、和list的容器。另外，采用中序遍歷算法可將鍵值由小到大遍歷出來，所以，可以理解為平衡二叉檢索樹在插入元素時，就會自動將元素按鍵值從小到大的順序排列。

? ? ? ? 構造set集合的主要目的是為了快速檢索，使用set前，需要在程序頭文件中包含聲明“#include<set>”。

1.創建set集合對象

? ? ? ? ? ?創建set對象時，需要指定元素的類型，這一點和其他容器一樣。

[cpp] view plaincopy 在CODE上查看代碼片派生到我的代碼片
  1. #include<iostream>??
  2. #include<set>??
  3. using?namespace?std;??
  4. int?main()??
  5. {??
  6. ????set<int>?s;??
  7. ????return?0;??
  8. }??

2.元素的插入與中序遍歷

? ? ? ? 采用inset()方法把元素插入到集合中，插入規則在默認的比較規則下，是按元素值從小到大插入，如果自己指定了比較規則函數，則按自定義比較規則函數插入。使用前向迭代器對集合中序遍歷，結果正好是元素排序后的結果。

[cpp] view plaincopy 在CODE上查看代碼片派生到我的代碼片
  1. #include<iostream>??
  2. #include<set>??
  3. using?namespace?std;??
  4. int?main()??
  5. {??
  6. ????set<int>?s;??
  7. ????s.insert(5);?//第一次插入5，可以插入??
  8. ????s.insert(1);??
  9. ????s.insert(6);??
  10. ????s.insert(3);??
  11. ????s.insert(5);?//第二次插入5，重復元素，不會插入??
  12. ????set<int>::iterator?it;?//定義前向迭代器??
  13. ????//中序遍歷集合中的所有元素??
  14. ????for(it?=?s.begin();?it?!=?s.end();?it++)??
  15. ????{??
  16. ????????cout?<<?*it?<<?"?";??
  17. ????}??
  18. ????cout?<<?endl;??
  19. ????return?0;??
  20. }??
  21. //運行結果：1?3?5?6??

3.元素的方向遍歷

? ? ? ? 使用反向迭代器reverse_iterator可以反向遍歷集合，輸出的結果正好是集合元素的反向排序結果。它需要用到rbegin()和rend()兩個方法，它們分別給出了反向遍歷的開始位置和結束位置。

[cpp] view plaincopy 在CODE上查看代碼片派生到我的代碼片
  1. #include<iostream>??
  2. #include<set>??
  3. using?namespace?std;??
  4. int?main()??
  5. {??
  6. ????set<int>?s;??
  7. ????s.insert(5);?//第一次插入5，可以插入??
  8. ????s.insert(1);??
  9. ????s.insert(6);??
  10. ????s.insert(3);??
  11. ????s.insert(5);?//第二次插入5，重復元素，不會插入??
  12. ????set<int>::reverse_iterator?rit;?//定義反向迭代器??
  13. ????//反向遍歷集合中的所有元素??
  14. ????for(rit?=?s.rbegin();?rit?!=?s.rend();?rit++)??
  15. ????{??
  16. ????????cout?<<?*rit?<<?"?";??
  17. ????}??
  18. ????cout?<<?endl;??
  19. ????return?0;??
  20. }??
  21. //運行結果：6?5?3?1??

4.元素的刪除

? ? ? ? 與插入元素的處理一樣，集合具有高效的刪除處理功能，并自動重新調整內部的紅黑樹的平衡。刪除的對象可以是某個迭代器位置上的元素、等于某鍵值的元素、一個區間上的元素和清空集合。

[cpp] view plaincopy 在CODE上查看代碼片派生到我的代碼片
  1. #include<iostream>??
  2. #include<set>??
  3. using?namespace?std;??
  4. int?main()??
  5. {??
  6. ????set<int>?s;??
  7. ????s.insert(5);?//第一次插入5，可以插入??
  8. ????s.insert(1);??
  9. ????s.insert(6);??
  10. ????s.insert(3);??
  11. ????s.insert(5);?//第二次插入5，重復元素，不會插入??
  12. ????s.erase(6);?//刪除鍵值為6的元素??
  13. ????set<int>::reverse_iterator?rit;?//定義反向迭代器??
  14. ????//反向遍歷集合中的所有元素??
  15. ????for(rit?=?s.rbegin();?rit?!=?s.rend();?rit++)??
  16. ????{??
  17. ????????cout?<<?*rit?<<?"?";??
  18. ????}??
  19. ????cout?<<?endl;???
  20. ????set<int>::iterator?it;??
  21. ??
  22. ????it?=?s.begin();??
  23. ????for(int?i?=?0;?i?<?2;?i++)??
  24. ????????it?=?s.erase(it);???
  25. ????for(it?=?s.begin();?it?!=?s.end();?it++)??
  26. ????????cout?<<?*it?<<?"?";??
  27. ????cout?<<?endl;??
  28. ??
  29. ????s.clear();??
  30. ????cout?<<?s.size()?<<?endl;??
  31. ??
  32. ????return?0;??
  33. }??
  34. /*?
  35. 運行結果：?
  36. 5?3?1?
  37. 5?
  38. 0?????
  39. */??

5.元素的檢索

? ? ? ? ? 使用find()方法對集合進行檢索，如果找到查找的的鍵值，則返回該鍵值的迭代器位置；否則，返回集合最后一個元素后面的一個位置，即end()。

[cpp] view plaincopy 在CODE上查看代碼片派生到我的代碼片
  1. #include<iostream>??
  2. #include<set>??
  3. using?namespace?std;??
  4. int?main()??
  5. {??
  6. ????set<int>?s;??
  7. ????s.insert(5);?//第一次插入5，可以插入??
  8. ????s.insert(1);??
  9. ????s.insert(6);??
  10. ????s.insert(3);??
  11. ????s.insert(5);?//第二次插入5，重復元素，不會插入??
  12. ????set<int>::iterator?it;??
  13. ????it?=?s.find(6);?//查找鍵值為6的元素??
  14. ????if(it?!=?s.end())??
  15. ????????cout?<<?*it?<<?endl;??
  16. ????else??
  17. ????????cout?<<?"not?find?it"?<<?endl;??
  18. ????it?=?s.find(20);??
  19. ????if(it?!=?s.end())??
  20. ????????cout?<<?*it?<<?endl;??
  21. ????else??
  22. ????????cout?<<?"not?find?it"?<<?endl;??
  23. ????return?0;??
  24. }??
  25. /*?
  26. 運行結果：?
  27. 6?
  28. not?find?it????
  29. */??

下面這種方法也能判斷一個數是否在集合中：

[cpp] view plaincopy 在CODE上查看代碼片派生到我的代碼片
  1. #include?<cstdio>??
  2. #include?<set>??
  3. using?namespace?std;??
  4. int?main()?{??
  5. ????set?<int>?s;??
  6. ????int?a;??
  7. ????for(int?i?=?0;?i?<?10;?i++)??
  8. ????????s.insert(i);??
  9. ????for(int?i?=?0;?i?<?5;?i++)?{??
  10. ????????scanf("%d",?&a);??
  11. ????????if(!s.count(a))?//不存在??
  12. ????????????printf("does?not?exist\n");??
  13. ????????else??
  14. ????????????printf("exist\n");??
  15. ????}??
  16. ????return?0;??
  17. }??


6.自定義比較函數

? ? ? ? ?使用insert將元素插入到集合中去的時候，集合會根據設定的比較函數獎該元素放到該放的節點上去。在定義集合的時候，如果沒有指定比較函數，那么采用默認的比較函數，即按鍵值從小到大的順序插入元素。但在很多情況下，需要自己編寫比較函數。

編寫比較函數有兩種方法。

(1)如果元素不是結構體，那么可以編寫比較函數。下面的程序比較規則為按鍵值從大到小的順序插入到集合中。

[cpp] view plaincopy 在CODE上查看代碼片派生到我的代碼片
  1. #include<iostream>??
  2. #include<set>??
  3. using?namespace?std;??
  4. struct?mycomp??
  5. {?//自定義比較函數，重載“（）”操作符??
  6. ????bool?operator()?(const?int?&a,?const?int?&b)??
  7. ????{??
  8. ????????if(a?!=?b)??
  9. ????????????return?a?>?b;??
  10. ????????else??
  11. ????????????return?a?>?b;??
  12. ????}??
  13. };??
  14. int?main()??
  15. {??
  16. ????set<int,?mycomp>?s;?//采用比較函數mycomp??
  17. ????s.insert(5);?//第一次插入5，可以插入??
  18. ????s.insert(1);??
  19. ????s.insert(6);??
  20. ????s.insert(3);??
  21. ????s.insert(5);?//第二次插入5，重復元素，不會插入??
  22. ????set<int,mycomp>::iterator?it;??
  23. ????for(it?=?s.begin();?it?!=?s.end();?it++)??
  24. ????????cout?<<?*it?<<?"?";??
  25. ????cout?<<?endl;??
  26. ????return?0;??
  27. }??
  28. /*?
  29. 運行結果：6?5?3?1???
  30. */??

(2)如果元素是結構體，那么可以直接把比較函數寫在結構體內。

[cpp] view plaincopy 在CODE上查看代碼片派生到我的代碼片
    1. #include<iostream>??
    2. #include<set>??
    3. #include<string>??
    4. using?namespace?std;??
    5. struct?Info??
    6. {??
    7. ????string?name;??
    8. ????double?score;??
    9. ????bool?operator?<?(const?Info?&a)?const?//?重載“<”操作符，自定義排序規則??
    10. ????{??
    11. ????????//按score由大到小排序。如果要由小到大排序，使用“>”即可。??
    12. ????????return?a.score?<?score;??
    13. ????}??
    14. };??
    15. int?main()??
    16. {??
    17. ????set<Info>?s;??
    18. ????Info?info;??
    19. ??
    20. ????//插入三個元素??
    21. ????info.name?=?"Jack";??
    22. ????info.score?=?80;??
    23. ????s.insert(info);??
    24. ????info.name?=?"Tom";??
    25. ????info.score?=?99;??
    26. ????s.insert(info);??
    27. ????info.name?=?"Steaven";??
    28. ????info.score?=?60;??
    29. ????s.insert(info);??
    30. ??
    31. ????set<Info>::iterator?it;??
    32. ????for(it?=?s.begin();?it?!=?s.end();?it++)??
    33. ????????cout?<<?(*it).name?<<?"?:?"?<<?(*it).score?<<?endl;???
    34. ????return?0;??
    35. }??
    36. /*?
    37. 運行結果：?
    38. Tom?:?99?
    39. Jack?:?80?
    40. Steaven?:?60?
    41. */?

轉載于:https://www.cnblogs.com/PrayG/p/5719600.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/458200.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/458200.shtml
英文地址，請注明出處：http://en.pswp.cn/news/458200.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

【機器學習實戰之一】：C++實現K-近鄰算法KNN

【機器學習實戰之一】：C++實現K-近鄰算法KNN

本文不對KNN算法做過多的理論上的解釋&#xff0c;主要是針對問題&#xff0c;進行算法的設計和代碼的注解。 KNN算法&#xff1a; 優點&#xff1a;精度高、對異常值不敏感、無數據輸入假定。 缺點&#xff1a;計算復雜度高、空間復雜度高。 適用數據范圍&#xff1a;數值…
閱讀更多...
libsvm C++ 代碼參數說明匯總

libsvm C++ 代碼參數說明匯總

幾個重要的數據結構 2.1 struct svm_problem {int l; // 記錄樣本的總數double *y; // 樣本所屬的標簽(1, -1)struct svm_node **x; // 指向樣本數據的二維數組(即一個矩陣&#xff0c;行數是樣本數&#xff0c;列數是特征向量維度) }; 2.2 struct svm_node {int …
閱讀更多...
javascript設計模式-繼承

javascript設計模式-繼承

javascript繼承分為兩種&#xff1a;類式繼承&#xff08;原型鏈、extend函數&#xff09;、原型式繼承&#xff08;對繼承而來的成員的讀和寫的不對等性、clone函數&#xff09;。 類式繼承-->prototype繼承&#xff1a; 1 function Person(name){2 this.name …
閱讀更多...
GIS基礎軟件及操作(二)

GIS基礎軟件及操作(二)

原文 GIS基礎軟件及操作(二) 練習二、管理地理空間數據庫 1.利用ArcCatalog 管理地理空間數據庫 2.在ArcMap中編輯屬性數據 第1步 啟動 ArcCatalog 打開一個地理數據庫 當 ArcCatalog打開后&#xff0c;點擊, 按鈕&#xff08;連接到文件夾&#xff09;. 建立到包含練習數據的…
閱讀更多...
libSVM分類小例C++

libSVM分類小例C++

from&#xff1a;http://www.doczj.com/list_31/ 使用libSVM求解分類問題的C小例 1.libSVM簡介 訓練模型的結構體 struct svm_problem//儲存參加計算的所有樣本 { int l; //記錄樣本總數 double *y; //指向樣本類別的組數 //prob.y new double[prob.l]; struct svm_node …
閱讀更多...
qunit 前端腳本測試用例

qunit 前端腳本測試用例

首先引用qunit 測試框架文件 <link rel"stylesheet" href"qunit-1.22.0.css"> <script src"qunit-1.22.0.js"></script> <div id"qunit"></div> <div id"qunit-fixture"></div>…
閱讀更多...
非常規文件名刪除

非常規文件名刪除

生活中我們偶爾會遇到這樣一件事&#xff1a;走在路上&#xff0c;突然感覺鞋底有東西&#xff0c;抬腳一看&#xff0c;是個泡泡糖。拿不掉&#xff0c;走路還一粘一粘的。要多難受有多難受&#xff01;同樣在linux中也有這么一種文件名。看著不舒服&#xff0c;卻刪不掉。今天…
閱讀更多...
Machine Learning（Stanford）| 斯坦福大學機（吳恩達）器學習筆記【匯總】

Machine Learning（Stanford）| 斯坦福大學機（吳恩達）器學習筆記【匯總】

from&#xff1a;https://blog.csdn.net/m399498400/article/details/52556168 定義本課程常用符號 訓練數據&#xff1a;機器用來學習的數據 測試數據&#xff1a;用來考察機器學習效果的數據&#xff0c;相當于考試。 m 訓練樣本的數量&#xff08;訓練集的個數) x 輸入的…
閱讀更多...
PHP OOP

PHP OOP

類跟對象的關系類是對象的抽象(對象的描述(屬性)&#xff0c;對象的行為(方法))對象是類的實體面相對象的三大特征&#xff1a;封裝、集成、多態自定義類Class Person{}屬性定義屬性是類里面的成員&#xff0c;所以要定義屬性的前提條件是需要聲明一個類Class Person{public $n…
閱讀更多...
kv存儲對抗關系型數據庫

kv存儲對抗關系型數據庫

http://www.searchdatabase.com.cn/showcontent_52657.htm轉載于:https://www.cnblogs.com/hexie/p/5276034.html
閱讀更多...
模板匹配算法

模板匹配算法

from&#xff1a;https://blog.csdn.net/zhi_neng_zhi_fu/article/details/51029864 模板匹配(Template Matching)算法 模板匹配&#xff08;Template Matching&#xff09;是圖像識別中最具代表性的方法之一。它從待識別圖像中提取若干特征向量與模板對應的特征向量進行比較…
閱讀更多...
關于linux用戶權限的理解

關于linux用戶權限的理解

創建用戶useradd 用戶名創建用戶組groupadd 組名查看用戶Idid 用戶修改文件權限chmod 777 文件名或目錄-R 遞歸修改用戶數組chown 屬主&#xff1a;屬組 文件名或目錄名-R 遞歸轉載于:https://blog.51cto.com/1979431/1833512
閱讀更多...
IMEI串號

IMEI串號

IMEI串號就是國際移動設備身份碼&#xff0c;是電子設備的唯一身份證&#xff0c;由于它的唯一性&#xff0c;它可以用來查詢電子設備的保修期還有產地&#xff0c;可以說用處直逼人民的身份證啊&#xff01; 在撥號鍵盤頁面 輸入【*#06#】五個字符轉載于:https://www.cnblogs…
閱讀更多...
立體匹配十大概念綜述---立體匹配算法介紹

立體匹配十大概念綜述---立體匹配算法介紹

from&#xff1a;https://blog.csdn.net/wintergeng/article/details/51049596 一、概念 立體匹配算法主要是通過建立一個能量代價函數&#xff0c;通過此能量代價函數最小化來估計像素點視差值。立體匹配算法的實質就是一個最優化求解問題&#xff0c;通過建立合理的能量函數…
閱讀更多...
zjnu1730 PIRAMIDA(字符串，模擬)

zjnu1730 PIRAMIDA(字符串，模擬)

Description Sample Input 6 JANJETINA 5 1 J 1 A 6 N 6 I 5 E Sample Output 1 0 2 1 1題意&#xff1a;給你一個長度小于等于10^6的字符串&#xff0c;然后每次讓它循環鋪蓋&#xff0c;構成層數為n的塔&#xff0c;讓你求得第i層塔中某個字符的個數。 思路&#xff1a;首先要…
閱讀更多...
ICP算法理解

ICP算法理解

from&#xff1a;https://blog.csdn.net/linear_luo/article/details/52576082 1 經典ICP ICP的目的很簡單&#xff0c;就是求解兩堆點云之間的變換關系。怎么做呢&#xff1f;思路很自然&#xff0c;既然不知道R和t(針對剛體運動)&#xff0c;那我們就假設為未知量唄&#xf…
閱讀更多...
2016-8-2更新日志

2016-8-2更新日志

1.修正版本管理器資源文件名 不能正確拉取 91Resource 文件下的資源的問題2.修正商城購買物品不計算負重的問題3.修正拾取疊加物品 只計算一個物品的重量的問題4.游戲參數-> 游戲選項2->增加物品使用間隔5.修正冷酷不加技能點的BUG6.自定義UI開放測試[目前只能針對熱血傳…
閱讀更多...
字符流緩沖區的使用之BufferedWriter和BufferedReader

字符流緩沖區的使用之BufferedWriter和BufferedReader

從字符輸入流中讀取文本&#xff0c;緩沖各個字符&#xff0c;從而實現字符、數組和行的高效讀取&#xff0c;代碼中使用了輸入緩沖區的特有的方法&#xff1a;readLine(),獲取一行文本數據 import java.io.BufferedReader; import java.io.FileNotFoundException; import java…
閱讀更多...
圖像處理的灰度化和二值化

圖像處理的灰度化和二值化

from&#xff1a;http://blog.sina.com.cn/s/blog_13c6397540102wqtt.html 在圖像處理中&#xff0c;用RGB三個分量&#xff08;R&#xff1a;Red&#xff0c;G&#xff1a;Green&#xff0c;B&#xff1a;Blue&#xff09;&#xff0c;即紅、綠、藍三原色來表示真彩色&#x…
閱讀更多...
結合 category 工作原理分析 OC2.0 中的 runtime

結合 category 工作原理分析 OC2.0 中的 runtime

絕大多數 iOS 開發者在學習 runtime 時都閱讀過 runtime.h 文件中的這段代碼: struct objc_class {Class isa OBJC_ISA_AVAILABILITY;#if !__OBJC2__Class super_class OBJC2_UNAVAILABLE;const char *name …
閱讀更多...
最新文章

Copyright @ 2022~2023