Bug 91620 - std::[forward_]list::remove_if/unique should respect to DR 526
Summary: std::[forward_]list::remove_if/unique should respect to DR 526
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: libstdc++ (show other bugs)
Version: 9.1.0
: P3 normal
Target Milestone: 11.0
Assignee: François Dumont
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2019-08-30 19:24 UTC by frankhb1989
Modified: 2020-08-12 06:03 UTC (History)
2 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2019-12-19 00:00:00

Attachments
Add an attachment (proposed patch, testcase, etc.)

Note You need to log in before you can comment on or make changes to this bug.
Description frankhb1989 2019-08-30 19:24:36 UTC 
A case for std::list taken from libc++'s testsuite:

#include <cstddef>
#include <cassert>
#include <functional>
#include <list>
using namespace std;

struct PredLWG529
{
	PredLWG529(int i) : i_(i) {};
	~PredLWG529() { i_ = -32767; }
	bool operator() (const PredLWG529& p) const { return p.i_ == i_; }

	bool operator==(int i) const { return i == i_; }
	int i_;
};

int main()
{
	int a1[] = {1, 2, 1, 3, 5, 8, 11};
	int a2[] = {2, 3, 5, 8, 11};
	std::list<PredLWG529> c(a1, a1 + 7);
	c.remove_if(std::ref(c.front()));
	assert(c.size() == 5);
	for(size_t i = 0; i < c.size(); ++i)
	{
		assert(c.front() == a2[i]);
		c.pop_front();
	}
}
Comment 1 frankhb1989 2019-08-30 19:30:52 UTC 
(The issue number in the case seems a typo. It is introduced in https://reviews.llvm.org/rL358534.)
Comment 2 frankhb1989 2019-08-31 15:21:55 UTC 
I missed `unique` should be also affected. The fixes have been applied in libc++ in the same commit to fix `remove_if`.

MSVC's current implementations are also correct, with a different implementation strategy. It uses a singly liked list for nodes pending to delete.
Comment 3 François Dumont 2019-12-19 20:09:06 UTC 
I take it !
Comment 4 GCC Commits 2020-08-11 19:30:30 UTC 
The master branch has been updated by Franथà¤ois Dumont <fdumont@gcc.gnu.org>:

https://gcc.gnu.org/g:8b7af071b0cd4a6f8d989453ac81a4c3768d6343

commit r11-2658-g8b7af071b0cd4a6f8d989453ac81a4c3768d6343
Author: François Dumont <fdumont@gcc.gnu.org>
Date:   Sat Aug 8 22:22:00 2020 +0200

    libstdc++: Implement DR 526 on [forward_]list remove_if/unique [PR 91620]
    
    Respect DR 526 in implementation of std::[forward_]list remove/remove_if/unique.
    [forward_]list::remove was already implementing it but the implementation has
    been modified to generalize the following pattern. All nodes to remove are
    collected in an intermediate [forward_]list which purpose is just to be
    detroyed once out of scope.
    
    libstdc++-v3/ChangeLog:
    
            PR libstdc++/91620
            * include/bits/forward_list.tcc (forward_list<>::remove): Collect nodes
            to destroy in an intermediate forward_list.
            (forward_list<>::remove_if, forward_list<>::unique): Likewise.
            * include/bits/list.tcc (list<>::remove, list<>::unique): Likewise.
            (list<>::remove_if): Likewise.
            * include/debug/forward_list (forward_list<>::_M_erase_after): Remove.
            (forward_list<>::erase_after): Adapt.
            (forward_list<>::remove, forward_list<>::remove_if): Collect nodes to
            destroy in an intermediate forward_list.
            (forward_list<>::unique): Likewise.
            * include/debug/list (list<>::remove, list<>::unique): Likewise.
            (list<>::remove_if): Likewise.
            * testsuite/23_containers/forward_list/operations/91620.cc: New test.
            * testsuite/23_containers/list/operations/91620.cc: New test.
Comment 5 François Dumont 2020-08-12 06:03:56 UTC 
Should be fine now, thanks for the report.