跳转到内容

C++multiset

来自代码酷

模板:Note

C++ multiset 容器[编辑 | 编辑源代码]

multiset是C++标准模板库(STL)中的一个关联容器，它存储的元素按照特定排序准则自动排序，且允许存在重复元素。作为set容器的扩展版本，multiset在需要处理重复有序数据的场景中非常有用。

基本特性[编辑 | 编辑源代码]

multiset具有以下关键特性：

  • 元素自动排序（默认升序）
  • 允许存储重复元素
  • 基于红黑树实现，提供O(log n)的查找、插入和删除操作
  • 元素不可直接修改（需先删除再插入）

数学上，multiset可以表示为：M={a1,a2,...,an|ai≤ai+1}

头文件与声明[编辑 | 编辑源代码]

使用multiset需要包含头文件： 

#include <set>

基本声明语法： 

std::multiset<数据类型> 容器名称;

构造函数[编辑 | 编辑源代码]

multiset提供多种构造函数：

构造函数 描述
multiset<T> m 默认构造函数
multiset<T> m(comp) 使用自定义比较器
multiset<T> m(begin, end) 通过迭代器范围构造
multiset<T> m(other) 拷贝构造函数

示例： 

// 默认构造
std::multiset<int> nums;

// 自定义排序（降序）
auto cmp = [](int a, int b) { return a > b; };
std::multiset<int, decltype(cmp)> descendingNums(cmp);

// 从数组初始化
int arr[] = {5, 2, 8, 2, 5};
std::multiset<int> fromArray(arr, arr + 5);

常用成员函数[编辑 | 编辑源代码]

容量相关[编辑 | 编辑源代码]

  • empty() - 检查是否为空
  • size() - 返回元素数量
  • max_size() - 返回可能的最大元素数

修改操作[编辑 | 编辑源代码]

  • insert(const T& value) - 插入元素
  • erase(iterator pos) - 删除指定位置元素
  • erase(const T& value) - 删除所有等于value的元素
  • clear() - 清空容器

查找操作[编辑 | 编辑源代码]

  • find(const T& value) - 查找元素
  • count(const T& value) - 统计特定值出现次数
  • lower_bound(const T& value) - 返回第一个不小于value的迭代器
  • upper_bound(const T& value) - 返回第一个大于value的迭代器
  • equal_range(const T& value) - 返回等于value的范围

代码示例[编辑 | 编辑源代码]

基本操作示例[编辑 | 编辑源代码]

#include <iostream>
#include <set>

int main() {
    std::multiset<int> scores = {85, 90, 78, 90, 82};
    
    // 插入元素
    scores.insert(88);
    scores.insert(90); // 允许重复
    
    // 遍历输出
    std::cout << "All scores: ";
    for(int s : scores) {
        std::cout << s << " ";
    }
    std::cout << "\n";
    
    // 统计特定分数出现次数
    std::cout << "Number of 90s: " << scores.count(90) << "\n";
    
    // 删除第一个90
    auto it = scores.find(90);
    if(it != scores.end()) {
        scores.erase(it);
    }
    
    return 0;
}

输出： 

All scores: 78 82 85 88 90 90 90 
Number of 90s: 3

高级查找示例[编辑 | 编辑源代码]

#include <iostream>
#include <set>

int main() {
    std::multiset<int> data = {10, 20, 30, 30, 30, 40, 50};
    
    // 使用equal_range查找所有30
    auto range = data.equal_range(30);
    
    std::cout << "All 30s: ";
    for(auto it = range.first; it != range.second; ++it) {
        std::cout << *it << " ";
    }
    std::cout << "\n";
    
    // 使用lower_bound和upper_bound
    std::cout << "Elements >=25 and <=35: ";
    for(auto it = data.lower_bound(25); it != data.upper_bound(35); ++it) {
        std::cout << *it << " ";
    }
    
    return 0;
}

输出： 

All 30s: 30 30 30 
Elements >=25 and <=35: 30 30 30

实际应用案例[编辑 | 编辑源代码]

成绩统计系统[编辑 | 编辑源代码]

multiset非常适合需要处理重复有序数据的场景，如学生成绩统计： 

#include <iostream>
#include <set>
#include <string>

struct Student {
    std::string name;
    int score;
    
    bool operator<(const Student& other) const {
        return score < other.score;
    }
};

int main() {
    std::multiset<Student> classA;
    
    // 添加学生成绩（允许同分）
    classA.insert({"Alice", 88});
    classA.insert({"Bob", 92});
    classA.insert({"Charlie", 88});
    classA.insert({"David", 85});
    
    // 输出按分数排序的学生列表
    std::cout << "Students ranked by score:\n";
    for(const auto& s : classA) {
        std::cout << s.name << ": " << s.score << "\n";
    }
    
    // 查找88分的学生
    auto range = classA.equal_range({"", 88});
    std::cout << "\nStudents with 88 points:\n";
    for(auto it = range.first; it != range.second; ++it) {
        std::cout << it->name << "\n";
    }
    
    return 0;
}

输出： 

Students ranked by score:
David: 85
Alice: 88
Charlie: 88
Bob: 92

Students with 88 points:
Alice
Charlie

实时数据流处理[编辑 | 编辑源代码]

multiset可用于维护实时数据流的中位数： 

#include <iostream>
#include <set>

class MedianTracker {
    std::multiset<int> data;
    
public:
    void addNumber(int num) {
        data.insert(num);
    }
    
    double getMedian() {
        if(data.empty()) return 0.0;
        
        auto size = data.size();
        auto it = data.begin();
        std::advance(it, size/2);
        
        if(size % 2 == 1) {
            return *it;
        } else {
            auto prev = it;
            --prev;
            return (*prev + *it) / 2.0;
        }
    }
};

int main() {
    MedianTracker tracker;
    int stream[] = {5, 3, 7, 2, 8, 4, 9, 1, 6};
    
    for(int num : stream) {
        tracker.addNumber(num);
        std::cout << "Current median: " << tracker.getMedian() << "\n";
    }
    
    return 0;
}

输出： 

Current median: 5
Current median: 4
Current median: 5
Current median: 4
Current median: 5
Current median: 4.5
Current median: 5
Current median: 4.5
Current median: 5

性能分析[编辑 | 编辑源代码]

multiset的常见操作时间复杂度如下：

gantt title multiset操作时间复杂度 dateFormat X axisFormat %s section 基本操作 查找 : 0, 5 : O(log n) 插入 : 5, 10 : O(log n) 删除单个元素 : 10, 15 : O(log n) 删除所有匹配元素 : 15, 20 : O(log n + k), k为匹配元素数 section 范围操作 遍历范围 : 20, 25 : O(k), k为范围内元素数 equal_range : 25, 30 : O(log n)

与相关容器比较[编辑 | 编辑源代码]

特性 multiset set unordered_multiset
是 | 是 | 否
是 | 否 | 是
红黑树 | 红黑树 | 哈希表
O(log n) | O(log n) | O(1)
排序顺序 | 排序顺序 | 无特定顺序

最佳实践[编辑 | 编辑源代码]

1. 选择合适的比较器：默认是升序排列，但可以通过自定义比较器改变排序方式 

   struct CaseInsensitiveCompare {
       bool operator()(const std::string& a, const std::string& b) const {
           return std::lexicographical_compare(
               a.begin(), a.end(),
               b.begin(), b.end(),
               [](char c1, char c2) {
                   return tolower(c1) < tolower(c2);
               });
       }
   };
   
   std::multiset<std::string, CaseInsensitiveCompare> words;

2. 高效删除：当需要删除特定值的所有实例时，使用erase(val)比循环删除更高效

3. 范围查询优化：对于连续范围查询，使用lower_bound()和upper_bound()组合

4. 内存考虑：multiset的每个元素都有额外开销（树节点结构），在内存敏感场景需谨慎使用

常见问题[编辑 | 编辑源代码]

Q: 为什么不能直接修改multiset中的元素？ A: 直接修改会破坏内部的红黑树结构。正确做法是先删除旧元素，再插入新元素。

Q: multiset和priority_queue有什么区别？ A: priority_queue只提供对最大/最小元素的快速访问，而multiset允许访问任意元素并保持全局有序。

Q: 如何获取multiset的第N个元素？ A: 使用std::next(m.begin(), N-1)，但注意这是O(N)操作。

总结[编辑 | 编辑源代码]

multiset是C++ STL中一个强大的有序容器，特别适合需要处理重复元素且保持有序的场景。通过红黑树实现，它在插入、删除和查找操作上都能保持较好的对数时间复杂度。理解multiset的特性和正确使用方法，可以显著提高涉及有序数据处理的程序效率和简洁性。

检索自“https://wiki.echo.cool/index.php?title=C%2B%2Bmultiset&oldid=573”