STL之set

2019-11-08 19:26:08

字體：大中小

來源：轉載

供稿：網友

首先要知道set是STL中的一種標準關聯容器（例如set，map，multiset，multimap都是標準關聯容器，而像vector,list,string,deque這些都是序列容器），那什么是關聯式容器，什么又是序列容器呢？關聯容器與序列容器的區別在于：關聯容器是通過鍵存儲和讀取元素的，而序列容器則是通過元素在容器中的位置順序存儲和訪問元素的。 set特性： set的底層其實就是使用平衡搜索樹——紅黑樹(RB-tree)實現的,所以他的插入和刪除操作只需要用迭代器操作節點即可完成（但不能通過迭代器改變它的元素值，因為它的鍵值就是元素值，改變會影響它的排列規則，當然STL也不會給你改變鍵值的接口），不需要內存移動和拷貝，所以效率函數比較高的。另外set里所有元素都會根據鍵值自動被排列（并且默認進行升序排列），跟map不同的是，map同時擁有實值和鍵值，而set只有鍵值，或者說它的實值就是鍵值，鍵值就是實值，同時set不允許兩個元素有相同的鍵值。 set的標準形式是

template < class T, // set::key_type/value_type class Compare = less<T>, // set::key_compare/value_compare class Alloc = allocator<T> // set::allocator_type > class set;

這里寫圖片描述

我們來看看set的接口：由于set底層是由RB-tree實現的，所以set的大部分接口紅黑樹都提供了，幾乎都在轉調用RB-tree的操作。

insert接口中原型是這樣的：

這里寫圖片描述

pair類型： pair模板類用來綁定兩個對象為一個新的對象，該類型在頭文件中定義。pair類型提供的操作如下表： pair

template<typename K, typename V>struct pair{ K first; V value;}

現在因為它的value是不存在的，前面說過它只有鍵值，value存的是bool類型,如果插入成功返回true，失敗返回false。這里insert有兩種情況，一種是已存在的，一種不存在的，不存在的返回的pair是返回插入的迭代器，bool返回的是ture，對于已經存在的，返回的是已經存在的迭代器，第二個參數bool返回false。下面可以驗證一下。

std::set<int> s; s.insert(3); pair<set<int>::iterator, int > ret1 = s.insert(4); s.insert(ret1.first, 12); cout << ret1.second << endl; pair<set<int>::iterator, int >ret = s.insert(3); cout<<ret.second<<endl; system("pause"); return 0;

輸出的是1 0也就是對應的true false。最后驗證一下它不允許兩個相同鍵值存儲：

int main(){ set<int> s; s.insert(5); s.insert(2); s.insert(3); s.insert(1); s.insert(3); set<int>::iterator it = s.begin(); while (it != s.end()) { cout << *it << " "; it++; } cout << endl; system("pause"); return 0;}

這里寫圖片描述發現set已經按照默認升序排列完成，并且沒有將重復出現的3插入。