在C++向量中删除重复条目

Question

我只想删除重复项。池是vector<pair<string, int>>，但我似乎在某种情况下错过了向量开头的一些元素。有人能验证一下删除的逻辑吗？谢谢:)

Pool Master::eliminateDuplicates(Pool generation)
{
    for(int i = 0; i < generation.size(); i++)
    {
        string current = generation.at(i).first;

        for(int j = i; j < generation.size(); j++)
        {
            if(j == i)
            {
                continue;
            }
            else
            {
                string temp = generation.at(j).first;
                if(current.compare(temp) == 0)
                {
                    Pool::iterator iter = generation.begin() + j;
                    generation.erase(iter);
                }
            }
        }
    }

    return generation;
}

- Jarrod Cabalzar

---

你介意它被排序吗？ - chris

一种更简单（并且可能比当前的O(n^2)方式更快）的方法是将所有元素添加到std::set中，然后再转回std::vector。 - Yuushi

另外，我假设你的意思是Pool是一个vector<pair<string, int>>？ - Yuushi

这个语句 if(j == i){continue;} 是必要的吗？你可以直接从 i+1 开始循环。 - Quazi Marufur Rahman

无论如何，您不必使用set。您可以对向量进行排序，并使用std::unique。这将是O（Nlog（N））。 - juanchopanza

Answer 1

如果您不介意对向量进行排序，那么可以使用std::unique。这将是O(Nlog(N))。

#include <iostream>
#include <algorithm>
#include <vector>

int main() 
{
    std::vector<int> v{1,2,3,1,2,3,3,4,5,4,5,6,7};
    std::sort(v.begin(), v.end()); 
    auto last = std::unique(v.begin(), v.end());
    v.erase(last, v.end());
    for (const auto& i : v)
      std::cout << i << " ";
    std::cout << "\n";
}

- juanchopanza

---

有人应该为所有常见的矢量使用编写维基/常见问题解答条目。+1 - TemplateRex

@rhalbersma，SO应该维护一个关于热门主题的最常见问题列表，比如前10个C++问题之类的。那将非常方便。 :D - Jarrod Cabalzar

我想知道为什么在所有关于使用std::unique的答案中，似乎没有人提到unique不考虑最后一个元素。 - tomi.lee.jones

@tomi.lee.jones 由于所有标准库算法都适用于开放区间，通常我们会传递起始点和结束点，这种方式是开放的。 - juanchopanza

如果你要排序，为什么不用std::sort呢？ - user3139831

Answer 2

这是一个非常常见的问题。

因为在删除元素后，由于for循环中的j++，位置j将跳过一个元素。 基于您的代码解决该问题的最简单方法是在generation.erase(iter)之后添加j--：

  generation.erase(iter);
  j--;

- www.diwatu.com