【筆記】set

發布於 更新於 分類於 ， 閱讀次數： 文章字數： 569 所需閱讀時間 ≈ 2 分鐘

簡介

  • 使用前，需引入 <set> 標頭檔。
  • 通常是用紅黑樹實作的。
  • set 容器內的元素是唯一的（不重複）。
  • set 容器具有排序性。
  • set 容器內的值不可被修改。

常用用法

以下 st 皆為 set 容器的變數

insert()

插入元素

1
2
3
set<int> st{2, 5, 9};
st.insert(7);
for (const auto &i : st) cout << i << " ";
1
2 5 7 9

erase()

1
2
3
set<int> st{2, 4, 6, 8};
set.erase(2);
for (const auto &i : st) cout << i << " ";
1
4 6 8

可以刪除不存在的元素，但回傳值為 0

1
2
set<int> st{2, 4, 6, 8};
cout << st.erase(3) << "\n";
1
0

find()

1
2
3
4
5
6
set<int> st{2, 6, 8};
if (st.find(1) == st.end()) {
    cout << "Cannot be found.";
} else {
    cout << "The value is in this set.";
}
1
Cannot be found.

count()

也可以當作查詢是否有元素來使用，因為 set 每個值只會存在一個，因此使用 count() 會回傳 1（即存在）或 0（即不存在）。

1
2
set<int> st{1, 2, 3};
cout << st.count(5);
1
0

empty()

1
2
3
4
5
set<int> st;
if (st.empty())  // .empty() 的回傳值為 true/false
    cout << "It is a empty set.";
else
    cout << "It is not empty.";
1
It is a empty set.

clear()

1
2
3
set<int> st{2, 5, 8};
st.clear();  // 清空 set
if (st.empty()) cout << "It is empty.";
1
It is empty.

遍歷 Set

迭代

第一種

1
for (set<int>::iterator it = st.begin(); it != st.end(); it++) cout << *it << " ";

第二種（第一種的簡化）

1
for (auto it = st.begin(); it != st.end(); it++) cout << *it << " ";

第三種

1
for (const auto &i : st) cout << i << " ";

反向迭代

1
for (auto it = st.rbegin(); it != st.rend(); it++) cout << *it << " ";

unordered_set vs set

參考資料

set unordered_set
Ordering increasing order (by default) no ordering
Implementation Self balancing BST Hash Table
search time O(log(n)) O(1) -> Average
O(n) -> Worst Case
Insertion time log(n) + Rebalance Same as search
Deletion time log(n) + Rebalance Same as search

by set vs unordered_set in C++ STL

詳細資料

Use set when

  • We need ordered data.
  • We would have to print/access the data (in sorted order).
  • We need predecessor/successor of elements.
  • Since set is ordered, we can use functions like binary_search(), lower_bound() and upper_bound() on set elements. These functions cannot be used on unordered_set().
  • See advantages of BST over Hash Table for more cases.

Use unordered_set when

  • We need to keep a set of distinct elements and no ordering is required.
  • We need single element access i.e. no traversal.

總結

有大量且極端的數據時，使用 set 可以有效的增加效率。
相反地，如果是小量數據，可以使用 unordered_set。

參考資料

  • C++ std::set 用法與範例
  • set vs unordered_set in C++ STL
  • set - C++ Reference