简介

  • C++ 标准库

set

  • set容器定义在头文件中，和map非常相似。
  • 区别在于set保存的不是键值对，在set中本身就是键。如果信息没有显式的键，且希望进行排序(不包含重复)以便快速的执行插入，查找和删除，就可以考虑使用set容器存储此类信息。
  • 不能修改set中元素的键值，因为修改容器中的set元素会破坏顺序。

C++ 标准库

<set> 是 C++ 标准库中的头文件，定义了一组容器类模板，用于实现集合（Set）和关联容器的功能。

std::set：

  • std::set 是一个关联容器，用于存储一组唯一的、已排序的元素。
  • 内部元素按照某个严格弱顺序排列（默认是升序），并且元素值是唯一的。
  • 主要特点：
    • 自动排序：元素按照某个严格弱顺序（由比较函数或默认的 < 运算符决定）自动排序。
    • 唯一性：不允许重复的元素存在。
    • 查找、插入和删除操作的时间复杂度为 O(log n)。
  • 主要操作：
    • insert(const value_type& val): 插入元素 val。
    • erase(const_iterator position): 删除指定位置的元素。
    • find(const value_type& val): 查找元素 val 的位置。
    • size(): 返回集合中元素的数量。
    • empty(): 判断集合是否为空。

示例：

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

#include <iostream>
#include <set>

int main() {
    std::set<int> mySet;

    // 插入元素
    mySet.insert(3);
    mySet.insert(1);
    mySet.insert(5);

    // 查找元素
    auto it = mySet.find(3);
    if (it != mySet.end()) {
        std::cout << "Element found in set" << std::endl;
    }

    // 删除元素
    mySet.erase(1);

    // 输出集合中的元素
    for (const auto& elem : mySet) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

这个示例展示了 std::set 的基本使用方法，包括插入元素、查找元素、删除元素以及遍历输出集合中的元素。

C++ 标准库 详解

<set> 是 C++ 标准库中的头文件，提供了实现关联容器中集合（Set）的类模板。这些集合类模板允许用户存储一组唯一的、已排序的元素。

std::set 和 std::multiset：

  • std::set 和 std::multiset 都是关联容器。
  • std::set 存储一组唯一的已排序元素，每个元素只能出现一次。
  • std::multiset 存储一组已排序的元素，允许元素重复出现。

主要特点：

  • 有序性： 内部元素按照某个严格弱顺序（默认是升序）排列。
  • 唯一性： std::set 中的元素是唯一的，而 std::multiset 允许重复元素存在。
  • 自动排序： 插入新元素时会自动按照严格弱顺序进行排序。
  • 底层实现： 通常使用平衡二叉树（红黑树）来实现。

主要操作：

  • insert(const value_type& val): 插入元素。
  • erase(const_iterator position): 删除指定位置的元素。
  • find(const value_type& val): 查找元素。
  • size(): 返回集合中元素的数量。
  • empty(): 判断集合是否为空。
  • 迭代器支持：可以使用迭代器遍历集合中的元素。

示例：

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

#include <iostream>
#include <set>

int main() {
    // 创建一个 std::set
    std::set<int> mySet = {3, 1, 5, 2, 4};

    // 插入元素
    mySet.insert(6);
    mySet.insert(2); // 重复元素不会被插入

    // 删除元素
    mySet.erase(1);

    // 查找元素
    auto it = mySet.find(3);
    if (it != mySet.end()) {
        std::cout << "Element found in set" << std::endl;
    }

    // 输出集合中的元素
    for (const auto& elem : mySet) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

此示例演示了 std::set 的基本用法，包括创建、插入、删除、查找元素以及遍历输出集合中的元素。

C++ 标准库 常用的类和函数

在 C++ <set> 标准库中，最常用的类包括 std::set 和 std::multiset，它们提供了操作集合的常用函数和方法。

主要类：

  1. std::set：
    • 用于存储一组唯一的、已排序的元素。
    • 特点：
      • 内部元素按照严格弱顺序（默认升序）排列。
      • 元素是唯一的，不允许重复。
    • 主要方法：
      • insert(const value_type& val): 插入元素。
      • erase(const_iterator position): 删除指定位置的元素。
      • find(const value_type& val): 查找元素。
      • size(): 返回集合中元素的数量。
      • empty(): 判断集合是否为空。
  2. std::multiset：
    • 用于存储一组已排序的元素，允许元素重复。
    • 特点：
      • 内部元素按照严格弱顺序（默认升序）排列。
      • 元素允许重复出现。
    • 主要方法与 std::set 类似。

常用方法：

  • insert(const value_type& val): 将元素 val 插入集合。
  • erase(const_iterator position): 删除指定位置的元素。
  • find(const value_type& val): 查找元素 val。
  • size(): 返回集合中元素的数量。
  • empty(): 判断集合是否为空。

示例：

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

#include <iostream>
#include <set>

int main() {
    std::set<int> mySet = {3, 1, 5, 2, 4};
    std::multiset<int> myMultiSet = {3, 1, 5, 2, 2, 4};

    mySet.insert(6);
    myMultiSet.insert(6);

    mySet.erase(1);
    myMultiSet.erase(2);

    auto it = mySet.find(3);
    if (it != mySet.end()) {
        std::cout << "Element found in set" << std::endl;
    }

    std::cout << "Elements in set:";
    for (const auto& elem : mySet) {
        std::cout << " " << elem;
    }
    std::cout << std::endl;

    std::cout << "Elements in multiset:";
    for (const auto& elem : myMultiSet) {
        std::cout << " " << elem;
    }
    std::cout << std::endl;

    return 0;
}

这个示例展示了 std::set 和 std::multiset 的基本用法，包括插入、删除、查找元素以及遍历输出集合中的元素。

std::set

std::set 是 C++ 标准库中定义的关联容器，用于存储一组唯一的、已排序的元素。

主要特点：

  • 有序性： 内部元素按照某个严格弱顺序（默认是升序）排列。
  • 唯一性： std::set 中的元素是唯一的，不允许重复。
  • 自动排序： 插入新元素时会自动按照严格弱顺序进行排序。
  • 底层实现： 通常使用平衡二叉树（红黑树）来实现。

主要操作：

  • insert(const value_type& val): 插入元素。
  • erase(const_iterator position): 删除指定位置的元素。
  • find(const value_type& val): 查找元素。
  • size(): 返回集合中元素的数量。
  • empty(): 判断集合是否为空。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <iostream>
#include <set>

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

    mySet.insert(6);
    mySet.insert(2); // 重复元素不会被插入

    mySet.erase(1);

    auto it = mySet.find(3);
    if (it != mySet.end()) {
        std::cout << "Element found in set" << std::endl;
    }

    for (const auto& elem : mySet) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

在这个示例中，展示了 std::set 的基本使用方法，包括创建、插入、删除、查找元素以及遍历输出集合中的元素。

std::set::find()

std::set::find() 是用于在 std::set 集合中查找特定元素的成员函数。

函数签名：

1
2

iterator find(const key_type& key);
const_iterator find(const key_type& key) const;
  • key：要查找的元素的键值。
  • 返回值：如果找到匹配的元素，则返回指向该元素的迭代器；如果未找到匹配的元素，则返回指向集合末尾的迭代器 end()。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <iostream>
#include <set>

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

    auto it = mySet.find(3);
    if (it != mySet.end()) {
        std::cout << "Element found in set: " << *it << std::endl;
    } else {
        std::cout << "Element not found in set" << std::endl;
    }

    it = mySet.find(6);
    if (it != mySet.end()) {
        std::cout << "Element found in set: " << *it << std::endl;
    } else {
        std::cout << "Element not found in set" << std::endl;
    }

    return 0;
}

在这个示例中，std::set::find() 用于查找集合中的特定元素。如果找到匹配的元素，则返回指向该元素的迭代器；否则返回 end()。

std::multiset

std::multiset 是 C++ 标准库中定义的关联容器，类似于 std::set，但允许元素重复出现。

主要特点：

  • 有序性： 内部元素按照某个严格弱顺序（默认是升序）排列。
  • 允许重复： std::multiset 中的元素可以重复出现，即允许存储相同的元素。
  • 自动排序： 插入新元素时会自动按照严格弱顺序进行排序。
  • 底层实现： 通常使用平衡二叉树（红黑树）来实现。

主要操作：

  • insert(const value_type& val): 插入元素。
  • erase(const_iterator position): 删除指定位置的元素。
  • find(const value_type& val): 查找元素。
  • size(): 返回集合中元素的数量。
  • empty(): 判断集合是否为空。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <iostream>
#include <set>

int main() {
    std::multiset<int> myMultiSet = {3, 1, 5, 2, 2, 4};

    myMultiSet.insert(6);
    myMultiSet.insert(2); // 允许重复元素插入

    myMultiSet.erase(2); // 删除一个 2

    auto it = myMultiSet.find(3);
    if (it != myMultiSet.end()) {
        std::cout << "Element found in multiset" << std::endl;
    }

    for (const auto& elem : myMultiSet) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

这个示例演示了 std::multiset 的基本用法，包括创建、插入、删除、查找元素以及遍历输出集合中的元素。与 std::set 不同的是，std::multiset 允许重复元素的存在。

std::multiset::find()

std::multiset::find() 是用于在 std::multiset 多重集合中查找特定元素的成员函数。

函数签名：

1
2

iterator find(const key_type& key);
const_iterator find(const key_type& key) const;
  • key：要查找的元素的键值。
  • 返回值：如果找到匹配的元素，则返回指向该元素的迭代器；如果未找到匹配的元素，则返回指向集合末尾的迭代器 end()。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <iostream>
#include <set>

int main() {
    std::multiset<int> myMultiSet = {3, 1, 5, 2, 2, 4};

    auto it = myMultiSet.find(3);
    if (it != myMultiSet.end()) {
        std::cout << "Element found in multiset: " << *it << std::endl;
    } else {
        std::cout << "Element not found in multiset" << std::endl;
    }

    it = myMultiSet.find(6);
    if (it != myMultiSet.end()) {
        std::cout << "Element found in multiset: " << *it << std::endl;
    } else {
        std::cout << "Element not found in multiset" << std::endl;
    }

    return 0;
}

在这个示例中，std::multiset::find() 用于查找多重集合中的特定元素。如果找到匹配的元素，则返回指向该元素的迭代器；否则返回 end()。与 std::set 不同，std::multiset 允许元素重复，因此可能会返回多个匹配的元素。