2021-03-22

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

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

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

set 初始化用法
set 插入元素與讀取元素
迴圈遍歷 set 容器
set 刪除指定元素
清空 set 元素
判斷 set 容器是否為空
set 判斷元素是否存在
std::set 和 std::vector 有什麼不同？

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

set 初始化用法

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

1	std::set<int> myset{1, 2, 3, 4, 5};

從 c-style 陣列來初始化

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

set 插入元素與讀取元素

set 插入元素的用法如下，

std::set<int> myset;
myset.insert(1);
myset.insert(2);
myset.insert(3);
myset.insert(4);
myset.insert(5);

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

迴圈遍歷 set 容器

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

std-set.cpp

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

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

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

    return 0;
}

輸出內容如下，從這個輸出結果發現是元素是由小到大排列，所以 set 容器裡面真的是會幫你排序的，在插入元素的同時會根據元素來進行排序，並且沒有元素重複

1 2 3 4 5

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

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

如果要從後面印到前面的話，可以使用反向迭代器，如果嫌 iterator 迭代器名稱太長的話可以善用 auto 關鍵字讓編譯器去推導該變數類型，用法如下，

// for (std::set<int>::reverse_iterator it = myset.rbegin(); it != myset.rend(); it++) {
// or
for (auto it = myset.rbegin(); it != myset.rend(); it++) {
    std::cout << *it << " ";
}
std::cout << "\n";

使用反向迭代器的輸出結果如下，

5 4 3 2 1

set 刪除指定元素

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

std-set2.cpp

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

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

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

    return 0;
}

結果如下，

4 6 8

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

std-set3.cpp

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

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

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

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

    return 0;
}

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

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

清空 set 元素

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

std::set<int> myset;
myset.insert(1);
myset.insert(2);
myset.insert(3);

myset.clear();

set 判斷元素是否存在

set 要判斷指定元素是否存在的話有兩種方法，
第一種方法是使用 count() 成員函式，count() 存在該元素的話回傳 1，不存在的話回傳 0，

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

換成 char 字元試試，

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

第二種方法是使用 find() 成員函式來判斷指定元素是否存在，
與 count() 不同的是 find() 有找到該指定元素的話會回傳指向該特定元素的 iterator，否則回傳 past-the-end (end()) iterator，
以下範例示範在一個 int 整數的 set 裡使用 find(2) 搜尋看看有沒有 2 這個元素，

std::set<int> myset = {2, 4, 6};
auto search = myset.find(2);
if (search != myset.end()) {
    std::cout << "Found " << *search << "\n"; // Found 2
} else {
    std::cout << "Not found\n";
}

換成 std::string 字串試試，

std::set<std::string> myset = {"Tom", "Jack", "John"};
std::string key = "Tom";
auto search = myset.find(key);
if (search != myset.end()) {
    std::cout << "Found " << *search << "\n"; // Found Tom
} else {
    std::cout << "Not found\n";
}

判斷 set 容器是否為空

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

std-set4.cpp

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

int main() {
    std::set<int> myset;
    myset.clear();

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

    return 0;
}

結果如下，

empty

std::set 和 std::vector 有什麼不同？

唯一性
set 跟 vector 不同之處是 set 容器裡面的元素是唯一的，具有不重複的特性，vector 則沒有這個限制。
不可修改性
vector 可以修改元素的值，但 set 容器裡面元素的值是不可修改的。
順序性
set 是有序的，也就是裡面的元素會按照特定順序擺放，跟插入順序無關，vector 則不是。

其它參考
set - C++ Reference
http://www.cplusplus.com/reference/set/set/
std::set - cppreference.com
https://en.cppreference.com/w/cpp/container/set
C++ set新增、刪除和存取(STL set新增、刪除和存取)元素詳解
https://tw511.com/a/01/1324.html
c++ - What is the difference between std::set and std::vector? - Stack Overflow
https://stackoverflow.com/questions/8686725/what-is-the-difference-between-stdset-and-stdvector