c++ - 合并两个 std::set 和(尚未)std::set::merge()

Question

我刚刚写了这段代码:

// Somewhere earlier, the equivalent of this happens.
std::set<T> a;
std::set<T> b;
FillMeUp(a);
FillMeUp(b);

// Later, in another function that sees a and b, this happens.
std::set<T> c;
std::set_union(a.begin(), a.end(),
               b.begin(), b.end(),
               std::inserter(c, c.begin()));
a.swap(c);

重点是第二段代码，在某些情况下，想把a和b合并成a。

(出于动机:我有一个带有集合的对象数组。我遍历该数组。如果满足某个条件，我正在查看的对象基本上复制了我之前看到的对象，所以我想将其集合合并到之前的集合中。)

C++17 中有一个名为 std::set::merge 的新函数，但我的 g++ 5.3.1 显然不知道它(说 g++ 5.3.1 用 -std=c++17 调用)。

真正的问题是，我能否做得比现在做得更好？

Answer 1

正式地，std::set::merge 定义在 draft standard 中:

Attempts to extract each element in a2 and insert it into a using the comparison object of a. In containers with unique keys, if there is an element in a with key equivalent to the key of an element from a2, then that element is not extracted from a2.

复杂度为:

N log(a.size()+ N) where N has the value a2.size().

因为这与 insert 的重载之一的复杂性相匹配:

template< class InputIt >
void insert( InputIt first, InputIt last );

这听起来像是 insert 的美化包装:

a.insert(b.begin(), b.end());