爲什麼沒有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？

回答

相關問題