实现partition_unique和stable_partition_unique算法

Question

我正在寻找一种方法来分区一组有序元素，以便所有唯一元素都出现在它们各自的重复之前，注意到std::unique不适用，因为重复元素被覆盖，我想使用 std::partition.调用这个算法partition_unique，我还需要相应的stable_partition_unique（即喜欢stable_partition）。

partition_unique的基本实现是：

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

可以像这样使用：

#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来实现。

这些方法的问题在于它们不必要地缓冲std::unordered_set中的所有唯一值（这也增加了哈希函数要求），这在元素排序时不应该是必需的。为partition_unique提出更好的实现并不需要太多的工作，但是实现stable_partition_unique似乎要困难得多，如果可能的话，我宁愿自己不实现。

有没有办法利用现有的算法来实现最优partition_unique和stable_ partition_unique算法？

Answer 1

创建一个队列来保存重复项。然后，初始化两个索引，src和dest，从索引 1 开始，并浏览列表。如果当前项 （ list[src] ） 等于前一项 （ list[dest-1] ），则将其复制到队列中。否则，请将其复制到 list[dest] 并递增dest 。

用

尽列表后，将队列中的项目复制到原始列表的尾部。

像这样：

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
}

我知道STL有一个队列。它是否有类似于上述的算法，我不知道。