实现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的实现似乎要困难得多，如果可能的话，我宁愿不要使用implement this myself。

有没有一种方法可以使用现有的算法来实现最优的partition_unique和stable_ partition_unique算法？

Answer 1

创建一个队列来保存副本。然后，从索引1开始初始化两个索引src和dest，并遍历列表。如果当前项(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有一个队列。它是否有类似上面的算法，我不知道。