[Bug libstdc++/43595] New: std::unique incorrectly assumes transitive property on functor, operator==

[Bug libstdc++/43595] New: std::unique incorrectly assumes transitive property on functor, operator==

[potswa at mac dot com]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1031 bytes --]

According to the standard §25.2.8, std::unique has behavior defined in terms of

   *i == *(i - 1) or pred(*i, *(i - 1)) != false

however the current implementation compares each successive element to the
first in the "equal" range. This is only equivalent if the transitive property
holds.

This is certainly wrong if a functor is passed, and it may be wrong for the
other case as well. The non-functor version is defined to evaluate *i == *(i -
1) but does not require EqualityComparable elements.

C++0x does impose this requirement: "The comparison function shall be an
equivalence relation."


-- 
           Summary: std::unique incorrectly assumes transitive property on
                    functor, operator==
           Product: gcc
           Version: 4.5.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: potswa at mac dot com


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=43595

[Bug libstdc++/43595] std::unique incorrectly assumes transitive property on functor, operator==

[chris at bubblescope dot net]

------- Comment #1 from chris at bubblescope dot net  2010-03-31 08:09 -------
Fixing this would make std::unique quite a bit less efficient. I personally
believe the intention was always to make it an equivalence relation and as you
say C++0x tightens up the condition.

If this had come up 5 or 6 years ago, I might have suggested fixing it, but
changing it now would produce an incompatibility between our C++03 and C++0x
implementations unnecessarily.

Does any other compiler get this right? If they did that would make a more
convincing case, but I'm fairly sure they don't.


-- 

chris at bubblescope dot net changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |chris at bubblescope dot net


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=43595

[Bug libstdc++/43595] std::unique incorrectly assumes transitive property on functor, operator==

[redi at gcc dot gnu dot org]

------- Comment #2 from redi at gcc dot gnu dot org  2010-03-31 09:57 -------
This is a defect in the original standard:
http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#202

The policy of libstdc++ is to fix defects, and I see no benefit in changing the
C++03 behaviour to be incompatible with C++0x.

I'm closing this as WONTFIX rather than INVALID


-- 

redi at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|                            |WONTFIX


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=43595