Python及C++中的集合

1. Python 中的集合（set）

1.1 特性

• 无序性：集合中的元素没有顺序，不能通过索引访问。
• 唯一性：集合中的元素不能重复，如果尝试添加重复的元素，集合会自动忽略。
• 可变性：集合是可变的，可以添加或删除元素。
• 基于哈希表实现：集合的底层是哈希表，因此查找、插入和删除操作的平均时间复杂度都是 O(1)。

1.2 创建集合

# 创建空集合
my_set = set()

# 通过列表创建集合
my_set = set([1, 2, 3, 4, 4])  # 结果为 {1, 2, 3, 4}，自动去重

1.3 常见操作

• 添加元素

  my_set.add(5)  # 添加一个元素
  

• 删除元素

  my_set.remove(3)  # 删除元素 3，如果元素不存在会抛出 KeyError
  my_set.discard(3)  # 删除元素 3，如果元素不存在不会报错
  

• 查找元素

  if 2 in my_set:
      print("2 is in the set")
  

• 集合运算
  • 并集

    set1 = {1, 2, 3}
    set2 = {3, 4, 5}
    union_set = set1.union(set2)  # 或者 set1 | set2
    print(union_set)  # 输出 {1, 2, 3, 4, 5}
    

  • 交集

    intersection_set = set1.intersection(set2)  # 或者 set1 & set2
    print(intersection_set)  # 输出 {3}
    

  • 差集

    difference_set = set1.difference(set2)  # 或者 set1 - set2
    print(difference_set)  # 输出 {1, 2}
    

  • 对称差集

    symmetric_difference_set = set1.symmetric_difference(set2)  # 或者 set1 ^ set2
    print(symmetric_difference_set)  # 输出 {1, 2, 4, 5}
    

1.4 应用场景

• 去重：将列表转换为集合可以快速去除重复元素。
• 快速查找：利用集合的 O(1) 查找特性，可以高效地判断某个元素是否存在。
• 集合运算：用于处理集合之间的并集、交集、差集等操作，常用于图论、组合数学等问题。

2. C++ 中的集合（std::set 和 std::unordered_set）

2.1 std::set

• 特性
  • 有序性：集合中的元素会自动按照升序排列。
  • 唯一性：集合中的元素不能重复。
  • 基于红黑树实现：查找、插入和删除操作的时间复杂度为 O(log n)。
• 创建集合

  #include <set>
  std::set<int> my_set;
  

• 常见操作
  • 添加元素

    my_set.insert(5);
    

  • 删除元素

    my_set.erase(3);
    

  • 查找元素

    if (my_set.find(2) != my_set.end()) {
        std::cout << "2 is in the set" << std::endl;
    }
    

  • 遍历集合

    for (int num : my_set) {
        std::cout << num << " ";
    }
    

2.2 std::unordered_set

• 特性
  • 无序性：集合中的元素没有顺序。
  • 唯一性：集合中的元素不能重复。
  • 基于哈希表实现：查找、插入和删除操作的平均时间复杂度为 O(1)。
• 创建集合

  #include <unordered_set>
  std::unordered_set<int> my_unordered_set;
  

• 常见操作
  • 添加元素

    my_unordered_set.insert(5);
    

  • 删除元素

    my_unordered_set.erase(3);
    

  • 查找元素

    if (my_unordered_set.find(2) != my_unordered_set.end()) {
        std::cout << "2 is in the set" << std::endl;
    }
    

2.3 应用场景

• 快速查找：std::unordered_set 的 O(1) 查找特性适合需要快速判断元素是否存在的场景。
• 有序操作：std::set 的有序特性适合需要对元素进行排序或二分查找的场景。
• 去重：两种集合都可以用于去除重复元素。

3. 总结

• Python 的 set：
  • 无序、唯一、基于哈希表实现。
  • 查找、插入、删除操作的平均时间复杂度为 O(1)。
  • 适合快速查找、去重和集合运算。
• C++ 的 std::set：
  • 有序、唯一、基于红黑树实现。
  • 查找、插入、删除操作的时间复杂度为 O(log n)。
  • 适合需要有序操作的场景。
• C++ 的 std::unordered_set：
  • 无序、唯一、基于哈希表实现。
  • 查找、插入、删除操作的平均时间复杂度为 O(1)。
  • 适合快速查找和去重。