删除备份结构成员:: vector的

Question

我有一个像下面结构件的载体：

struct pnt 
{ 
    bool has; 
    int num; 
}; 
std::vector<pnt> myvector; 

让我们有这样一个样本向量：

myvector (num): 3 4 4 3 5 5 7 8 9 10 10             
myvector (has): 1 1 0 1 0 1 0 0 0 1 0 

我想要做的是找到重复的成员（根据具有相同的int num），并用false bool成员删除。 让自己的矢量变成了这个样子：

myvector (num): 3 4 3 5 7 8 9 10               
myvector (has): 1 1 1 1 0 0 0 1 

这样做，我写如下功能：

void removeDuplicatedPnt(pnt_vec& myvector) 
{ 
    std::vector<pnt>::iterator pnt_iter; 
    for(pnt_iter = myvector.begin(); pnt_iter != myvector.end(); ++pnt_iter) 
    { 
     if(pnt_iter->has) 
     { 
      if(pnt_iter->num == (pnt_iter+1)->num) 
      { 
       myvector.erase(pnt_iter+1); 
      } 
      if(pnt_iter == myvector.begin()) 
      { 
      continue; 
      } 
      if(pnt_iter->num == (pnt_iter-1)->num) 
      { 
       myvector.erase(pnt_iter-1); 
       pnt_iter++; 
      } 
     } 
    } 
} 

我还可以通过会员的顺序检查做到这一点。但真正的矢量可能会很长。所以这就是为什么我第一次去找到真正的布尔成员，然后我检查了下一个和上一个成员。问题是我如何在效率和稳健性方面修改上述代码。

注意：我只能使用C++ 03（不是C++ 11）。我也可以使用嘘声（版本1.53），所以如果觉得在那里有任何有用的功能，请放心。 :)

Answer 1

你可以使用这个算法只切向有关：

• 收集所有num S其中has是true在set<int>
• 通过您vector<pnt>再去吧，删除has为false和num的所有条目存在于set<int>

这里s是一个示例实现：

struct filter { 
    set<int> seen; 
    bool operator()(const pnt& p) { 
     return !p.has && (seen.find(p.num) != seen.end()); 
    } 
}; 
... 
filter f; 
for (vector<pnt>::const_iterator i = v.begin() ; i != v.end() ; i++) { 
    if (i->has) { 
     f.seen.insert(i->num); 
    } 
} 
v.erase(remove_if(v.begin(), v.end(), f), v.end()); 

Demo.

Answer 2

您可以使用std ::排序和std ::使用自定义比较谓词独特：

[](const pnt& a, const pnt& b) { return a.num < b.num; } 

下面是使用Boost范围，以减少打字演示它的快捷方法：

更新 C++ 03版Live On Coliru

#include <boost/range.hpp> 
#include <boost/range/algorithm.hpp> 
#include <iostream> 

using namespace boost; 

struct pnt { 
    int num; 
    bool has; 

    pnt(int num = 0, bool has = false) : num(num), has(has) {} 

    friend bool operator<(pnt const& a, pnt const& b) { return a.num<b.num; } 
    friend bool operator==(pnt const& a, pnt const& b) { return a.num==b.num; } 
}; 

int main() { 
    std::vector<pnt> v { {10,0 },{10,1 },{9,0 },{8,0 },{7,0 },{5,1 },{5,0 },{3,1 },{4,0 },{4,1 },{3,1 } }; 

    for (pnt p : boost::unique(boost::sort(v))) 
     std::cout << "{ num:" << p.num << ", has:" << p.has << "}\n"; 
} 

这实际ly有一些微妙的点，可以使例如做

it = std::find(v.begin(), v.end(), 3); // find a `pnt` with `num==3` 

但这