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

[Ahmed Charles]

----------------------------------------
> 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.

It's also not obvious that CopyConstructible is related to EqualityComparable either. 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. I'd be interested in a stronger guarantee if it exists and I'd be interested in having the guarantee be stronger, but the reality is likely not that.


> 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]".
>
>> I'm amused by the fact that this suggests that if the constructor copies the comparison object twice, that the copy constructor/copy assignment operator would have to also do it twice.
>
> There should be no such requirement, as copying once gets a value
> equivalent to the original (and hence equivalent to copying n times,
> for any n).
>
> -- James