[cfe-dev] libc++ std::map self-assignment bug

[James Dennett]

On Thu, Feb 27, 2014 at 9:09 PM, Ahmed Charles <acharles at outlook.com> wrote:
> ----------------------------------------
>> Date: Thu, 27 Feb 2014 00:09:51 -0800
>> Subject: Re: [cfe-dev] libc++ std::map self-assignment bug
>> From: james.dennett at gmail.com
>> To: acharles at outlook.com
>> CC: silvas at purdue.edu; howard.hinnant at gmail.com; cfe-dev at cs.uiuc.edu
>>
>> On Wed, Feb 26, 2014 at 11:43 PM, Ahmed Charles <acharles at outlook.com> wrote:
>>> I just got around to reading my backlog of cfe-dev mail and noticed this. So, forgive me for replying but obscure is awesome.
>>>
>>> I think the following paragraph makes the standard require rebalancing, (which suggests that the container requirements are wrong, since rebalancing isn't linear time.
>>>
>>> 23.2.4 [associative.reqmts]/p11
>>>
>>> When an associative container is constructed by passing a comparison object the container shall not store a pointer or reference to the passed object, even if that object is passed by reference. When an associative container is copied, either through a copy constructor or an assignment operator, the target container shall then use the comparison object from the container being copied, as if that comparison object had been passed to the target container in its constructor.
>>>
>>> This suggests that your implementation below isn't conforming, since assigning the comparison object below doesn't behave the same way as passing it to the target container's constructor. But, this would be conforming:
>>>
>>> template <class T>
>>> class my_compare
>>> {
>>> bool reversed_ = false;
>>> public:
>>> my_compare() = default;
>>> my_compare(bool r) : reversed_(r) {}
>>> my_compare(const my_compare& o) : reversed_(!o.reversed_) {}
>>> my_compare& operator=(const my_compare& o) {
>>> reversed_ = !o.reversed_;
>>> return *this;
>>> }
>>> bool operator()(const T& x, const T& y) const
>>> {
>>> if (reversed_)
>>> return y < x;
>>> return x < y;
>>> }
>>> };
>>>
>>> Note, the important thing is that both copy operations do the same thing, consistently.
>>
>> But what they do is not copying; they violate the CopyConstructible
>> requirement that the associative containers' constructors place on
>> their Compare type (when a comparator is passed, at least... there may
>> be a gap in the wording, where the standard should say that copying an
>> associative container requires that its comparator be
>> CopyConstructible).
>
> I tried to find the place in the standard the describes the requirements on the comparison type, but I wasn't able to. Granted, I didn't spend too much time on this. If you can point to the section, that would be great.

The table of associative container requirements has some rows
describing various required constructors, and those require that the
comparator be CopyConstructible if one is passed in.

(The small defect that I think is present is that the copy operations
of the associative container itself don't appear to have this
requirement.)

> It's also not obvious that CopyConstructible is related to EqualityComparable either.

Indeed, it's not so closely related.  CopyConstructible doesn't imply
EqualityComparable; a copy is not required to compare equal to the
original, it's required to be "equivalent" to it, in some ill-defined
sense.

> I've never seen a place in the standard that says that copying needs to maintain the same value, though it does allow elision to occur, which means that your program can't usefully rely on the side effects of the copy actually having happened.

The CopyConstructible requirements are where you want to look, I
think.  (Table 21 in my draft of C++14.)  I quoted them in my original
message (still quoted below), though maybe not very explicitly so:

>> Note that CopyConstructible is not a merely syntactic requirement: it
>> implied that for after copying a value v, "the value of v is unchanged
>> and is equivalent to [the copy]".

Hope this helps,

James