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)?

Have you considered using a set instead of a vector? You will need to write a comparison to tell the set that two structs with the same qieid are equal. — Katu
– Katu, Commented May 22, 2014 at 7:07
@katutxakurra That is a good idea! I have never used set before. Thx! — Hua Wei
– Hua Wei, Commented May 22, 2014 at 7:20

lethal-guitar · Accepted Answer · 2014-05-22 07:21:49Z

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) { ... }

+1, didn't know std::unique, always nice to learn new things
@Kiroxas yeah there are quite a few goodies hidden in the STL :)

tofi9 · Accepted Answer · 2014-05-22 07:24:33Z

when you use erase, it will invalidate iterators.

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

Kiroxas · Accepted Answer · 2014-05-22 07:36:31Z

you can remove duplicate with the std::set trick, it's quite readable, and easily maintanable, but is less efficient.

std::vector<int> r = {14,26,58,56,26,14}; std::set<int> s(r.begin(),r.end()); r = std::vector<int>(s.begin(),s.end());

You'll need to give the std::set your own comparison function in order for it to work with your structure.

"less efficient" - not if he uses the set everywhere instead of the vector :) Anyway, nice and concise solution

Collectives™ on Stack Overflow

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

3 Answers 3

2 Comments

Comments

1 Comment

Linked

Hot Network Questions