c++ - set_difference、set_intersection 和 set_union 的就地版本

Question

我实现了 set_union、set_intersection 和 set_difference 的版本，它们接受一个排序的容器和一个排序的范围(不能在容器内), 并将运算结果写入容器。

template<class Container, class Iter>
void assign_difference(Container& cont, Iter first, Iter last)
{
    auto new_end = std::set_difference( // (1)
        cont.begin(), cont.end(), first, last, cont.begin());
    cont.erase(new_end, cont.end());
}

template<class Container, class Iter>
void assign_intersection(Container& cont, Iter first, Iter last)
{
    auto new_end = std::set_intersection( // (2)
        cont.begin(), cont.end(), first, last, cont.begin());
    cont.erase(new_end, cont.end());
}

template<class Container, class Iter>
void assign_union(Container& cont, Iter first, Iter last)
{
    auto insert_count = last - first;
    cont.resize(cont.size() + insert_count); // T must be default-constructible
    auto rfirst1 = cont.rbegin() + insert_count, rlast1 = cont.rend();
    auto rfirst2 = std::make_reverse_iterator(last);
    auto rlast2 = std::make_reverse_iterator(first);
    rlast1 = std::set_union( // (3)
        rfirst1, rlast1, rfirst2, rlast2, cont.rbegin(), std::greater<>());
    cont.erase(std::copy(rlast1.base(), cont.end(), cont.begin()), cont.end());
}

目标是:

• 如果容器有足够的容量容纳结果，则不执行分配。
• 否则只执行一次分配，使容器有能力容纳结果。

正如您在标记 (1)、(2) 和 (3) 的行中看到的，同一容器用作这些 STL 算法的输入和输出。假设这些 STL 算法的通常实现，这段代码是有效的，因为它只写入容器中已经处理过的部分。

正如评论中所指出的，标准并不能保证它一定有效。 set_union、set_intersection 和 set_difference 要求结果范围不与输入范围之一重叠。但是，是否可以有一个破坏代码的 STL 实现？

如果您的回答是肯定的，请提供破坏代码的三种使用的 STL 算法之一的符合标准的实现。

Answer 1

符合规范的实现可以检查 set_intersection 的参数 1 和 5 是否相等，以及它们是否正在格式化您的硬盘。

如果你违反了要求，你的程序的行为就不受标准的约束；你的程序格式错误。

在某些情况下，UB 可能值得冒风险和成本(审核所有编译器更改和程序集输出)。我不明白这一点；写你自己的。当您违反要求时，std 库提出的任何花哨的优化都可能导致问题，正如您所注意到的那样，天真的实现很简单。