[Bug libstdc++/78595] Unnecessary copies in _Rb_tree

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=78595

--- Comment #7 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Pure evil:


#include <map>
#include <cassert>

struct Key { int key; };

struct X {
  operator std::pair<const Key, int>() const { return { { x }, 0 }; }
  int x;
};

template<typename T>
struct Alloc
{
  Alloc() = default;
  template<typename U>
    Alloc(const Alloc<U>&) { }
  using value_type = T;

  T* allocate(std::size_t n) { return std::allocator<T>().allocate(n); }
  void deallocate(T* p, std::size_t n) { std::allocator<T>().deallocate(p, n);
}

  template<typename U>
    void construct(U* p, const X&) { ::new (p) U{ { 99 }, 0}; }

  template<typename U>
    bool operator==(const Alloc<U>&) { return true; }
  template<typename U>
    bool operator!=(const Alloc<U>&) { return false; }
};

bool operator<(const Key& l, const Key& r) { return l.key < r.key; }

int main()
{
  using namespace std;
  map<Key, int, less<>, Alloc<pair<const Key, int>>> m;
  m.insert(X{});
  m.insert(X{}); // RB tree is corrupted
  if (m.size() != 1)
    __builtin_puts("RB tree corrupt");

  map<Key, int, less<>, Alloc<pair<const Key, int>>> m2;
  m.insert(X{});
  m.insert(X{99});
  if (m.size() != 2)
    __builtin_puts("RB tree failed to insert distinct value");
}