在一个字符串向量中去除重复项

Question

我有一个字符串向量：

std::vector<std::string> fName

该列表包含文件名的列表 <a,b,c,d,a,e,e,d,b>。

我想要摆脱所有具有重复项的文件，并且只保留向量中没有重复项的文件。

for(size_t l = 0; l < fName.size(); l++)
{
    strFile = fName.at(l);
    for(size_t k = 1; k < fName.size(); k++)
    {
        strFile2 = fName.at(k);
        if(strFile.compare(strFile2) == 0)
        {
            fName.erase(fName.begin() + l);
            fName.erase(fName.begin() + k);
        }
    }
}

这里移除了一些重复元素，但仍有一些剩余，需要帮助进行调试。

另外，我的输入看起来像是<a,b,c,d,e,e,d,c,a>，期望的输出是<b>，因为其它的文件b、c、d、e都有重复，它们被移除了。

- Deepak B

---

你想保留重复项的任何副本吗？即，你想要<a,b,c,d,e>，还是只要<c>？ - Karl Knechtel

我不想保留重复项的副本。 - Deepak B

Answer 1

#include <algorithm>

template <typename T>
void remove_duplicates(std::vector<T>& vec)
{
  std::sort(vec.begin(), vec.end());
  vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
}

注意：这需要T定义了operator<和operator==。

为什么它能工作？ std::sort使用元素的小于比较运算符对它们进行排序。 std::unique使用元素的等于比较运算符比较并移除重复的连续元素。

如果我只想要唯一的元素怎么办？

那你最好使用std::map。

#include <algorithm>
#include <map>

template <typename T>
void unique_elements(std::vector<T>& vec)
{   
  std::map<T, int> m;
  for(auto p : vec) ++m[p];
  vec.erase(transform_if(m.begin(), m.end(), vec.begin(),
                         [](std::pair<T,int> const& p) {return p.first;},
                         [](std::pair<T,int> const& p) {return p.second==1;}),
            vec.end());
}

请查看：这里。

- Gigi

---

还需要包含 #include <algorithm> 才能使用 std::sort 和 std::unique。 - Deepak B

Gigi，谢谢你的帮助，这个方法确实有效，但并没有解决我的原始问题... 我最初的输入是 <a,b,c,d,e,e,d,b,a>，我想要的输出是 <a> 而不是 <a,b,c,d,e>。 - Deepak B

抱歉，我希望我的输出是<c>，而且不重复。 - Deepak B

你应该只需使用 vec.swap(ret)，而不是复制所有内容。更好的方法是直接返回向量。另外，如果你真的想要复制，只需调用 vec = ret; 即可。 - Xeo

你测试过这个函数吗？它在你的电脑上能编译通过吗？ - Benjamin Lindley

Answer 2

如果我正确理解您的要求，但我并不完全确定。您想仅保留向量中不重复的元素，对吗？

创建一个字符串到整数的映射，用于计算每个字符串的出现次数。清空向量，然后只复制仅出现一次的字符串。

map<string,int> m;
for (auto & i : v)
    m[i]++;
v.clear();
for (auto & i : m)
    if(i.second == 1)
        v.push_back(i.first);

或者，对于编译器特性方面有挑战的人：

map<string,int> m;
for (vector<string>::iterator i=v.begin(); i!=v.end(); ++i)
    m[*i]++;
v.clear();
for (map<string,int>::iterator i=m.begin(); i!=m.end(); ++i)
    if (i->second == 1)
        v.push_back(i->first);

- Benjamin Lindley

Answer 3

#include <algorithms>

template <typename T>
remove_duplicates(std::vector<T>& vec)
{
  std::vector<T> tvec;
  uint32_t size = vec.size();
  for (uint32_t i; i < size; i++) {
    if (std::find(vec.begin() + i + 1, vec.end(), vec[i]) == vector.end()) {
      tvec.push_back(t);
    } else {
      vec.push_back(t);
    }
  vec = tvec; // : )
  }
}

- perreal

---

std::vector 没有 pop_front()。 - Benjamin Lindley

只有pop_back()，找不到pop_front()。林德利先生如果您能帮忙就太好了。谢谢。 - Deepak B

@DeepakB：我帮忙了。你没看到我的答案吗？ - Benjamin Lindley

Answer 4

您可以在O(log n)的运行时间和O(n)的空间内消除重复项：

std::set<std::string> const uniques(vec.begin(), vec.end());
vec.assign(uniques.begin(), uniques.end());

但是O（log n）的运行时间有点误导，因为O（n）的空间实际上会进行O（n）动态分配，这在速度方面是昂贵的。元素也必须是可比较的（这里使用operator<()，std::string支持按字典顺序比较）。

如果您只想存储唯一的元素：

template<typename In>
In find_unique(In first, In last)
{
    if( first == last ) return last;
    In tail(first++);
    int dupes = 0;
    while( first != last ) {
        if( *tail++ == *first++ ) ++dupes;
        else if( dupes != 0 ) dupes = 0;
        else return --tail;
    }
    return dupes == 0 ? tail : last;
}

上面的算法使用排序好的范围并在线性时间和常量空间内返回第一个唯一元素。要在容器中获取所有唯一元素，您可以像这样使用它：

auto pivot = vec.begin();
for( auto i(find_unique(vec.begin(), vec.end()));
     i != vec.end();
     i = find_unique(++i, vec.end())) {
    std::iter_swap(pivot++, i);
}
vec.erase(pivot, vec.end());

- wilhelmtell

---

坦白说，我会选择使用std::sort()和std::unique()方法。我只是想展示一种替代方案。 :) - wilhelmtell

无论是在性能方面还是其他方面，这都是一个糟糕的例子，看起来像是那些懒得检查算法库的人的权宜之计。 - newhouse

O(log N) 的运行时间不可能实现。这是一个排序问题，因此时间复杂度为 O(N*logN)，如果数据已经排序，则时间复杂度为 O(N)。 - ABaumstumpf