Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

std::list<>::remove_if() visits elements multiple times #20894

Closed
llvmbot opened this issue Aug 3, 2014 · 7 comments
Closed

std::list<>::remove_if() visits elements multiple times #20894

llvmbot opened this issue Aug 3, 2014 · 7 comments
Labels
bugzilla Issues migrated from bugzilla libc++ libc++ C++ Standard Library. Not GNU libstdc++. Not libc++abi.

Comments

@llvmbot
Copy link
Collaborator

llvmbot commented Aug 3, 2014

Bugzilla Link 20520
Resolution FIXED
Resolved on Aug 05, 2014 07:57
Version 3.4
OS FreeBSD
Reporter LLVM Bugzilla Contributor
CC @DimitryAndric,@mclow

Extended Description

When calling std::list<>::remove_if() with a lambda for the condition (I did not test without lambdas), it visits the list entry following a delete twice.

Demo code and a patch can be found with the respective FreeBSD bug report:
https://bugs.freebsd.org/bugzilla/show_bug.cgi?id=192303

@DimitryAndric
Copy link
Collaborator

Fix erase() invocation arguments in std::list<>::remove() and remove_if()
This is actually a problem in both std::list<>::remove() and remove_if(), but the proposed patch in the FreeBSD bug is not correct. The optimization in remove_if() goes as follows:

        iterator __j = _VSTD::next(__i);
        for (; __j != __e && __pred(*__j); ++__j)
            ;
        __i = erase(__i, __j);

However, erase() erases from i up to, but not including j, and returns j. So j should be incremented to after the last __pred match (or equals match, in case of remove()) instead:

        iterator __j = _VSTD::next(__i);
        while (__j != __e && __pred(*__j++))
            ;
        __i = erase(__i, __j);

Similar for remove():

        iterator __j = _VSTD::next(__i);
        while (__j != __e && *__j++ == __x)
            ;
        __i = erase(__i, __j);

Attached patch makes it so. This also fixes the testcase from the FreeBSD bug for me.

@DimitryAndric
Copy link
Collaborator

[Fix erase() invocation arguments in std::list<>::remove()/remove_if(), and std::forward_list<>::remove()https://user-images.githubusercontent.com/9060368/143749821-0559ea8f-c3d7-466b-a4f7-b8d399806da8.gz)
A similar fix should also be applied to std::forward_list<>::remove() and remove_if(). Here is an updated patch.

@llvmbot
Copy link
Collaborator Author

llvmbot commented Aug 4, 2014

[Fix erase() invocation arguments in std::list<>::remove()/remove_if(), and std::forward_list<>::remove()https://user-images.githubusercontent.com/60944935/143749820-b4b0221b-5042-40d1-b627-f272d16617b9.gz)
Note that the fixes posted here remove the first elements that return false after a true element, as well. Removing list elements that shouldn't be removed.

@mclow
Copy link
Contributor

mclow commented Aug 4, 2014

After the call to erase, we know that either (a) we're at the end of the list, or (b) we're looking at an element that the predicate has returned "false" for. So we can just increment the iterator, and move on.

         __i = erase(__i, __j);
  •        if (__i != __e)
    
  •            __i = _VSTD::next(__i);
    

I don't see that forward_list has this problem, because the code is somewhat different.

Committed revision 214736 to fix this (and add tests).

@llvmbot
Copy link
Collaborator Author

llvmbot commented Aug 4, 2014

         __i = erase(__i, __j);
  •        if (__i != __e)
    
  •            __i = _VSTD::next(__i);
    

That's pretty much the same fix I posted on the FreeBSD PR.

I don't see that forward_list has this problem, because the code is somewhat
different.

Committed revision 214736 to fix this (and add tests).

I tested that, too and couldn't find problems with forward_list.

Thank you for fixing this so fast.

@DimitryAndric
Copy link
Collaborator

Ah sorry, I really should have had more coffee before attempting to fix this. :)

@llvmbot
Copy link
Collaborator Author

llvmbot commented Aug 5, 2014

NetBSD llvm branch is also affected.

@llvmbot llvmbot transferred this issue from llvm/llvm-bugzilla-archive Dec 9, 2021
This issue was closed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bugzilla Issues migrated from bugzilla libc++ libc++ C++ Standard Library. Not GNU libstdc++. Not libc++abi.
Projects
None yet
Development

No branches or pull requests

3 participants