Subversion Repositories openrisc

// { dg-do compile }

// { dg-options "-fgnu-tm -O0"}

namespace std __attribute__ ((__visibility__ ("default"))) {

  template

    struct pair

    {

      typedef _T1 first_type;

      typedef _T2 second_type;

      _T1 first;

      _T2 second;

      pair()

      : first(), second() { }

      pair(const _T1& __a, const _T2& __b)

      : first(__a), second(__b) { }

    };

}

typedef long int ptrdiff_t;

typedef __SIZE_TYPE__ size_t;

namespace std __attribute__ ((__visibility__ ("default"))) {

  using ::ptrdiff_t;

  using ::size_t;

}

namespace std __attribute__ ((__visibility__ ("default"))) {

  struct input_iterator_tag { };

  struct output_iterator_tag { };

  struct forward_iterator_tag : public input_iterator_tag { };

  struct bidirectional_iterator_tag : public forward_iterator_tag { };

  struct random_access_iterator_tag : public bidirectional_iterator_tag { };

  template

           typename _Pointer = _Tp*, typename _Reference = _Tp&>

    struct iterator

    {

      typedef _Category iterator_category;

      typedef _Tp value_type;

      typedef _Distance difference_type;

      typedef _Pointer pointer;

      typedef _Reference reference;

    };

  template

    struct iterator_traits

    {

      typedef typename _Iterator::iterator_category iterator_category;

      typedef typename _Iterator::value_type value_type;

      typedef typename _Iterator::difference_type difference_type;

      typedef typename _Iterator::pointer pointer;

      typedef typename _Iterator::reference reference;

    };

  template

    struct iterator_traits<_Tp*>

    {

      typedef random_access_iterator_tag iterator_category;

      typedef _Tp value_type;

      typedef ptrdiff_t difference_type;

      typedef _Tp* pointer;

      typedef _Tp& reference;

    };

  template

    struct iterator_traits

    {

      typedef random_access_iterator_tag iterator_category;

      typedef _Tp value_type;

      typedef ptrdiff_t difference_type;

      typedef const _Tp* pointer;

      typedef const _Tp& reference;

    };

  template

    inline typename iterator_traits<_Iter>::iterator_category

    __iterator_category(const _Iter&)

    { return typename iterator_traits<_Iter>::iterator_category(); }

}

namespace std __attribute__ ((__visibility__ ("default"))) {

  template

    class reverse_iterator

    : public iterator::iterator_category,

        typename iterator_traits<_Iterator>::value_type,

        typename iterator_traits<_Iterator>::difference_type,

        typename iterator_traits<_Iterator>::pointer,

                      typename iterator_traits<_Iterator>::reference>

    {

    protected:

      _Iterator current;

      typedef iterator_traits<_Iterator> __traits_type;

    public:

      typedef _Iterator iterator_type;

      typedef typename __traits_type::difference_type difference_type;

      typedef typename __traits_type::pointer pointer;

      typedef typename __traits_type::reference reference;

      reverse_iterator() : current() { }

      explicit

      reverse_iterator(iterator_type __x) : current(__x) { }

      reverse_iterator(const reverse_iterator& __x)

      : current(__x.current) { }

      template

        reverse_iterator(const reverse_iterator<_Iter>& __x)

 : current(__x.base()) { }

      iterator_type

      base() const

      { return current; }

      reference

      operator*() const

      {

 _Iterator __tmp = current;

 return *--__tmp;

      }

      pointer

      operator->() const

      { return &(operator*()); }

      reverse_iterator&

      operator++()

      {

 --current;

 return *this;

      }

      reverse_iterator

      operator++(int)

      {

 reverse_iterator __tmp = *this;

 --current;

 return __tmp;

      }

      reverse_iterator&

      operator--()

      {

 ++current;

 return *this;

      }

      reverse_iterator

      operator--(int)

      {

 reverse_iterator __tmp = *this;

 ++current;

 return __tmp;

      }

      reverse_iterator

      operator+(difference_type __n) const

      { return reverse_iterator(current - __n); }

      reverse_iterator&

      operator+=(difference_type __n)

      {

 current -= __n;

 return *this;

      }

      reverse_iterator

      operator-(difference_type __n) const

      { return reverse_iterator(current + __n); }

      reverse_iterator&

      operator-=(difference_type __n)

      {

 current += __n;

 return *this;

      }

      reference

      operator[](difference_type __n) const

      { return *(*this + __n); }

    };

}

extern "C++" {

namespace std

{

  class exception

  {

  public:

    exception() throw() { }

    virtual ~exception() throw();

    virtual const char* what() const throw();

  };

  class bad_exception : public exception

  {

  public:

    bad_exception() throw() { }

    virtual ~bad_exception() throw();

    virtual const char* what() const throw();

  };

  typedef void (*terminate_handler) ();

  typedef void (*unexpected_handler) ();

  terminate_handler set_terminate(terminate_handler) throw();

  void terminate() throw() __attribute__ ((__noreturn__));

  unexpected_handler set_unexpected(unexpected_handler) throw();

  void unexpected() __attribute__ ((__noreturn__));

  bool uncaught_exception() throw() __attribute__ ((__pure__));

}

namespace __gnu_cxx __attribute__ ((__visibility__ ("default"))) {

  void __verbose_terminate_handler();

}

}

extern "C++" {

namespace std

{

  class bad_alloc : public exception

  {

  public:

    bad_alloc() throw() { }

    virtual ~bad_alloc() throw();

    virtual const char* what() const throw();

  };

  struct nothrow_t { };

  extern const nothrow_t nothrow;

  typedef void (*new_handler)();

  new_handler set_new_handler(new_handler) throw();

}

void* operator new(std::size_t, const std::nothrow_t&) throw();

void* operator new[](std::size_t, const std::nothrow_t&) throw();

void operator delete(void*, const std::nothrow_t&) throw();

void operator delete[](void*, const std::nothrow_t&) throw();

inline void* operator new(std::size_t, void* __p) throw() { return __p; }

inline void* operator new[](std::size_t, void* __p) throw() { return __p; }

inline void operator delete (void*, void*) throw() { }

inline void operator delete[](void*, void*) throw() { }

}

namespace std __attribute__ ((__visibility__ ("default"))) {

  void

  __throw_bad_exception(void) __attribute__((__noreturn__));

  __attribute__((transaction_safe))

  void

  __throw_bad_alloc(void) __attribute__((__noreturn__));

  void

  __throw_bad_cast(void) __attribute__((__noreturn__));

  void

  __throw_bad_typeid(void) __attribute__((__noreturn__));

  void

  __throw_logic_error(const char*) __attribute__((__noreturn__));

  void

  __throw_domain_error(const char*) __attribute__((__noreturn__));

  void

  __throw_invalid_argument(const char*) __attribute__((__noreturn__));

  void

  __throw_length_error(const char*) __attribute__((__noreturn__));

  void

  __throw_out_of_range(const char*) __attribute__((__noreturn__));

  void

  __throw_runtime_error(const char*) __attribute__((__noreturn__));

  void

  __throw_range_error(const char*) __attribute__((__noreturn__));

  void

  __throw_overflow_error(const char*) __attribute__((__noreturn__));

  void

  __throw_underflow_error(const char*) __attribute__((__noreturn__));

  void

  __throw_ios_failure(const char*) __attribute__((__noreturn__));

  void

  __throw_system_error(int) __attribute__((__noreturn__));

  void

  __throw_future_error(int) __attribute__((__noreturn__));

  void

  __throw_bad_function_call() __attribute__((__noreturn__));

}

namespace std __attribute__ ((__visibility__ ("default"))) {

  template

    inline void

    swap(_Tp& __a, _Tp& __b)

    {

      _Tp __tmp = (__a);

      __a = (__b);

      __b = (__tmp);

    }

  template

    inline void

    swap(_Tp (&__a)[_Nm], _Tp (&__b)[_Nm])

    {

      for (size_t __n = 0; __n < _Nm; ++__n)

 swap(__a[__n], __b[__n]);

    }

}

namespace __gnu_cxx __attribute__ ((__visibility__ ("default"))) {

  using std::size_t;

  using std::ptrdiff_t;

  template

    class new_allocator

    {

    public:

      typedef size_t size_type;

      typedef ptrdiff_t difference_type;

      typedef _Tp* pointer;

      typedef const _Tp* const_pointer;

      typedef _Tp& reference;

      typedef const _Tp& const_reference;

      typedef _Tp value_type;

      template

        struct rebind

        { typedef new_allocator<_Tp1> other; };

      new_allocator() throw() { }

      new_allocator(const new_allocator&) throw() { }

      template

        new_allocator(const new_allocator<_Tp1>&) throw() { }

      ~new_allocator() throw() { }

      pointer

      address(reference __x) const { return &__x; }

      const_pointer

      address(const_reference __x) const { return &__x; }

      __attribute__((transaction_safe))

      pointer

      allocate(size_type __n, const void* = 0)

      {

 if (__n > this->max_size())

   std::__throw_bad_alloc();

 return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp)));

      }

__attribute__((transaction_safe))

void

      deallocate(pointer __p, size_type)

      { ::operator delete(__p); }

      size_type

      max_size() const throw()

      { return size_t(-1) / sizeof(_Tp); }

      void

      construct(pointer __p, const _Tp& __val)

      { ::new((void *)__p) _Tp(__val); }

      void

      destroy(pointer __p) { __p->~_Tp(); }

    };

  template

    inline bool

    operator==(const new_allocator<_Tp>&, const new_allocator<_Tp>&)

    { return true; }

  template

    inline bool

    operator!=(const new_allocator<_Tp>&, const new_allocator<_Tp>&)

    { return false; }

}

namespace std __attribute__ ((__visibility__ ("default"))) {

  template

    class allocator;

  template<>

    class allocator

    {

    public:

      typedef size_t size_type;

      typedef ptrdiff_t difference_type;

      typedef void* pointer;

      typedef const void* const_pointer;

      typedef void value_type;

      template

        struct rebind

        { typedef allocator<_Tp1> other; };

    };

  template

    class allocator: public __gnu_cxx::new_allocator<_Tp>

    {

   public:

      typedef size_t size_type;

      typedef ptrdiff_t difference_type;

      typedef _Tp* pointer;

      typedef const _Tp* const_pointer;

      typedef _Tp& reference;

      typedef const _Tp& const_reference;

      typedef _Tp value_type;

      template

        struct rebind

        { typedef allocator<_Tp1> other; };

      allocator() throw() { }

      allocator(const allocator& __a) throw()

      : __gnu_cxx::new_allocator<_Tp>(__a) { }

      template

        allocator(const allocator<_Tp1>&) throw() { }

      ~allocator() throw() { }

    };

  template

    inline bool

    operator==(const allocator<_T1>&, const allocator<_T2>&)

    { return true; }

  template

    inline bool

    operator==(const allocator<_Tp>&, const allocator<_Tp>&)

    { return true; }

  template

    inline bool

    operator!=(const allocator<_T1>&, const allocator<_T2>&)

    { return false; }

  template

    inline bool

    operator!=(const allocator<_Tp>&, const allocator<_Tp>&)

    { return false; }

  //extern template class allocator;

  //  extern template class allocator;

  template

    struct __alloc_swap

    { static void _S_do_it(_Alloc&, _Alloc&) { } };

  template

    struct __alloc_swap<_Alloc, false>

    {

      static void

      _S_do_it(_Alloc& __one, _Alloc& __two)

      {

 if (__one != __two)

   swap(__one, __two);

      }

    };

  template

    struct __alloc_neq

    {

      static bool

      _S_do_it(const _Alloc&, const _Alloc&)

      { return false; }

    };

  template

    struct __alloc_neq<_Alloc, false>

    {

      static bool

      _S_do_it(const _Alloc& __one, const _Alloc& __two)

      { return __one != __two; }

    };

}

namespace std __attribute__ ((__visibility__ ("default"))) {

  template

    struct unary_function

    {

      typedef _Arg argument_type;

      typedef _Result result_type;

    };

  template

    struct binary_function

    {

      typedef _Arg1 first_argument_type;

      typedef _Arg2 second_argument_type;

      typedef _Result result_type;

    };

  template

    struct equal_to : public binary_function<_Tp, _Tp, bool>

    {

      bool

      operator()(const _Tp& __x, const _Tp& __y) const

      { return __x == __y; }

    };

  template

    struct not_equal_to : public binary_function<_Tp, _Tp, bool>

    {

      bool

      operator()(const _Tp& __x, const _Tp& __y) const

      { return __x != __y; }

    };

  template

    struct greater : public binary_function<_Tp, _Tp, bool>

    {

      bool

      operator()(const _Tp& __x, const _Tp& __y) const

      { return __x > __y; }

    };

  template

    struct less : public binary_function<_Tp, _Tp, bool>

    {

      bool

      operator()(const _Tp& __x, const _Tp& __y) const

      { return __x < __y; }

    };

  template

    struct _Identity : public unary_function<_Tp,_Tp>

    {

      _Tp&

      operator()(_Tp& __x) const

      { return __x; }

      const _Tp&

      operator()(const _Tp& __x) const

      { return __x; }

    };

}

namespace std __attribute__ ((__visibility__ ("default"))) {

  enum _Rb_tree_color { _S_red = false, _S_black = true };

  struct _Rb_tree_node_base

  {

    typedef _Rb_tree_node_base* _Base_ptr;

    typedef const _Rb_tree_node_base* _Const_Base_ptr;

    _Rb_tree_color _M_color;

    _Base_ptr _M_parent;

    _Base_ptr _M_left;

    _Base_ptr _M_right;

    static _Base_ptr

    _S_minimum(_Base_ptr __x)

    {

      while (__x->_M_left != 0) __x = __x->_M_left;

      return __x;

    }

    static _Const_Base_ptr

    _S_minimum(_Const_Base_ptr __x)

    {

      while (__x->_M_left != 0) __x = __x->_M_left;

      return __x;

    }

    static _Base_ptr

    _S_maximum(_Base_ptr __x)

    {

      while (__x->_M_right != 0) __x = __x->_M_right;

      return __x;

    }

    static _Const_Base_ptr

    _S_maximum(_Const_Base_ptr __x)

    {

      while (__x->_M_right != 0) __x = __x->_M_right;

      return __x;

    }

  };

  template

    struct _Rb_tree_node : public _Rb_tree_node_base

    {

      typedef _Rb_tree_node<_Val>* _Link_type;

      _Val _M_value_field;

    };

  __attribute__ ((__pure__)) _Rb_tree_node_base*

  _Rb_tree_increment(_Rb_tree_node_base* __x) throw ();

  __attribute__ ((__pure__)) const _Rb_tree_node_base*

  _Rb_tree_increment(const _Rb_tree_node_base* __x) throw ();

  __attribute__ ((__pure__)) _Rb_tree_node_base*

  _Rb_tree_decrement(_Rb_tree_node_base* __x) throw ();

  __attribute__ ((__pure__)) const _Rb_tree_node_base*

  _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw ();

  template

    struct _Rb_tree_iterator

    {

      typedef _Tp value_type;

      typedef _Tp& reference;

      typedef _Tp* pointer;

      typedef bidirectional_iterator_tag iterator_category;

      typedef ptrdiff_t difference_type;

      typedef _Rb_tree_iterator<_Tp> _Self;

      typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;

      typedef _Rb_tree_node<_Tp>* _Link_type;

      _Rb_tree_iterator()

      : _M_node() { }

      explicit

      _Rb_tree_iterator(_Link_type __x)

      : _M_node(__x) { }

      reference

      operator*() const

      { return static_cast<_Link_type>(_M_node)->_M_value_field; }

      pointer

      operator->() const

      { return &static_cast<_Link_type>(_M_node)->_M_value_field; }

      _Self&

      operator++()

      {

 _M_node = _Rb_tree_increment(_M_node);

 return *this;

      }

      _Self

      operator++(int)

      {

 _Self __tmp = *this;

 _M_node = _Rb_tree_increment(_M_node);

 return __tmp;

      }

      _Self&

      operator--()

      {

 _M_node = _Rb_tree_decrement(_M_node);

 return *this;

      }

      _Self

      operator--(int)

      {

 _Self __tmp = *this;

 _M_node = _Rb_tree_decrement(_M_node);

 return __tmp;

      }

      bool

      operator==(const _Self& __x) const

      { return _M_node == __x._M_node; }

      bool

      operator!=(const _Self& __x) const

      { return _M_node != __x._M_node; }

      _Base_ptr _M_node;

  };

  template

    struct _Rb_tree_const_iterator

    {

      typedef _Tp value_type;

      typedef const _Tp& reference;

      typedef const _Tp* pointer;

      typedef _Rb_tree_iterator<_Tp> iterator;

      typedef bidirectional_iterator_tag iterator_category;

      typedef ptrdiff_t difference_type;

      typedef _Rb_tree_const_iterator<_Tp> _Self;

      typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;

      typedef const _Rb_tree_node<_Tp>* _Link_type;

      _Rb_tree_const_iterator()

      : _M_node() { }

      explicit

      _Rb_tree_const_iterator(_Link_type __x)

      : _M_node(__x) { }

      _Rb_tree_const_iterator(const iterator& __it)

      : _M_node(__it._M_node) { }

      reference

      operator*() const

      { return static_cast<_Link_type>(_M_node)->_M_value_field; }

      pointer

      operator->() const

      { return &static_cast<_Link_type>(_M_node)->_M_value_field; }

      _Self&

      operator++()

      {

 _M_node = _Rb_tree_increment(_M_node);

 return *this;

      }

      _Self

      operator++(int)

      {

 _Self __tmp = *this;

 _M_node = _Rb_tree_increment(_M_node);

 return __tmp;

      }

      _Self&

      operator--()

      {

 _M_node = _Rb_tree_decrement(_M_node);

 return *this;

      }

      _Self

      operator--(int)

      {

 _Self __tmp = *this;

 _M_node = _Rb_tree_decrement(_M_node);

 return __tmp;

      }

      bool

      operator==(const _Self& __x) const

      { return _M_node == __x._M_node; }

      bool

      operator!=(const _Self& __x) const

      { return _M_node != __x._M_node; }

      _Base_ptr _M_node;

    };

  void

  _Rb_tree_insert_and_rebalance(const bool __insert_left,

                                _Rb_tree_node_base* __x,

                                _Rb_tree_node_base* __p,

                                _Rb_tree_node_base& __header) throw ();

  _Rb_tree_node_base*

  _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,

          _Rb_tree_node_base& __header) throw ();

  template

           typename _Compare, typename _Alloc = allocator<_Val> >

    class _Rb_tree

    {

      typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other

              _Node_allocator;

    protected:

      typedef _Rb_tree_node_base* _Base_ptr;

      typedef const _Rb_tree_node_base* _Const_Base_ptr;

    public:

      typedef _Key key_type;

      typedef _Val value_type;

      typedef value_type* pointer;

      typedef const value_type* const_pointer;

      typedef value_type& reference;

      typedef const value_type& const_reference;

      typedef _Rb_tree_node<_Val>* _Link_type;

      typedef const _Rb_tree_node<_Val>* _Const_Link_type;

      typedef size_t size_type;

      typedef ptrdiff_t difference_type;

      typedef _Alloc allocator_type;

      _Node_allocator&

      _M_get_Node_allocator()

      { return *static_cast<_Node_allocator*>(&this->_M_impl); }

      const _Node_allocator&

      _M_get_Node_allocator() const

      { return *static_cast(&this->_M_impl); }

      allocator_type

      get_allocator() const

      { return allocator_type(_M_get_Node_allocator()); }

    protected:

      _Link_type

      _M_get_node()

      { return _M_impl._Node_allocator::allocate(1); }

      __attribute__((transaction_safe))

      void

      _M_put_node(_Link_type __p)

      { _M_impl._Node_allocator::deallocate(__p, 1); }

      __attribute__((transaction_safe))

      _Link_type

      _M_create_node(const value_type& __x)

      {

 _Link_type __tmp = _M_get_node();

 try

   { get_allocator().construct(&__tmp->_M_value_field, __x); }

 catch(...)

   {

     _M_put_node(__tmp);

     throw;

   }

 return __tmp;

      }

      void

      _M_destroy_node(_Link_type __p)

      {

 get_allocator().destroy(&__p->_M_value_field);

 _M_put_node(__p);

      }

    protected:

      template

        bool _Is_pod_comparator = __is_pod(_Key_compare)>

        struct _Rb_tree_impl : public _Node_allocator

        {

   _Key_compare _M_key_compare;

   _Rb_tree_node_base _M_header;

   size_type _M_node_count;

   _Rb_tree_impl()

   : _Node_allocator(), _M_key_compare(), _M_header(),

     _M_node_count(0)

   { _M_initialize(); }

   _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a)

   : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),

     _M_node_count(0)

   { _M_initialize(); }

 private:

   void

   _M_initialize()

   {

     this->_M_header._M_color = _S_red;

     this->_M_header._M_parent = 0;

     this->_M_header._M_left = &this->_M_header;

     this->_M_header._M_right = &this->_M_header;

   }

 };

      _Rb_tree_impl<_Compare> _M_impl;

    protected:

      _Base_ptr&

      _M_root()

      { return this->_M_impl._M_header._M_parent; }

      _Const_Base_ptr

      _M_root() const

      { return this->_M_impl._M_header._M_parent; }

      _Base_ptr&

      _M_leftmost()

      { return this->_M_impl._M_header._M_left; }

      _Const_Base_ptr

      _M_leftmost() const

      { return this->_M_impl._M_header._M_left; }

      _Base_ptr&

      _M_rightmost()

      { return this->_M_impl._M_header._M_right; }

      _Const_Base_ptr

      _M_rightmost() const

      { return this->_M_impl._M_header._M_right; }

      _Link_type

      _M_begin()

      { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }

      _Const_Link_type

      _M_begin() const

      {

 return static_cast<_Const_Link_type>

   (this->_M_impl._M_header._M_parent);

      }

      _Link_type

      _M_end()

      { return static_cast<_Link_type>(&this->_M_impl._M_header); }

      _Const_Link_type

      _M_end() const

      { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }

      static const_reference

      _S_value(_Const_Link_type __x)

      { return __x->_M_value_field; }

      static const _Key&

      _S_key(_Const_Link_type __x)

      { return _KeyOfValue()(_S_value(__x)); }

      static _Link_type

      _S_left(_Base_ptr __x)

      { return static_cast<_Link_type>(__x->_M_left); }

      static _Const_Link_type

      _S_left(_Const_Base_ptr __x)

      { return static_cast<_Const_Link_type>(__x->_M_left); }

      static _Link_type

      _S_right(_Base_ptr __x)

      { return static_cast<_Link_type>(__x->_M_right); }

      static _Const_Link_type

      _S_right(_Const_Base_ptr __x)

      { return static_cast<_Const_Link_type>(__x->_M_right); }

      static const_reference

      _S_value(_Const_Base_ptr __x)

      { return static_cast<_Const_Link_type>(__x)->_M_value_field; }

      static const _Key&

      _S_key(_Const_Base_ptr __x)

      { return _KeyOfValue()(_S_value(__x)); }

    public:

      typedef _Rb_tree_iterator iterator;

      typedef _Rb_tree_const_iterator const_iterator;

      typedef std::reverse_iterator reverse_iterator;

      typedef std::reverse_iterator const_reverse_iterator;

    private:

      iterator

      _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __y,

   const value_type& __v);

    public:

      _Rb_tree() { }

      iterator

      begin()

      {

 return iterator(static_cast<_Link_type>

   (this->_M_impl._M_header._M_left));

      }

      const_iterator

      begin() const

      {

 return const_iterator(static_cast<_Const_Link_type>

         (this->_M_impl._M_header._M_left));

      }

      iterator

      end()

      { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); }

      const_iterator

      end() const

      {

 return const_iterator(static_cast<_Const_Link_type>

         (&this->_M_impl._M_header));

      }

      pair

      _M_insert_unique(const value_type& __x);

    };

  template

           typename _Compare, typename _Alloc>

    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator

    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::

    _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v)

    {

      _Link_type __z = _M_create_node(__v);

      return iterator(__z);

    }

  template

           typename _Compare, typename _Alloc>

    pair

      _Compare, _Alloc>::iterator, bool>

    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::

    _M_insert_unique(const _Val& __v)

    {

      _Link_type __x = _M_begin();

      _Link_type __y = _M_end();

      iterator __j = iterator(__y);

 return pair(_M_insert_(__x, __y, __v), true);

    }

}

namespace std __attribute__ ((__visibility__ ("default"))) {

  template,

    typename _Alloc = std::allocator<_Key> >

    class set

    {

    public:

      typedef _Key key_type;

      typedef _Key value_type;

      typedef _Compare key_compare;

      typedef _Compare value_compare;

      typedef _Alloc allocator_type;

    private:

      typedef typename _Alloc::template rebind<_Key>::other _Key_alloc_type;

      typedef _Rb_tree,

         key_compare, _Key_alloc_type> _Rep_type;

      _Rep_type _M_t;

    public:

      typedef typename _Key_alloc_type::pointer pointer;

      typedef typename _Key_alloc_type::const_pointer const_pointer;

      typedef typename _Key_alloc_type::reference reference;

      typedef typename _Key_alloc_type::const_reference const_reference;

      typedef typename _Rep_type::const_iterator iterator;

      typedef typename _Rep_type::const_iterator const_iterator;

      typedef typename _Rep_type::const_reverse_iterator reverse_iterator;

      typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;

      typedef typename _Rep_type::size_type size_type;

      typedef typename _Rep_type::difference_type difference_type;

      std::pair

      insert(const value_type& __x)

      {

   _M_t._M_insert_unique(__x);

      }

    };

}

__attribute__((transaction_pure))

void* operator new(size_t);

__attribute__((transaction_pure))

void operator delete(void*);

class Widget

{

private:

};

class Screen

{

protected:

std::set widgets;

public:

void addWidget(Widget* widget);

};

void Screen::addWidget(Widget* widget)

{

widgets.insert(widget);

}