1

我有一个非常大的 std::vector 的 std::vectors 包含固定数量的无符号整数。

uint 的所有向量都按升序排序。

我目前消除重复向量的方法是

unsigned int i = 0;
while ( i < new_combs.size() )
{
  unsigned int j = i + 1;
  while ( j < new_combs.size() )
  {
     unsigned int k = 0;
     while ( k < new_combs.at(i).size() && new_combs.at(i).at(k) == new_combs.at(j).at(k) )
        ++k;
     if ( k == new_combs.at(j).size() )
        new_combs.erase(new_combs.begin() + j);
     else
        ++j;
  }
  ++i;
}

这里，new_combs 是一个包含上述向量的向量。

如果向量的向量未排序，是否有更有效的方法来消除重复项？

4

6 回答 6

9

更短的方法是使用<algorithm>：

std::sort(new_combs.begin(), new_combs.end());
new_combs.erase(std::unique(new_combs.begin(), new_combs.end()), new_combs.end());

除非您特别需要 a std::vector，否则您可以使用它std::set来避免重复。

于 2012-04-10T12:16:42.807 回答
3

您是否考虑过使用 std::set？它是有序的，不允许以重复项开头。

于 2012-04-10T12:17:35.350 回答
2

如果向量未排序，您无能为力。但是，如果已排序，则可以使用算法中定义的唯一方法：

new_combs.erase(unique(new_combs.begin(), new_combs.end()), new_combs.end());
于 2012-04-10T12:17:51.647 回答
0

您的代码中有几个元素敲响了我关于性能的警钟。

首先，您正在使用向量。从向量中擦除元素总是很慢。您可能会考虑使用不同的容器（std::list）或调整您的代码，以便您有一个特殊的值（例如零或-1）。

其次，您可以使用 std::set 或 std::unordered_set 来保留您已经遇到的值。这样，您只需循环一次向量。

编辑：忘记这个答案。我误读了这个问题，并认为必须删除重复值（而不是重复向量）。

尽管如此，对给出的评论的一些反应：

  • @Jerry：我同意向量在大多数情况下比列表快，但前提是向量的大小是有限的。如果向量包含 100 万个元素，并且您需要删除第 3 个、第 5 个、第 10 个，......您最终会移动很多元素。在这种情况下，列表可能会更快。
  • @James：在最初的问题中，元素不是从向量的末尾删除，而是在中间。如果向量非常大（比如说 100 万个元素），那么删除元素仍然会成为瓶颈。但是，我同意比使用排序，然后是唯一的可能更快。
于 2012-04-10T12:19:15.920 回答
0

渐近地，您的算法看起来像通常的 O(n) 实现，因此是最优的。（尽管我不了解您的对角化策略i以及j为什么只擦除而不移动元素。您的代码非常不清楚。）但是，您正在复制 STL，并且唯一循环的较短版本是：

struct unique {
    template <class C>
    void operator()( C& c ) {
         c.erase( std::unique( c.begin(), c.end() ), c.end() );
    }
};

std::for_each( new_combs.begin(), new_combs.end(), unique() );
于 2012-04-10T12:19:50.413 回答
0

我同意Luchian Grigore 的回答，但您也可以考虑将整个外部vector转换unordered_set为用于排序）。您甚至可以在 中使用指向子向量的指针unordered_set，以避免不必要的复制。对于大量数据，这可能是一个重要的性能差异。

这个例子说明了使用你自己的散列函数和指针的基本思想（它处理vectorof strings 和 uses unordered_map， not unordered_set，但你应该能够很容易地修改它以满足你的需要）。

于 2012-04-10T13:09:12.103 回答