set是關聯容器,類似于集合。
特點是里面的元素不會重復,而且元素時有序的。
1.聲明定義:
#include<set>using namespace std;set<int> s;
2.常見用法
s.inert(5); //插入
s.begin(); //返回s的第一個元素 s.end(); // 返回最后一個元素 s.clear() ; //清空 s.empty(); //判斷是否為空 s.max_size() //返回最可能包含的元素最大個數 s.size(); //返回當前元素的個數 s.rbegin(); //同end() s.rend(); // 同begin() s.equal_range(); //返回集合中與給定值相等的上下限兩個迭代器 s.erase(); //刪除集合中的元素 s.lower_bound //返回大于或等于某值的第一個元素迭代器 s.key_comp(); //返回一個用于中間值比較的函數 s.upper_bound //返回大于的第一個元素迭代器
3.自定義比較函數
1)元素不是結構體:(自定義比較函數myComp,重載“()”操作符)
struct myComp{bool operator() (const your_type &a,const your_type &b){return a.data - b.data > 0;} }
2)如果元素是結構體
struct Info{string name;int score;bool operator<const Info &a) const{return a.score < score;} }
---------------------------------------------------------------------------------------------
補充:
C++容器分為順序容器和關聯性容器:
? ? 順序容器包括vector、deque、list、forward_list、array、string,所有順序容器都提供了快速順序訪問元素的能力。
? ? 關聯容器包括set、map的關聯型容器和順序容器有著根本的不同:關聯容器中的元素是按關鍵字來保存和訪問的。
? ? 關聯容器不支持順序容器的位置相關的操作。原因是關聯容器中元素是根據關鍵字存儲的,這些操作對關聯容器沒有意義。
而且,關聯容器也不支持構造函數或插入操作這些接受一個元素值和一個數量值得操作。
? ? 關聯容器支持高效的關鍵字查找和訪問
? ??map中的元素是一些關鍵字----值(key--value)對:關鍵字起到索引的作用,值則表示與索引相關聯的數據。
? ??set中每個元素只包含一個關鍵字:set支持高效的關鍵字查詢操作----檢查一個給定關鍵字是否在set中。
? ??set封裝的二叉樹,所以它支持插入數據的排序,它是關聯式容器,存儲同一數據類型,set中的每一個元素都是唯一的,系統會根據元素的值自動進行排序。
? ? 它們內部采用的是平衡檢索二叉樹:紅黑樹,它的統計性能要好于一般的平衡二叉樹。
1)map和set的插入刪除效率要比其他序列容器高
? ? 對于關聯容器來說,不需要內存拷貝和移動。
? ? set容器所有元素都是以節點的方式來存儲,節點結構和鏈表相似,指向父節點和子節點。插入和刪除的時候改變的都是指針,不會移動內存。
2)每次insert之后,以前保存的iterator不會失效。
? ? iterator等價于指向節點的指針,其內存沒有發生變化,指向內存的指針也不會出現失效的情況。
? ? 對于vector來說,每一次插入和刪除都有可能使指針失效,即使在尾部插入也是 如此。
? ? 這是因為為了保證內部數據的連續存放,iterator指向的那塊內存在刪除和插入的過程可能已經被其他內存覆蓋和釋放了。
? ? 即使是用push_back的時候,容器的存儲空間可能不夠,需要一塊更大的內存。
? ? 只有把以前的內存釋放掉,申請更大的內存,復制已有的數據元素到新的內存,最后把需要插入的元素放到最后。
? ?那么以前的內存指針必然不可再用了。
3)當元素增多的時候,set的插入和搜索速度變化是不變的。? ?紅黑樹的查找時間復雜度都是logN。
----------------------------------------------------------------------------------------------------------------------------------------------------------------------
未完待續
?