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

[Howard Hinnant]

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:

#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