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

[Sean Silva]

On Sat, Nov 30, 2013 at 11:53 PM, Howard Hinnant
<howard.hinnant at gmail.com>wrote:

>
> On Nov 30, 2013, at 11:02 PM, Sean Silva <silvas at purdue.edu> wrote:
>
> >> In C++11, using libc++, if two equal sized map<int, int> are assigned,
> there are zero trips to the heap.  The nodes in the lhs are assigned new
> values, and rebalancing takes place as necessary.
> >>
> > In what situation would rebalancing need to happen during this
> operation? If they are the same size, wouldn't you just simultaneously
> inorder walk both, assigning element by element (or the equivalent)? The
> structure of an rb-tree is independent of the actual values contained.
> >
>
> One of the things this allows for is a state-full comparator where the
> state is not assigned under the copy assignment operator:
>

Ah, that makes perfect sense! Kind of devilish, but it doesn't seem
unreasonable to support it.

-- Sean Silva


>
> #include <iostream>
> #include <iterator>
> #include <set>
> #include <cassert>
>
> template <class C>
> void
> display(const C& c)
> {
>     std::cout << "{";
>     if (!c.empty())
>     {
>         std::cout << *c.begin();
>         for (auto i = ++c.begin(); i != c.end(); ++i)
>             std::cout << ", " << *i;
>     }
>     std::cout << "}\n";
> }
>
> template <class T>
> class my_compare
> {
>     bool reversed_ = false;
> public:
>     my_compare() = default;
>     my_compare(bool r) : reversed_(r) {}
>     my_compare& operator=(const my_compare&) {return *this;}  // don't
> assign comparator state
>     bool operator()(const T& x, const T& y) const
>     {
>         if (reversed_)
>             return y < x;
>         return x < y;
>     }
> };
>
> int
> main()
> {
>     std::set<int, my_compare<int> > s1;
>     for (int i = 1; i <= 3; ++i)
>         s1.insert(i);
>     std::set<int, my_compare<int> > s2(my_compare<int>(true));
>     for (int i = 4; i <= 6; ++i)
>         s2.insert(i);
>     display(s1);
>     display(s2);
>     s2 = s1;
>     display(s2);
>     assert(s2.find(3) != s2.end());
> }
>
> {1, 2, 3}
> {6, 5, 4}
> {3, 2, 1}
>
> This is pretty weird code, and I might flunk it on a code review.  One
> could even argue that the standard does not permit such code.  But it works
> if you don't force a structural copy under copy assignment.  And my
> experience is that I am continually surprised at what my customers want to
> do (and for very clever reasons).  And so if I want to disallow code like
> this, I need to come up with a very strong motivation for doing so.
>  Rebalancing is generally fairly fast, and with red-black logic, not
> actually done that often (one path from root to child can be up to twice as
> long as another).  My current engineering judgement is that this capability
> is worth the cost of rebalancing under copy assignment.
>
> With an implementation that does do a structural copy under assignment the
> output of this program is:
>
> {1, 2, 3}
> {6, 5, 4}
> {1, 2, 3}
> Assertion failed: (s2.find(3) != s2.end()), function main, file test.cpp,
> line 49.
> Abort trap: 6
>
> If this example is not standard conforming, I consider it a valuable
> conforming extension to support it.  I find it far more preferable than
> putting the rb-tree into an invalid state.
>
> Howard
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20131203/84714e17/attachment.html>