partition_uniqueとstable_partition_uniqueのアルゴリズムを実装する

Question

私は、それぞれの重複する要素の前にすべての一意の要素が存在するように順序付き要素のセットを分割する方法を探していますが、std::uniqueは重複した要素が上書きされるため適用できません。std::partition 。このアルゴリズムpartition_uniqueを呼び出すと、対応するstable_partition_unique（つまりstable_partitionのような）も必要です。

partition_unique

の基本的な実装は、次のとおり

#include <vector> 
#include <iostream> 

int main() 
{ 
    std::vector<int> vals {1, 1, 2, 4, 5, 5, 5, 7, 7, 9, 10}; 

    const auto it = partition_unique(std::begin(vals), std::end(vals)); 

    std::cout << "Unique values: "; 
    std::copy(std::begin(vals), it, std::ostream_iterator<int> {std::cout, " "}); // Unique values: 1 10 2 4 5 9 7 
    std::cout << '\n' << "Duplicate values: "; 
    std::copy(it, std::end(vals), std::ostream_iterator<int> {std::cout, " "}); // Duplicate values: 7 5 5 1 
} 

対応stable_partition_unqiueがstd::stable_partitionとstd::partitionを交換することによって達成することができる。

#include <algorithm> 
#include <iterator> 
#include <unordered_set> 
#include <functional> 

template <typename BidirIt, typename BinaryPredicate = std::equal_to<void>> 
BidirIt partition_unique(BidirIt first, BidirIt last, BinaryPredicate p = BinaryPredicate {}) 
{ 
    using ValueTp = typename std::iterator_traits<BidirIt>::value_type; 

    std::unordered_set<ValueTp, std::hash<ValueTp>, BinaryPredicate> seen {}; 
    seen.reserve(std::distance(first, last)); 

    return std::partition(first, last, 
          [&p, &seen] (const ValueTp& value) { 
           return seen.insert(value).second; 
          }); 
} 

ように使用することができます。

これらのアプローチの問題点は、std::unordered_set（すべてハッシュ関数要件を追加）のすべての一意の値を不必要にバッファリングすることです。この要素は、要素のソート時には不要である必要があります。 partition_uniqueの実装を考え出すのはあまり手間がかかりませんが、stable_partition_uniqueの実装はかなり難しいようです。可能であれば、私はむしろimplement this myselfではないでしょう。

partition_uniqueアルゴリズムとstable_ partition_uniqueアルゴリズムを最適化するための既存のアルゴリズムを使用する方法はありますか？

Answer 1

重複を保持するキューを作成します。次に、インデックス1から始まる2つのインデックスsrcとdestを初期化し、リストを通過します。現在のアイテム（list[src]）が前のアイテム（list[dest-1]）と等しい場合は、それをキューにコピーします。それ以外の場合は、list[dest]にコピーし、を増やしてください。

リストを使い果たしたら、キューから元のリストの末尾にアイテムをコピーします。私はSTLのキューを持って知っている

Queue dupQueue 
int src = 1 
int dest = 1 
while (src < list.count) 
{ 
    if (list[src] == list[dest-1]) 
    { 
     // it's a duplicate. 
     dupQueue.push(list[src]) 
    } 
    else 
    { 
     list[dest] = list[src] 
     ++dest 
    } 
    ++src 
} 
while (!dupQueue.IsEmpty) 
{ 
    list[dest] = dupQueue.pop() 
    ++dest 
} 

：よう

何か。上記に類似したアルゴリズムを持っているかどうかはわかりません。