Home Programming C/C++

C++ set 是一個關聯式容器， set 容器裡面的元素是唯一的，具有不重複的特性，而且是有排序的容器， set 容器裡面元素的值是不可修改，但 set 容器可以插入或刪除元素， set 的實作方式通常是用紅黑樹 (red-black tree) 實作的。

# set 初始化

C++ set 初始化用法如下，
需要引入 include<set> 標頭檔

set<int> st{1, 2, 3, 4, 5};

從 c-style 陣列來初始化

int arr[] = {1, 2, 3, 4, 5};
set<int> st(arr, arr + 5);

# set 插入元素

set 使用 insert() 來插入元素。
用法如下，

set<int> st;
st.insert(1);
st.insert(2);
st.insert(3);
st.insert(4);
st.insert(5);

# set 讀取元素

由於 set 容器中沒有 at() 成員函數，也沒有 operator[] ，set 無法單純地隨機讀取某元素，但能透過 iterator 來讀取元素。

# 迴圈遍歷 set 容器

迴圈遍歷 set 容器的方式有幾種，
以下先介紹使用 range-based for loop 來遍歷 set 容器並且印出來，這邊故意將元素不按順序初始化以及插入，然後我們再來觀察看看是不是 set 會將其排序，同時看看是不是具有不重複性，

set<int> st = {3, 1};
st.insert(2);
st.insert(5);
st.insert(4);
st.insert(5);
st.insert(4);
for (auto& s: st) cout << s << " ";
輸出內容如下，從這個輸出結果發現是元素是由小到大排列，所以 set 容器裡面真的是會幫你排序的，在插入元素的同時會根據元素來進行排序，並且沒有元素重複。
1 2 3 4 5
迴圈也可以使用迭代器的方式，用法如下，
for (set<int>::iterator it = st.begin(); it != st.end(); it++) {
    cout << *it << " ";
}
// or
for (auto it = st.begin(); it != st.end(); it++) {
    cout << *it << " ";
}
如果要從後面印到前面的話，可以使用反向迭代器，如果嫌 iterator 迭代器名稱太長的話可以善用 auto 關鍵字讓編譯器去推導該變數類型，用法如下
for (auto it = st.rbegin(); it != st.rend(); it++) {
    cout << *it << " ";
}
使用反向迭代器的輸出結果如下
5 4 3 2 1
# set 刪除指定元素
set 刪除指定元素要使用 erase()
set<int> st{2, 4, 6, 8};
st.erase(2);
for (auto& s: st) cout << s << " ";
結果如下，
4 6 8
那 set 刪除不存在的元素呢？
set<int> st{2, 4, 6, 8};
auto ret = st.erase(2);
cout << ret << endl;
for (auto& s : st) cout << s << ' ';
ret = st.erase(3);
cout << endl << ret << endl;
for (auto& s : st) cout << s << ' ';
結果是可以這麼作的，不會發生什麼事。另外 erase() 會回傳告訴你刪除了幾個元素。
1
4 6 8
0
4 6 8
# 清空 set 元素
要清空 set 容器的的話，要使用 clear() ，
set<int> st{1, 2, 3};
st.clear();
# set 判斷元素是否存在
set 要判斷指定元素是否存在的話有兩種方法，
# count()
第一種方法是使用 count() 成員函式， count() 存在該元素的話回傳 1 ，不存在的話回傳 0 ，
set<int> st{2, 4, 6};
cout << st.count(4) << ", ";
cout << st.count(8);
結果如下，
1, 0
# find()
第二種方法是使用 find() 成員函式來判斷指定元素是否存在，
與 count() 不同的是 find() 有找到該指定元素的話會回傳指向該特定元素的 iterator，否則回傳 past-the-end (end ()) iterator
set<int> st = {2, 4, 6};
auto search = st.find(2);
if (search != st.end()) cout << "Found " << *search << endl;
else cout << "Not found\n";
Found 2
# 判斷 set 容器是否為空
要判斷 set 是否為空或是裡面有沒有元素的話，可以用 empty()
set<int> st;
st.clear();
if (st.empty()) cout << "Empty\n";
else cout << "Not empty";
Empty
# set vs. vector
  • 唯一性
    • set 跟 vector 不同之處是 set 容器裡面的元素是唯一的，具有不重複的特性，vector 則沒有這個限制。
  • 不可修改性
    • vector 可以修改元素的值，但 set 容器裡面元素的值是不可修改的。
  • 順序性
    • set 是有序的，也就是裡面的元素會按照特定順序擺放，跟插入順序無關，vector 則不是。
# 參考資料
  • https://shengyu7697.github.io/std-set/