为什么没有std :: inplace_merge_unique？

我试过寻找一个算法，会做什么std::inplace_merge 其次std::unique会做。看起来效率更高，可以在1遍中完成，而不是在2中。无法在标准库中找到它，或者无法通过搜索。为什么没有std :: inplace_merge_unique？

那么有没有在不同名称下的提升实现？
这样的算法是否可能（从某种意义上说它与普通的inplace_merge具有相同的复杂性保证）？

来源

2014-12-06 NoSenseEtAl

这样的算法很容易实现。您可以轻松地在合并排序的合并步骤中放置元素。 – kay 2014-12-06 16:33:19

用boost来模拟这个有点不好的方法是Boost.Range函数'boost :: inplace_merge'和'uniqued'适配器的组合。如果范围迭代并且不会增加额外的N个步骤，这将会延迟'unique'到点。尽管离完美还很远。 – pmr 2014-12-06 16:36:35

pmr，你确定吗？感觉像范围将首先inplace_merged，然后uniqued？由于编译器/提升不知道这两个可以融合 – NoSenseEtAl 2014-12-06 16:41:42

它不是在原地操作，但假设前面的范围都不包含重复项，std::set_union将找到与合并后跟唯一的结果相同的结果。

来源

2014-12-06 16:36:04

这是选项之一我认为，但它不是现在...我现在发现的最好的东西，再加上1 – NoSenseEtAl 2014-12-06 17:24:25

算法部分缺少许多有趣的算法。斯捷潘诺夫认为STL的原始提交并不完整，有些算法甚至被删除。 Alexander Stepanov和Meng Lee的proposal似乎没有包括算法inplace_merge_unique()或其任何变体。

为什么没有这种算法的一个潜在原因是，不清楚哪个元素应该被丢弃：因为比较只是一个严格的弱排序，所以元素的选择很重要。实施inplace_merge_unique()一种方法是

使用std::remove_if()上，以去除从第二范围重复的任何元件。
使用inplace_merge()来做实际的合并。

对std::remove_if()的判断将跟踪要合并的序列的第一部分中的当前位置。下面的代码没有经过测试，但类似的东西应该可以工作：

template <typename BiDirIt, typename Comp> 
BiDirIt inplace_merge_unique(BiDirIt begin, BiDirIt middle, BiDirIt end, Comp comp) { 
    using reference = typename std::iterator_traits<BiDirIt>::reference; 
    BiDirIt result = std::remove_if(middle, end, [=](reference other) mutable -> bool { 
      begin = std::find_if(begin, middle, [=](reference arg)->bool { 
        return !comp(arg, other); 
       }); 
      return begin != middle && !comp(other, *begin); 
     }); 
    std::inplace_merge(begin, middle, result, comp); 
    return result; 
}

来源

2014-12-15 03:25:47

为什么没有std :: inplace_merge_unique？

回答

相关问题