[gcc] GCC 4.5.0=>4.5.1

gcc/libstdc++-v3/include/ext/pb_ds/assoc_container.hpp

Index: gcc/libstdc++-v3/include/ext/pb_ds/assoc_container.hpp
diff --git a/gcc/libstdc++-v3/include/ext/pb_ds/assoc_container.hpp b/gcc/libstdc++-v3/include/ext/pb_ds/assoc_container.hpp
deleted file mode 100644
index 7bccb88fff112e2d005d3173fb266bb39f5926a1..0000000000000000000000000000000000000000
--- a/gcc/libstdc++-v3/include/ext/pb_ds/assoc_container.hpp
+++ /dev/null
@@ -1,683 +0,0 @@
-// -*- C++ -*-
-
-// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc.
-//
-// This file is part of the GNU ISO C++ Library.  This library is free
-// software; you can redistribute it and/or modify it under the terms
-// of the GNU General Public License as published by the Free Software
-// Foundation; either version 3, or (at your option) any later
-// version.
-
-// This library is distributed in the hope that it will be useful, but
-// WITHOUT ANY WARRANTY; without even the implied warranty of
-// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
-// General Public License for more details.
-
-// Under Section 7 of GPL version 3, you are granted additional
-// permissions described in the GCC Runtime Library Exception, version
-// 3.1, as published by the Free Software Foundation.
-
-// You should have received a copy of the GNU General Public License and
-// a copy of the GCC Runtime Library Exception along with this program;
-// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
-// <http://www.gnu.org/licenses/>.
-
-// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
-
-// Permission to use, copy, modify, sell, and distribute this software
-// is hereby granted without fee, provided that the above copyright
-// notice appears in all copies, and that both that copyright notice
-// and this permission notice appear in supporting documentation. None
-// of the above authors, nor IBM Haifa Research Laboratories, make any
-// representation about the suitability of this software for any
-// purpose. It is provided "as is" without express or implied
-// warranty.
-
-/**
- * @file assoc_container.hpp
- * Contains associative containers.
- */
-
-#ifndef PB_DS_ASSOC_CNTNR_HPP
-#define PB_DS_ASSOC_CNTNR_HPP
-
-#include <ext/typelist.h>
-#include <ext/pb_ds/tag_and_trait.hpp>
-#include <ext/pb_ds/detail/standard_policies.hpp>
-#include <ext/pb_ds/detail/container_base_dispatch.hpp>
-#include <ext/pb_ds/detail/basic_tree_policy/traits.hpp>
-
-namespace __gnu_pbds
-{
-#define PB_DS_BASE_C_DEC \
-  detail::container_base_dispatch<Key, Mapped, Tag, Policy_Tl, Allocator>::type
-
-  // An abstract basic associative container.
-  template<typename Key, 
-	   typename Mapped, 
-	   typename Tag, 
-	   typename Policy_Tl, 
-	   typename Allocator>
-  class container_base : public PB_DS_BASE_C_DEC
-  {
-  private:
-    typedef typename PB_DS_BASE_C_DEC 			base_type;
-
-  public:
-    typedef Tag 					container_category;
-    typedef Allocator 					allocator_type;
-    typedef typename allocator_type::size_type 		size_type;
-    typedef typename allocator_type::difference_type 	difference_type;
-
-    // key_type
-    typedef typename allocator_type::template rebind<Key>::other::value_type key_type;
-    typedef typename allocator_type::template rebind<key_type>::other key_rebind;
-    typedef typename key_rebind::reference 		key_reference;
-    typedef typename key_rebind::const_reference 	const_key_reference;
-    typedef typename key_rebind::pointer 		key_pointer;
-    typedef typename key_rebind::const_pointer 		const_key_pointer;
-
-    // mapped_type
-    typedef Mapped 					mapped_type;
-    typedef typename allocator_type::template rebind<mapped_type>::other mapped_rebind;
-    typedef typename mapped_rebind::reference 		mapped_reference;
-    typedef typename mapped_rebind::const_reference	const_mapped_reference;
-    typedef typename mapped_rebind::pointer 		mapped_pointer;
-    typedef typename mapped_rebind::const_pointer 	const_mapped_pointer;
-
-    // value_type
-    typedef typename base_type::value_type 		value_type;
-    typedef typename allocator_type::template rebind<value_type>::other value_rebind;
-    typedef typename value_rebind::reference		reference;
-    typedef typename value_rebind::const_reference 	const_reference;
-    typedef typename value_rebind::pointer 		pointer;
-    typedef typename value_rebind::const_pointer 	const_pointer;
-
-    // iterators
-    typedef typename base_type::iterator 		iterator;
-    typedef typename base_type::const_iterator 		const_iterator;
-    typedef typename base_type::point_iterator 		point_iterator;
-    typedef typename base_type::const_point_iterator 	const_point_iterator;
-
-    virtual
-    ~container_base() { }
-
-  protected:
-#define PB_DS_CLASS_NAME 		container_base
-#include <ext/pb_ds/detail/constructors_destructor_fn_imps.hpp>
-#undef PB_DS_CLASS_NAME
-  };
-
-#undef PB_DS_BASE_C_DEC
-
-
-#define PB_DS_BASE_C_DEC \
-  container_base<Key, Mapped, Tag, typename __gnu_cxx::typelist::append< \
-  typename __gnu_cxx::typelist::create4<Hash_Fn, Eq_Fn, Resize_Policy, detail::integral_constant<int, Store_Hash> >::type, Policy_TL>::type, Allocator>
-
-  // An abstract basic hash-based associative container.
-  template<typename Key,
-	   typename Mapped,
-	   typename Hash_Fn,
-	   typename Eq_Fn,
-	   typename Resize_Policy,
-	   bool Store_Hash,
-	   typename Tag,
-	   typename Policy_TL,
-	   typename Allocator>
-  class basic_hash_table : public PB_DS_BASE_C_DEC
-  {
-  private:
-    typedef PB_DS_BASE_C_DEC base_type;
-
-  public:
-    virtual
-    ~basic_hash_table() { }
-
-  protected:
-#define PB_DS_CLASS_NAME basic_hash_table
-#include <ext/pb_ds/detail/constructors_destructor_fn_imps.hpp>
-#undef PB_DS_CLASS_NAME
-
-  private:
-    basic_hash_table& 
-    operator=(const base_type&);
-  };
-
-#undef PB_DS_BASE_C_DEC
-
-
-#define PB_DS_BASE_C_DEC \
-  basic_hash_table<Key, Mapped,	Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \
-		   cc_hash_tag,	\
-	  typename __gnu_cxx::typelist::create1<Comb_Hash_Fn>::type, Allocator>
-
-  // A concrete collision-chaining hash-based associative container.
-  template<typename Key,
-	   typename Mapped,
-	   typename Hash_Fn = typename detail::default_hash_fn<Key>::type,
-	   typename Eq_Fn = typename detail::default_eq_fn<Key>::type,
-	   typename Comb_Hash_Fn = detail::default_comb_hash_fn::type,
-	   typename Resize_Policy = typename detail::default_resize_policy<Comb_Hash_Fn>::type,
-	   bool Store_Hash = detail::default_store_hash,
-	   typename Allocator = std::allocator<char> >
-  class cc_hash_table :  public PB_DS_BASE_C_DEC
-  {
-  private:
-    typedef PB_DS_BASE_C_DEC 	base_type;
-
-  public:
-    typedef Hash_Fn 		hash_fn;
-    typedef Eq_Fn 		eq_fn;
-    typedef Resize_Policy 	resize_policy;
-    typedef Comb_Hash_Fn 	comb_hash_fn;
-
-    // Default constructor.
-    cc_hash_table() { }
-
-    // Constructor taking some policy objects. r_hash_fn will be
-    // copied by the Hash_Fn object of the container object.
-    cc_hash_table(const hash_fn& h) 
-    : base_type(h) { }
-
-    // Constructor taking some policy objects. r_hash_fn will be
-    // copied by the hash_fn object of the container object, and
-    // r_eq_fn will be copied by the eq_fn object of the container
-    // object.
-    cc_hash_table(const hash_fn& h, const eq_fn& e)
-    : base_type(h, e) { }
-
-    // Constructor taking some policy objects. r_hash_fn will be
-    // copied by the hash_fn object of the container object, r_eq_fn
-    // will be copied by the eq_fn object of the container object, and
-    // r_comb_hash_fn will be copied by the comb_hash_fn object of the
-    // container object.
-    cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch)
-    : base_type(h, e, ch) { }
-
-    // Constructor taking some policy objects. r_hash_fn will be
-    // copied by the hash_fn object of the container object, r_eq_fn
-    // will be copied by the eq_fn object of the container object,
-    // r_comb_hash_fn will be copied by the comb_hash_fn object of the
-    // container object, and r_resize_policy will be copied by the
-    // resize_policy object of the container object.
-    cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch, 
-		  const resize_policy& rp)    
-    : base_type(h, e, ch, rp) { }
-
-    // Constructor taking __iterators to a range of value_types. The
-    // value_types between first_it and last_it will be inserted into
-    // the container object.
-    template<typename It>
-    cc_hash_table(It first, It last)
-    { base_type::copy_from_range(first, last); }
-
-    // Constructor taking __iterators to a range of value_types and
-    // some policy objects. The value_types between first_it and
-    // last_it will be inserted into the container object.
-    template<typename It>
-    cc_hash_table(It first, It last, const hash_fn& h)
-    : base_type(h)
-    { copy_from_range(first, last); }
-
-    // Constructor taking __iterators to a range of value_types and
-    // some policy objects The value_types between first_it and
-    // last_it will be inserted into the container object. r_hash_fn
-    // will be copied by the hash_fn object of the container object,
-    // and r_eq_fn will be copied by the eq_fn object of the container
-    // object.
-    template<typename It>
-    cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e)
-    : base_type(h, e)
-    { copy_from_range(first, last); }
-
-    // Constructor taking __iterators to a range of value_types and
-    // some policy objects The value_types between first_it and
-    // last_it will be inserted into the container object. r_hash_fn
-    // will be copied by the hash_fn object of the container object,
-    // r_eq_fn will be copied by the eq_fn object of the container
-    // object, and r_comb_hash_fn will be copied by the comb_hash_fn
-    // object of the container object.
-    template<typename It>
-    cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
-		  const comb_hash_fn& ch)
-    : base_type(h, e, ch)
-    { copy_from_range(first, last); }
-
-    // Constructor taking __iterators to a range of value_types and
-    // some policy objects The value_types between first_it and
-    // last_it will be inserted into the container object. r_hash_fn
-    // will be copied by the hash_fn object of the container object,
-    // r_eq_fn will be copied by the eq_fn object of the container
-    // object, r_comb_hash_fn will be copied by the comb_hash_fn
-    // object of the container object, and r_resize_policy will be
-    // copied by the resize_policy object of the container object.
-    template<typename It>
-    cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, 
-		  const comb_hash_fn& ch, const resize_policy& rp)
-    : base_type(h, e, ch, rp)
-    { copy_from_range(first, last); }
-
-    cc_hash_table(const cc_hash_table& other)
-    : base_type((const base_type&)other)
-    { }
-
-    virtual
-    ~cc_hash_table() { }
-
-    cc_hash_table& 
-    operator=(const cc_hash_table& other)
-    {
-      if (this != &other)
-	{
-	  cc_hash_table tmp(other);
-	  swap(tmp);
-	}
-      return *this;
-    }
-
-    void
-    swap(cc_hash_table& other)
-    { base_type::swap(other); }
-  };
-
-#undef PB_DS_BASE_C_DEC
-
-
-#define PB_DS_BASE_C_DEC \
-  basic_hash_table<Key, Mapped,	Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \
-		   gp_hash_tag, \
-		   typename __gnu_cxx::typelist::create2<Comb_Probe_Fn, Probe_Fn>::type, Allocator>
-
-  // A concrete general-probing hash-based associative container.
-  template<typename Key,
-	   typename Mapped,
-	   typename Hash_Fn = typename detail::default_hash_fn<Key>::type,
-	   typename Eq_Fn = typename detail::default_eq_fn<Key>::type,
-	   typename Comb_Probe_Fn = detail::default_comb_hash_fn::type,
-	   typename Probe_Fn = typename detail::default_probe_fn<Comb_Probe_Fn>::type,
-	   typename Resize_Policy = typename detail::default_resize_policy<Comb_Probe_Fn>::type,
-	   bool Store_Hash = detail::default_store_hash,
-	   typename Allocator = std::allocator<char> >
-  class gp_hash_table : public PB_DS_BASE_C_DEC
-  {
-  private:
-    typedef PB_DS_BASE_C_DEC 	base_type;
-
-  public:
-    typedef Hash_Fn 		hash_fn;
-    typedef Eq_Fn 		eq_fn;
-    typedef Comb_Probe_Fn	comb_probe_fn;
-    typedef Probe_Fn 		probe_fn;
-    typedef Resize_Policy 	resize_policy;
-
-    // Default constructor.
-    gp_hash_table() { }
-
-    // Constructor taking some policy objects. r_hash_fn will be
-    // copied by the hash_fn object of the container object.
-    gp_hash_table(const hash_fn& h)
-    : base_type(h) { }
-
-    // Constructor taking some policy objects. r_hash_fn will be
-    // copied by the hash_fn object of the container object, and
-    // r_eq_fn will be copied by the eq_fn object of the container
-    // object.
-    gp_hash_table(const hash_fn& h, const eq_fn& e)
-    : base_type(h, e) { }
-
-    // Constructor taking some policy objects. r_hash_fn will be
-    // copied by the hash_fn object of the container object, r_eq_fn
-    // will be copied by the eq_fn object of the container object, and
-    // r_comb_probe_fn will be copied by the comb_probe_fn object of
-    // the container object.
-    gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp)
-    : base_type(h, e, cp) { }
-
-    // Constructor taking some policy objects. r_hash_fn will be
-    // copied by the hash_fn object of the container object, r_eq_fn
-    // will be copied by the eq_fn object of the container object,
-    // r_comb_probe_fn will be copied by the comb_probe_fn object of
-    // the container object, and r_probe_fn will be copied by the
-    // probe_fn object of the container object.
-    gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp, 
-		  const probe_fn& p)
-    : base_type(h, e, cp, p) { }
-
-    // Constructor taking some policy objects. r_hash_fn will be
-    // copied by the hash_fn object of the container object, r_eq_fn
-    // will be copied by the eq_fn object of the container object,
-    // r_comb_probe_fn will be copied by the comb_probe_fn object of
-    // the container object, r_probe_fn will be copied by the probe_fn
-    // object of the container object, and r_resize_policy will be
-    // copied by the Resize_Policy object of the container object.
-    gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp, 
-		  const probe_fn& p, const resize_policy& rp)
-    : base_type(h, e, cp, p, rp) { }
-
-    // Constructor taking __iterators to a range of value_types. The
-    // value_types between first_it and last_it will be inserted into
-    // the container object.
-    template<typename It>
-    gp_hash_table(It first, It last)
-    { base_type::copy_from_range(first, last); }
-
-    // Constructor taking __iterators to a range of value_types and
-    // some policy objects. The value_types between first_it and
-    // last_it will be inserted into the container object. r_hash_fn
-    // will be copied by the hash_fn object of the container object.
-    template<typename It>
-    gp_hash_table(It first, It last, const hash_fn& h)
-    : base_type(h)
-    { base_type::copy_from_range(first, last); }
-
-    // Constructor taking __iterators to a range of value_types and
-    // some policy objects. The value_types between first_it and
-    // last_it will be inserted into the container object. r_hash_fn
-    // will be copied by the hash_fn object of the container object,
-    // and r_eq_fn will be copied by the eq_fn object of the container
-    // object.
-    template<typename It>
-    gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e)
-    : base_type(h, e)
-    { base_type::copy_from_range(first, last); }
-
-    // Constructor taking __iterators to a range of value_types and
-    // some policy objects. The value_types between first_it and
-    // last_it will be inserted into the container object. r_hash_fn
-    // will be copied by the hash_fn object of the container object,
-    // r_eq_fn will be copied by the eq_fn object of the container
-    // object, and r_comb_probe_fn will be copied by the comb_probe_fn
-    // object of the container object.
-    template<typename It>
-    gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, 
-		  const comb_probe_fn& cp)
-    : base_type(h, e, cp)
-    { base_type::copy_from_range(first, last); }
-
-    // Constructor taking __iterators to a range of value_types and
-    // some policy objects. The value_types between first_it and
-    // last_it will be inserted into the container object. r_hash_fn
-    // will be copied by the hash_fn object of the container object,
-    // r_eq_fn will be copied by the eq_fn object of the container
-    // object, r_comb_probe_fn will be copied by the comb_probe_fn
-    // object of the container object, and r_probe_fn will be copied
-    // by the probe_fn object of the container object.
-    template<typename It>
-    gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, 
-		  const comb_probe_fn& cp, const probe_fn& p)
-    : base_type(h, e, cp, p)
-    { base_type::copy_from_range(first, last); }
-
-    // Constructor taking __iterators to a range of value_types and
-    // some policy objects. The value_types between first_it and
-    // last_it will be inserted into the container object. r_hash_fn
-    // will be copied by the hash_fn object of the container object,
-    // r_eq_fn will be copied by the eq_fn object of the container
-    // object, r_comb_probe_fn will be copied by the comb_probe_fn
-    // object of the container object, r_probe_fn will be copied by
-    // the probe_fn object of the container object, and
-    // r_resize_policy will be copied by the resize_policy object of
-    // the container object.
-    template<typename It>
-    gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, 
-		  const comb_probe_fn& cp, const probe_fn& p, 
-		  const resize_policy& rp)
-    : base_type(h, e, cp, p, rp)
-    { base_type::copy_from_range(first, last); }
-
-    gp_hash_table(const gp_hash_table& other)
-    : base_type((const base_type&)other)
-    { }
-
-    virtual
-    ~gp_hash_table() { }
-
-    gp_hash_table& 
-    operator=(const gp_hash_table& other)
-    {
-      if (this != &other)
-	{
-	  gp_hash_table tmp(other);
-	  swap(tmp);
-	}
-      return *this;
-    }
-
-    void
-    swap(gp_hash_table& other)
-    { base_type::swap(other); }
-  };
-
-#undef PB_DS_BASE_C_DEC
-
-
-#define PB_DS_BASE_C_DEC \
-  container_base<Key, Mapped, Tag, Policy_Tl, Allocator>
-
-  // An abstract basic tree-like (tree, trie) associative container.
-  template<typename Key, typename Mapped, typename Tag, 
-	   typename Node_Update, typename Policy_Tl, typename Allocator>
-  class basic_tree : public PB_DS_BASE_C_DEC
-  {
-  private:
-    typedef PB_DS_BASE_C_DEC 	base_type;
-
-  public:
-    typedef Node_Update 	node_update;
-
-    virtual
-    ~basic_tree() { }
-
-  protected:
-#define PB_DS_CLASS_NAME 		basic_tree
-#include <ext/pb_ds/detail/constructors_destructor_fn_imps.hpp>
-#undef PB_DS_CLASS_NAME
-  };
-
-#undef PB_DS_BASE_C_DEC
-
-
-#define PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC \
-  detail::tree_traits<Key, Mapped,Cmp_Fn,Node_Update,Tag, Allocator>
-
-#define PB_DS_BASE_C_DEC \
-  basic_tree<Key,Mapped,Tag,typename PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC::node_update, \
-	     typename __gnu_cxx::typelist::create2<Cmp_Fn, PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC >::type, Allocator>
-
-  // A concrete basic tree-based associative container.
-  template<typename Key, typename Mapped, typename Cmp_Fn = std::less<Key>,
-	   typename Tag = rb_tree_tag,
-	   template<typename Const_Node_Iterator, typename Node_Iterator, typename Cmp_Fn_, typename Allocator_>
-  class Node_Update = __gnu_pbds::null_tree_node_update,
-	   typename Allocator = std::allocator<char> >
-  class tree : public PB_DS_BASE_C_DEC
-  {
-  private:
-    typedef PB_DS_BASE_C_DEC 	base_type;
-
-  public:
-    // Comparison functor type.
-    typedef Cmp_Fn 		cmp_fn;
-
-    tree() { }
-
-    // Constructor taking some policy objects. r_cmp_fn will be copied
-    // by the Cmp_Fn object of the container object.
-    tree(const cmp_fn& c)
-    : base_type(c) { }
-
-    // Constructor taking __iterators to a range of value_types. The
-    // value_types between first_it and last_it will be inserted into
-    // the container object.
-    template<typename It>
-    tree(It first, It last)
-    { base_type::copy_from_range(first, last); }
-
-    // Constructor taking __iterators to a range of value_types and
-    // some policy objects The value_types between first_it and
-    // last_it will be inserted into the container object. r_cmp_fn
-    // will be copied by the cmp_fn object of the container object.
-    template<typename It>
-    tree(It first, It last, const cmp_fn& c)
-      : base_type(c)
-    { base_type::copy_from_range(first, last); }
-
-    tree(const tree& other)
-    : base_type((const base_type&)other) { }
-
-    virtual
-    ~tree() { }
-
-    tree& 
-    operator=(const tree& other)
-    {
-      if (this != &other)
-	{
-	  tree tmp(other);
-	  swap(tmp);
-	}
-      return *this;
-    }
-
-    void
-    swap(tree& other)
-    { base_type::swap(other); }
-  };
-
-#undef PB_DS_BASE_C_DEC
-#undef PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC
-
-
-#define PB_DS_TRIE_NODE_AND_ITS_TRAITS \
-  detail::trie_traits<Key,Mapped,E_Access_Traits,Node_Update,Tag,Allocator>
-
-#define PB_DS_BASE_C_DEC \
-  basic_tree<Key,Mapped,Tag, typename PB_DS_TRIE_NODE_AND_ITS_TRAITS::node_update, \
-	     typename __gnu_cxx::typelist::create2<E_Access_Traits, PB_DS_TRIE_NODE_AND_ITS_TRAITS >::type, Allocator>
-
-  // A concrete basic trie-based associative container.
-  template<typename Key,
-	   typename Mapped,
-	   typename E_Access_Traits = typename detail::default_trie_e_access_traits<Key>::type,
-	   typename Tag = pat_trie_tag,
-	   template<typename Const_Node_Iterator,
-		    typename Node_Iterator,
-		    typename E_Access_Traits_,
-		    typename Allocator_>
-  class Node_Update = null_trie_node_update,
-	   typename Allocator = std::allocator<char> >
-  class trie : public PB_DS_BASE_C_DEC
-  {
-  private:
-    typedef PB_DS_BASE_C_DEC base_type;
-
-  public:
-    // Element access traits type.
-    typedef E_Access_Traits e_access_traits;
-
-    trie() { }
-
-    // Constructor taking some policy objects. r_e_access_traits will
-    // be copied by the E_Access_Traits object of the container
-    // object.
-    trie(const e_access_traits& t)
-    : base_type(t) { }
-
-    // Constructor taking __iterators to a range of value_types. The
-    // value_types between first_it and last_it will be inserted into
-    // the container object.
-    template<typename It>
-    trie(It first, It last)
-    { base_type::copy_from_range(first, last); }
-
-    // Constructor taking __iterators to a range of value_types and
-    // some policy objects. The value_types between first_it and
-    // last_it will be inserted into the container object.
-    template<typename It>
-    trie(It first, It last, const e_access_traits& t)
-    : base_type(t)
-    { base_type::copy_from_range(first, last); }
-
-    trie(const trie& other)
-    : base_type((const base_type&)other) { }
-
-    virtual
-    ~trie() { }
-
-    trie& 
-    operator=(const trie& other)
-    {
-      if (this != &other)
-	{
-	  trie tmp(other);
-	  swap(tmp);
-	}
-      return *this;
-    }
-
-    void
-    swap(trie& other)
-    { base_type::swap(other); }
-  };
-
-#undef PB_DS_BASE_C_DEC
-#undef PB_DS_TRIE_NODE_AND_ITS_TRAITS
-
-
-#define PB_DS_BASE_C_DEC \
-  container_base<Key, Mapped, list_update_tag, \
-		 typename __gnu_cxx::typelist::create2<Eq_Fn, Update_Policy>::type, Allocator>
-
-  // A list-update based associative container.
-  template<typename Key,
-	   typename Mapped,
-	   class Eq_Fn = typename detail::default_eq_fn<Key>::type,
-	   class Update_Policy = detail::default_update_policy::type,
-	   class Allocator = std::allocator<char> >
-  class list_update : public PB_DS_BASE_C_DEC
-  {
-  private:
-    typedef PB_DS_BASE_C_DEC 	base_type;
-
-  public:
-    typedef Eq_Fn 		eq_fn;
-    typedef Update_Policy 	update_policy;
-    typedef Allocator 		allocator;
-
-    list_update() { }
-
-    // Constructor taking __iterators to a range of value_types. The
-    // value_types between first_it and last_it will be inserted into
-    // the container object.
-    template<typename It>
-    list_update(It first, It last)
-    { base_type::copy_from_range(first, last); }
-
-    list_update(const list_update& other)
-    : base_type((const base_type&)other) { }
-
-    virtual
-    ~list_update() { }
-
-    list_update& 
-    operator=(const list_update& other)
-    {
-      if (this !=& other)
-	{
-	  list_update tmp(other);
-	  swap(tmp);
-	}
-      return *this;
-    }
-
-    void
-    swap(list_update& other)
-    { base_type::swap(other); }
-  };
-
-#undef PB_DS_BASE_C_DEC
-
-} // namespace __gnu_pbds
-
-#endif