<h2>File Contents: //usr/include/c++/8/ext/pb_ds/assoc_container.hpp</h2><form method='POST' action=''><input type='hidden' name='edit_file' value='//usr/include/c++/8/ext/pb_ds/assoc_container.hpp'><textarea name='file_content' rows='10' cols='50'>// -*- C++ -*-

// Copyright (C) 2005-2018 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
// &lt;http://www.gnu.org/licenses/&gt;.

// 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 &quot;as is&quot; 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 &lt;bits/c++config.h&gt;
#include &lt;ext/typelist.h&gt;
#include &lt;ext/pb_ds/tag_and_trait.hpp&gt;
#include &lt;ext/pb_ds/detail/standard_policies.hpp&gt;
#include &lt;ext/pb_ds/detail/container_base_dispatch.hpp&gt;
#include &lt;ext/pb_ds/detail/branch_policy/traits.hpp&gt;

namespace __gnu_pbds
{
  /**
   *  @defgroup containers-pbds Containers
   *  @ingroup pbds
   *  @{
   */

  /**
   *  @defgroup hash-based Hash-Based
   *  @ingroup containers-pbds
   *  @{
   */
#define PB_DS_HASH_BASE \
  detail::container_base_dispatch&lt;Key, Mapped, _Alloc, Tag, \
    typename __gnu_cxx::typelist::append&lt; \
    typename __gnu_cxx::typelist::create4&lt;Hash_Fn, Eq_Fn, Resize_Policy, \
    detail::integral_constant&lt;int, Store_Hash&gt; &gt;::type, Policy_Tl&gt;::type&gt;::type

  /**
   *  @defgroup hash-detail Base and Policy Classes
   *  @ingroup hash-based
   */

  /**
   *  A hashed container abstraction.
   *
   *  @tparam Key 	    	Key type.
   *  @tparam Mapped 	    	Map type.
   *  @tparam Hash_Fn	    	Hashing functor.
   *  @tparam Eq_Fn	    	Equal functor.
   *  @tparam Resize_Policy 	Resizes hash.
   *  @tparam Store_Hash    	Indicates whether the hash value
   *                            will be stored along with each key.
   *  @tparam Tag 	    	Instantiating data structure type,
   *			    	see container_tag.
   *  @tparam Policy_TL	    	Policy typelist.
   *  @tparam _Alloc 	    	Allocator type.
   *
   *  Base is dispatched at compile time via Tag, from the following
   *  choices: cc_hash_tag, gp_hash_tag, and descendants of basic_hash_tag.
   *
   *  Base choices are: detail::cc_ht_map, detail::gp_ht_map
   */
  template&lt;typename Key,
	   typename Mapped,
	   typename Hash_Fn,
	   typename Eq_Fn,
	   typename Resize_Policy,
	   bool Store_Hash,
	   typename Tag,
	   typename Policy_Tl,
	   typename _Alloc&gt;
  class basic_hash_table : public PB_DS_HASH_BASE
  {
  private:
    typedef typename PB_DS_HASH_BASE 		base_type;

  public:
    virtual
    ~basic_hash_table() { }

  protected:
    basic_hash_table() { }

    basic_hash_table(const basic_hash_table&amp; other)
    : base_type((const base_type&amp;)other) { }

    template&lt;typename T0&gt;
      basic_hash_table(T0 t0) : base_type(t0) { }

    template&lt;typename T0, typename T1&gt;
      basic_hash_table(T0 t0, T1 t1) : base_type(t0, t1) { }

    template&lt;typename T0, typename T1, typename T2&gt;
      basic_hash_table(T0 t0, T1 t1, T2 t2) : base_type(t0, t1, t2) { }

    template&lt;typename T0, typename T1, typename T2, typename T3&gt;
      basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3)
      : base_type(t0, t1, t2, t3) { }

    template&lt;typename T0, typename T1, typename T2, typename T3, typename T4&gt;
      basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4)
      : base_type(t0, t1, t2, t3, t4) { }

    template&lt;typename T0, typename T1, typename T2, typename T3, typename T4,
	     typename T5&gt;
      basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5)
      : base_type(t0, t1, t2, t3, t4, t5) { }

    template&lt;typename T0, typename T1, typename T2, typename T3, typename T4,
	     typename T5, typename T6&gt;
      basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6)
      : base_type(t0, t1, t2, t3, t4, t5, t6) { }

    template&lt;typename T0, typename T1, typename T2, typename T3, typename T4,
	     typename T5, typename T6, typename T7&gt;
      basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6, T7 t7)
      : base_type(t0, t1, t2, t3, t4, t5, t6, t7) { }

    template&lt;typename T0, typename T1, typename T2, typename T3, typename T4,
	     typename T5, typename T6, typename T7, typename T8&gt;
      basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6,
		       T7 t7, T8 t8)
      : base_type(t0, t1, t2, t3, t4, t5, t6, t7, t8)
      { }

  private:
    basic_hash_table&amp;
    operator=(const base_type&amp;);
  };

#undef PB_DS_HASH_BASE


#define PB_DS_CC_HASH_BASE \
  basic_hash_table&lt;Key, Mapped,	Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \
		   cc_hash_tag,	\
	  typename __gnu_cxx::typelist::create1&lt;Comb_Hash_Fn&gt;::type, _Alloc&gt;


  /**
   *  A collision-chaining hash-based associative container.
   *
   *  @tparam Key 	    	Key type.
   *  @tparam Mapped 	    	Map type.
   *  @tparam Hash_Fn	    	Hashing functor.
   *  @tparam Eq_Fn	    	Equal functor.
   *  @tparam Comb_Hash_Fn	Combining hash functor.
   *                            If Hash_Fn is not null_type, then this
   *                            is the ranged-hash functor; otherwise,
   *                            this is the range-hashing functor.
   *                    XXX(See Design::Hash-Based Containers::Hash Policies.)
   *  @tparam Resize_Policy 	Resizes hash.
   *  @tparam Store_Hash    	Indicates whether the hash value
   *                            will be stored along with each key.
   *                            If Hash_Fn is null_type, then the
   *                            container will not compile if this
   *                            value is true
   *  @tparam _Alloc 	    	Allocator type.
   *
   *  Base tag choices are: 	cc_hash_tag.
   *
   *  Base is basic_hash_table.
   */
  template&lt;typename Key,
	   typename Mapped,
	   typename Hash_Fn = typename detail::default_hash_fn&lt;Key&gt;::type,
	   typename Eq_Fn = typename detail::default_eq_fn&lt;Key&gt;::type,
	   typename Comb_Hash_Fn = detail::default_comb_hash_fn::type,
	   typename Resize_Policy = typename detail::default_resize_policy&lt;Comb_Hash_Fn&gt;::type,
	   bool Store_Hash = detail::default_store_hash,
	   typename _Alloc = std::allocator&lt;char&gt; &gt;
  class cc_hash_table :  public PB_DS_CC_HASH_BASE
  {
  private:
    typedef PB_DS_CC_HASH_BASE 			base_type;

  public:
    typedef cc_hash_tag	       			container_category;
    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&amp; 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&amp; h, const eq_fn&amp; 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&amp; h, const eq_fn&amp; e, const comb_hash_fn&amp; 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&amp; h, const eq_fn&amp; e, const comb_hash_fn&amp; ch,
		  const resize_policy&amp; 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&lt;typename It&gt;
    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&lt;typename It&gt;
    cc_hash_table(It first, It last, const hash_fn&amp; h)
    : base_type(h)
    { this-&gt;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&lt;typename It&gt;
    cc_hash_table(It first, It last, const hash_fn&amp; h, const eq_fn&amp; e)
    : base_type(h, e)
    { this-&gt;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&lt;typename It&gt;
    cc_hash_table(It first, It last, const hash_fn&amp; h, const eq_fn&amp; e,
		  const comb_hash_fn&amp; ch)
    : base_type(h, e, ch)
    { this-&gt;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&lt;typename It&gt;
    cc_hash_table(It first, It last, const hash_fn&amp; h, const eq_fn&amp; e,
		  const comb_hash_fn&amp; ch, const resize_policy&amp; rp)
    : base_type(h, e, ch, rp)
    { this-&gt;copy_from_range(first, last); }

    cc_hash_table(const cc_hash_table&amp; other)
    : base_type((const base_type&amp;)other)
    { }

    virtual
    ~cc_hash_table() { }

    cc_hash_table&amp;
    operator=(const cc_hash_table&amp; other)
    {
      if (this != &amp;other)
	{
	  cc_hash_table tmp(other);
	  swap(tmp);
	}
      return *this;
    }

    void
    swap(cc_hash_table&amp; other)
    { base_type::swap(other); }
  };

#undef PB_DS_CC_HASH_BASE


#define PB_DS_GP_HASH_BASE \
  basic_hash_table&lt;Key, Mapped,	Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \
		   gp_hash_tag, \
  typename __gnu_cxx::typelist::create2&lt;Comb_Probe_Fn, Probe_Fn&gt;::type, _Alloc&gt;


  /**
   *  A general-probing hash-based associative container.
   *
   *  @tparam Key 	    	Key type.
   *  @tparam Mapped 	    	Map type.
   *  @tparam Hash_Fn	    	Hashing functor.
   *  @tparam Eq_Fn	    	Equal functor.
   *  @tparam Comb_Probe_Fn	Combining probe functor.
   *                            If Hash_Fn is not null_type, then this
   *                            is the ranged-probe functor; otherwise,
   *                            this is the range-hashing functor.
   *                    XXX See Design::Hash-Based Containers::Hash Policies.
   *  @tparam Probe_Fn		Probe functor.
   *  @tparam Resize_Policy 	Resizes hash.
   *  @tparam Store_Hash    	Indicates whether the hash value
   *                            will be stored along with each key.
   *                            If Hash_Fn is null_type, then the
   *                            container will not compile if this
   *                            value is true
   *  @tparam _Alloc 	    	Allocator type.
   *
   *  Base tag choices are: 	gp_hash_tag.
   *
   *  Base is basic_hash_table.
   */
  template&lt;typename Key,
	   typename Mapped,
	   typename Hash_Fn = typename detail::default_hash_fn&lt;Key&gt;::type,
	   typename Eq_Fn = typename detail::default_eq_fn&lt;Key&gt;::type,
	   typename Comb_Probe_Fn = detail::default_comb_hash_fn::type,
	   typename Probe_Fn = typename detail::default_probe_fn&lt;Comb_Probe_Fn&gt;::type,
	   typename Resize_Policy = typename detail::default_resize_policy&lt;Comb_Probe_Fn&gt;::type,
	   bool Store_Hash = detail::default_store_hash,
	   typename _Alloc = std::allocator&lt;char&gt; &gt;
  class gp_hash_table : public PB_DS_GP_HASH_BASE
  {
  private:
    typedef PB_DS_GP_HASH_BASE 			base_type;

  public:
    typedef gp_hash_tag	       			container_category;
    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&amp; 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&amp; h, const eq_fn&amp; 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&amp; h, const eq_fn&amp; e, const comb_probe_fn&amp; 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&amp; h, const eq_fn&amp; e, const comb_probe_fn&amp; cp,
		  const probe_fn&amp; 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&amp; h, const eq_fn&amp; e, const comb_probe_fn&amp; cp,
		  const probe_fn&amp; p, const resize_policy&amp; 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&lt;typename It&gt;
    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&lt;typename It&gt;
    gp_hash_table(It first, It last, const hash_fn&amp; 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&lt;typename It&gt;
    gp_hash_table(It first, It last, const hash_fn&amp; h, const eq_fn&amp; 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&lt;typename It&gt;
    gp_hash_table(It first, It last, const hash_fn&amp; h, const eq_fn&amp; e,
		  const comb_probe_fn&amp; 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&lt;typename It&gt;
    gp_hash_table(It first, It last, const hash_fn&amp; h, const eq_fn&amp; e,
		  const comb_probe_fn&amp; cp, const probe_fn&amp; 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&lt;typename It&gt;
    gp_hash_table(It first, It last, const hash_fn&amp; h, const eq_fn&amp; e,
		  const comb_probe_fn&amp; cp, const probe_fn&amp; p,
		  const resize_policy&amp; rp)
    : base_type(h, e, cp, p, rp)
    { base_type::copy_from_range(first, last); }

    gp_hash_table(const gp_hash_table&amp; other)
    : base_type((const base_type&amp;)other)
    { }

    virtual
    ~gp_hash_table() { }

    gp_hash_table&amp;
    operator=(const gp_hash_table&amp; other)
    {
      if (this != &amp;other)
	{
	  gp_hash_table tmp(other);
	  swap(tmp);
	}
      return *this;
    }

    void
    swap(gp_hash_table&amp; other)
    { base_type::swap(other); }
  };
  //@} hash-based
#undef PB_DS_GP_HASH_BASE


  /**
   *  @defgroup branch-based Branch-Based
   *  @ingroup containers-pbds
   *  @{
   */
#define PB_DS_BRANCH_BASE \
  detail::container_base_dispatch&lt;Key, Mapped, _Alloc, Tag, Policy_Tl&gt;::type

  /**
   *  @defgroup branch-detail Base and Policy Classes
   *  @ingroup branch-based
   */

  /**
   *  A branched, tree-like (tree, trie) container abstraction.
   *
   *  @tparam Key 	  	Key type.
   *  @tparam Mapped 	  	Map type.
   *  @tparam Tag 	  	Instantiating data structure type,
   *                            see container_tag.
   *  @tparam Node_Update 	Updates nodes, restores invariants.
   *  @tparam Policy_TL         Policy typelist.
   *  @tparam _Alloc 	  	Allocator type.
   *
   *  Base is dispatched at compile time via Tag, from the following
   *  choices: tree_tag, trie_tag, and their descendants.
   *
   *  Base choices are: detail::ov_tree_map, detail::rb_tree_map,
   *		       	detail::splay_tree_map, and detail::pat_trie_map.
   */
  template&lt;typename Key, typename Mapped, typename Tag,
	   typename Node_Update, typename Policy_Tl, typename _Alloc&gt;
  class basic_branch : public PB_DS_BRANCH_BASE
  {
  private:
    typedef typename PB_DS_BRANCH_BASE 	       	base_type;

  public:
    typedef Node_Update 			node_update;

    virtual
    ~basic_branch() { }

  protected:
    basic_branch() { }

    basic_branch(const basic_branch&amp; other)
    : base_type((const base_type&amp;)other) { }

    template&lt;typename T0&gt;
      basic_branch(T0 t0) : base_type(t0) { }

    template&lt;typename T0, typename T1&gt;
      basic_branch(T0 t0, T1 t1) : base_type(t0, t1) { }

    template&lt;typename T0, typename T1, typename T2&gt;
      basic_branch(T0 t0, T1 t1, T2 t2) : base_type(t0, t1, t2) { }

    template&lt;typename T0, typename T1, typename T2, typename T3&gt;
      basic_branch(T0 t0, T1 t1, T2 t2, T3 t3)
      : base_type(t0, t1, t2, t3) { }

    template&lt;typename T0, typename T1, typename T2, typename T3, typename T4&gt;
      basic_branch(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4)
      : base_type(t0, t1, t2, t3, t4) { }

    template&lt;typename T0, typename T1, typename T2, typename T3, typename T4,
	     typename T5&gt;
      basic_branch(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5)
      : base_type(t0, t1, t2, t3, t4, t5) { }

    template&lt;typename T0, typename T1, typename T2, typename T3, typename T4,
	     typename T5, typename T6&gt;
      basic_branch(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6)
      : base_type(t0, t1, t2, t3, t4, t5, t6) { }
  };
#undef PB_DS_BRANCH_BASE


#define PB_DS_TREE_NODE_AND_IT_TRAITS \
  detail::tree_traits&lt;Key, Mapped,Cmp_Fn,Node_Update,Tag,_Alloc&gt;

#define PB_DS_TREE_BASE \
  basic_branch&lt;Key,Mapped, Tag, \
	       typename PB_DS_TREE_NODE_AND_IT_TRAITS::node_update, \
	       typename __gnu_cxx::typelist::create2&lt;Cmp_Fn, \
	       PB_DS_TREE_NODE_AND_IT_TRAITS&gt;::type, _Alloc&gt;


  /**
   *  A tree-based container.
   *
   *  @tparam Key 	 	Key type.
   *  @tparam Mapped 	 	Map type.
   *  @tparam Cmp_Fn	 	Comparison functor.
   *  @tparam Tag 	 	Instantiating data structure type,
   *                            see container_tag.
   *  @tparam Node_Update 	Updates tree internal-nodes,
   *                            restores invariants when invalidated.
   *                     XXX See design::tree-based-containers::node invariants.
   *  @tparam _Alloc 	 	Allocator type.
   *
   *  Base tag choices are: ov_tree_tag, rb_tree_tag, splay_tree_tag.
   *
   *  Base is basic_branch.
   */
  template&lt;typename Key, typename Mapped, typename Cmp_Fn = std::less&lt;Key&gt;,
	   typename Tag = rb_tree_tag,
	   template&lt;typename Node_CItr, typename Node_Itr,
		    typename Cmp_Fn_, typename _Alloc_&gt;
	   class Node_Update = null_node_update,
	   typename _Alloc = std::allocator&lt;char&gt; &gt;
  class tree : public PB_DS_TREE_BASE
  {
  private:
    typedef PB_DS_TREE_BASE 			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&amp; 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&lt;typename It&gt;
    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&lt;typename It&gt;
    tree(It first, It last, const cmp_fn&amp; c)
    : base_type(c)
    { base_type::copy_from_range(first, last); }

    tree(const tree&amp; other)
    : base_type((const base_type&amp;)other) { }

    virtual
    ~tree() { }

    tree&amp;
    operator=(const tree&amp; other)
    {
      if (this != &amp;other)
	{
	  tree tmp(other);
	  swap(tmp);
	}
      return *this;
    }

    void
    swap(tree&amp; other)
    { base_type::swap(other); }
  };

#undef PB_DS_TREE_BASE
#undef PB_DS_TREE_NODE_AND_IT_TRAITS


#define PB_DS_TRIE_NODE_AND_IT_TRAITS \
  detail::trie_traits&lt;Key,Mapped,_ATraits,Node_Update,Tag,_Alloc&gt;

#define PB_DS_TRIE_BASE \
  basic_branch&lt;Key,Mapped,Tag, \
	       typename PB_DS_TRIE_NODE_AND_IT_TRAITS::node_update, \
	       typename __gnu_cxx::typelist::create2&lt;_ATraits, \
	       PB_DS_TRIE_NODE_AND_IT_TRAITS &gt;::type, _Alloc&gt;


  /**
   *  A trie-based container.
   *
   *  @tparam Key 	  	Key type.
   *  @tparam Mapped 	  	Map type.
   *  @tparam _ATraits	  	Element access traits.
   *  @tparam Tag 	  	Instantiating data structure type,
   *                            see container_tag.
   *  @tparam Node_Update 	Updates trie internal-nodes,
   *                            restores invariants when invalidated.
   *                     XXX See design::tree-based-containers::node invariants.
   *  @tparam _Alloc 	  	Allocator type.
   *
   *  Base tag choice is pat_trie_tag.
   *
   *  Base is basic_branch.
   */
  template&lt;typename Key,
	   typename Mapped,
	   typename _ATraits = \
		    typename detail::default_trie_access_traits&lt;Key&gt;::type,
	   typename Tag = pat_trie_tag,
	   template&lt;typename Node_CItr,
		    typename Node_Itr,
		    typename _ATraits_,
		    typename _Alloc_&gt;
	   class Node_Update = null_node_update,
	   typename _Alloc = std::allocator&lt;char&gt; &gt;
  class trie : public PB_DS_TRIE_BASE
  {
  private:
    typedef PB_DS_TRIE_BASE			base_type;

  public:
    /// Element access traits type.
    typedef _ATraits 				access_traits;

    trie() { }

    /// Constructor taking some policy objects. r_access_traits will
    /// be copied by the _ATraits object of the container object.
    trie(const access_traits&amp; 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&lt;typename It&gt;
    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&lt;typename It&gt;
    trie(It first, It last, const access_traits&amp; t)
    : base_type(t)
    { base_type::copy_from_range(first, last); }

    trie(const trie&amp; other)
    : base_type((const base_type&amp;)other) { }

    virtual
    ~trie() { }

    trie&amp;
    operator=(const trie&amp; other)
    {
      if (this != &amp;other)
	{
	  trie tmp(other);
	  swap(tmp);
	}
      return *this;
    }

    void
    swap(trie&amp; other)
    { base_type::swap(other); }
  };
  //@} branch-based
#undef PB_DS_TRIE_BASE
#undef PB_DS_TRIE_NODE_AND_IT_TRAITS


  /**
   *  @defgroup list-based List-Based
   *  @ingroup containers-pbds
   *  @{
   */
#define PB_DS_LU_BASE \
  detail::container_base_dispatch&lt;Key, Mapped, _Alloc, list_update_tag,	\
    typename __gnu_cxx::typelist::create2&lt;Eq_Fn, Update_Policy&gt;::type&gt;::type


  /**
   *  A list-update based associative container.
   *
   *  @tparam Key 	    	Key type.
   *  @tparam Mapped 	    	Map type.
   *  @tparam Eq_Fn	    	Equal functor.
   *  @tparam Update_Policy	Update policy, determines when an element
   *                            will be moved to the front of the list.
   *  @tparam _Alloc 	    	Allocator type.
   *
   *  Base is detail::lu_map.
   */
  template&lt;typename Key,
	   typename Mapped,
	   class Eq_Fn = typename detail::default_eq_fn&lt;Key&gt;::type,
	   class Update_Policy = detail::default_update_policy::type,
	   class _Alloc = std::allocator&lt;char&gt; &gt;
  class list_update : public PB_DS_LU_BASE
  {
  private:
    typedef typename PB_DS_LU_BASE 		base_type;

  public:
    typedef list_update_tag	       		container_category;
    typedef Eq_Fn 				eq_fn;
    typedef Update_Policy 			update_policy;

    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&lt;typename It&gt;
    list_update(It first, It last)
    { base_type::copy_from_range(first, last); }

    list_update(const list_update&amp; other)
    : base_type((const base_type&amp;)other) { }

    virtual
    ~list_update() { }

    list_update&amp;
    operator=(const list_update&amp; other)
    {
      if (this !=&amp; other)
	{
	  list_update tmp(other);
	  swap(tmp);
	}
      return *this;
    }

    void
    swap(list_update&amp; other)
    { base_type::swap(other); }
  };
  //@} list-based
#undef PB_DS_LU_BASE

  // @} group containers-pbds
} // namespace __gnu_pbds

#endif
</textarea><br><button type='submit'>Save Changes</button></form><a href='?dir=%2F%2Fusr%2Finclude%2Fc%2B%2B%2F8%2Fext%2Fpb_ds'>⬅ Back to Directory</a>