c++容器

c++怎么用set

Posted by farmer3-c on February 2, 2026
相关文章
  • 暂无相关文章

什么是set

简单来说，set是一个集合，里面的元素是唯一的，而且是有序的。

set是一个容器，可以提供快速的查找、插入和删除操作,具有对数复杂度。

set 通常实现为 红黑树。

怎么用set

迭代器

  • begin      返回指向起始的迭代器
  • cbegin (C++11)      (public 成员函数)
1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include <algorithm>
#include <iostream>
#include <set>
 
int main()
{
    std::set<int> set{3, 1, 4, 1, 5, 9, 2, 6, 5};
    // std::for_each(set.begin(), set.end(), [](int x)
    // {
    //     std::cout << x << ' ';
    // });
    std::cout<<*set.begin();
    std::cout << '\n';
}
  • end      返回指向末尾的迭代器
  • cend (C++11)      (public 成员函数)

cbegin()和cend()是C++11新增的，它们返回一个const的迭代器，不能用于修改元素。

  • rbegin      返回指向起始的逆向迭代器

  • crbegin (C++11)      (public 成员函数)

  • rend      返回指向末尾的逆向迭代器
  • crend (C++11)      (public 成员函数)
1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include <iostream>
#include <set>
 
int main()
{
    std::set<unsigned> rep{1, 2, 3, 4, 1, 2, 3, 4};
 
    for (auto it = rep.crbegin(); it != rep.crend(); ++it)
    {
        for (auto n = *it; n > 0; --n)
            std::cout << "⏼" << ' ';
        std::cout << '\n';
    }
}

容量

  • empty      检查容器是否为空
1
2
3
4
5
6
7
8
9
10
11
12
13

#include <iostream>
#include <set>
 
int main()
{
    std::set<int> numbers;
    std::cout << std::boolalpha;
    std::cout << "Initially, numbers.empty(): " << numbers.empty() << '\n';
 
    numbers.insert(42);
    numbers.insert(19937);
    std::cout << "After adding elements, numbers.empty(): " << numbers.empty() << '\n';
}
  • size      返回元素数量
1
2
3
4
5
6
7
8

#include <cassert>
#include <set>
 
int main()
{
    std::set<int> nums{4, 2, 4, 2};
    assert(nums.size() != 2);
}
  • max_size      返回元素的最大可能数量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#include <iostream>
#include <locale>
#include <set>
 
int main()
{
    std::set<char> p;
    std::set<long> q;
 
    // std::cout.imbue(std::locale("en_US.UTF-8"));
    std::cout << std::uppercase
              << "p.max_size() = " << std::dec << p.max_size() << " = 0x"
              << std::hex << p.max_size() << '\n'
              << "q.max_size() = " << std::dec << q.max_size() << " = 0x"
              << std::hex << q.max_size() << '\n';
}

修改器

  • clear      清除内容
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#include <iostream>
#include <string_view>
#include <set>
 
void print_info(std::string_view rem, const std::set<int>& v)
{
    std::cout << rem << "{ ";
    for (const auto& value : v)
        std::cout << value << ' ';
    std::cout << "}\n";
    std::cout << "Size=" << v.size() << '\n';
}
 
int main()
{
    std::set<int> container{1, 2, 3};
    print_info("Before clear: ", container);
    container.clear();
    print_info("After clear: ", container);
}
  • insert      插入元素 或节点 (C++17 起)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <cassert>
#include <iostream>
#include <set>
 
int main()
{
    std::set<int> set;
 
    auto result_1 = set.insert(3);
    assert(result_1.first != set.end()); // it is a valid iterator
    assert(*result_1.first == 3);
    if (result_1.second)
        std::cout << "insert done\n";
 
    auto result_2 = set.insert(3);
    assert(result_2.first == result_1.first); // same iterator
    assert(*result_2.first == 3);
    if (!result_2.second)
        std::cout << "no insertion\n";

    for(auto it:set){
       std:: cout<<it<<"\n";
    }
}
  • insert_range (C++23)      插入元素范围
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include <iostream>
#include <set>
 
void println(auto, auto const& container)
{
    for (const auto& elem : container)
        std::cout << elem << ' ';
    std::cout << '\n';
}
 
int main()
{
    auto container = std::set{1, 3, 2, 4};
    const auto rg = {-1, 3, -2};
// #ifdef __cpp_lib_containers_ranges
//     container.insert_range(rg);
// #else
    container.insert(rg.begin(), rg.end());
// #endif
    println("{}", container);
}
  • emplace (C++11)      就地构造元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

#include <chrono>
#include <cstddef>
#include <functional>
#include <iomanip>
#include <iostream>
#include <string>
#include <set>
 
class Dew
{
private:
    int a, b, c;
 
public:
    Dew(int _a, int _b, int _c)
        : a(_a), b(_b), c(_c)
    {}
 
    bool operator<(const Dew& other) const
    {
        return (a < other.a) ||
               (a == other.a && b < other.b) ||
               (a == other.a && b == other.b && c < other.c);
    }
};
 
constexpr int nof_operations{30};
 
std::size_t set_emplace()
{
    std::set<Dew> set;
    for (int i = 0; i < nof_operations; ++i)
        for (int j = 0; j < nof_operations; ++j)
            for (int k = 0; k < nof_operations; ++k)
                set.emplace(i, j, k);
 
    return set.size();
}
 
std::size_t set_insert()
{
    std::set<Dew> set;
    for (int i = 0; i < nof_operations; ++i)
        for (int j = 0; j < nof_operations; ++j)
            for (int k = 0; k < nof_operations; ++k)
                set.insert(Dew(i, j, k));
 
    return set.size();
}

// Overload operator<< for std::chrono::duration
template <typename Rep, typename Period>
std::ostream& operator<<(std::ostream& os, const std::chrono::duration<Rep, Period>& duration) {
    os << duration.count() << " ";
    if constexpr (std::is_same_v<Period, std::ratio<1>>) {
        os << "seconds";
    } else if constexpr (std::is_same_v<Period, std::milli>) {
        os << "milliseconds";
    } else if constexpr (std::is_same_v<Period, std::micro>) {
        os << "microseconds";
    } else if constexpr (std::is_same_v<Period, std::nano>) {
        os << "nanoseconds";
    } else if constexpr (std::is_same_v<Period, std::ratio<60>>) {
        os << "minutes";
    } else if constexpr (std::is_same_v<Period, std::ratio<3600>>) {
        os << "hours";
    } else {
        os << "custom time unit";
    }
    return os;
}
 
void time_it(std::function<int()> set_test, std::string what = "")
{
    const auto start = std::chrono::system_clock::now();
    const auto the_size = set_test();
    const auto stop = std::chrono::system_clock::now();
    const std::chrono::duration<double, std::milli> time = stop - start;
    if (!what.empty() && the_size)
        std::cout << std::fixed << std::setprecision(2)
                  << time << " for " << what << '\n';
}
 
int main()
{
    time_it(set_insert, "cache warming...");
    time_it(set_insert, "insert");
    time_it(set_insert, "insert");
    time_it(set_emplace, "emplace");
    time_it(set_emplace, "emplace");
}
  • emplace_hint (C++11)      使用提示就地构造元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

#include <chrono>
#include <cstddef>
#include <functional>
#include <iomanip>
#include <iostream>
#include <set>
 
const int n_operations = 100050;
 
std::size_t set_emplace()
{
    std::set<int> set;
    for (int i = 0; i < n_operations; ++i)
        set.emplace(i);
    return set.size();
}
 
std::size_t set_emplace_hint()
{
    std::set<int> set;
    auto it = set.begin();
    for (int i = 0; i < n_operations; ++i)
    {
        set.emplace_hint(it, i);
        it = set.end();
    }
    return set.size();
}
 
std::size_t set_emplace_hint_wrong()
{
    std::set<int> set;
    auto it = set.begin();
    for (int i = n_operations; i > 0; --i)
    {
        set.emplace_hint(it, i);
        it = set.end();
    }
    return set.size();
}
 
std::size_t set_emplace_hint_corrected()
{
    std::set<int> set;
    auto it = set.begin();
    for (int i = n_operations; i > 0; --i)
    {
        set.emplace_hint(it, i);
        it = set.begin();
    }
    return set.size();
}
 
std::size_t set_emplace_hint_closest()
{
    std::set<int> set;
    auto it = set.begin();
    for (int i = 0; i < n_operations; ++i)
        it = set.emplace_hint(it, i);
    return set.size();
}
 
template <typename Rep, typename Period>
std::ostream& operator<<(std::ostream& os, const std::chrono::duration<Rep, Period>& duration) {
    os << duration.count() << " ";
    if constexpr (std::is_same_v<Period, std::ratio<1>>) {
        os << "seconds";
    } else if constexpr (std::is_same_v<Period, std::milli>) {
        os << "milliseconds";
    } else if constexpr (std::is_same_v<Period, std::micro>) {
        os << "microseconds";
    } else if constexpr (std::is_same_v<Period, std::nano>) {
        os << "nanoseconds";
    } else if constexpr (std::is_same_v<Period, std::ratio<60>>) {
        os << "minutes";
    } else if constexpr (std::is_same_v<Period, std::ratio<3600>>) {
        os << "hours";
    } else {
        os << "custom time unit";
    }
    return os;
}


double time_it(std::function<std::size_t()> set_test,
               const char* what = nullptr,
               double ratio = 0.0)
{
    const auto start = std::chrono::system_clock::now();
    const std::size_t setsize = set_test();
    const auto stop = std::chrono::system_clock::now();
    const std::chrono::duration<double, std::milli> time = stop - start;
    if (what != nullptr && setsize > 0)
        std::cout << std::setw(8) << time << " for " << what << " (ratio: "
                  << (ratio == 0.0 ? 1.0 : ratio / time.count()) << ")\n";
    return time.count();
}
 
int main()
{
    std::cout << std::fixed << std::setprecision(2);
    time_it(set_emplace); // cache warmup
    const auto x = time_it(set_emplace, "plain emplace");
    time_it(set_emplace_hint, "emplace with correct hint", x);
    time_it(set_emplace_hint_wrong, "emplace with wrong hint", x);
    time_it(set_emplace_hint_corrected, "corrected emplace", x);
    time_it(set_emplace_hint_closest, "emplace using returned iterator", x);
}
  • erase      擦除元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include <set>
#include <iostream>
 
int main()
{
    std::set<int> c = {1, 2, 3, 4, 1, 2, 3, 4};
 
    auto print = [&c]
    {
        std::cout << "c = { ";
        for (int n : c)
            std::cout << n << ' ';
        std::cout << "}\n";
    };
    print();
 
    std::cout << "Erase all odd numbers:\n";
    for (auto it = c.begin(); it != c.end();)
    {
        if (*it % 2 != 0)
            it = c.erase(it);
        else
            ++it;
    }
    print();
 
    std::cout << "Erase 1, erased count: " << c.erase(1) << '\n';
    std::cout << "Erase 2, erased count: " << c.erase(2) << '\n';
    std::cout << "Erase 2, erased count: " << c.erase(2) << '\n';
    print();
}
  • swap      交换内容
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

#include <functional>
#include <iostream>
#include <set>
 
template<class Os, class Co>
Os& operator<<(Os& os, const Co& co)
{
    os << '{';
    for (auto const& i : co)
        os << ' ' << i;
    return os << " } ";
}
 
int main()
{
    std::set<int> a1{3, 1, 3, 2}, a2{5, 4, 5};
 
    auto it1 = std::next(a1.begin());
    auto it2 = std::next(a2.begin());
 
    const int& ref1 = *(a1.begin());
    const int& ref2 = *(a2.begin());
 
    std::cout << a1 << a2 << *it1 << ' ' << *it2 << ' ' << ref1 << ' ' << ref2 << '\n';
    a1.swap(a2);
    std::cout << a1 << a2 << *it1 << ' ' << *it2 << ' ' << ref1 << ' ' << ref2 << '\n';
 
    // Note that every iterator referring to an element in one container before the swap
    // refers to the same element in the other container after the swap. Same is true
    // for references.
 
    struct Cmp : std::less<int>
    {
        int id{};
        Cmp(int i) : id{i} {}
    };
 
    std::set<int, Cmp> s1{ {2, 2, 1, 1}, Cmp{6}}, s2{ {4, 4, 3, 3}, Cmp{9}};
 
    std::cout << s1 << s2 << s1.key_comp().id << ' ' << s2.key_comp().id << '\n';
    s1.swap(s2);
    std::cout << s1 << s2 << s1.key_comp().id << ' ' << s2.key_comp().id << '\n';
 
    // So, comparator objects (Cmp) are also exchanged after the swap.
}
  • extract (C++17)      从容器中提取节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include <algorithm>
#include <iostream>
#include <string_view>
#include <set>
 
void print(std::string_view comment, const auto& data)
{
    std::cout << comment;
    for (auto datum : data)
        std::cout << ' ' << datum;
 
    std::cout << '\n';
}
 
int main()
{
    std::set<int> cont{1, 2, 3};
 
    print("Start:", cont);
 
    // Extract node handle and change key
    auto nh = cont.extract(1);
    nh.value() = 4;
 
    print("After extract and before insert:", cont);
 
    // Insert node handle back
    cont.insert(std::move(nh));
 
    print("End:", cont);
}
  • merge (C++17)      从另一个容器拼接节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include <iostream>
#include <set>
 
// print out a container
template<class Os, class K>
Os& operator<<(Os& os, const std::set<K>& v)
{
    os << '[' << v.size() << "] {";
    bool o{};
    for (const auto& e : v)
        os << (o ? ", " : (o = 1, " ")) << e;
    return os << " }\n";
}
 
int main()
{
    std::set<char>
        p{'C', 'B', 'B', 'A'}, 
        q{'E', 'D', 'E', 'C'};
 
    std::cout << "p: " << p << "q: " << q;
 
    p.merge(q);
 
    std::cout << "p.merge(q);\n" << "p: " << p << "q: " << q;
}

查找

  • count      返回匹配特定键的元素数量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

#include <functional>
#include <iostream>
#include <set>
 
struct S
{
    int x;
    S(int i) : x{i} { std::cout << "S{" << i << "} "; }
    bool operator<(S const& s) const { return x < s.x; }
};
 
struct R
{
    int x;
    R(int i) : x{i} { std::cout << "R{" << i << "} "; }
    bool operator<(R const& r) const { return x < r.x; }
};
 
bool operator<(R const& r, int i) { return r.x < i; }
bool operator<(int i, R const& r) { return i < r.x; }
 
int main()
{
    std::set<int> t{3, 1, 4, 1, 5};
    std::cout << t.count(1) << ", " << t.count(2) << ".\n";
 
    std::set<S> s{3, 1, 4, 1, 5};
    std::cout << ": " << s.count(1) << ", " << s.count(2) << ".\n";
        // Two temporary objects S{1} and S{2} were created.
        // Comparison function object is defaulted std::less<S>,
        // which is not transparent (has no is_transparent member type).
 
    std::set<R, std::less<>> r{3, 1, 4, 1, 5};
    std::cout << ": " << r.count(1) << ", " << r.count(2) << ".\n";
        // C++14 heterogeneous lookup; temporary objects were not created.
        // Comparator std::less<void> has predefined is_transparent.
}
  • find      查找具有特定键的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#include <iostream>
#include <set>
 
struct LightKey
{
    int x;
};
 
struct FatKey
{
    int x;
    int data[1000]; // a heavy blob
};
 
// As detailed above, the container must use std::less<> (or other transparent
// Comparator) to access these overloads. This includes standard overloads,
// such as comparison between std::string and std::string_view.
bool operator<(const FatKey& fk, const LightKey& lk) { return fk.x < lk.x; }
bool operator<(const LightKey& lk, const FatKey& fk) { return lk.x < fk.x; }
bool operator<(const FatKey& fk1, const FatKey& fk2) { return fk1.x < fk2.x; }
 
int main()
{
    // Simple comparison demo.
    std::set<int> example{1, 2, 3, 4};
 
    if (auto search = example.find(2); search != example.end())
        std::cout << "Found " << (*search) << '\n';
    else
        std::cout << "Not found\n";
 
    // Transparent comparison demo.
    std::set<FatKey, std::less<>> example21, {2, {}}, {3, {}}, {4, {}}};
 
    LightKey lk = {2};
    if (auto search = example2.find(lk); search != example2.end())
        std::cout << "Found " << search->x << '\n';
    else
        std::cout << "Not found\n";
}
  • contains (C++20)      检查容器是否包含具有特定键的元素
1
2
3
4
5
6
7
8
9
10
11
12
13

#include <iostream>
#include <set>
 
int main()
{
    std::set<int> example{1, 2, 3, 4};
 
    for (int x : {2, 5})
        if (example.contains(x))
            std::cout << x << ": Found\n";
        else
            std::cout << x << ": Not found\n";
}

  • equal_range      返回与特定键匹配的元素范围

  • lower_bound      返回指向第一个不小于给定键的元素的迭代器

  • upper_bound      返回指向第一个大于给定键的元素的迭代器

观察器

  • key_comp      返回比较键的函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include <iostream>
#include <set>
#include <utility>
 
// Example module 97 key compare function
struct ModCmp
{
    bool operator()(int lhs, int rhs) const
    {
        return (lhs % 97) < (rhs % 97);
    }
};
 
int main()
{
    std::set<int, ModCmp> cont{1, 2, 3, 4, 5};
 
    auto comp_func = cont.key_comp();
 
    for (const int key : cont)
    {
        const bool before = comp_func(key, 100);
        const bool after = comp_func(100, key);
 
        std::cout << '(' << key << ") ";
        if (!before && !after)
            std::cout << "equivalent to key (100)\n";
        else if (before)
            std::cout << "goes before key (100)\n";
        else if (after)
            std::cout << "goes after key (100)\n";
        else 
            std::cout << "unreachable\n";
            // std::unreachable();
            
    }
    
}
  • value_comp      返回比较 value_type 类型对象中的键的函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#include <iostream>
#include <set>
#include <utility>
 
// Example module 97 key compare function
struct ModCmp
{
    bool operator()(int lhs, int rhs) const
    {
        return (lhs % 97) < (rhs % 97);
    }
};
 
int main()
{
    std::set<int, ModCmp> cont{1, 2, 3, 4, 5};
 
    // Same behaviour as key_comp()
    auto comp_func = cont.value_comp();
 
    for (const int val{100}; const int key : cont)
    {
        const bool before = comp_func(key, val);
        const bool after = comp_func(val, key);
 
        std::cout << "Key (" << key << ") ";
        if (!before && !after)
            std::cout << "equivalent to key (" << val << ")\n";
        else if (before)
            std::cout << "goes before key (" << val << ")\n";
        else if (after)
            std::cout << "goes after key (" << val << ")\n";
        else
            std::unreachable();
    }
}

非成员函数

  • operator==
  • operator!=（在 C++20 中移除）
  • operator<（在 C++20 中移除）      按字典顺序比较两个 set 的值
  • operator<= （在 C++20 中移除）     
  • operator> （在 C++20 中移除）     （函数模板）
  • operator>= （在 C++20 中移除）
  • operator<=> (C++20)

参考

CATALOG