2021-08-12

C++ std::unordered_set 用法與範例

本篇 ShengYu 將介紹 C++ std unordered_set 用法與範例，C++ std::unordered_set 是一個關聯式容器，unordered_set 容器裡面的元素是唯一的，具有不重複的特性，而且是無排序的容器，unordered_set 容器裡面元素的值是不可修改，但 unordered_set 容器可以插入或刪除元素。

unordered_set 跟 set 不同之處是，set 是紅黑樹(red-black tree)實作，紅黑樹具有排序功能，
unordered_set 的實作方式通常是用雜湊表(hash table)實作的，資料插入和查詢的時間複雜度很低，為常數級別O(1)，相對的代價是消耗較多的記憶體，空間複雜度較高，無自動排序功能。

以下 C++ unordered_set 用法與範例將分為這幾部分，

unordered_set 初始化用法
unordered_set 插入元素與讀取元素
迴圈遍歷 unordered_set 容器
unordered_set 刪除指定元素
清空 unordered_set 元素
判斷 unordered_set 容器是否為空
unordered_set 判斷元素是否存在

要使用 unordered_set 容器的話，需要引入的標頭檔：<unordered_set>

unordered_set 初始化用法

C++ unordered_set 初始化用法如下，

1	std::unordered_set<int> myunordered_set{1, 2, 3, 4, 5};

從 c-style 陣列來初始化

1 2	int arr[] = {1, 2, 3, 4, 5}; std::unordered_set<int> myunordered_set(arr, arr+5);

unordered_set 插入元素與讀取元素

unordered_set 插入元素的用法如下，

std::unordered_set<int> myunordered_set;
myunordered_set.insert(1);
myunordered_set.insert(2);
myunordered_set.insert(3);
myunordered_set.insert(4);
myunordered_set.insert(5);

由於 unordered_set 容器中沒有 at() 成員函數，也沒有 operator[]，unordered_set 無法單純地隨機讀取某元素，但能透過 iterator 來讀取元素，可參考下節的介紹。

迴圈遍歷 unordered_set 容器

以下用迴圈來遍歷 unordered_set 容器並且印出來，這邊故意將元素不按順序初始化以及插入，然後我們再來觀察看看是不是 unordered_set 會將其排序，同時看看是不是具有不重複性，

std-unordered_set.cpp

// g++ std-unordered_set.cpp -o a.out -std=c++11
#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> myunordered_set = {3, 1};
    myunordered_set.insert(2);
    myunordered_set.insert(5);
    myunordered_set.insert(4);
    myunordered_set.insert(5);
    myunordered_set.insert(4);

    for (const auto &s : myunordered_set) {
        std::cout << s << " ";
    }
    std::cout << "\n";

    return 0;
}

輸出內容如下，從這個輸出結果可以發現 unordered_set 容器裡元素是不會排序的，也沒有元素重複

4 5 2 1 3

迴圈也可以使用迭代器的方式，用法如下，

for (std::unordered_set<int>::iterator it = myunordered_set.begin(); it != myunordered_set.end(); it++) {
// or
// for (auto it = myunordered_set.begin(); it != myunordered_set.end(); it++) {
    std::cout << *it << " ";
}
std::cout << "\n";

如果嫌 iterator 迭代器名稱太長的話可以善用 auto 關鍵字讓編譯器去推導該變數類型，
因為 unordered_set 沒有像 set 的 rbegin() 與 rend() 可使用，自然就無法使用使用反向迭代器來反著印，

unordered_set 刪除指定元素

以下是 unordered_set 刪除指定元素的用法，unordered_set 刪除指定元素要使用 erase()，

std-unordered_set2.cpp

// g++ std-unordered_set2.cpp -o a.out -std=c++11
#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> myunordered_set{2, 4, 6, 8};

    myunordered_set.erase(2);
    for (const auto &s : myunordered_set) {
        std::cout << s << " ";
    }
    std::cout << "\n";

    return 0;
}

結果如下，

8 6 4

那 unordered_set 刪除不存在的元素呢？

std-unordered_set3.cpp

// g++ std-unordered_set3.cpp -o a.out -std=c++11
#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> myunordered_set{2, 4, 6, 8};

    auto ret = myunordered_set.erase(2);
    std::cout << ret << "\n";
    for (const auto &s : myunordered_set) {
        std::cout << s << " ";
    }
    std::cout << "\n";

    ret = myunordered_set.erase(3);
    std::cout << ret << "\n";
    for (const auto &s : myunordered_set) {
        std::cout << s << " ";
    }
    std::cout << "\n";

    return 0;
}

結果是可以這麼作的，不會發生什麼事。另外會回傳告訴你刪除了幾個元素。

unordered_set erase() 刪除元素還有另外兩種用法，關於這部分下次我再寫一篇給大家講解。

清空 unordered_set 元素

要清空 unordered_set 容器的的話，要使用 clear()，

std::unordered_set<int> myunordered_set;
myunordered_set.insert(1);
myunordered_set.insert(2);
myunordered_set.insert(3);

myunordered_set.clear();

unordered_set 判斷元素是否存在

unordered_set 要判斷元素是否存在的話，可以使用 count()，存在回傳 1，不存在回傳 0，

std::unordered_set<int> myunordered_set;
myunordered_set.insert(2);
myunordered_set.insert(4);
myunordered_set.insert(6);
std::cout << myunordered_set.count(4) << "\n"; // 1
std::cout << myunordered_set.count(8) << "\n"; // 0

換成 char 字元試試，

std::unordered_set<char> myunordered_set;
myunordered_set.insert('a');
myunordered_set.insert('b');
myunordered_set.insert('c');
std::cout << myunordered_set.count('a') << "\n"; // 1
std::cout << myunordered_set.count('c') << "\n"; // 1
std::cout << myunordered_set.count('d') << "\n"; // 0

判斷 unordered_set 容器是否為空

要判斷 unordered_set 是否為空或是裡面有沒有元素的話，可以用 empty()，寫法如下，

std-unordered_set4.cpp

// g++ std-unordered_set4.cpp -o a.out -std=c++11
#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> myunordered_set;
    myunordered_set.clear();

    if (myunordered_set.empty()) {
        std::cout << "empty\n";
    } else {
        std::cout << "not empty, size is "<< myunordered_set.size() <<"\n";
    }

    return 0;
}

結果如下，

empty

以上就是 C++ std::unordered_set 用法與範例介紹，
如果你覺得我的文章寫得不錯、對你有幫助的話記得 Facebook 按讚支持一下！

其它參考
unordered_set - C++ Reference
https://www.cplusplus.com/reference/unordered_set/unordered_set/
std::unordered_set - cppreference.com
https://en.cppreference.com/w/cpp/container/unordered_set
Unordered Sets in C++ Standard Template Library - GeeksforGeeks
https://www.geeksforgeeks.org/unordered_set-in-cpp-stl/