---

set和multiset會根據特定的排序準則，自動將元素排序。兩者不同之處在于multiset 允許元素重復而 set 不允許。如下圖:

使用set或multiset，必須先包含頭文件:

#include <set>

上述兩個類型都被定義為命名空間std內的class template:

namespace std {template <typename T,typename Compare = less<T>,typename Allocator = allocator<T> >class set;template <typename T,typename Compare = less<T>,typename Allocator = allocator<T> >class multiset;
}

其中T是能進行排序的數據類型。第二個參數是進行排序的規則,默認為升序(小于,<),第三個是內存分配器,不用管。

set 和multiset通常用平衡二叉樹(balanced binary tree,確切說是紅黑樹)實現。這樣在插入數據時能自動排序,使得查找元素時有良好性能。其查找函數具有對數O(logn)時間復雜度。

但是,自動排序也造成set和multiset的一個重要限制:你**不能直接改變元素值，**因為這樣會打亂原本正確的順序。

從其接口也能反映這種情況:

set和multiset不提供任何函數可以直接訪問元素。

通過迭代器訪問元素時都是常量。

1.1 定義及初始化🍗

set的定義和初始化如下:

#include <set>
#include <iostream>
using namespace std;//輸出s(升序)的所有數據
void Show(const set<int>& s)
{for (auto i : s)cout << i << " ";cout << endl;
}//輸出s(降序)的所有數據
void Show(const set<int,greater<int>>&s)
{for (auto i : s)cout << i << " ";cout << endl;
}int main()
{set <int> s0;//創建一個空的int set集合    s0.insert(5); //插入數據    s0.insert(3);    s0.insert(1);    s0.insert(2);    s0.insert(4);    s0.insert(4);//相同數據插入失敗    set <int> s1(s0); //利用原來的set對象,創建一個新的set對象    set <int> s2 = s1;//同上    set <int> s3(s0.begin(), --s0.end());//利用迭代器創建一個新的set對象set <int> s4{  1, 6, 3, 5, 4, 2  };//利用初始化列表創建一個set對象,可以無序    cout << "s0:"; Show(s0); //輸出數據    cout << "s1:"; Show(s1);    cout << "s2:"; Show(s2);    cout << "s3:"; Show(s3);    cout << "s4:"; Show(s4);    cout << "降序的集合" << endl;    set <int, greater<int> > s5; //創建一個降序的set集合    s5.insert(10);//插入數據    s5.insert(40);    s5.insert(30);    s5.insert(20);    cout << "s5:"; Show(s5);//輸出數據    return 0;    
}

---

multiset定義和初始化如下:

#include <set>
#include <iostream>
using namespace std;//輸出s(升序)的所有數據
void Show(const multiset<int>& s)
{for (auto i : s)cout << i << " ";cout << endl;
}//輸出s(降序)的所有數據
void Show(const multiset<int, greater<int>>& s)
{for (auto i : s)cout << i << " ";cout << endl;
}int main()
{multiset <int> s0;//創建一個空的int set集合s0.insert(5); //插入數據s0.insert(3);s0.insert(1);s0.insert(2);s0.insert(4);s0.insert(4);//可以插入相同數據multiset <int> s1(s0); //利用原來的set對象,創建一個新的set對象multiset <int> s2 = s1;//同上multiset <int> s3(s0.begin(), --s0.end());//利用迭代器創建一個新的set對象multiset <int> s4{ { 1, 6, 3, 5, 4, 2 } };//利用初始化列表創建一個set對象cout << "s0:"; Show(s0); //輸出數據cout << "s1:"; Show(s1);cout << "s2:"; Show(s2);cout << "s3:"; Show(s3);cout << "s4:"; Show(s4);cout << "降序的集合" << endl;multiset <int, greater<int> > s5; //創建一個降序的set集合s5.insert(10);//插入數據s5.insert(40);s5.insert(30);s5.insert(20);cout << "s5:"; Show(s5);//輸出數據return 0;
}

1.2 向set和multiset中添加元素和刪除元素🍗

通過insert函數插入數據。通過erase刪除元素。

//輸出s(升序)的所有數據
void Show(const set<int>& s)
{for (auto i : s)cout << i << " ";cout << endl;
}
int main()
{set<int> s1;s1.insert(4);s1.insert(1);s1.insert(5);s1.insert(2);cout << "s1:";  Show(s1);s1.erase(2);cout << "刪除2后,s1:";  Show(s1);s1.clear();cout << "清空后,s1:";  Show(s1);return 0;
}

1.3 常用迭代器🍗

set和multiset支持雙向迭代器,不支持隨機迭代器,可以往前和往后,但不能+1,-1(這是隨機迭代器)等。
常用的迭代器如下:
s.begin()
第一個元素的迭代器
s.end()
最后一個元素的下一個位置迭代器(尾后迭代器或尾迭代器)
s.cbegin()
第一個元素的常量迭代器(不修改元素內容)
s.cend()
尾后常量迭代器(不修改元素內容)
s.rbegin()
第一個反向迭代器
s.rend()
尾后反向迭代器

int main()    
{set<int> s1;    s1.insert(4);    s1.insert(1);    s1.insert(5);    s1.insert(2);    cout << "從頭到尾輸出s1:";    for (auto p = s1.begin(); p != s1.end(); p++)    cout << *p << " ";    cout << endl;    cout << "從后往前輸出s1:";    for (auto p = s1.rbegin(); p != s1.rend(); p++)    cout << *p << " ";    cout << endl;    auto p = s1.begin();    cout << "第二個元素:"<< * (++p) << endl;//輸出第二個元素    cout << "第一個元素:"<< * (--p) << endl;//輸出第一個元素    //cout << *(p + 1) << endl;//錯誤    return 0;    
}

---

1.4 set和multiset常用的運算符🍗

set和multiset類既支持常用的=,==,!=,< , >等運算符,也可以通過調用其成員函數來執行相應的操作。下面列舉了其常用的操作。詳細情況可以參考set或multiset幫助手冊。

//輸出s(升序)的所有數據    
void Show(const set<int>& s)    
{for (auto i : s)    cout << i << " ";    cout << endl;    
}int main()    
{set<int> s1;    s1.insert(4);    s1.insert(1);    s1.insert(5);    s1.insert(2);    cout << "s1:";  Show(s1);    set<int> s2;    s2 = s1;    cout << "s2:";  Show(s2);    if (s1 == s2)    cout << "s1 == s2" << endl;    s2.insert(7);    cout << "往s2插入7后,";    if (s1 > s2)    cout << "s1 > s2" ;    else if (s1 < s2)    cout << "s1 < s2" ;    //cout << s1[1] << endl;//錯誤    return 0;    
}

---

1.5 set和multiset常用成員函數🍗

下面列舉set和multiset對象常用的成員函數,詳細的介紹請查看幫助手冊。

1.6 set應用場景🍗

set在C++中是一個內部自動有序且不含重復元素的容器，它的應用場景廣泛且多樣。以下是一些set的常見應用場景：

1.自動排序
如果需要對元素保持持續的排序狀態，如維持一個按字母順序排列的單詞列表、存儲并維護一個按年齡升序或降序排列的人口數據庫等，std::set 可以實現這一功能。每次插入新元素，容器都會自動調整元素的順序。

當然如果僅僅是排序,可以使用sort函數進行排序.
sort排序是在排序瞬間的,如果又插入新的數據可能不再有序
set的有序是持續的,不管插入還是刪除數據它始終有序
2.快速查找
由于set內部采用了高效的平衡查找二叉樹（如紅黑樹），因此它提供快速的查找性能。包括檢查元素是否已存在（.count() 或 .find()）、查找特定值的下一個/前一個元素（迭代器操作）。這對于實現諸如查找詞匯表中的下一個更大詞、或者在游戲中查找排名高于當前玩家的下一個玩家等場景很有用。

---

本篇完！🍗