Boost容器合并咨询：手动插入效率及多集合合并方案

逐个插入方式的效率问题 #

你当前用循环逐个插入的方式，对于boost::container::flat_multiset来说效率并不高：

• flat_multiset底层基于有序动态数组实现，每次insert操作需要先通过二分查找确定插入位置（时间复杂度O(log k)，k为当前set1的元素数），然后移动插入位置后的所有元素（时间复杂度O(k)）
• 合并两个大小为n和m的集合时，总时间复杂度为O(m*(log(n+i) + (n+i)))（i为已插入的元素数），当集合元素较多时，性能损耗会非常明显

更高效的合并方案：利用有序性做归并 #

因为flat_multiset本身是有序容器，两个待合并的集合均处于有序状态，我们可以直接用归并算法合并两个有序序列，时间复杂度仅为O(n+m)，远优于逐个插入。

实现代码示例 #

借助std::merge完成归并，再将结果赋值给目标集合：

#include <algorithm>
#include <boost/container/flat_multiset.hpp>

int main() {
    boost::container::flat_multiset<int> set1 = {1, 2, 3};
    boost::container::flat_multiset<int> set2 = {3, 4, 5};

    // 预分配空间避免动态扩容开销
    boost::container::flat_multiset<int> merged;
    merged.reserve(set1.size() + set2.size());

    // 归并两个有序集合
    std::merge(set1.begin(), set1.end(),
               set2.begin(), set2.end(),
               std::inserter(merged, merged.begin()));

    // 替换原set1
    set1.swap(merged);
}

也可以直接用assign方法简化步骤：

set1.assign(
    std::merge(set1.begin(), set1.end(),
               set2.begin(), set2.end(),
               std::back_inserter(boost::container::flat_multiset<int>()))
);

多集合的合并处理 #

如果需要合并多个flat_multiset，核心思路仍是利用有序性逐步归并：

• 初始化一个空的目标集合，或直接以第一个待合并集合作为初始值
• 遍历所有待合并集合，每次将当前目标集合与下一个集合做归并，更新目标集合
• 若待合并集合数量较多，可使用优先队列维护各集合的当前元素，实现多路归并进一步优化效率

多集合合并示例 #

#include <vector>
#include <algorithm>
#include <boost/container/flat_multiset.hpp>

int main() {
    std::vector<boost::container::flat_multiset<int>> sets = {
        {1,2,3}, {3,4,5}, {5,6,7}
    };

    boost::container::flat_multiset<int> merged;
    if (sets.empty()) return 0;

    merged = sets[0];
    for (size_t i = 1; i < sets.size(); ++i) {
        boost::container::flat_multiset<int> temp;
        temp.reserve(merged.size() + sets[i].size());
        std::merge(merged.begin(), merged.end(),
                   sets[i].begin(), sets[i].end(),
                   std::inserter(temp, temp.begin()));
        merged.swap(temp);
    }
}

内容的提问来源于stack exchange，提问作者Ted Zach