explicit set (const key_compare& comp = key_compare(),
               const allocator_type& alloc = allocator_type());

template <class InputIterator>
set (InputIterator first, InputIterator last,
     const key_compare& comp = key_compare(),
     const allocator_type& alloc = allocator_type());

set (const set& x);

void test_set1()
{
    set<int> s = { 5,1,5,3,4,2,6,83,9,10,22 };
    // 中序，排序+去重
    set<int>::iterator it = s.begin();
    while (it != s.end())
    {
        // 普通迭代器也不支持修改
        // *it = 1;
        
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

#include <set>
#include <iostream>
using namespace std;

int main() {
    set<int> s;
    // 插入單個(gè)元素
    s.insert(3);
    s.insert(1);
    s.insert(2);
    s.insert(2); // 重復(fù)元素，插入失?。╯et自動(dòng)去重）

    // 遍歷輸出：1 2 3（默認(rèn)升序）
    for (int val : s) cout << val << " ";
    return 0;
}

int main() {
    set<int> s = {1,2,3,4,5};
    // 1. 按鍵值刪除
    s.erase(3); 
    // 2. 按迭代器刪除
    auto it = s.find(4);
    if (it != s.end()) s.erase(it);
    // 3. 按范圍刪除（刪除[begin, end)）
    s.erase(s.begin(), s.end()); //左閉右開(kāi)

    cout << s.size(); // 輸出0
    return 0;
}

int main() {
    set<int> s1 = {1,2,3};
    set<int> s2 = {4,5,6};
    s1.swap(s2);

    // s1變?yōu)閧4,5,6}，s2變?yōu)閧1,2,3}
    for (int val : s1) cout << val << " "; // 輸出4 5 6
    return 0;
}

int main() {
    set<int> s = {1,2,3};
    s.clear();
    cout << s.empty(); // 輸出1（表示容器為空）
    return 0;
}

int main() {
    set<pair<int, string>> s;
    // emplace直接構(gòu)造pair（無(wú)需手動(dòng)創(chuàng)建臨時(shí)pair）
    s.emplace(1, "apple"); 
    // 等價(jià)于insert，但emplace更高效
    s.insert(pair<int, string>(2, "banana"));

    return 0;
}

int main() {
    set<int> s = {1,3,5};
    // 提示在3的位置附近插入2（實(shí)際插入到1和3之間）
    auto it = s.find(3);
    s.emplace_hint(it, 2);

    for (int val : s) cout << val << " "; // 輸出1 2 3 5
    return 0;
}

iterator find (const value_type& val) const;

#include <set>
#include <iostream>
using namespace std;

int main() {
    set<int> s = {1, 2, 3, 4, 5};
    
    // 查找鍵值3
    auto it = s.find(3);
    if (it != s.end()) {
        cout << "找到元素：" << *it << endl; // 輸出“找到元素：3”
    }

    // 查找不存在的鍵值6
    it = s.find(6);
    if (it == s.end()) {
        cout << "未找到元素" << endl; // 輸出“未找到元素”
    }

    return 0;
}

#include <set>
#include <iostream>
using namespace std;

int main() {
    // 定義一個(gè)按降序排序的set
    set<int, greater<int>> s = {3, 1, 2};

    // 獲取key_comp比較對(duì)象
    auto comp = s.key_comp();

    // 使用comp判斷兩個(gè)鍵的大小關(guān)系（符合set的降序規(guī)則）
    bool res = comp(1, 2); // 等價(jià)于greater<int>()(1,2)，結(jié)果為false
    cout << "1 > 2 ? " << boolalpha << res << endl; // 輸出“1 > 2 ? false”

    return 0;
}

#include <set>
#include <iostream>
using namespace std;

int main() {
    set<int> s = {1, 2, 3, 4};

    // 統(tǒng)計(jì)存在的元素
    size_t cnt1 = s.count(3);
    cout << "元素3的出現(xiàn)次數(shù)：" << cnt1 << endl; // 輸出1

    // 統(tǒng)計(jì)不存在的元素
    size_t cnt2 = s.count(5);
    cout << "元素5的出現(xiàn)次數(shù)：" << cnt2 << endl; // 輸出0

    return 0;
}

#include <set>
#include <iostream>
using namespace std;

int main() {
    set<int> s = {1, 3, 5, 7, 9};
    int val = 5;

    // 獲取lower_bound：第一個(gè)≥5的元素（即5）
    auto lb = s.lower_bound(val);
    cout << "lower_bound(" << val << "): " << *lb << endl; // 輸出5

    // 獲取upper_bound：第一個(gè)>5的元素（即7）
    auto ub = s.upper_bound(val);
    cout << "upper_bound(" << val << "): " << *ub << endl; // 輸出7

    // 若val不存在（如val=4）
    val = 4;
    lb = s.lower_bound(val); // 第一個(gè)≥4的元素是5
    ub = s.upper_bound(val); // 第一個(gè)>4的元素是5
    cout << "val=4時(shí)，[lb, ub)區(qū)間長(zhǎng)度：" << distance(lb, ub) << endl; // 輸出0（無(wú)元素）

    return 0;
}

#include <set>
#include <iostream>
using namespace std;

int main() {
    // set：鍵唯一
    set<int> s = {1, 2, 2, 3};
    cout << "set大小：" << s.size() << endl; // 輸出3（自動(dòng)去重）

    // multiset：鍵可重復(fù)
    multiset<int> ms = {1, 2, 2, 3};
    cout << "multiset大?。? << ms.size() << endl; // 輸出4（保留重復(fù)）

    // count接口差異
    cout << "set中2的數(shù)量：" << s.count(2) << endl; // 輸出1
    cout << "multiset中2的數(shù)量：" << ms.count(2) << endl; // 輸出2

    return 0;
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode* head) 
    {
        set<ListNode*> s;
        ListNode* tmp=head;
        while(tmp!=NULL)
        {
            if(s.count(tmp)==0)
            {
                s.insert(tmp);
                tmp=tmp->next;
            }
            else
            {
                return tmp;
            }
        }
        return NULL;
    }
};

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2)
    {
     //去重 
     set<int> s1(nums1.begin(),nums1.end());  
     set<int> s2(nums2.begin(),nums2.end());  
     vector<int> v;
     for(auto e : s1)
     {
        if(s2.count(e))
        {
            v.push_back(e);
        }
     }
     return v;
    }
};