从列表<int>中删除重复项

Question

使用STL算法(尽可能多),例如remove_if()和list::erase,有一种很好的方法可以从定义如下的列表中删除重复项:

list<int> l;

请注意,list::unique()仅当连续元素中出现重复时才有效.就我而言,无论在列表中的位置如何,都必须删除所有重复项.此外,删除重复意味着在最终结果中仅保留每个元素的一个副本.

编辑:l.sort()后面的选项l.unique()无法使用,因为这将破坏列表的顺序.

Answer 1

如果保留列表的顺序并不重要,您可以这样做 list.sort(); list.unique();

如果订单很重要,请使用Rup的建议:

list<int>::iterator iter = l.begin();
set<int> elements;
while (iter != l.end()) {
  if (elements.find(*iter) != elements.end())
    iter = l.erase(iter);
  else {
    elements.insert(*iter);
    ++iter;
  }
}

Answer 2

使用list::remove_if成员函数,临时哈希集和lambda表达式.

std::list<int> l;
std::unordered_set<int> s;

l.remove_if([&](int n) {
    return (s.find(n) == s.end()) ? (s.insert(n), false) : true;
});

Answer 3

他说他想使用擦除删除习惯用法,所以这是一种可能的方法,使用一个函数对象:

struct Unifier{
    set<int> foundElements;

    bool operator()(int & a){
        if(foundElements.find(a) != foundElements.end()){
            return true;
        }else{
            foundElements.insert(a);
            return false;
        }
    }
};


int main(){
    list<int> v;

    v.push_back(5);
    v.push_back(4);
    v.push_back(5);
    v.push_back(3);
    v.push_back(5);
    v.push_back(3);

    copy (v.begin(), v.end(), ostream_iterator<int>(cout," "));

    Unifier u;
    v.remove_if(u);

    cout << endl << "After:" << endl;
    copy (v.begin(), v.end(), ostream_iterator<int>(cout," "));

}

更新:上面的代码有一个微妙的bug.根据C++ 11 [algorithms.general]/10:

[注意:除非另有说明,否则允许将函数对象作为参数的算法自由复制这些函数对象.对象标识很重要的程序员应考虑使用指向非复制实现对象的包装类,如reference_wrapper<T>(20.8.3)或某些等效解决方案. - 尾注]

似乎没有"另外指定" std::list::remove_if,因此此代码可能无法删除所有重复项,因为它可能在开始时创建谓词的副本,然后对列表的不同部分使用谓词的不同副本.std :: remove_if实际发生这种情况的示例.

C++ 11的一个简单修复就是替换v.remove_if(u)为:

v.remove_if( reference_wrapper<decltype(u)>(u) );

在C++ 03中,我不确定上面的引用是否存在; 但如果它是一个修复将是foundElements静态,或重构,Unifier以便它的所有副本引用单个实例foundElements.

链接到相关问题