<div dir="ltr"><br><div class="gmail_extra"><br><br><div class="gmail_quote">On Sat, Nov 30, 2013 at 11:53 PM, Howard Hinnant <span dir="ltr"><<a href="mailto:howard.hinnant@gmail.com" target="_blank">howard.hinnant@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im"><br>
On Nov 30, 2013, at 11:02 PM, Sean Silva <<a href="mailto:silvas@purdue.edu">silvas@purdue.edu</a>> wrote:<br>
<br>
>> 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.<br>
>><br>
> 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.<br>

><br>
<br>
</div>One of the things this allows for is a state-full comparator where the state is not assigned under the copy assignment operator:<br></blockquote><div><br></div><div>Ah, that makes perfect sense! Kind of devilish, but it doesn't seem unreasonable to support it.</div>
<div><br></div><div>-- Sean Silva</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
#include <iostream><br>
#include <iterator><br>
#include <set><br>
#include <cassert><br>
<br>
template <class C><br>
void<br>
display(const C& c)<br>
{<br>
    std::cout << "{";<br>
    if (!c.empty())<br>
    {<br>
        std::cout << *c.begin();<br>
        for (auto i = ++c.begin(); i != c.end(); ++i)<br>
            std::cout << ", " << *i;<br>
    }<br>
    std::cout << "}\n";<br>
}<br>
<br>
template <class T><br>
class my_compare<br>
{<br>
    bool reversed_ = false;<br>
public:<br>
    my_compare() = default;<br>
    my_compare(bool r) : reversed_(r) {}<br>
    my_compare& operator=(const my_compare&) {return *this;}  // don't assign comparator state<br>
    bool operator()(const T& x, const T& y) const<br>
    {<br>
        if (reversed_)<br>
            return y < x;<br>
        return x < y;<br>
    }<br>
};<br>
<br>
int<br>
main()<br>
{<br>
    std::set<int, my_compare<int> > s1;<br>
    for (int i = 1; i <= 3; ++i)<br>
        s1.insert(i);<br>
    std::set<int, my_compare<int> > s2(my_compare<int>(true));<br>
    for (int i = 4; i <= 6; ++i)<br>
        s2.insert(i);<br>
    display(s1);<br>
    display(s2);<br>
    s2 = s1;<br>
    display(s2);<br>
    assert(s2.find(3) != s2.end());<br>
}<br>
<br>
{1, 2, 3}<br>
{6, 5, 4}<br>
{3, 2, 1}<br>
<br>
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.<br>

<br>
With an implementation that does do a structural copy under assignment the output of this program is:<br>
<br>
{1, 2, 3}<br>
{6, 5, 4}<br>
{1, 2, 3}<br>
Assertion failed: (s2.find(3) != s2.end()), function main, file test.cpp, line 49.<br>
Abort trap: 6<br>
<br>
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.<br>
<span class="HOEnZb"><font color="#888888"><br>
Howard<br>
<br>
</font></span></blockquote></div><br></div></div>