系列文章目录

点击直达——文章总目录

C++ STL源码剖析 11-set multiset

Overview

1.set multiset

在C++标准模板库（STL）中，std::set和std::multiset是两种不同的关联容器，它们都基于平衡二叉树实现（通常是红黑树），但有一些关键的区别：

1.1.std::set

std::set是一个有序不重复元素的集合。它不允许插入重复的元素，如果尝试插入一个已存在的值，插入操作将不会执行。

主要特性：

• 唯一性：不允许有重复的元素。
• 排序：元素默认按照升序排列，可以通过自定义比较函数来改变排序方式。
• 效率：插入、删除和查找操作的时间复杂度为O(log n)。

示例代码：

#include 
#include 

int main() {
    std::set<int> mySet;

    // 插入元素
    mySet.insert(10);
    mySet.insert(5);
    mySet.insert(20);

    // 尝试插入重复元素
    mySet.insert(10); // 不会插入

    // 遍历set
    for (const int& value : mySet) {
        std::cout << value << " ";
    }
    // 输出: 5 10 20

    return 0;
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22

1.2.std::multiset

std::multiset与std::set类似，但它允许插入重复的元素。

主要特性：

• 重复性：允许有重复的元素。
• 排序：元素默认按照升序排列，可以通过自定义比较函数来改变排序方式。
• 效率：插入、删除和查找操作的时间复杂度为O(log n)。

示例代码：

#include 
#include 

int main() {
    std::multiset<int> myMultiSet;

    // 插入元素
    myMultiSet.insert(10);
    myMultiSet.insert(5);
    myMultiSet.insert(10); // 允许插入重复元素

    // 遍历multiset
    for (const int& value : myMultiSet) {
        std::cout << value << " ";
    }
    // 输出: 5 10 10

    return 0;
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19

1.3.选择std::set还是std::multiset？

• 如果你需要保证元素的唯一性，选择std::set。
• 如果你需要允许元素重复，选择std::multiset。
• 对于两者，都可以通过传递一个自定义比较函数来控制元素的排序方式。

1.4.自定义比较函数

如果你想自定义元素的排序方式，可以在声明std::set或std::multiset时提供一个比较函数。

示例代码：

#include 
#include 

// 自定义比较函数
struct CustomCompare {
    bool operator()(int lhs, int rhs) const {
        return lhs > rhs; // 降序排列
    }
};

int main() {
    std::set<int, CustomCompare> mySet;

    // 插入元素
    mySet.insert(10);
    mySet.insert(5);
    mySet.insert(20);

    // 遍历set
    for (const int& value : mySet) {
        std::cout << value << " ";
    }
    // 输出: 20 10 5

    return 0;
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26

通过使用std::set和std::multiset，你可以有效地管理有序的元素集合，无论是唯一还是重复的元素。

2.std::multiset 在插入元素时，如果元素的顺序被打乱了，我该如何恢复它的排序顺序？

std::multiset 在插入元素时会自动根据元素的值进行排序，以保持元素的有序状态。通常情况下，你不需要手动恢复它的排序顺序，因为插入操作会立即将元素放置在正确的位置以维持排序。

如果你的意思是插入一系列元素后，std::multiset 的元素顺序与预期不符，这通常是因为插入的元素没有按照 std::multiset 的默认排序规则（通常是元素类型的 < 操作符定义的顺序）来排列。

如果你需要按照不同的顺序对 std::multiset 进行排序，你可以：

1. 使用自定义比较函数：在创建 std::multiset 时提供一个自定义比较函数来改变排序逻辑。

struct MyCompare {
    bool operator()(const int& a, const int& b) const {
        // 自定义排序逻辑
        return /* 你的排序条件 */;
    }
};

std::multiset<int, MyCompare> myMultiSet;

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8

2. 插入后重新排序：如果已经插入了元素，但需要按照不同的顺序重新排序，你可以将 std::multiset 的元素复制到一个新容器中，然后使用 std::sort 函数进行排序。

#include 
#include 
#include 

std::multiset<int> myMultiSet;
// 插入元素...

// 复制到vector
std::vector<int> vec(myMultiSet.begin(), myMultiSet.end());

// 使用自定义排序规则进行排序
std::sort(vec.begin(), vec.end(), [](int a, int b) {
    // 自定义排序逻辑
    return /* 你的排序条件 */;
});

// 清空原multiset并重新插入排序后的元素
myMultiSet.clear();
for (int elem : vec) {
    myMultiSet.insert(elem);
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21

请注意，std::multiset 的设计初衷是保持元素的有序状态，所以如果你需要经常改变排序规则，可能需要考虑其他数据结构，如 std::vector 或 std::list，它们允许更灵活的排序操作。

如果你的意思是插入元素后，std::multiset 的内部顺序被某种外部因素打乱了，那么这是不可能的，因为 std::multiset 会保证每次插入操作后元素都是有序的。如果遇到这种情况，可能是代码中存在其他问题，需要进一步检查。

3.std::multiset 在插入元素时的性能如何，有没有可能影响程序的效率？

std::multiset 是 C++ STL 中的一种关联容器，它允许存储多个相同值的元素，并且会自动按照一定的顺序对元素进行排序。std::multiset 的底层实现通常是红黑树，这种自平衡的二叉搜索树能够保证在插入和删除操作时保持较高的效率，时间复杂度为 O(log n)。

3.1.插入性能

在插入元素时，std::multiset 会根据元素的键值进行排序，并找到适当的位置插入新元素。由于 std::multiset 允许重复元素，它不会检查元素是否已经存在，而是直接插入。插入操作的性能通常很高，因为红黑树的结构能够保持元素有序，从而避免了额外的排序开销。

3.2.性能优化

尽管 std::multiset 的插入性能已经非常优秀，但在处理大量数据时，仍然可以通过以下方式进一步优化性能：

1. 批量插入：如果需要插入大量元素，可以考虑使用批量插入的方法，这样可以减少树的调整次数。

2. 预留空间：如果已知将要插入的元素数量，可以在插入之前使用 reserve() 函数预留足够的空间，这样可以减少容器在增长过程中的重新分配次数。

3. 自定义比较函数：通过提供一个自定义比较函数，可以改变元素的排序方式，从而可能提高特定情况下的插入效率。

4. 并行插入：在多核处理器上，可以考虑使用并行算法来同时处理多个插入操作，但这通常需要额外的工作来管理并发和同步。

5. 避免频繁删除：频繁的删除操作可能会导致树的重新平衡，这可能会影响插入操作的性能。如果需要删除大量元素，可以考虑先收集要删除的元素，然后一次性删除。

6. 使用适当的数据结构：如果对插入性能有极端要求，可以考虑使用其他数据结构，如 std::unordered_multiset，它基于哈希表实现，提供了平均时间复杂度为 O(1) 的插入操作。

3.3.性能瓶颈

在某些情况下，std::multiset 可能会遇到性能瓶颈：

1. 大量重复元素：如果插入的元素中有大量重复值，可能会导致树的某些节点有很多子节点，这可能会影响性能。

2. 内存分配：如果容器需要频繁地重新分配内存以容纳更多元素，这可能会导致性能下降。

3. 系统资源限制：在资源受限的环境下，如嵌入式系统或内存限制严格的系统，std::multiset 的性能可能会受到影响。

总的来说，std::multiset 是一个非常高效的容器，适用于需要保持元素有序且允许重复元素的场景。通过合理的优化和适当的使用，可以确保程序的效率。

4.在使用std:multiset时，有哪些常见的错误或问题需要避免？

在使用 std::multiset 时，以下是一些常见的错误或问题，以及如何避免它们：

1. 误解插入操作：

   • 错误：认为 std::multiset 不会处理重复元素。
   • 正确：std::multiset 允许重复元素，并且会根据元素的值自动排序。

2. 错误使用迭代器：

   • 错误：在容器修改（如插入或删除）后未更新迭代器。
   • 正确：容器的迭代器在修改操作后可能会变得无效，需要重新获取迭代器。

3. 性能问题：

   • 错误：在循环中使用成员函数 insert() 插入大量元素，导致频繁的树旋转和重新平衡。
   • 正确：可以使用 insert() 批量插入元素，或者使用 emplace() 来避免额外的拷贝或移动。

4. 使用默认排序：

   • 错误：假设 std::multiset 会按照自定义的方式排序元素。
   • 正确：std::multiset 默认使用元素的 < 操作符进行排序。如果需要自定义排序，需要在声明时提供自定义比较函数。

5. 错误地处理范围插入：

   • 错误：使用范围插入时，错误地处理了迭代器范围。
   • 正确：确保提供的迭代器范围是有效的，并且包含在要插入的序列中。

6. 内存使用：

   • 错误：未考虑 std::multiset 可能比 std::vector 使用更多内存。
   • 正确：了解 std::multiset 的内存开销，因为它需要额外的空间来维护元素的排序。

7. 并发访问：

   • 错误：在没有适当同步的情况下，从多个线程访问和修改 std::multiset。
   • 正确：在多线程环境中，需要使用互斥锁或其他同步机制来保护共享数据。

8. 错误地使用 count 函数：

   • 错误：使用 count 函数来检查元素是否存在，而 std::multiset 中可能存在多个相同的元素。
   • 正确：使用 count 函数时要知道它返回的是元素出现的次数，而不是一个布尔值。

9. 错误地使用 erase 函数：

   • 错误：错误地使用 erase 函数，例如尝试删除不存在的元素。
   • 正确：确保在调用 erase 之前，元素确实存在，或者使用 erase 返回的下一个迭代器。

10. 未考虑元素的相等性：

    • 错误：在比较元素时，只比较了元素的一部分，而忽略了其他可能相等的部分。
    • 正确：确保比较函数能够正确处理所有可能的相等情况。

11. 未考虑元素的键值提取：

    • 错误：在使用 std::multiset 的键值提取函数（如 lower_bound、upper_bound）时，未正确定义键值。
    • 正确：确保键值提取函数与自定义比较函数（如果有的话）一致。

通过避免这些常见的错误和问题，你可以更有效地使用 std::multiset 来管理有序的元素集合。

5.我在使用std:set时遇到了性能瓶颈，有什么优化技巧可以提高它的效率吗？

在使用 std::set 时遇到性能瓶颈，可以考虑以下优化技巧来提高效率：

1. 预先分配内存：如果已知将要插入的元素数量，可以使用 reserve() 来预先分配足够的内存空间，减少在插入过程中的动态内存分配次数。

2. 使用 emplace 而非 insert：emplace 可以直接在容器中构造元素，避免了额外的复制或移动操作，这可能更高效。

3. 批量插入：如果需要插入大量元素，可以考虑先使用一个临时容器（如 std::vector）收集所有元素，然后一次性插入到 std::set 中，这样可以减少树的重新平衡次数。

4. 自定义比较函数：如果默认的比较函数不够高效或者不符合需求，可以提供一个自定义比较函数来改变排序逻辑，可能会提高性能。

5. 减少查找操作：频繁的查找操作可能会成为性能瓶颈，可以通过缓存结果或者使用更合适的数据结构来优化。

6. 使用 unordered_set：如果元素的唯一性和有序性不是严格要求的，可以考虑使用 std::unordered_set，它基于哈希表实现，提供了平均时间复杂度为 O(1) 的插入和查找性能。

7. 避免频繁的删除操作：频繁删除元素可能会导致树的频繁重新平衡，如果需要删除大量元素，可以考虑先收集要删除的元素，然后一次性删除。

8. 并行插入：如果环境支持并发操作，可以考虑使用并行算法来同时处理多个插入操作，但这通常需要额外的工作来管理并发和同步。

9. 避免在遍历过程中修改容器：在遍历 std::set 时进行插入或删除操作会导致迭代器失效，应该先记录需要插入或删除的元素，遍历完成后再进行修改。

10. 使用适当的数据结构：如果 std::set 的性能仍然不满足需求，可以考虑使用其他数据结构，如 std::vector 或 std::list，它们可能在某些特定场景下提供更好的性能。

通过这些优化技巧，可以在不同的场景下提高 std::set 的性能，使其在查找和插入操作上更加高效。

6.在什么情况下应该使用 std::unordered_set 而不是 std::set？

std::unordered_set 和 std::set 都是 C++ STL 提供的集合容器，但它们在内部实现和性能特性上有显著差异。以下是一些你应该考虑使用 std::unordered_set 而不是 std::set 的情况：

1. 不关心元素顺序：

   • 如果你不关心元素的排序顺序，只关心元素的存在性，那么 std::unordered_set 是更好的选择。

2. 查找性能：

   • std::unordered_set 提供平均时间复杂度为 O(1) 的查找性能，因为它是基于哈希表实现的。
   • 如果你的应用中查找操作非常频繁，并且对查找性能有较高要求，那么 std::unordered_set 更适合。

3. 插入性能：

   • 与查找类似，std::unordered_set 提供平均时间复杂度为 O(1) 的插入性能。
   • 如果你的应用中插入操作非常频繁，并且对插入性能有较高要求，那么 std::unordered_set 更适合。

4. 内存使用：

   • 如果内存使用是一个关键因素，并且你愿意牺牲有序性来换取更少的内存占用，那么 std::unordered_set 可能更合适，因为它通常比 std::set 使用更少的内存。

5. 大量元素：

   • 当处理大量元素时，std::unordered_set 通常比 std::set 更高效，因为它不需要维护元素的有序性。

6. 不需要有序遍历：

   • 如果你不需要有序遍历容器中的元素，那么使用 std::unordered_set 更合适。

7. 元素具有良好哈希函数：

   • 如果元素类型已经有一个良好的哈希函数，或者你可以为元素类型提供一个高效的哈希函数，那么 std::unordered_set 可以提供更好的性能。

8. 并发读写：

   • 在某些实现中，std::unordered_set 可能比 std::set 更容易支持并发读写操作，因为哈希表的并发访问通常比平衡树的并发访问更容易实现。

9. 快速内存分配：

   • std::unordered_set 的内存分配通常是连续的，这可能有助于提高内存访问的局部性和缓存命中率。

10. 避免删除操作导致的性能问题：

    • 在 std::set 中，删除操作可能需要树的重新平衡，这可能影响性能。而在 std::unordered_set 中，删除操作通常不会影响其他元素的位置。

在选择使用 std::unordered_set 还是 std::set 时，需要根据具体的应用场景和性能要求来决定。如果元素的有序性对你的应用至关重要，那么 std::set 可能是更好的选择。如果元素的查找和插入性能更加关键，并且不需要元素的有序性，那么 std::unordered_set 可能更适合。

关于作者

• 微信公众号:WeSiGJ
• GitHub:https://github.com/wesigj/cplusplusboys
• CSDN:https://blog.csdn.net/wesigj
• 微博:
• -版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。