C++ 判断集合成员|🧐

前言

之前我们讲到，哈希表的主要作用是判断给定的整数是否存在于给定的数据中, 哈希表常使用的数据结构有数组、set集合、map映射, 上节课我们学习了数组作为哈希表，这节课我们来学习set集合, 具体包括下列内容

set、``unordered_set, multiset `的概念和特点
set、``unordered_set, multiset `的基本操作，比如创建、插入、删除、查找
迭代器iterator

Set

关于unordered_set,multiset 的区别，，可以移步至代码随想录官方网站查看

和数学中的集合一样，C++中的集合set用于允许存储一组不重复的元素, 并且元素的值按照有序排列， set基于红黑树实现，支持高效的关键字查询操作, 可以用来检查一个给定关键字是否在set中。

无序集合unordered-set类似于集合（Set），但不会按照元素的值进行排序，而是由哈希函数的结果决定的。

multiset 则是一个用于存储一组元素，允许元素重复，并按照元素的值进行有序排列的集合。

集合	底层实现	是否有序	数值是否可以重复
std::set	红黑树	有序	否
std::multiset	红黑树	有序	是
std::unordered_set	哈希表	无序	否

Set的使用

使用集合set需要先引入头文件

// 引入<unordered_set>头文件
#include <unordered_set>
// 引入set头文件
#include <set>

创建一个集合的写法如下

// 创建一个存储整数的无序集合
unordered_set<int> mySet;
// 创建一个存储整数的set
set<int> mySet;
// 创建一个存储整数的 multiset
multiset<int> myMultiSet;

想要向集合中插入元素需要使用insert()方法

 // 向集合中插入元素
mySet.insert(1);
mySet.insert(2);
mySet.insert(3);

想要往集合中删除元素需要使用erase方法

mySet.erase(1);

find() 方法用于查找特定元素是否存在于集合中，如果 find() 方法找到了要查找的元素，它会返回指向该元素的迭代器，如果未找到要查找的元素，它会返回一个指向集合的 end() 的迭代器，表示未找到。通过比较find()方法返回的迭代器是否等于 end()，可以确定集合中是否有查找的元素。

// 判断元素是否在集合中, 只要不等于end(), 说明元素在集合中
if (mySet.find(i) != mySet.end()) {
}

代码编写

根据题目要求，先把代码的基础结构书写完成

#include <iostream>
#include <unordered_set>
using namespace std;
int main() {
  int k, m // k组测试数据, m代表需要集合的数量
  cin >> k;
  while(k--) {
    cin >> m; // 接收集合的数据
  }
}

然后需要创建一个集合，将输入的数据使用insert()方法插入到集合中

unordered_set<int> uset; // 创建一个无序集合
while (n--) {
    cin >> val;
    // 将数据放进set中
    uset.insert(val);
}

判断某个元素是否在集合中，需要使用到find()方法，如果找到了，返回指向元素的迭代器，如果不存在，则最终指向end()的迭代器，通过判断find()的返回结果可以判定元素是否在集合中。

cin >> n; // 输入需要判定的数字n
// 查询n是否在set里
if (uset.find(n) != uset.end()) {
  cout << "YES" << endl; // 在集合中
} else {
  cout << "NO" << endl; // 不在集合中
}

完整代码如下

#include <iostream>
#include <unordered_set>
using namespace std;
int main() {
    int k, n, val, m;
    cin >> k;
    while (k--) {
        cin >> n;
        unordered_set<int> uset; // 创建一个无序集合
        while (n--) {
            cin >> val;
            // 使用insert方法将数据放进set中
            uset.insert(val);
        }
        cin >> m;
        // 使用find()方法查询m是否在set里
        if (uset.find(m) != uset.end()) cout << "YES" << endl;
        else cout << "NO" << endl;
    }

}

延伸

迭代器iterator提供了一种类似指针的接口，可以用来遍历访问容器（比如数组、集合）中的元素，并执行各种操作。

可以理解为，迭代器和下标运算符的作用一样，用来访问容器中的元素，并且迭代器可以从一个元素移动到另外一个元素。

迭代器都拥有名为begin()和end()的成员，表示指向第一个元素和最后一个元素的下一个元素的迭代器（尾后迭代器），如果容器为空，则begin和end返回的是同一个迭代器。

可以使用比较运算符来判断两个迭代器是否相等，如果迭代器想要从一个元素移动到另外一个元素，可以使用递增++运算符和递减--运算符，表示向前（后）移动一个位置。

通过解引用*可以获取迭代器所指的对象，下面的示例表示了vector的遍历。

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

int main() {
    vector<int> myVector = {1, 2, 3, 4, 5};

    // 使用迭代器遍历容器
      // vector<int>::iterator it  用于创建一个能读取<vector>int 元素的迭代器it，最初指向begin()
      // ++it表示迭代器的移动
    for (vector<int>::iterator it = myVector.begin(); it != myVector.end(); ++it) {
        cout << *it << " "; // 通过解引用获取迭代器所指的对象
    }

    cout << endl; 

    return 0;
}