APCS 2021/1(ZJf607)

集合 Set

實現

• std::set背後是一棵紅黑樹

用途

• 為一關聯容器
• set中元素唯一且按規則排序好(默認為從小到大排)
• 可以很快很方便的插入、訪問元素

用法

宣告

• 需要引入函式庫<set>

#include <set>
//set<"dataType"> "name";

set<int> test;
set<long long> test;
set<char>
set<pair<int, int> >test;

函式

狀態回傳
set.empty(); //回傳set是否為空
set.size(); //回傳set目前元素數
set.count(e); //回傳set中e的個數(1或0，用來檢查set中是否有e)
    
加入移除元素
set.insert(e); //將e插入set中
set.erase(e); //將e從set中移除
set.clear(); //移除set中所有元素

指標回傳 
set.begin(); //回傳指向set中第一個元素的指標
set.end(); //回傳指向set中最後一個元素的指標
set.find(e); //回傳指向set中e的指標
set.lower_bound(e); //回傳指向set中第一個大於等於e的元素的指標
set.upper_bound(e); //回傳指向set中最後一個大於等於e的元素的指標 
set.equal_range(e); //以一個pair回傳指向set中第一個大於等於e的元素和第一個大於e的元素的指標
// 以上若有任一指標失效，則效果等同於end()

• 插入、移除、訪問的複雜度皆為
  $O(logN)$