set_difference，set_intersection和set_union的就地版本

我实现了set_union,0 set_intersection和set_difference版本，它们采用已排序的容器和已排序范围（不得在容器内），并将操作结果写入容器。set_difference，set_intersection和set_union的就地版本

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()); 
}

的目标是：如果容器有容纳结果enaugh能力进行

没有分配。
否则正好进行一个分配给容器保存结果的能力。

正如您在标记为（1），（2）和（3）的行中可以看到的那样，相同的容器被用作这些STL算法的输入和输出。假设这些STL算法的通常实现，此代码有效，因为它只写入已经处理的容器部分。

正如在评论中指出，它不是由这个作品的标准保证的。 set_union，set_intersection和set_difference要求所得到的范围不与所述输入范围中的一个重叠。 然而，才会有打破的代码STL实现？

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

来源

2017-06-04 Creep4Play

即使符合标准的实现今天不破坏代码，如果没有标准保证然后简单地升级编译器可能会导致它打破。甚至不同的优化设置或任何其他编译器标志。我想你必须提供你自己的实现来确保tbh。 – Galik

这些算法的实现只需要几行代码，因此您可以编写一个破解代码的代码。 – Creep4Play

对于所有这些算法，我的标准副本具有以下文本：'要求：结果范围不得与原始范围中的任何一个重叠。'我认为您不能保证它可行。 – Blastfurnace

符合的实现可以检查set_intersection的参数1和5是否相等，以及它们是否格式化硬盘驱动器。

如果违反规定，你的程序的行为不被限制标准;你的程序不正常。

在某些情况下，UB可能值得风险和成本（审计所有编译器更改和程序集输出）。我在这里看不到这一点;写你自己的。当你违背需求时，std库所提出的任何花哨的优化都可能导致问题，正如你所指出的那样，简单的实现很简单。

来源

2017-06-04 23:04:40 Yakk

根据经验我用不上你迭代的容器上写的规则。一切都可能发生。总的来说，这很奇怪。

正如@Yakk说，这听起来生病。而已。从你的代码中删除的东西可以安然入睡。

如果你真的需要这些功能，我会建议自己的内部循环来写（如：内的std::set_intersection），以处理你需要为你的算法工作的约束。

我不认为寻求一个不起作用的STL实现是正确的方法。这听起来不像是一个长期的解决方案。从长远来看：标准应该是你的参考，正如有人已经指出的那样，你的解决方案似乎没有妥善处理它。

我的2美分

来源

2017-06-04 23:34:42

set_difference，set_intersection和set_union的就地版本

回答

相关问题