// { dg-do compile }
// { dg-options "-O -fstrict-aliasing -ftree-pre -fno-tree-fre -fno-tree-sra -Wno-return-type" }

typedef __SIZE_TYPE__ size_t;
namespace std 
{
  template < class _T1, class > struct pair
  {
    _T1 first;
  };
}
namespace __gnu_cxx
{
  template < typename _Tp > class new_allocator
  {
  public:
    typedef size_t size_type;
    typedef _Tp * pointer;
    typedef _Tp const_pointer;
    typedef _Tp & reference;
    typedef const _Tp & const_reference;
    template < typename _Tp1 > struct rebind
    {
      typedef new_allocator < _Tp1 > other;
    };
  };
}
namespace std
{
template < typename _Tp > class allocator:
  public __gnu_cxx::new_allocator < _Tp >
  {};
  template < typename, typename, typename > struct binary_function;
  template < typename _Tp > struct less:binary_function < _Tp, _Tp, bool >
  {};
}
namespace __gnu_cxx
{
  namespace typelist
  {
    struct null_type;
    template < typename Root > struct node
    {
      typedef Root root;
    };
    template < typename, typename > struct chain;
    namespace detail
    {
      template < typename, int >struct chain_at_index_;
      template
	<
	typename
	Hd, typename Tl > struct chain_at_index_ <chain < Hd, Tl >, 0 >
      {
	typedef Hd type;
      };
      template
	<
	typename
	Hd, typename Tl, int i > struct chain_at_index_ <chain < Hd, Tl >, i >
      {
	typedef typename chain_at_index_ < Tl, i - 1 >::type type;
      };
    }
    template < typename Typelist, int i > struct at_index
    {
      typedef typename Typelist::root root_type;
      typedef detail::chain_at_index_ < root_type, i > index_type;
      typedef typename index_type::type type;
    };
    template < typename T1, typename T2 > struct create2
    {
      typedef node < chain < T1, chain < T2, null_type > > >type;
    };
  }
}
namespace std
{
  namespace tr1
  {
    template < typename _Tp, _Tp __v > struct integral_constant
    {
      static const _Tp value = __v;
    };
    typedef integral_constant < bool, false > false_type;
    template < typename, typename > struct is_same:false_type
    {};
  }
}
using std::tr1::is_same;
namespace __gnu_pbds
{
  struct null_mapped_type;
  struct rb_tree_tag;
  namespace detail
  {
    template < typename, typename, typename > struct basic_tree_policy_base;
    template
      <
      typename
      Const_Node_Iterator,
      typename
      Allocator
      >
      struct
      basic_tree_policy_base
      <Const_Node_Iterator, Const_Node_Iterator, Allocator >
    {};
  }
  template
    < typename, typename, typename, typename > struct null_tree_node_update;
template < typename Const_Node_Iterator, typename Node_Iterator, typename, typename Allocator > class tree_order_statistics_node_update:
  detail::basic_tree_policy_base
    < Const_Node_Iterator, Node_Iterator, Allocator >
  {
  public:
    typedef Allocator allocator_type;
    typedef typename allocator_type::size_type size_type;
    typedef size_type metadata_type;
    typedef Const_Node_Iterator const_node_iterator;
    typedef Node_Iterator node_iterator;
    typedef
      typename
      allocator_type::template
      rebind < metadata_type >::other::reference metadata_reference;
    void operator () (node_iterator, const_node_iterator) const;
  };
  template
    <
    typename
    Const_Node_Iterator,
    class
    Node_Iterator,
    class
    Cmp_Fn,
    class
    Allocator
    >
    inline
    void
    tree_order_statistics_node_update
    <
    Const_Node_Iterator,
    Node_Iterator,
    Cmp_Fn,
    Allocator
    >::operator
    () (node_iterator node_it, const_node_iterator end_nd_it) const
  {
    node_iterator l_child_it;
    size_type
      l_rank = (l_child_it == end_nd_it) ? : l_child_it.get_metadata ();
    node_iterator r_child_it = node_it.get_r_child ();
    size_type
      r_rank = (r_child_it == end_nd_it) ? : r_child_it.get_metadata ();
    const_cast
      < metadata_reference > (node_it.get_metadata ()) = l_rank + r_rank;
  }
  namespace
  {
    template < typename, typename, typename, bool > struct value_type_base;
    template
      <
      typename
      Key,
      typename
      Allocator
      > struct value_type_base <Key, null_mapped_type, Allocator, false >
    {
      typedef Key value_type;
      typedef
	typename
	Allocator::template rebind < value_type >::other value_type_allocator;
      typedef typename value_type_allocator::pointer pointer;
      typedef typename value_type_allocator::const_pointer const_pointer;
      typedef typename value_type_allocator::reference reference;
      typedef typename value_type_allocator::const_reference const_reference;
    };
    template
      <
      typename
      Key,
      typename
      Mapped, typename Alloc, bool Store_Extra > struct vt_base_selector
    {
      typedef value_type_base < Key, Mapped, Alloc, Store_Extra > type;
    };
    template
      <
      typename
      Key,
      typename
      Mapped,
      typename
      Alloc,
      bool
      Store_Extra
      >
      struct
      types_traits:vt_base_selector < Key, Mapped, Alloc, Store_Extra >::type
    {};
    template < typename, class, class > struct dumconst_node_iterator;
    template
      <
      typename
      Key,
      typename
      Mapped,
      class,
      class
      Node_And_It_Traits, class Allocator > class bin_search_tree_no_data_
    {
    protected:
      typedef
	typename
	Allocator::template
	rebind
	< typename Node_And_It_Traits::node >::other::pointer node_pointer;
      typedef
	typename
	types_traits
	< Key, Mapped, Allocator, false >::const_reference const_reference;
      typedef typename Node_And_It_Traits::point_iterator point_iterator;
      typedef typename Node_And_It_Traits::node_update node_update;
      void rotate_right (node_pointer);
      template
	<
	typename
	Node_Update_ > void apply_update (node_pointer, Node_Update_ *);
    };
    template
      <
      typename
      Key,
      typename
      Mapped,
      class
      Cmp_Fn,
      class
      Node_And_It_Traits,
      class
      Allocator
      >
      void
      bin_search_tree_no_data_
      <
      Key,
      Mapped,
      Cmp_Fn, Node_And_It_Traits, Allocator >::rotate_right (node_pointer p_x)
    {
      node_pointer p_y = p_x->m_p_parent;
      p_y->m_p_right = p_x;
      apply_update (p_x, this);
      apply_update (p_x->m_p_parent, (node_update *) this);
    }
    template
      <
      typename
      Key,
      typename
      Mapped,
      class
      Cmp_Fn,
      class
      Node_And_It_Traits,
      class
      Allocator
      >
      template
      <
      typename
      Node_Update_
      >
      void
      bin_search_tree_no_data_
      <
      Key,
      Mapped,
      Cmp_Fn,
      Node_And_It_Traits,
      Allocator >::apply_update (node_pointer p_nd, Node_Update_ *)
    {
      node_update ()((p_nd), ((0)));
    }
  }
  namespace detail
  {
  template < typename Key, typename Mapped, typename Cmp_Fn, typename Node_And_It_Traits, typename Allocator > class rb_tree_no_data_:
    bin_search_tree_no_data_
      < Key, Mapped, Cmp_Fn, Node_And_It_Traits, Allocator >
    {
      typedef
	bin_search_tree_no_data_
	< Key, Mapped, Cmp_Fn, Node_And_It_Traits, Allocator > base_type;
      typedef typename base_type::node_pointer node_pointer;
    public:
      typedef typename base_type::const_reference const_reference;
      typedef typename base_type::point_iterator point_iterator;
      std::pair < point_iterator, bool > insert (const_reference);
      void insert_fixup (node_pointer);
    };
    template
      <
      typename
      Key,
      typename
      Mapped,
      typename
      Cmp_Fn,
      typename
      Node_And_It_Traits,
      typename
      Allocator
      >
      std::pair
      <
      typename
      rb_tree_no_data_
      <
      Key,
      Mapped,
      Cmp_Fn,
      Node_And_It_Traits,
      Allocator
      >::point_iterator,
      bool
      >
      rb_tree_no_data_
      <
      Key,
      Mapped,
      Cmp_Fn, Node_And_It_Traits, Allocator >::insert (const_reference)
    {
      std::pair < point_iterator, bool > ins_pair;
{
	insert_fixup (ins_pair.first.m_p_nd);
      }
    }
    template
      <
      typename
      Key,
      typename
      Mapped,
      typename
      Cmp_Fn,
      typename
      Node_And_It_Traits,
      typename
      Allocator
      >
      void
      rb_tree_no_data_
      <
      Key,
      Mapped,
      Cmp_Fn,
      Node_And_It_Traits, Allocator >::insert_fixup (node_pointer p_nd)
    {
{
{
{
	    this->rotate_right (p_nd);
	  }
	}
      }
    }
    template
      <
      typename,
      typename, typename, typename, typename > struct container_base_dispatch;
    template
      <
      typename
      Key,
      typename
      Policy_Tl,
      typename
      Alloc
      >
      struct
      container_base_dispatch
      <Key, null_mapped_type, rb_tree_tag, Policy_Tl, Alloc >
    {
      typedef __gnu_cxx::typelist::at_index < Policy_Tl, 0 > at0;
      typedef typename at0::type at0t;
      typedef __gnu_cxx::typelist::at_index < Policy_Tl, 1 > at1;
      typedef typename at1::type at1t;
      typedef
	rb_tree_no_data_ < Key, null_mapped_type, at0t, at1t, Alloc > type;
    };
    template
      <
      typename
      Node_Pointer,
      typename,
      typename,
      typename,
      typename, typename, bool, class > class bin_search_tree_const_it_
    {
    public:
      Node_Pointer m_p_nd;
    };
    template
      <
      typename
      Node,
      class
      Const_Iterator,
      class Iterator, class Allocator > class bin_search_tree_const_node_it_
    {
      typedef
	typename
	Allocator::template rebind < Node >::other::pointer node_pointer;
    public:
      typedef typename Node::metadata_type metadata_type;
      typedef
	typename
	Allocator::template
	rebind
	< metadata_type >::other::const_reference const_metadata_reference;
    bin_search_tree_const_node_it_ (node_pointer p_nd):
      m_p_nd ((p_nd))
      {}
      const_metadata_reference get_metadata ()
      {
	return (m_p_nd->get_metadata ());
      }
      bin_search_tree_const_node_it_ ()
      {}
      bin_search_tree_const_node_it_
	< Node, Const_Iterator, Iterator, Allocator > get_r_child ()
      {
	return ((m_p_nd->m_p_right));
      }
      bool operator == (bin_search_tree_const_node_it_)
      { return true; }
      node_pointer m_p_nd;
    };
    template
      <
      typename,
      typename,
      class,
      template
      <
      typename,
      class,
      class, class > class, class, class > struct bin_search_tree_traits;
    template
      <
      typename
      Key,
      class
      Cmp_Fn,
      template
      <
      typename,
      class,
      class,
      class
      >
      class
      Node_Update,
      class
      Node,
      class
      Allocator
      >
      struct
      bin_search_tree_traits
      <Key, null_mapped_type, Cmp_Fn, Node_Update, Node, Allocator >
    {
      typedef
	types_traits < Key, null_mapped_type, Allocator, false > type_traits;
      typedef Node node;
      typedef
	bin_search_tree_const_it_
	<
	typename
	Allocator::template
	rebind
	<
	node
	>::other::pointer,
	typename
	type_traits::value_type,
	typename
	type_traits::pointer,
	typename
	type_traits::const_pointer,
	typename
	type_traits::reference,
	typename
	type_traits::const_reference, true, Allocator > const_point_iterator;
      typedef const_point_iterator point_iterator;
      typedef
	bin_search_tree_const_node_it_
	<
	Node,
	const_point_iterator, point_iterator, Allocator > const_node_iterator;
      typedef const_node_iterator node_iterator;
      typedef
	Node_Update
	< const_node_iterator, node_iterator, Cmp_Fn, Allocator > node_update;
    };
    template < typename Node_Update, bool > struct tree_metadata_helper
    {
      typedef typename Node_Update::metadata_type type;
    };
    template
      <
      typename
      Key,
      typename
      Data,
      class
      Cmp_Fn,
      template
      <
      typename,
      class,
      class,
      class
      >
      class Node_Update, class Allocator > struct tree_node_metadata_selector
    {
      typedef
	dumconst_node_iterator < Key, Data, Allocator > dumconst_node_it;
      enum
      {
	null_update = is_same < Node_Update < dumconst_node_it,
	dumconst_node_it,
	Cmp_Fn,
	Allocator >,
	null_tree_node_update < dumconst_node_it,
	dumconst_node_it,
	Cmp_Fn,
	Allocator > >::value
      };
      typedef
	typename
	tree_metadata_helper
	<
	Node_Update
	<
	dumconst_node_it,
	dumconst_node_it, Cmp_Fn, Allocator >, null_update >::type type;
    };
    template
      <
      typename,
      typename,
      class,
      template
      <
      typename,
      class, class, class > class, class, class > struct tree_traits;
    template < typename Value_Type, class Metadata, class Allocator > struct rb_tree_node_
    {
      typedef Metadata metadata_type;
      typedef
	typename
	Allocator::template
	rebind
	<
	rb_tree_node_
	< Value_Type, Metadata, Allocator > >::other::pointer node_pointer;
      typedef
	typename
	Allocator::template
	rebind < metadata_type >::other::reference metadata_reference;
        metadata_reference get_metadata ()
      {
	return m_metadata;
      }
      node_pointer m_p_right;
      node_pointer m_p_parent;
      metadata_type m_metadata;
    };
    template
      <
      typename
      Key,
      typename
      Mapped,
      typename
      Cmp_Fn,
      template
      <
      typename,
      class,
      class,
      class
      >
      class
      Node_Update,
      typename
      Allocator
      >
      struct
      tree_traits
      <Key,
      Mapped,
      Cmp_Fn,
      Node_Update,
      rb_tree_tag,
      Allocator
      >:bin_search_tree_traits
      <
      Key,
      Mapped,
      Cmp_Fn,
      Node_Update,
      rb_tree_node_
      <
      typename
      types_traits
      <
      Key,
      Mapped,
      Allocator,
      false
      >::value_type,
      typename
      tree_node_metadata_selector
      <
      Key,
      Mapped, Cmp_Fn, Node_Update, Allocator >::type, Allocator >, Allocator >
    {};
  }
template < typename Key, typename Mapped, typename Tag, typename Policy_Tl, typename Allocator > class container_base:
  public
    detail::container_base_dispatch
    < Key, Mapped, Tag, Policy_Tl, Allocator >::type
  {};
template < typename Key, typename Mapped, typename Tag, typename, typename Policy_Tl, typename Allocator > class basic_tree:
  public
    container_base < Key, Mapped, Tag, Policy_Tl, Allocator >
  {};
  template
    <
    typename
    Key,
    typename
    Mapped,
    typename
    Cmp_Fn
    =
    std::less
    <
    Key
    >,
    typename
    Tag
    =
    rb_tree_tag,
    template
    <
    typename,
    typename,
    typename,
    typename
    >
    class
    Node_Update
    =
    null_tree_node_update,
    typename
    Allocator
    =
    std::allocator
    <
    char
    > >class
    tree:public
    basic_tree
    <
    Key,
    Mapped,
    Tag,
    detail::tree_traits
    <
    Key,
    Mapped,
    Cmp_Fn,
    Node_Update,
    Tag,
    Allocator
    >,
    typename
    __gnu_cxx::typelist::create2
    <
    Cmp_Fn,
    detail::tree_traits
    < Key, Mapped, Cmp_Fn, Node_Update, Tag, Allocator > >::type, Allocator >
  {};
}
using namespace std;
using namespace __gnu_pbds;
typedef
  tree
  <
  int,
  null_mapped_type,
  less < int >, rb_tree_tag, tree_order_statistics_node_update > set_t;
int main ()
{
  set_t s;
  s.insert (12);
}