集合容器(set container in STL)

C++程序设计第十四章标准模板库(STL) 集合容器(set container in STL)

组别：提高级
难度：5

集合是一个元素有序且不重合的容器。一般使用平衡树作为底层数据结构。

集合(set)的基本操作

成员函数(member function)	overview
st.empty()	判断是否为空
st.size()	返回集合中元素个数
st.clear()	擦除所有元素
st.insert(value)	在集合中插入元素
st.erase(value)	从集合中删除给定值的元素
st.erase(postion)	从集合中删除位于position位置的元素
st.erase(first, last)	从集合中删除迭代器范围为[first, last-1]中的元素
st.find(value)	从集合中给定值对应的迭代器，如果不存在则返回end()
st.count(value)	查询一个给定值在集合中的个数，因为是不可重集，所以个数不超过1
st.lower_bound(value)	查询集合中不小于给定值的迭代器，如果不存在则返回end()
st.upper_bound(value)	查询集合中大于给定值的迭代器，如果不存在则人返回end()
st.swap(st1)	交换两个集合的值

/**************************************************************** 
 * Description: C++  set
 * Author: Alex Li
 * Date: 2024-11-23 18:00:29
 * LastEditTime: 2024-11-23 18:02:52
****************************************************************/
#include <iostream>  
#include <set>  
using namespace std;
int main() {  
    set<int> mySet;  
  
    // 插入元素  
    mySet.insert(3);  
    mySet.insert(1);  
    mySet.insert(4);  
    mySet.insert(1); // 不会插入重复的元素  
  
    // 遍历并打印元素  
    for (int num : mySet) {  
        cout << num << " ";  
    }  
    cout << std::endl; // 输出: 1 3 4  
  
    // 查找元素  
    if (mySet.find(3) != mySet.end()) {  
        cout << "Found 3 in the set." <<endl;  
    }  
  
    // 删除元素  
    mySet.erase(4);  
  
    // 再次遍历并打印元素  
    for (int num : mySet) {  
        cout << num << " ";  
    }  
    cout <<endl; // 输出: 1 3  
  
    return 0;  
}

`unordered_set`（无序集合）

1. 定义

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

unordered_set 是 C++11 引入的 无序关联容器。
特点：存储唯一元素（不允许重复），查找速度快，但不保证顺序。

2. 底层实现

使用 哈希表（hash table） 作为底层数据结构。
通过元素的哈希值决定它落在哪个“桶（bucket）”里。
当桶内冲突发生时，通常用 链表/拉链法（或开放寻址）解决。

3. 主要性质

无序性：元素存放位置由哈希值决定，遍历时顺序不可预测，也与插入顺序不同。
唯一性：与 set 一样，不允许重复元素。
快速查找：平均情况下，查找 / 插入 / 删除都是 O(1)。

4. 时间复杂度

平均情况：
- 插入：O(1)
- 删除：O(1)
- 查找：O(1)
最坏情况：
- O(n)（当所有元素都哈希到同一个桶时）。
实际使用中，只要哈希函数设计合理，性能非常接近常数时间。

5. 内存开销

unordered_set 为了降低冲突，会预留较多空桶。
因此通常比 set 更耗内存。

6. 常用操作

unordered_set<int> us;

// 插入
us.insert(10);
us.insert(20);

// 查找
if (us.find(10) != us.end()) {
    cout << "Found\n";
}

// 删除
us.erase(20);

// 遍历（顺序不可预测）
for (auto x : us) {
    cout << x << " ";
}

7. 适用场景

只关心“有没有”，不关心顺序。
大量查找/插入操作，希望比 set 更快。
例如：统计单词是否出现过、判断某个值是否存在于大数据集合中。

✅一句话总结：
unordered_set 是基于哈希表的 无序集合，
优点是 平均 O(1) 的插入、查找、删除，
缺点是 顺序不可控，内存占用可能较大。

多重集合(multiset)

multiset是维护有序可重集合的容器，基本操作与set类似，以下是其特殊方法。

多重集合特有方法

成员函数	功能
ms.erase(value)	从集合中删除给定值的所有元素
ms.equal_range(value)	查询一个给定值在集合中出现的范围，用pair的形式返回迭代器对

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

int main(){
    set<int> st0;  //创建一个集合
    set<int> st1= {6, 10, 5, 1}; // 创建一个有初始值的集合
    set<int,greater<int> > st2; //创建一个集合，元素降序
    multiset<int> st3;  //创建一个多重集合
    
    st0.insert(4);
    st0.insert(3);
    st0.insert(6);
    st0.insert(9);
    st0.insert(5);
    st0.insert(6);
    
    st2.insert(5);
    st2.insert(7);
    st2.insert(3);
    
    st3.insert(5);
    st3.insert(7);
    st3.insert(5);
    
    cout<<st0.size()<<'\n';
    for( auto i:st0)cout<<i<<' ';
    cout<<'\n';
    
    st0.swap(st1);  //交投st0和st1中的元素
    for( auto i:st0)cout<<i<<' ';
    cout<<'\n';
    
    for(auto i:st1)cout<<i<<' ';    
    cout<<'\n';
    
    for(auto i:st2)cout<<i<<' ';    
    cout<<'\n';
    
    for(auto i:st3)cout<<i<<' ';    
    
    
}

Previous Topic

Back to Lesson

Next Topic

C++程序设计