从std :: vector中删除/删除重复元素的方法，同时保持顺序？

有没有办法在维护顺序的同时从包含字符串元素的矢量容器中删除重复的元素。从std :: vector中删除/删除重复元素的方法，同时保持顺序？

直到现在我已经使用set方法，但它不保留顺序。

我不知道如何使用remove_if来解决这个问题。

2013-08-03 Quoros

如果容器有一个命令（也就是说，它的元素是分类的）重复是连续的。那么，问题在哪里？如果您删除重复项，则订单不会被修改。 – Manu343726

@ Manu343726：“有订单”并不意味着“已排序”。 –

是否只想删除连续的重复值（如Unix命令'uniq'），还是以后重复？也就是说，如果你的原始矢量看起来像“苹果”，“苹果”，“桔子”，“苹果”，“葡萄”}，结果应该是“苹果”，“桔子”，“苹果” ，“葡萄”}'或'{“苹果”，“橘子”，“葡萄”}'？ – celtschk

如何使用临时容器：

std::vector<int>::iterator i , j ; 
std::set<int> t_set; 
for(i = v.begin() , j = v.begin() ; i != v.end() ; ++i) 
    if(t_set.insert(*i).second) 
     *j++ = *i ; 
v.erase(j , v.end());

使用std::remove_if ，我能想到的是：

std::set<int> t_set; 
std::vector<int> res; //Resultant vector 

remove_copy_if(v.begin(), v.end(), std::back_inserter(res), 
    [&t_set](int x){ 
     return !t_set.insert(x).second; 
    });

来源

2013-08-03 15:04:42 P0W

+1，我已经发布了几乎完全相同的解决方案，但是比您的要晚得多。这是最快的（O（n log n））。 –

@LeonidVolnitsky：D – P0W

如果对象的拷贝成本很高（问题涉及到字符串;它没有说明这些字符串有多长），您还可以使用自定义比较函子将迭代器存储到集合中的原始向量中它取消了迭代器的引用。另外，如果这些对象有便宜的swap，则可以使用swap来代替赋值。在C++ 11中，移动分配将是明显的选择。 – celtschk

你可以这样做：

std::vector<int> v = { 1, 2, 2, 3, 4, 5, 6, 7, 8, 9, 8 }; 
// 1 2 2 3 4 5 6 7 8 9 8 

for(size_t i=0;i<v.size();i++) 
{ 
    for(size_t j=0;j<v.size();j++) 
    { 
     if(v[i] == v[j] && i != j) 
     { 
       v.erase(v.begin()+j); 
       j--; // Fix for certain datasets ie: 
     }   //        1 2 1 1 
    } 
} 

// Produces: 
// 1 2 3 4 5 6 7 8 9

来源

2013-08-03 14:21:21

为了确保您不首次出现值，请确保将当前迭代器+1作为std :: remove的第一个参数传递。 –

谢谢。这给了正确的解决方案 – Quoros

等一下，你改变了。为什么你在'erase'语句中加1到'j'？ –

您可以创建一个空数组，然后遍历原始载体，只拷贝过来向量中的每个项目的第一个实例。您可以通过将其添加到集合中并检查集合中的项目存在性，然后将其添加到新数组中，来跟踪是否已经看到该矢量中的项目。

来源

2013-08-03 14:22:54

一个简单的解决方案的最后一个元素

std::vector<int>::iterator it; 
it = std::unique (myvector.begin(), myvector.end());

这个迭代器将指向元素下一步。如果不需要，你可以不使用这个迭代器。

进一步参考见THIS

编辑：

正如我以为载体可以排序，新的解决方案可能是：

vector<int> vec= {5,1,2,3,5,4,2,1,1,4,3,2,4,5,2,1,3,5,2,3,5,2,3,2,3,5,2,1,3}; 
    set<int> s; 
    vector<int>::iterator vecIter=vec.begin(); 
    vector<int>::iterator vecIterCopy; 
    for(;vecIter!=vec.end(); vecIter++) 
    { 
     if(s.find(*vecIter)==s.end()) 
     { 
      s.insert(*vecIter); 
      *vecIterCopy++ = *vecIter; 
     } 
    }

来源

2013-08-03 15:03:43 Saksham

这要求对矢量进行排序（或者至少对所有的副本要连续）。您无法保持任意矢量的顺序。 –

哦，我的坏。我将订单解释为排序。 – Saksham

@MikeSeymour排序需要nlogn，它将给出与接受的答案相同的复杂度。 – BartoszKP

O（N *的log（n））解决方案：

vector<string> V={"aa","bb","aa","cc","cc"}; 
set<string> S; 

auto i=V.begin(); 
auto j=i; 

for(; i!=V.end(); ++i) { 
    if(S.insert(*i).second && i!=j++) 
     *j = std::move(*i); 
} 

V.erase(j,V.end());

还修改了战俘的版本std::remove_copy_if。但是这里没有多余的临时性：

set<string> S; 
V.erase(
    copy_if(
     make_move_iterator(V.begin()), 
     make_move_iterator(V.end()), 
     V.begin(), 
     [&](const string& x){ return S.insert(x).second;} 
    ), 
    V.end() 
);

来源

2013-08-03 16:10:42

从std :: vector中删除/删除重复元素的方法，同时保持顺序？

回答

相关问题