Segmentation fault when removing from std::vector [duplicate]

Question

I am trying to remove duplications in a vector of struct and this duplication is determined by qieid in the struct:

struct infotable
{
  int qieid;
  int fid;
  int valid;
};

And I write a subfunction to do this:

void erase_duplicate(vector<infotable> &info)
{
  vector<infotable>::iterator it0,it1;

  for(it0 = info.begin();it0 != info.end()-1; it0++)
  {
    //it1 = find(qieidarray1.begin(),it0,*it0);

    for(it1 = it0 +1;it1 != info.end(); it1++)
    {
      if((*it1).qieid == (*it0).qieid)
        it1 = info.erase(it1);
    }
  }
}

But I have some problems with this piece of code. When the number of struct in the vector is small, it works fine. But when I have about more than 3000 structs in the vector, the program will go wrong and I have:

segmentation fault 11

showed on my screen. I know it is a memory access problem and I may access to somewhere I should not touch because I have so many elements in the vector. But is there anyway I can improve my code in order to get a better performance(run more elements)?

Answer 1

You could also use <algorithm> functions to do it, std::unique in particular.

First, sort by qieid, then use unique, which moves the "deleted" elements at the end and returns a new iterator, which you can then use to actually erase these elements.

std::sort(info.begin(), info.end(), [](const infotable& a, const infotable& b) {
    return a.qieid < b.qieid;
});
auto newIt = std::unique(info.begin(), info.end(), [](const infotable& a, const infotable& b) {
    return a.qieid == b.qieid;
});
info.erase(newIt, info.end());

This will run in O(n+log n), whereas your original solution has O(n²) time complexity. Personally, I'd prefer this solution especially because it's more expressive and so it's easier to see what the code is doing.

Note: If your compiler already supports C++ 14's generic lambdas, you can simplify the expressions even more by using: [](const auto& a, const auto& b) { ... }