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++ 的集合基本上是儲存資料的容器，如果要處理兩個集合的交集、聯集、差集、對稱差，需要自己手刻一些工具。以上是我目前常用到的集合功能，如果之後有遇到其它需求會再補充內容。

參考資料

1. Built-in Types: Set
2. Python Set Methods
3. cplusplus.com std::set

---

HackMD 版本連結：https://hackmd.io/@yizhewang/rJ-XtPV2h