---
# System prepended metadata

title: Set
tags: [STL]

---

---
tags: STL
title: Set
---
:::info
#### [APCS 2021/1(ZJf607)](https://zerojudge.tw/ShowProblem?problemid=f607)
:::

:::success
# 集合 Set

## 實現

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

## 用途

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

## 用法

### 宣告

- 需要引入函式庫\<set>
```cpp=
#include <set>
//set<"dataType"> "name";

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

### 函式
```cpp=
狀態回傳
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)$
:::