set

SET概念

主要特点

1. 唯一元素：set 是一种不允许重复元素的集合，每个元素在集合中只能出现一次。
2. 有序：set 中的元素是按照特定的顺序自动排列的，默认情况下是升序排列。
3. 底层实现：set 通常使用红黑树或其他平衡树结构作为底层实现。
4. 查找效率：由于底层实现为平衡树，set 提供对元素的对数时间复杂度的查找、插入和删除操作。

基本用法

1. 创建和初始化

#include <set>
#include <iostream>

using namespace std;

int main() {
    set<int> s; // 创建一个空的 set

    return 0;
}

2. 元素操作

#include <set>
#include <iostream>

using namespace std;

int main() {
    set<int> s;

    // 插入元素
    s.insert(3);
    s.insert(1);
    s.insert(2);
    s.insert(1); // 插入重复元素不会有任何效果

    // 输出所有元素
    for (int x : s) {
        cout << x << " ";
    }
    cout << endl; // 输出: 1 2 3

    // 查找元素
    if (s.find(2) != s.end()) {
        cout << "2 is in the set." << endl;
    }

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

    // 输出所有元素
    for (int x : s) {
        cout << x << " ";
    }
    cout << endl; // 输出: 2 3

    return 0;
}

3. 迭代器的使用

#include <set>
#include <iostream>

using namespace std;

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

    // 使用迭代器遍历
    for (set<int>::iterator it = s.begin(); it != s.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl; // 输出: 1 2 3 4 5

    // 使用范围 for 循环遍历
    for (int x : s) {
        cout << x << " ";
    }
    cout << endl; // 输出: 1 2 3 4 5

    return 0;
}

常用成员函数

• 元素操作：

  • insert(const T& value)：插入一个元素，如果元素已存在，则不会重复插入。
  • erase(const T& value)：删除指定的元素。
  • find(const T& value)：查找指定的元素，返回指向该元素的迭代器，如果未找到则返回 end()。

• 状态检查：

  • empty()：检查 set 是否为空，返回布尔值。
  • size()：返回 set 中元素的数量。

• 迭代器：

  • begin()：返回指向第一个元素的迭代器。
  • end()：返回指向 set 尾部之后的位置的迭代器。

• 其他操作：

  • count(const T& value)：返回集合中与 value 匹配的元素的数量（set 中要么是 0，要么是 1）。
  • lower_bound(const T& value)：返回指向第一个不小于 value 的元素的迭代器。
  • upper_bound(const T& value)：返回指向第一个大于 value 的元素的迭代器。
  • equal_range(const T& value)：返回一个 pair，包含 value 的 lower_bound 和 upper_bound 迭代器。

MAP概念

类似于py里面的字典

主要特点

1. 键值对存储：map 存储的是键值对，每个元素由一个键和一个对应的值组成。
2. 唯一键：map 中的每个键都是唯一的，不允许重复。如果插入一个已有键的元素，会更新该键的值。
3. 有序：map 中的键是按照特定的顺序自动排列的，默认情况下是升序排列。
4. 底层实现：map 通常使用红黑树或其他平衡树结构作为底层实现。
5. 查找效率：由于底层实现为平衡树，map 提供对元素的对数时间复杂度的查找、插入和删除操作。

基本用法

1. 创建和初始化

#include <map>
#include <iostream>

using namespace std;

int main() {
    map<int, string> m; // 创建一个空的 map

    return 0;
}