HackMD
Python 及 C++ 集合 (set)
作者：王一哲
日期：2023年8月13日
前言
集合 (set) 的性質與陣列很像，但是集合中的資料不能重複。以下的程式碼測試版本為 Python 3.10.12 及 C++14。
Python Set
Python 預設的資料容器有串列 (list)、數組 (tuple)、字典 (dictionary)、集合 (set)，使用 set 不需要引入函式庫。集合中的資料不能重複、沒有排序，無法使用索引值存取、改變資料，但是可以移除或新增資料。
建立集合
語法有以下
名稱 = set() # 産生空的集合，如果用 名稱 = {} 會産生空的字典
名稱 = {資料1, 資料2, 資料3, ...} # 産生集合同時指定資料
名稱 = set(可迭代的資料) # 由可迭代的資料産生集合
例如以下的程式碼
a = set() # 産生空的集合 a
b = {1, 3, 5, 2, 4, 6} # 産生集合 b，print 輸出為 {1, 2, 3, 4, 5, 6}
c = {1, -3, 5, -2, 4, 6}# 産生集合 c，print 輸出為 {1, 4, 5, 6, -3, -2}
# 由串列産生集合 d，print 輸出為 {1, 2, 3, 4, 5, 6}
mylist = [1, 3, 5, 2, 4, 6]
d = set(mylist)
# 由數組産生集合 f，print 輸出為 {1, 2, 3, 4, 5, 6}
mytuple = (1, 3, 5, 2, 4, 6)
f = set(mytuple)
# 由字典産生集合 g、h、k
mydict = {1: 3, 5: 2, 4: 6}
g = set(mydict) # 預設由 key 産生集合，print 輸出為 {1, 4, 5}
h = set(mydict.keys()) # 由 key 産生集合，print 輸出為 {1, 4, 5}
k = set(mydict.values()) # 由 value 産生集合，print 輸出為 {2, 4, 6}
# 由字串産生集合 s
hello = "Hello World!"
s = set(hello) # 産生集合 s，print 輸出為 {'d', 'e', 'l', ' ', 'r', 'o', '!', 'W', 'H'}
# 産生內容為字元的集合 t，print 輸出為 {'c', 'A', 'C', 'a', 'b', 'B'}
t = {'a', 'A', 'c', 'C', 'b', 'B'}
加入資料
語法為
名稱.add(資料)
一次只能加入一筆資料，如果集合中已經有這筆資料，則集合內容不變。例如以下的程式碼
a = {1, 3, 5, 2, 4, 6}
a.add(1) # a 的內容不變
a.add(-1) # a 的內容變為 {1, 2, 3, 4, 5, 6, -1}
複製集合
語法為
集合2 ＝ 集合1.copy()
不需要加上任何參數。如果不使用 copy 而是用等號，則改變集合2時也會改變集合1的內容，例如以下的程式碼
a = {1, 3, 5, 2, 4, 6} # a 的內容是 {1, 2, 3, 4, 5, 6}
b = a.copy() # 將 a 的內容複製給 b
c = a # c 指向 a，兩者會同時改變
c.add(-1) # a、c 的內容都變為 {1, 2, 3, 4, 5, 6, -1}，但是 b 不變
清除資料
語法為
名稱.clear()
不需要加上任何參數，清空資料集合長度為 0。
隨機移除一筆資料並回傳被移除的資料
語法為
回傳值 ＝ 集合.pop()
不需要加上任何參數。但在測試時發現，如果集合的資料皆為數字，都是移除第一筆資料；如果集合中的資料皆為字元，每次移除的資料不固定，例如以下的程式碼
a = {1, 3, 5, 2, 4, 6}
b = {'a', 'A', 'c', 'C', 'b', 'B'}
print(a.pop()) # 每次都移除 1
print(b.pop()) # 隨機移除字元
移除指定的一筆資料
第一種語法為
集合.remove(資料)
只能加上一個參數，沒有回傳值。如果集合中沒有指定的資料，會回傳錯誤訊息 KeyError 並中止程式。例如以下的程式碼
a = {1, 3, 5, 2, 4, 6}
a.remove(5) # a 的內容都變為 {1, 2, 3, 4, 6}
a.remove(0) # 回傳錯誤訊息 KeyError 並中止程式
第二種語法為
集合.discard(資料)
只能加上一個參數，沒有回傳值。如果集合中沒有指定的資料，不會回傳錯誤訊息，不會中止程式，集合的內容不變。例如以下的程式碼
a = {1, 3, 5, 2, 4, 6}
a.discard(5) # a 的內容都變為 {1, 2, 3, 4, 6}
a.discard(0) # a 的內容不變
回傳兩個集合的相對差集
相對差集 (relative complement) 或稱為差集，如果有兩個集合 a、b，則 a 在 b 的相對差集，就是集合 b 扣掉集合 a、b 都有的資料。語法為
相對差集 = 集合b.difference(集合a)
例如以下的程式碼
a = {1, 2, 3, 4, 5, 6}
b = {1, 3, 5, 7, 9, 11}
c = a.difference(b) # c 的內容為 {2, 4, 6}
d = b.difference(a) # d 的內容為 {9, 11, 7}
更新資料為兩個集合的相對差集
如果有兩個集合 a、b，要將 b 更新為 a 在 b 的相對差集，語法為
集合b.difference_update(集合a)
沒有回傳值。例如以下的程式碼
a = {1, 2, 3, 4, 5, 6}
b = {1, 3, 5, 7, 9, 11}
b.difference_update(a) # b 的內容變為 {7, 9, 11}
回傳兩個集合的交集
兩個集合 a、b 的交集 (intersection)，就是同時存在於 a、b 中的資料。以下兩種語法效果相同
交集 = 集合a.intersection(集合b)
交集 = 集合b.intersection(集合a)
例如以下的程式碼
a = {1, 2, 3, 4, 5, 6}
b = {1, 3, 5, 7, 9, 11}
c = a.intersection(b) # c 的內容為 {1, 3, 5}
d = b.intersection(a) # d 的內容為 {1, 3, 5}
更新資料為兩個集合的交集
如果有兩個集合 a、b，要將 a 更新為 a、b 的交集，語法為
集合a.intersection_update(集合b)
沒有回傳值。例如以下的程式碼
a = {1, 2, 3, 4, 5, 6}
b = {1, 3, 5, 7, 9, 11}
a.intersection_update(b) # a 的內容變為 {1, 3, 5}
回傳兩個集合的聯集
兩個集合 a、b 的聯集 (union)，就是 a、b 當中所有的資料。以下兩種語法效果相同
聯集 = 集合a.union(集合b)
聯集 = 集合b.union(集合a)
例如以下的程式碼
a = {1, 2, 3, 4, 5, 6}
b = {1, 3, 5, 7, 9, 11}
c = a.union(b) # c 的內容為 {1, 2, 3, 4, 5, 6, 7, 9, 11}
d = b.union(a) # d 的內容為 {1, 2, 3, 4, 5, 6, 7, 9, 11}
更新集合的資料
可以從另一個可迭代的物件更新集合的資料，只會加入目前集合中沒有的資料。語法為
集合.update(可迭代的物件)
沒有回傳值。例如以下的程式碼
a = {1, 2, 3, 4, 5, 6}
b = [1, 3, 5, 7, 9, 11]
a.update(b) # a 的內容變為 {1, 2, 3, 4, 5, 6, 7, 9, 11}
回傳兩個集合是否沒有交集
如果集合 a、b 沒有交集回傳 True，如果有交集回傳 False。以下兩種語法效果相同
狀態 = 集合a.isdisjoint(集合b)
狀態 = 集合b.isdisjoint(集合a)
例如以下的程式碼
a = {1, 2, 3, 4, 5, 6}
b = {1, 3, 5, 7, 9, 11}
c = {7, 8, 9, 10}
print(a.isdisjoint(b)) # 印出 False
print(c.isdisjoint(a)) # 印出 True
回傳集合是否為另一個集合的子集
如果集合 a 包含集合 b 所有的資料，則 b 為 a 的子集，如果是子集回傳 True，反之回傳 False。語法為
狀態 = 集合b.issubset(集合a)
例如以下的程式碼
a = {1, 2, 3, 4, 5, 6}
b = {1, 3, 5, 7, 9, 11}
c = {1, 2, 3, 4}
print(c.issubset(a)) # 印出 True
print(c.issubset(b)) # 印出 False
回傳集合是否包含另一個集合
如果集合 a 包含集合 b 所有的資料回傳 True，反之回傳 False。語法為
狀態 = 集合a.issuperset(集合b)
例如以下的程式碼
a = {1, 2, 3, 4, 5, 6}
b = {1, 3, 5, 7, 9, 11}
c = {1, 2, 3, 4}
print(a.issuperset(c)) # 印出 True
print(b.issuperset(c)) # 印出 False
回傳兩個集合的對稱差
兩個集合 a、b 的對稱差 (symmetric difference)，就是沒有同時存在於 a、b 的資料，也就是 a、b 的聯集扣掉交集。以下兩種語法效果相同
對稱差 = 集合a.symmetric_difference(集合b)
對稱差 = 集合b.symmetric_difference(集合a)
例如以下的程式碼
a = {1, 2, 3, 4, 5, 6}
b = {1, 3, 5, 7, 9, 11}
c = a.symmetric_difference(b) # c 的內容為 {2, 4, 6, 7, 9, 11}
d = b.symmetric_difference(a) # d 的內容為 {2, 4, 6, 7, 9, 11}
更新資料為兩個集合的對稱差
如果有兩個集合 a、b，要將 a 更新為 a、b 的對稱差，語法為
集合a.symmetric_difference_update(集合b)
沒有回傳值。例如以下的程式碼
a = {1, 2, 3, 4, 5, 6}
b = {1, 3, 5, 7, 9, 11}
a.symmetric_difference_update(b) # a 的內容變為 {2, 4, 6, 7, 9, 11}
C++ STL set 函式庫
要先引入函式庫，函式庫的官方說明書在此 cplusplus.com std::set。
#include <set>
集合中的資料不能重複，由小到大排序，無法使用索引值存取、改變資料，但是可以移除或新增資料。
建立集合
集合的資料可以是所有內建的資料格式，例如 int、float、string，也可以使用自訂的資料格式。語法為
// 産生空的集合
set<資料格式> 集合名稱;
// 産生集合並指定資料
set<資料格式> 集合名稱 {用逗號分隔的資料};
set<資料格式> 集合名稱 = {用逗號分隔的資料};
// 由集合2複製資料，也可以改變記憶體位置只複製部分內容
set<資料格式> 集合名稱 (集合2名稱.begin(), 集合2名稱.end());
// 由集合2複製資料
set<資料格式> 集合名稱 (集合2名稱);
// 由已定義的陣列複製資料
set<資料格式> 集合名稱 (陣列名稱, 陣列名稱 + 陣列長度);
例如以下的程式碼
set<int> a; // a 是空的
set<int> b {1, 3, 5, 2, 4, 6}; // b 的內容為 {1, 2, 3, 4, 5, 6}
set<int> c = {1, 3, 5, 2, 4, 6}; // c 的內容為 {1, 2, 3, 4, 5, 6}
set<int> d (b.begin(), b.end()); // d 的內容為 {1, 2, 3, 4, 5, 6}
set<int> f (b); // f 的內容為 {1, 2, 3, 4, 5, 6}
int data[] = {1, 3, 5, 2, 4, 6};
set<int> g (data, data + sizeof(data)/sizeof(int)); // g 的內容為 {1, 2, 3, 4, 5, 6}
set<char> h = {'a', 'A', 'c', 'C', 'b', 'B'}; // h 的內容為 {A, B, C, a, b, c}
迭代器 iterator
迭代器可以用來取得物件對應的記憶體位址，有以下幾種：
集合名稱.begin(); // 回傳集合起點位址
集合名稱.end(); // 回傳集合終點位址
集合名稱.rbegin(); // 回傳集合終點位址，由後向前向讀取資料
集合名稱.rend(); // 回傳集合起點位址，由後向前向讀取資料
集合名稱.cbegin(); // 回傳集合起點位址，回傳值為常數
集合名稱.cend(); // 回傳集合終點位址，回傳值為常數
集合名稱.crbegin();// 回傳集合終點位址，由後向前向讀取資料，回傳值為常數
集合名稱.crend(); // 回傳集合起點位址，由後向前向讀取資料，回傳值為常數
迭代器的變數名稱通常是 it，寫法有兩種，例如以下的程式碼
set<int> a = {1, 3, 5, 2, 4, 6};
set<int>::iterator it = q.begin();
auto it = q.begin();
但是 set<int>::iterator 只能用在 begin()、end()、cbegin()、cend()，還是用 auto 會比較方便。如果要印出集合中所有的資料，可以配合迭代器處理，例如以下的程式碼
set<int> a = {1, 3, 5, 2, 4, 6};
for(auto it = a.begin(); it != a.end(); it++)
cout << *it << " "; // 印出的值為 1 2 3 4 5 6
cout << "\n";
for(auto it = a.rbegin(); it != a.rend(); it++)
cout << *it << " "; // 印出的值為 6 5 4 3 2 1
cout << "\n";
for(auto it = a.cbegin(); it != a.cend(); it++)
cout << *it << " "; // 印出的值為 1 2 3 4 5 6
cout << "\n";
for(auto it = a.crbegin(); it != a.crend(); it++)
cout << *it << " "; // 印出的值為 6 5 4 3 2 1
cout << "\n";
加入資料
語法為
集合名稱.insert(資料);
一次只能加入一筆資料，如果集合中已經有這筆資料，則集合內容不變。例如以下的程式碼
set<int> a = {1, 3, 5, 2, 4, 6};
a.insert(3); // a 的內容不變
a.insert(-1); // a 的內容變為 {-1, 1, 2, 3, 4, 5, 6}
另一個工具是 emplace，語法為
集合名稱.emplace(資料);
看起來效果和 insert 差不多，但是據說少了複製構造的步驟，所以效率更高。例如以下的程式碼
set<int> a = {1, 3, 5, 2, 4, 6};
a.emplace(3); // a 的內容不變
a.emplace(-1); // a 的內容變為 {-1, 1, 2, 3, 4, 5, 6}
刪除指定的資料
語法為
集合名稱.erase(資料);
一次只能刪除一筆資料，如果集合中沒有指定的資料則集合內容不變。例如以下的程式碼
set<int> a = {1, 3, 5, 2, 4, 6};
a.erase(3); // a 的內容變為 {1, 2, 4, 5, 6}
a.erase(-1); // a 的內容不變，仍然為 {1, 2, 4, 5, 6}
erase 也可以刪除指定範圍的資料，請參考下文中 lower_bound 及 upper_bound 的說明。
清除所有資料
語法為
集合名稱.clear();
不需要加上任何參數，清空資料後集合長度為 0。
交換兩個集合的資料
語法為
集合名稱1.swap(集合名稱2);
取得指定資料的位址
如果集合中有指定的資料，會回傳該資料位址的迭代器；如果集合中沒有指定的資料，會回 .end()。語法為
auto it = 集合名稱.find(資料);
例如以下的程式碼
set<int> a = {1, 3, 5, 2, 4, 6};
auto it = a.find(3);
a.erase(it); // a 的內容變為 {1, 2, 4, 5, 6}
if (a.find(-1) == a.end()) cout << "Not found\n"; // 集合中沒有 -1，印出 Not found
else cout << "Found\n";
另外有兩個工具，lower_bound 及 upper_bound，語法為
auto lowerit = 集合名稱.lower_bound(資料);
auto upperit = 集合名稱.upper_bound(資料); // 回傳的位置包含這筆資料
可以搭配 erase 刪除某個範圍內的資料，例如以下的程式碼
set<int> a = {1, 2, 3, 4, 5, 6};
auto lowit = a.lower_bound(2);
auto upit = a.upper_bound(5);
a.erase(lowit, upit); // a 的內容變為 {1, 6}
還有一個工具可以同時回傳指定資料對應的 lower_bound 及 upper_bound，語法為
auto ret = 集合名稱.equal_range(資料);
回傳值分為兩個部分，ret.first 為 lower_bound，ret.second 為 upper_bound。例如以下的程式碼
set<int> a = {1, 2, 3, 4, 5, 6};
auto ret = a.equal_range(3);
a.erase(ret.first, ret.second); // a 的內容變為 {1, 2, 4, 5, 6}
計算指定資料的數量
由於集合的資料不能重覆，因此指定資料的數量只有0或1，回傳值格式為 size_t，語法為
集合名稱.count(資料);
例如以下的程式碼
set<int> a = {1, 3, 5, 2, 4, 6};
cout << a.count(3) << endl; // 印出 1
cout << a.count(-1) << endl; // 印出 0
取得集合長度
語法為
集合名稱.size();
不需要任何參數，回傳值格式為 size_t，沒有正負號的整數。
回傳集合最大長度
語法為
集合名稱.max_size();
不需要任何參數，回傳值格式為 size_t，沒有正負號的整數。在我使用的系統中回傳值為 230584300921369395。
檢查集合是否為空
語法為
集合名稱.empty();
不需要任何參數，如果集合為空回傳 1，如果有資料回傳 0。
結語
Python 的集合除了可以儲存資料，還可以處理兩個集合的交集、聯集、差集、對稱差，功能十分強大。C++ 的集合基本上是儲存資料的容器，如果要處理兩個集合的交集、聯集、差集、對稱差，需要自己手刻一些工具。以上是我目前常用到的集合功能，如果之後有遇到其它需求會再補充內容。
