如何高效地保留重复项？

Question

给定一个STL向量，输出排序后的重复项，例如：

INPUT : { 4, 4, 1, 2, 3, 2, 3 }
OUTPUT: { 2, 3, 4 }

这个算法很简单，但目标是使其效率与std::unique()一样高。我天真的实现直接在容器中进行修改：

我天真的实现：

void not_unique(vector<int>* pv)
{
    if (!pv)
        return;

 // Sort (in-place) so we can find duplicates in linear time
 sort(pv->begin(), pv->end());

 vector<int>::iterator it_start = pv->begin();
 while (it_start != pv->end())
 {
  size_t nKeep = 0;

  // Find the next different element
  vector<int>::iterator it_stop = it_start + 1;
  while (it_stop != pv->end() && *it_start == *it_stop)
  {
   nKeep = 1; // This gets set redundantly
   ++it_stop;
  }

  // If the element is a duplicate, keep only the first one (nKeep=1).
  // Otherwise, the element is not duplicated so erase it (nKeep=0).
  it_start = pv->erase(it_start + nKeep, it_stop);
 }
}

如果你能让这个更加高效、优雅或通用，请让我知道。例如，自定义排序算法，或在第二次循环中复制元素以消除erase()调用。

- Marc Eaddy

---

std::unique() 假设向量已排序。你能提供一些具体的原因，说明为什么你认为你的代码不够高效吗？ - Artem Sokolov

只是挑选你所拥有的：通过引用获取容器。在这里使用指针没有理由（例如，keep_duplicates(0) 也不安全）。函数内部的代码和调用函数都会简化一些。 :) - GManNickG

这不是O(n)。由于while循环内部具有线性复杂度的erase，使其变成了O(n^2)。 - James McNellis

@GMan：我总是通过指针传递输出参数来表示它们可以被修改。这样，当用户看到像“foo(a, b, &c, &d);”这样的函数调用时，他们不必阅读文档就知道哪些参数是输入和输出。缺点是实现稍微复杂了一些，就像你指出的那样（是的，它应该检查是否为空）。 - Marc Eaddy

你如何将此内容插入到 void not_unique(vector<int>* pv) 中？ - Alain Rist

Answer 1

我第一次尝试惨败了，我以为std::unique会将所有重复的元素移动到范围的末尾（实际上并不会）。糟糕。这里是另一个尝试：

这是not_unique的实现。它删除在排序范围内仅出现一次的任何元素，并删除任何出现多次的元素的副本。因此，结果范围是出现多次的唯一元素列表。

该函数具有线性复杂度，并且对范围进行单次遍历（std::unique具有线性复杂度）。It必须满足前向迭代器的要求。返回结果范围的末尾。

template <typename It>
It not_unique(It first, It last)
{
    if (first == last) { return last; }

    It new_last = first;
    for (It current = first, next = ++first; next != last; ++current, ++next)
    {
        if (*current == *next)
        {
            if (current == new_last)
            {
                ++new_last;
            }
            else
            {
                *new_last++ = *current;
                while (next != last && *current == *next)
                {
                    ++current;
                    ++next;
                }
                if (next == last)
                    return new_last;
            }
        }
    }
    return new_last;
}

- James McNellis

---

+1 希望你不介意，但我在我的答案中给了它全部的内容。 （话虽如此，在我写作时我使用的是previous/current而不是current/next，所以我保留了那个。但除此之外，你写的内部部分很好。） - GManNickG

当范围需要排序时，我通常喜欢在开头添加一个 is_sorted（以防万一...）。可以使用 adjacent_find 和反向二元谓词很容易地编写它。 - Matthieu M.

@Matthieu：调用函数的前提条件是范围已排序（std::unique也有相同的前提条件）。我同意，调试断言对于捕获逻辑错误很有用。@GMan：我完全不介意。看起来不错。 - James McNellis

@Marc: 很好的发现。我不应该在半夜写代码 :-). 比较语句 *current != *new_last 是无效的，因为 *new_last 将永远不会是结果范围的有效部分。这可以通过比较 *current != *(new_last - 1) 来轻松地纠正，但那会要求随机访问迭代器。我已更新算法以修复它，使其适用于前向迭代器，但现在有点复杂 :-O。我可能有些时间今晚看一下它并清理它。 - James McNellis

请看一下我的解决方案，这是我从您的原始方案中改编而来的，请告诉我它是否有效。 - Marc Eaddy

Answer 2

你甚至可以使用不匹配的方式，获得额外的分数！顺便说一句：好的练习。

template<class TIter>
/** Moves duplicates to front, returning end of duplicates range.
 *  Use a sorted range as input. */
TIter Duplicates(TIter begin, TIter end) {
    TIter dup = begin;
    for (TIter it = begin; it != end; ++it) {
        TIter next = it;
        ++next;
        TIter const miss = std::mismatch(next, end, it).second;
        if (miss != it) {
            *dup++ = *miss;
            it = miss;
        }
    }
    return dup;
}

- Jan

Answer 3

比以前的版本更短，更类似于STL。假定输入已排序。

#include <algorithm>
#include <functional>

template< class I, class P >
I remove_unique( I first, I last, P pred = P() ) {
    I dest = first;
    while (
        ( first = std::adjacent_find( first, last, pred ) )
            != last ) {
        * dest = * first;
        ++ first;
        ++ dest;
        if ( ( first = std::adjacent_find( first, last, std::not2( pred ) ) )
            == last ) break;
        ++ first;
    }
    return dest;
}

template< class I >
I remove_unique( I first, I last ) {
    return remove_unique( first, last,
        std::equal_to< typename std::iterator_traits<I>::value_type >() );
}

- Potatoswatter

---

+1；非常好。我之前不熟悉adjacent_find。很遗憾这个问题已经变成社区维护的了。 - James McNellis

@James：谢谢。我之前错过了Jan的“mismatch”条目，我认为那可能更优雅。如果我使用boost::bind将交替标志绑定到std::equal_to而不是交替使用not2，我的方法会更好。但也许会更慢。 - Potatoswatter

Answer 4

这是标准库的风格。算法的功劳归功于詹姆斯！（如果你给我+1，你最好也给他+1，否则后果自负）。我所做的只是让它符合标准库的风格：

#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <vector>

// other stuff (not for you)
template <typename T>
void print(const char* pMsg, const T& pContainer)
{
    std::cout << pMsg << "\n    ";
    std::copy(pContainer.begin(), pContainer.end(),
        std::ostream_iterator<typename T::value_type>(std::cout, " "));
    std::cout << std::endl;
}

template <typename T, size_t N>
T* endof(T (&pArray)[N])
{
    return &pArray[0] + N;
}

// not_unique functions (for you)
template <typename ForwardIterator, typename BinaryPredicate>
ForwardIterator not_unique(ForwardIterator pFirst, ForwardIterator pLast,
                           BinaryPredicate pPred)
{
    // correctly handle case where an empty range was given:
    if (pFirst == pLast) 
    { 
        return pLast; 
    }

    ForwardIterator result = pFirst;
    ForwardIterator previous = pFirst;

    for (++pFirst; pFirst != pLast; ++pFirst, ++previous)
    {
        // if equal to previous
        if (pPred(*pFirst, *previous))
        {
            if (previous == result)
            {
                // if we just bumped bump again
                ++result;
            }
            else if (!pPred(*previous, *result))
            {
                // if it needs to be copied, copy it
                *result = *previous;

                // bump
                ++result;
            }
        }
    }

    return result;
}

template <typename ForwardIterator>
ForwardIterator not_unique(ForwardIterator pFirst, ForwardIterator pLast)
{
    return not_unique(pFirst, pLast,
                std::equal_to<typename ForwardIterator::value_type>());
}


//test
int main()
{
    typedef std::vector<int> vec;

    int data[] = {1, 4, 7, 7, 2, 2, 2, 3, 9, 9, 5, 4, 2, 8};
    vec v(data, endof(data));

    // precondition
    std::sort(v.begin(), v.end());
    print("before", v);

    // duplicatify (it's a word now)
    vec::iterator iter = not_unique(v.begin(), v.end());
    print("after", v);

    // remove extra
    v.erase(iter, v.end());
    print("erased", v);
}

- GManNickG

---

James算法中唯一困扰我的事情是我们没有检查它是否已经排序。然而，通过要求二进制谓词是sort操作使用的谓词（而不是相等谓词），我们可以实现它。 - Matthieu M.

@Matthieu：谢谢。嗯，这是一个前提条件。就像在“unique”中一样。 - GManNickG

我添加了守卫条款来处理 first == last 的情况，以便语义与空范围的 unique 相匹配。 除此之外，看起来非常好。 - James McNellis

这对于 { 4, 4, 1, 2, 3, 4, 2, 4, 3 } 不起作用。输出应该是 { 2, 3, 4 }，但实际上是 { 2, 3, 4, 4, 4 }。 - Marc Eaddy

Answer 5

我的建议是改进插入排序算法，这样你就可以同时对重复项进行排序和过滤。

- James Curran

Answer 6

我认为从大O的角度来看，您已经实现得很好了。最主要的成本是排序，其时间复杂度为 O(N log N)。另一种可能性是，建立一个包含重复项的新向量，而不是使用现有向量，并通过删除非重复项来删除它们。但是，仅当重复项的数量相对于总条目数较小时，这才更好。

考虑极端情况。如果原始数组由1000个条目组成，只有一个重复项，则输出将是仅具有一个值的向量。创建只包含一个条目的新向量可能会更有效，而不是从原始向量中删除其他999个条目。然而，我怀疑在实际测试中，这种更改带来的节省可能难以衡量。

编辑 我刚才在考虑这个问题时是从“面试”问题的角度来思考的。换句话说，这不是一个非常有用的答案。但是可以使用存储空间而不是 CPU，在 O(N)（线性时间）而不是 O(N Log N) 的时间内解决这个问题。创建两个“位”数组，并将它们最初清除。循环遍历整数值的向量。在第一个位数组中查找每个值。如果未设置，则设置该位（将其设置为1）。如果已设置，则在第二个数组中设置相应的位（表示重复）。处理完所有向量条目后，扫描第二个数组并输出重复的整数（由第二个位数组中设置的位表示）。使用位数组的原因仅是为了节省空间。如果处理 4 字节的整数，则所需的原始空间为 (2 * 2^32 / 8 )。但是，通过将其转换为稀疏数组，实际上可以将其变成可用的算法。伪代码如下：

bitarray1[infinite_size];
bitarray2[infinite_size];

clear/zero bitarrays

// NOTE - do not need to sort the input
foreach value in original vector {
    if ( bitarray1[value] ) 
        // duplicate
        bitarray2[value] = 1
    bitarray1[value] = 1
}

// At this point, bitarray2 contains a 1 for all duplicate values.
// Scan it and create the new vector with the answer
for i = 0 to maxvalue
    if ( bitarray2[i] )
        print/save/keep i

- Mark Wilkins

Answer 7

在 while 循环中调用 "erase(it_start + keep, it_stop);" 会导致重复地复制剩余的元素。

我建议将所有唯一的元素交换到向量的前面，然后一次性删除其余的元素。

int num_repeats(vector<int>::const_iterator curr, vector<int>::const_iterator end) {
  int same = *curr;
  int count = 0;
  while (curr != end && same == *curr) {
    ++curr;
    ++count;
  }
  return count;
}

void dups(vector<int> *v) {
  sort(v->begin(), v->end());
  vector<int>::iterator current = v->begin();
  vector<int>::iterator end_of_dups = v->begin();
  while (current != v->end()) {
    int n = num_repeats(current, v->end());
    if (n > 1) {
      swap(*end_of_dups, *current);
      end_of_dups++;
    }
    current += n;
  }
  v->erase(end_of_dups, v->end());
}

- Stephen

Answer 8

另一个：

template <typename T>
void keep_duplicates(vector<T>& v) 
{
    set<T> 
        u(v.begin(), v.end()), // unique 
        d; // duplicates
    for (size_t i = 0; i < v.size(); i++)
        if (u.find(v[i]) != u.end())
            u.erase(v[i]);
        else
            d.insert(v[i]);

    v = vector<T>(d.begin(), d.end());
}

- Alain Rist

---

好的解决方案，但当n很大（10B）时，不够内存或空间高效。在所有元素都是唯一的情况下，u是v的完全副本（考虑所有动态分配！）。创建u是O（n log n），for循环是O（n log n）。 - Marc Eaddy

这是对OP的回答，其中T是int，n是7:-)如果要进行昂贵的T复制，则应将T*或T&用作输入向量。 对于大型n，调用者应该并行化。 无论如何，请将其与其他答案进行基准测试 :-) - Alain Rist

Answer 9

这个修复了James McNellis原始版本中的错误。我也提供了就地和非就地版本。

// In-place version.  Uses less memory and works for more container
// types but is slower.
template <typename It>
It not_unique_inplace(It first, It last)
{
    if (first == last)
        return last;

    It new_last = first;
    for (It current = first, next = first + 1; next != last; ++current, ++next)
    {
        if (*current == *next && 
            (new_last == first || *current != *(new_last-1)))
            *new_last++ = *current;
    }
    return new_last;
}

// Out-of-place version. Fastest.
template <typename It, typename Container>
void not_unique(It first, It last, Container pout)
{
    if (first == last || !pout)
        return;

    for (It current = first, next = first + 1; next != last; ++current, ++next)
    {
        if (*current == *next && 
            (pout->empty() || *current != pout->back()))
            pout->push_back(*current);
    }
}

- Marc Eaddy

Answer 10

“as efficient as std::unique”是什么意思？在运行时间、开发时间、内存使用方面高效，还是其他方面？

正如其他人指出的那样，std::unique需要有序输入，而您没有提供，因此这不是一个公平的测试。

个人认为我会让std::map来完成所有工作。它具有我们可以用于最大优雅/简洁的属性。它已经保持其元素排序，并且operator[]将插入零值（如果键不存在）。通过利用这些属性，我们可以用两三行代码完成这项工作，并仍然实现合理的运行时复杂度。

基本上，我的算法是这样的：对于向量中的每个元素，按该元素的值递增一次映射条目的键。之后，只需遍历映射，输出任何值大于1的键即可。再简单不过了。

#include <iostream>
#include <vector>
#include <map>

void
output_sorted_duplicates(std::vector<int>* v)
{
   std::map<int, int> m;  

   // count how many of each element there are, putting results into map
   // map keys are elements in the vector, 
   // map values are the frequency of that element
   for (std::vector<int>::iterator vb = v->begin(); vb != v->end(); ++vb)
      ++m[*vb];

   // output keys whose values are 2 or more
   // the keys are already sorted by the map
   for (std::map<int, int>::iterator mb = m.begin(); mb != m.end(); ++mb)
      if ( (*mb).second >= 2 ) 
         std::cout << (*mb).first << " "; 
   std::cout << std::endl;
}

int main(void) 
{ 
   int initializer[] = { 4, 4, 1, 2, 3, 2, 3 };
   std::vector<int> data(&initializer[0], &initializer[0] + 7);
   output_sorted_duplicates(&data);
}

janks@phoenix:/tmp$ g++ test.cc && ./a.out
2 3 4

所以，我们遍历您的向量中的每个元素，然后遍历我的映射中的每个元素，其中我的映射中的元素数量最多不会超过您的向量。 我的解决方案的缺点是需要比在原地重新排列您的向量的解决方案更多的存储空间。 然而，它的优点是明显的。 它非常简短和简单，显然正确，无需进行大量测试或代码审查，并且具有合理的性能特性。

将我的函数变为模板，并使其操作STL样式范围而不仅仅是整数向量，留作练习。

- janks