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

[Ahmed Charles]

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.

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.

I wonder if I can usefully use this comparison object in algorithms...

________________________________
> Date: Tue, 3 Dec 2013 15:53:08 -0500 
> From: silvas at purdue.edu 
> To: howard.hinnant at gmail.com 
> CC: cfe-dev at cs.uiuc.edu 
> Subject: Re: [cfe-dev] libc++ std::map self-assignment bug 
>  
>  
>  
>  
> On Sat, Nov 30, 2013 at 11:53 PM, Howard Hinnant  
> <howard.hinnant at gmail.com<mailto:howard.hinnant at gmail.com>> wrote: 
>  
> On Nov 30, 2013, at 11:02 PM, Sean Silva  
> <silvas at purdue.edu<mailto: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 
>  
>  
>  
> _______________________________________________ cfe-dev mailing list  
> cfe-dev at cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev