C++ finding doubles in list

Question

I have to find if there are doubles in my list<SnakeParts> and set alive to false if there are doubles

I tried with the unique() function of the list and added an operator==() to my class. now when I execute the unique function I doesn't filter out the doubles. and after some debugging I found out that the == comparator only get's exececuted as many times as there are objects in my list I used the following code:

list<SnakePart> uniquelist = m_snakeParts;
uniquelist.unique();
if (m_snakeParts.size() != uniquelist.size()){
    alive = false;
}

operator:

bool SnakePart::operator==(const SnakePart& snakePart) const{
    return (x == snakePart.x && y == snakePart.y );
}

but that doesn't work. so what am I doing wrong, or is there another way I could do this?

relevant: http://stackoverflow.com/questions/4877504/how-can-i-remove-duplicate-values-from-a-list-in-c ...Also, is this a snake game? if so you should only check that the Head (first of the list) isn't duplicated in the list — Exceptyon, May 22 '13 at 16:18

score 2 · Answer 1 · answered May 22 '13 at 16:17

std::list::unique works only with consecutive duplicates. Say, if we have a {1, 2, 2, 1}, after calling unique we got {1, 2, 1}. You could use sort function before(N * log(N) + N complexity) , or use std::map to count every element in list(linear, + N memory(in worst case)).

score 1 · Answer 2 · answered May 22 '13 at 16:17

Notice that an element is only removed from the list container if it compares equal to the element immediately preceding it. Thus, this function is especially useful for sorted lists.

So you'll have to either sort your list beforehand, or use an std::set (sets by nature can't contain duplicate objects).

score 1 · Answer 3 · answered May 22 '13 at 16:17

If using a std::list is not a requirement then I would suggest using std::set which won't allow you to insert an element that's already in the set. Moreover, the insert method will let you know if the element you are trying to insert is already in the set or not via its return value.

If using a std::list is a requirement, then I would suggest you to use std::unique algorithm to weed out the duplicates. Please have a look at the example in there.

C++ finding doubles in list

3 Answers3