C++：从范围中删除重复值

标准模板库（Standard Template Library，STL）演示了对于基于结构的算法的复杂性，我们应该如何应付，也就是分隔它们。那正是我们有容器（std::vector，std::deque，std::list等等）和算法的原因。为尽可能做到泛型，算法要对范围（元素序列）进行处理。也就是说，如果愿意，算法可以只应用于向量的前一半元素。

经常都要从一个范围中删除重复值，STL为此提供了相应的工具，这就是std::unique算法。但std::unique需要一个排好序的范围。它检查连续的两个元素是否相等，如果有两个相等但不连续的元素，后一个元素就不会被删除。所以，如果你有一个未排序的范围，但又希望保持未排序状态（大多数时候都会如此），std::unique就变得毫无用处。

本文介绍如何实现一个泛型的stable_unique，它适用于任何范围。删除重复值后，剩余元素的顺序会得以保持。如果一个元素在同一个范围中多次出现，那么只有第一次出现的才会被保留；其他的会被删除。

更妙的是，stable_unique不仅容易使用，还提供了和你熟悉的STL算法类似的接口。这里并不打算重复别人做过的工作。stable_unique一方面非常高效，另一方面还尽可能利用了现成的STL算法。

std::unique行为

为了理解我们对stable_unique的要求，先来研究一下std::unique，看看用它能达到什么目标。清单A展示一个简单的例子，它尝试在向量中删除重复值。虽然成功完成任务，但元素原来的顺序丢失了，因为必须先对向量进行排序。

这便为我们指明了正确的方向：对元素排序，但保留它们的原始顺序。因此，要对元素指针进行排序。

实现mstable_unique

下面是实现stable_unique的步骤：

1. 创建一个数组（aPtr）来容纳元素指针
2. 对指针数组进行排序
3. 对指针数组调用std::unique
4. 对那些被std::unique删除的元素，把它们从原始范围中删除

为达到步骤4的要求，aPtr中的每个元素除了要包含到一个元素的指针，还必须包含它的索引（这样才知道要删除什么）。下面更详细地解释一下。假定我们不容纳任何索引，那么将拥有指向要删除的每个元素的指针。接着必须遍历原始范围，直到找到元素。伪代码如清单B所示。这样做的代价十分高昂；而这正是选择保留一个索引的原因。