C++ list remove duplicates strings

Question

I have a little problem when using lists.

What I have: I am reading lines from a chatbox where new lines of text come now and then. I always fetch the last 20 lines from the box, then i want to compare them to all the lines i have fetched before. If a new line is discovered it is sent to an external function which disassembles the line for further processing. Before I used arrays and vectors, but list seem to be the better way of doing it.

My Idea: I have one list called usedlines which contains all the old allready used lines. The list fetchedLines containes the newest 20lines fetched from the chatbox.

No I simply want to loop trough both of them to find out if fetched lines containes a new line not seen before. After the loop the remains in fetchedlines are handled over to the next function.

Problem: When I loop throug this loop i get a badpointer after a while. Why? Bonus: Does anyone have a better idea to solve this task?

typedef list<string> LISTSTR;
LISTSTR::iterator f;
LISTSTR::iterator u;
LISTSTR fetchedlines;                 
LISTSTR usedLines;                



fetchedlines.insert(fetchedlines.end(), "one");
fetchedlines.push_back("two");
fetchedlines.push_back("three");
fetchedlines.push_back("four");
fetchedlines.push_back("three");

usedLines.push_back("three");
usedLines.push_back("blää");
usedLines.push_back("lumpi");
usedLines.push_back("four");


 for (u =  usedLines.begin(); u != usedLines.end(); u++)
 {
 for (f =  fetchedlines.begin(); f != fetchedlines.end(); f++)
   {
   if(*u==*f)
    fetchedlines.remove(*f);
  }

}

Check out std::set, std::remove_if and std::set_intersection for a faster solution. — Fred Foo
– Fred Foo, Commented Jan 20, 2011 at 15:46

James · Accepted Answer · 2011-01-20 15:50:21Z

5

The call to fetchedlines.remove(*f) is invalidating your iterator.

EDIT:

A possible solution to the problem you are having is to instead just iterate usedLines and remove all elements in fetchedlines that are contained.

for (u = usedLines.begin() u != usedLines.end(); u++)
    fetchedLines.remove(*u);

//Process all of fetchedLines

edited Jan 20, 2011 at 15:50

answered Jan 20, 2011 at 15:44

James

5,4252 gold badges21 silver badges30 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Lumpi Over a year ago

Damn, that sounds smart! Thanks for the idea, I'll give it a try ;-)

James Over a year ago

There are faster solutions than this, such as larsmans suggestion, but this should address the problem at least.

Lumpi Over a year ago

Ok, It works this way!! I'm still alittle stuck in the array thinking, so I'll have a look at larsmans suggestions. Thank you all for the push in the right direction.

vmpstr · Accepted Answer · 2011-01-20 15:46:32Z

3

The reason you are getting an error is that fetchedlines.remove (*f) modifies fetchedlines, and if it was the last element, then the for loop increments too far

Try something like this:

for (u = userLines.begin (); u != usedLines.end (); ++u)
{
    for (f = fetchedlines.begin (); f != fetchedlines.end ();)
    {
        if (*u == *f)
        {
            f = fetchedlines.erase (f);
        }
        else
        {
            ++f;
        }
    }
}

(that's of course not addressing whether this is a good way to solve the problem)

answered Jan 20, 2011 at 15:46

vmpstr

5,2214 gold badges27 silver badges25 bronze badges

Comments

Thomas · Accepted Answer · 2011-01-20 15:50:38Z

2

You must never modify a list (or pretty much any other container) while iterating over it. That's your immediate problem.

A more interesting problem is why you're doing it like this in the first place. Isn't there a way to get sequential numbers on the lines, or maybe timestamps, so you could just compare those?

answered Jan 20, 2011 at 15:50

Thomas

183k57 gold badges383 silver badges510 bronze badges

2 Comments

Lumpi Over a year ago

I thought of such things, but there are no line numbers or timestamps in the lines i read... I have thought of altering the .unique feature of the list in such away that it if it finds duplicates not only erase the "to much" element but also the evil twin...

Lumpi Over a year ago

"You must never modify a list (or pretty much any other container) while iterating over it." I'll put that advise in my little blue book with notes about c++. Thanks

Xavier V. · Accepted Answer · 2011-01-20 15:45:05Z

2

You are removing an element from fetchedlines while your are iterating on it.

This is why you get a bad pointer.

answered Jan 20, 2011 at 15:45

Xavier V.

6,5486 gold badges32 silver badges35 bronze badges

2 Comments

Lumpi Over a year ago

Sounds logical... So I have to loop through the whole thing first and remember which elements i want to remove later(after looping trough the whole thing) ?!

Xavier V. Over a year ago

This is not a sexy way of doing it. See the answer of Goz or James... These are sexyer.

Goz · Accepted Answer · 2011-01-20 15:46:01Z

0

Because *f is an iterator pointing to an element you have just erased.

Try the following:

if(*u==*f)
{
    LISTSTR::iterator t = f;;

    f--;
    fetchedlines.remove(*t);
}

As an aside remove searches through the list for something that matches the data pointed to by the iterator f. If you want to simple get rid of the data pointed to you are better off doing

f = fetchedlines.erase( f );
f--;

answered Jan 20, 2011 at 15:46

Goz

62.5k26 gold badges131 silver badges212 bronze badges

Comments

Blastfurnace · Accepted Answer · 2011-01-20 17:05:20Z

0

This can be done with list::remove_if and a lambda expression. This method is still two nested loops but they are hidden inside the function calls. This may be fast enough for small lists but won't scale very well. It could be much faster if the data were sorted or if you used an ordered container.

fetchedLines.remove_if([&](std::string &str)
{
    return std::find(usedLines.begin(), usedLines.end(), str) != usedLines.end();
});

answered Jan 20, 2011 at 17:05

Blastfurnace

18.7k57 gold badges61 silver badges73 bronze badges

Collectives™ on Stack Overflow

C++ list remove duplicates strings

6 Answers 6

3 Comments

Comments

2 Comments

2 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

3 Comments

Comments

2 Comments

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related