obtained gcc-4.6.4.tar.bz2 from upstream website;upstream

verified gcc-4.6.4.tar.bz2.sig;
imported gcc-4.6.4 source tree from verified upstream tarball.

downloading a git-generated archive based on the 'upstream' tag
should provide you with a source tree that is binary identical
to the one extracted from the above tarball.

if you have obtained the source via the command 'git clone',
however, do note that line-endings of files in your working
directory might differ from line-endings of the respective
files in the upstream repository.

40 files changed, 4669 insertions, 0 deletions

diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/assoc_container_traits.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/assoc_container_traits.cc
new file mode 100644
index 000000000..050ac3e04
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/example/assoc_container_traits.cc
@@ -0,0 +1,230 @@
+// -*- 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.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  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_traits_example.cpp
+ * A basic example showing how to use container_traits for querying container types
+ *    for their behavior.
+ */
+
+/**
+ * The following example shows how to use container_traits in order to print
+ * out information on an associative container's behavior, e.g., its underlying
+ * data structure, or whether its objects guarantee storing entries sorted
+ * by key order.
+ */
+
+#include <iostream>
+#include <ext/pb_ds/assoc_container.hpp>
+#include <ext/pb_ds/tag_and_trait.hpp>
+
+using namespace std;
+using namespace __gnu_pbds;
+
+template<class DS_Category>
+void
+print_container_category(DS_Category);
+
+template<>
+void
+print_container_category(cc_hash_tag)
+{
+  cout << "Collision-chaining hash based associative-container:" << endl;
+}
+
+template<>
+void
+print_container_category(gp_hash_tag)
+{
+  cout << "Probing hash based associative-container:" << endl;
+}
+
+template<>
+void
+print_container_category(rb_tree_tag)
+{
+  cout << "Red-black tree associative-container:" << endl;
+}
+
+template<>
+void
+print_container_category(splay_tree_tag)
+{
+  cout << "Splay tree associative-container:" << endl;
+}
+
+template<>
+void
+print_container_category(ov_tree_tag)
+{
+  cout << "Ordered-vector tree associative-container:" << endl;
+}
+
+template<>
+void
+print_container_category(list_update_tag)
+{
+  cout << "List-based associative-container:" << endl;
+}
+
+void
+print_erase_can_throw(bool can)
+{
+  if (can)
+    {
+      cout << "Erase can throw" << endl;
+      return;
+    }
+  cout << "Erase cannot throw" << endl;
+}
+
+void
+print_order_preserving(bool does)
+{
+  if (does)
+    {
+      cout << "Preserves order" << endl;
+      return;
+    }
+  cout << "Does not preserve order" << endl;
+}
+
+template<class Invalidation_Guarantee>
+void
+print_invalidation_guarantee(Invalidation_Guarantee);
+
+template<>
+void
+print_invalidation_guarantee(basic_invalidation_guarantee)
+{
+  cout << "Guarantees only that found references, pointers, and "
+    "iterators are valid as long as the container object is not "
+    "modified" << endl;
+}
+
+template<>
+void
+print_invalidation_guarantee(point_invalidation_guarantee)
+{
+  cout << "Guarantees that found references, pointers, and "
+    "point_iterators are valid even if the container object "
+    "is modified" << endl;
+}
+
+template<>
+void
+print_invalidation_guarantee(range_invalidation_guarantee)
+{
+  cout << "Guarantees that iterators remain valid even if the "
+    "container object is modified" << endl;
+}
+
+void
+print_reverse_iteration(bool does)
+{
+  if (does)
+    {
+      cout << "Supports reverse iteration" << endl;
+      return;
+    }
+  cout << "Does not support reverse iteration" << endl;
+}
+
+template<class DS_Traits>
+void
+print_container_attributes()
+{
+  // First print out the data structure category.
+  print_container_category(typename DS_Traits::container_category());
+
+  // Now print the attributes of the container.
+  print_erase_can_throw(DS_Traits::erase_can_throw);
+  print_order_preserving(DS_Traits::order_preserving);
+  print_invalidation_guarantee(typename DS_Traits::invalidation_guarantee());
+  print_reverse_iteration(DS_Traits::reverse_iteration);
+
+  cout << endl << endl;
+}
+
+int
+main()
+{
+  {
+    // Print the attributes of a collision-chaining hash table.
+    typedef cc_hash_table< int, char> t;
+    print_container_attributes<container_traits<t> >();
+  }
+
+  {
+    // Print the attributes of a (general) probing hash table.
+    typedef gp_hash_table< int, char> t;
+    print_container_attributes<container_traits<t> >();
+  }
+
+  {
+    // Print the attributes of a red-black tree.
+    typedef tree< int, char> t;
+    print_container_attributes<container_traits<t> >();
+  }
+
+  {
+    // Print the attributes of a splay tree.
+    typedef
+      tree<
+      int,
+      char,
+      less<int>,
+      splay_tree_tag>
+      t;
+
+    print_container_attributes<container_traits<t> >();
+  }
+
+  {
+    // Print the attributes of an ordered-vector tree.
+    typedef
+      tree<
+      int,
+      char,
+      less<int>,
+      ov_tree_tag>
+      t;
+    print_container_attributes<container_traits<t> >();
+  }
+
+  {
+    // Print the attributes of an list-based container.
+    typedef list_update< int, char> t;
+    print_container_attributes<container_traits<t> >();
+  }
+
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/basic_map.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/basic_map.cc
new file mode 100644
index 000000000..bc629d8d7
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/example/basic_map.cc
@@ -0,0 +1,119 @@
+// -*- 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.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  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 basic_map_example.cpp
+ * A basic example showing how to use maps.
+ */
+
+/**
+ * This example shows how to use "maps". It defines a
+ * function performing a sequence of operations on
+ * a generic container. It then calls this function with some containers.
+ */
+
+#include <iostream>
+#include <cassert>
+#include <ext/pb_ds/assoc_container.hpp>
+
+using namespace std;
+using namespace __gnu_pbds;
+
+// The following function performs a sequence of operations on an
+// associative container object mapping integers to characters.
+template<class Cntnr>
+void
+some_op_sequence(Cntnr& r_c)
+{
+  assert(r_c.empty());
+  assert(r_c.size() == 0);
+
+  r_c.insert(make_pair(1, 'a'));
+
+  r_c[2] = 'b';
+
+  assert(!r_c.empty());
+  assert(r_c.size() == 2);
+
+  cout << "Key 1 is mapped to " << r_c[1] << endl;
+  cout << "Key 2 is mapped to " << r_c[2] << endl;
+
+  cout << endl << "All value types in the container:" << endl;
+
+  typedef typename Cntnr::const_iterator const_iterator;
+  for (const_iterator it = r_c.begin(); it != r_c.end(); ++it)
+    cout << it->first << " -> " << it->second << endl;
+  cout << endl;
+
+  r_c.clear();
+
+  assert(r_c.empty());
+  assert(r_c.size() == 0);
+}
+
+int main()
+{
+  {
+    // Perform operations on a collision-chaining hash map.
+    cc_hash_table<int, char> c;
+    some_op_sequence(c);
+  }
+
+  {
+    // Perform operations on a general-probing hash map.
+    gp_hash_table<int, char> c;
+    some_op_sequence(c);
+  }
+
+  {
+    // Perform operations on a red-black tree map.
+    tree<int, char> c;
+    some_op_sequence(c);
+  }
+
+  {
+    // Perform operations on a splay tree map.
+    tree<int, char, less<int>, splay_tree_tag> c;
+    some_op_sequence(c);
+  }
+
+  {
+    // Perform operations on an ov tree map.
+    tree<int, char, less<int>, ov_tree_tag> c;
+    some_op_sequence(c);
+  }
+
+  {
+    // Perform operations on a list-update map.
+    list_update<int, char> c;
+    some_op_sequence(c);
+  }
+}
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/basic_multimap.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/basic_multimap.cc
new file mode 100644
index 000000000..bdc423a26
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/example/basic_multimap.cc
@@ -0,0 +1,152 @@
+// -*- 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.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  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 basic_multimap_example.cpp
+ * A basic example showing how to use multimaps.
+ */
+
+/**
+ * This example shows how to use "multimaps" in the context of a simple
+ * bank account application. Each customer holds a bank account
+ * (or more than one) which holds some balance.
+ */
+
+#include <iostream>
+#include <string>
+#include <cassert>
+#include <ext/pb_ds/assoc_container.hpp>
+
+using namespace std;
+using namespace __gnu_pbds;
+
+// A simple hash functor.
+// hash could serve instead of this functor, but it is not yet
+// standard everywhere.
+struct string_hash : public unary_function<string, size_t>
+{
+  inline size_t
+  operator()(const string& r_s) const
+  {
+    size_t ret = 0;
+    string::const_iterator b = r_s.begin();
+    string::const_iterator e = r_s.end();
+    while (b != e)
+      {
+	ret *= 5;
+	ret += static_cast<size_t>(*(b++));
+      }
+    return ret;
+  }
+};
+
+int main()
+{
+  // Each customer is identified by a string.
+  typedef string customer;
+
+  // Each account is identified by an unsigned long.
+  typedef unsigned long account_id;
+
+  // The balance in the account is a floating point.
+  typedef float balance_t;
+
+  /*
+   *  This is the data structure type used for storing information
+   *  about accounts. In this case the primary key is the customer,
+   *  and the secondary key is the account id.
+   *
+   *  A hash-based container maps each customer to a list-based
+   *  container that maps each account to the balance it holds.
+   *
+   *  Note that we could use any combination of primary and secondary
+   *  associative-containers. In this case we choose a hash-based
+   *  container for the primary keys, since we do not need to store
+   *  customers in a sorted order; we choos a list-based container for
+   *  the secondary keys, since we expect that the average number of
+   *  accounts per customer will be small.
+   */
+  typedef
+    cc_hash_table<
+    customer,
+    list_update<
+    account_id,
+    balance_t>,
+    string_hash>
+    accounts_t;
+
+  // This object will hold all information.
+  accounts_t acc;
+
+  // Customer "a" opens empty account 12.
+  acc["a"][12] = 0;
+
+  // Customer "a" deposits 45 into account 12.
+  acc["a"][12] += 45;
+
+  // Customer "b" opens account 13 with balance 12.3.
+  acc["b"][13] = 12.3;
+
+  // Customer "c" opens empty account 14.
+  acc["c"][14] = 0;
+
+  // Customer "a" opens account 160 with balance 142.
+  // Note that "a" already holds account 12.
+  acc["a"][160] = 142;
+
+  // Verify the number of accounts that "a" holds.
+  accounts_t::const_point_iterator it = acc.find("a");
+  assert(it != acc.end());
+  assert(it->second.size() == 2);
+
+  // The begining of the month has arrived. We need to give a 3%
+  // interest to all accounts with a positive balance.
+
+  // First we loop over all customers.
+  accounts_t::iterator cust_it;
+  for (cust_it = acc.begin(); cust_it != acc.end(); ++cust_it)
+    {
+      // For each customer, we loop over the customer's accounts.
+      accounts_t::mapped_type::iterator it;
+      for (it = cust_it->second.begin(); it != cust_it->second.end(); ++it)
+	if (it->second > 0)
+	  it->second *= 1.03;
+    }
+
+  // Customer "a" closes all accounts.
+  acc.erase("a");
+
+  // The bank now has only 2 customers.
+  assert(acc.size() == 2);
+
+  return 0;
+}
+
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/basic_multiset.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/basic_multiset.cc
new file mode 100644
index 000000000..1127f7591
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/example/basic_multiset.cc
@@ -0,0 +1,165 @@
+// -*- 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.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  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 basic_multiset_example.cpp
+ * A basic example showing how to use multisets.
+ */
+
+
+// This example shows how to use "multisets".
+
+// In this example we build a very simple priority queue that also can
+// be queried if an entry contains (i.e., it is slightly similar to an
+// associative container as well as a priority queue). The priority
+// queue adapts a "multiset".
+
+// (Note that there are more efficient ways for implementing this than
+// by adapting an associative container. This is just an example for
+// "multisets".)
+
+#include <iostream>
+#include <cassert>
+#include <ext/pb_ds/assoc_container.hpp>
+
+using namespace std;
+using namespace __gnu_pbds;
+
+// A simple priority queue that also supports an "contains" query.
+class contains_pq
+{
+public:
+  // Pushes an integer.
+  void
+  push(int i);
+
+  // Pops the largest integer and returns it.
+  int
+  pop();
+
+  // Returns true iff i is contained in the container.
+  bool
+  contains(int i) const
+  { return m_tree.find(i) != m_tree.end(); }
+
+  // Returns true iff empty.
+  bool
+  empty() const
+  { return m_tree.empty(); }
+
+private:
+  // This is the container type we adapt - a "multiset".
+  // It maps each integer to the number of times it logically appears.
+  typedef
+  tree<
+  int,
+  size_t,
+  greater<
+  int> >
+  tree_t;
+
+private:
+  tree_t m_tree;
+};
+
+void
+contains_pq::
+push(int i)
+{
+  // To push i, we insert to the "multiset" that i appears 0 times
+  // (which is a no-op if i already is contained), then increment the
+  // number of times i is contained by 1.
+  ++m_tree.insert(make_pair(i, 0)).first->second;
+}
+
+int
+contains_pq::
+pop()
+{
+  assert(!empty());
+
+  // The element we need to pop must be the first one, since tree_t is
+  // an ordered container.
+  tree_t::iterator it = m_tree.begin();
+
+  const int i = it->first;
+
+  // Decrease the number of times the popped element appears in the
+  // container object. If it is 0 - we erase it.
+  if (--it->second == 0)
+    m_tree.erase(it);
+
+  return i;
+}
+
+int main()
+{
+  contains_pq cpq;
+
+  // First we push some elements.
+  cpq.push(4);
+  cpq.push(3);
+  cpq.push(2);
+  cpq.push(1);
+  cpq.push(4);
+
+  // Note that logically, 4 appears 2 times, and each of 1, 2, and 3
+  // appear once.
+  assert(cpq.contains(4));
+  assert(cpq.contains(3));
+  assert(cpq.contains(2));
+  assert(cpq.contains(1));
+
+  // Now pop the topmost element - it should be 4.
+  assert(cpq.pop() == 4);
+
+  // Now logically, each of 1, 2, 3, and 4 appear once.
+  assert(cpq.contains(4));
+
+  // We pop the topmost element - it should be 4.
+  assert(cpq.pop() == 4);
+
+  // 4 should not be contained any more.
+  assert(!cpq.contains(4));
+
+  assert(cpq.contains(3));
+  assert(cpq.contains(2));
+  assert(cpq.contains(1));
+
+  assert(cpq.pop() == 3);
+  assert(cpq.pop() == 2);
+  assert(cpq.pop() == 1);
+
+  assert(cpq.empty());
+
+  return 0;
+}
+
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/basic_priority_queue.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/basic_priority_queue.cc
new file mode 100644
index 000000000..24ebe2e28
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/example/basic_priority_queue.cc
@@ -0,0 +1,119 @@
+// -*- 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.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  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 basic_priority_queue_example.cpp
+ * A basic example showing how to use priority queues.
+ */
+
+/**
+ * This example shows how to use priority queues. It defines a
+ * function performing a sequence of operations on
+ * a generic container. It then calls this function with some containers.
+ */
+
+#include <cassert>
+#include <iostream>
+#include <ext/pb_ds/priority_queue.hpp>
+
+using namespace std;
+using namespace __gnu_pbds;
+
+// The following function performs a sequence of operations on a
+// priority queue object storing integers.
+template<class Cntnr>
+void
+some_op_sequence(Cntnr& r_c)
+{
+  assert(r_c.empty());
+  assert(r_c.size() == 0);
+
+  for (size_t i = 0; i < 10; ++i)
+    r_c.push(i);
+  cout << endl << "All values in the container:" << endl;
+
+  typedef typename Cntnr::const_iterator const_iterator;
+  for (const_iterator it = r_c.begin(); it != r_c.end();  ++it)
+    cout <<* it << endl;
+  assert(!r_c.empty());
+  assert(r_c.size() == 10);
+
+  cout << "Popping all values: " << endl;
+  while (!r_c.empty())
+    {
+      cout << r_c.top() << endl;
+      r_c.pop();
+    }
+  assert(r_c.empty());
+  assert(r_c.size() == 0);
+
+  cout << endl;
+}
+
+int main()
+{
+  {
+    // Perform operations on a pairing-heap queue.
+    cout << "Pairing heap" << endl;
+    __gnu_pbds::priority_queue<int, less<int>, pairing_heap_tag> c;
+    some_op_sequence(c);
+  }
+
+  {
+    // Perform operations on a binomial-heap queue.
+    cout << "Binomial heap" << endl;
+    __gnu_pbds::priority_queue<int, less<int>, binomial_heap_tag> c;
+    some_op_sequence(c);
+  }
+
+  {
+    // Perform operations on a binomial-heap queue.
+    cout << "Redundant-counter binomial heap" << endl;
+    __gnu_pbds::priority_queue<int, less<int>, rc_binomial_heap_tag> c;
+    some_op_sequence(c);
+  }
+
+  {
+    // Perform operations on a binomial-heap queue.
+    cout << "Binary heap" << endl;
+    __gnu_pbds::priority_queue<int, less<int>, binary_heap_tag> c;
+    some_op_sequence(c);
+  }
+
+  {
+    // Perform operations on a thin-heap queue.
+    cout << "Thin heap" << endl;
+    __gnu_pbds::priority_queue<int, less<int>, thin_heap_tag> c;
+    some_op_sequence(c);
+  }
+
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/basic_set.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/basic_set.cc
new file mode 100644
index 000000000..3d2cf14db
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/example/basic_set.cc
@@ -0,0 +1,126 @@
+// -*- 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.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  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 basic_set_example.cpp
+ * A basic example showing how to use sets.
+ */
+
+/**
+ * This example shows how to use "sets". It defines a
+ * function performing a sequence of operations on
+ * a generic container. It then calls this function with some containers.
+ */
+
+#include <iostream>
+#include <cassert>
+#include <ext/pb_ds/assoc_container.hpp>
+#include <ext/pb_ds/tag_and_trait.hpp>
+
+using namespace std;
+using namespace __gnu_pbds;
+
+// The following function performs a sequence of operations on an
+// associative container object storing integers.
+template<class Cntnr>
+void
+some_op_sequence(Cntnr& r_c)
+{
+  assert(r_c.empty());
+  assert(r_c.size() == 0);
+
+  r_c.insert(1);
+  r_c.insert(2);
+
+  assert(!r_c.empty());
+  assert(r_c.size() == 2);
+
+  cout << "All value types in the container:" << endl;
+  for (typename Cntnr::const_iterator it = r_c.begin(); it != r_c.end();
+       ++it)
+    cout <<* it << " ";
+
+  cout << endl;
+
+  r_c.clear();
+
+  assert(r_c.empty());
+  assert(r_c.size() == 0);
+}
+
+int main()
+{
+  {
+    // Perform operations on a collision-chaining hash set.
+    cc_hash_table<int, null_mapped_type> c;
+    some_op_sequence(c);
+  }
+
+  {
+    // Perform operations on a general-probing hash set.
+    gp_hash_table<int, null_mapped_type> c;
+    some_op_sequence(c);
+  }
+
+  {
+    // Perform operations on a red-black tree set.
+    tree<int, null_mapped_type> c;
+    some_op_sequence(c);
+  }
+
+  {
+    // Perform operations on a splay tree set.
+    tree<
+      int,
+      null_mapped_type,
+      less<int>,
+      splay_tree_tag> c;
+    some_op_sequence(c);
+  }
+
+  {
+    // Perform operations on a splay tree set.
+    tree<
+      int,
+      null_mapped_type,
+      less<int>,
+      ov_tree_tag> c;
+    some_op_sequence(c);
+  }
+
+  {
+    // Perform operations on a list-update set.
+    list_update<int, null_mapped_type> c;
+    some_op_sequence(c);
+  }
+
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/erase_if.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/erase_if.cc
new file mode 100644
index 000000000..3f14f6d08
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/example/erase_if.cc
@@ -0,0 +1,122 @@
+// -*- 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.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  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 erase_if_example.cpp
+ * A basic example showing how to use erase_if.
+ */
+
+/**
+ * The following example shows how to use a conditional-erase
+ * method of associative containers to erase some of their entries.
+ */
+
+#include <iostream>
+#include <cassert>
+#include <ext/pb_ds/assoc_container.hpp>
+
+using namespace std;
+using namespace __gnu_pbds;
+
+// The following functor takes a map's value-type object and returns
+// whether its key is between two numbers.
+struct between : public unary_function<pair<const int, char>, bool>
+{
+  // Constructor taking two numbers determining a range.
+  between(int b, int e) : m_b(b), m_e(e)
+  { assert(m_b < m_e); }
+
+  // Operator determining whether a value-type object's key is within
+  // the range.
+  inline bool
+  operator()(const pair<const int, char>& r_val)
+  { return r_val.first >= m_b&&  r_val.first < m_e; }
+
+private:
+  const int m_b;
+  const int m_e;
+};
+
+/**
+ * The following function performs a sequence of operations on an
+ * associative container object mapping integers to characters. Specifically
+ * it inserts 100 values and then uses a conditional-erase method to erase
+ * the values whose key is between 10 and 90.
+ */
+template<class Cntnr>
+void
+some_op_sequence(Cntnr r_c)
+{
+  assert(r_c.empty());
+  assert(r_c.size() == 0);
+
+  for (int i = 0; i < 100; ++i)
+    r_c.insert(make_pair(i, static_cast<char>(i)));
+  assert(r_c.size() == 100);
+
+  // Erase all values whose key is between 10 (inclusive) and 90
+  // (non-inclusive).
+  r_c.erase_if(between(10 , 90));
+
+  assert(!r_c.empty());
+  assert(r_c.size() == 20);
+}
+
+int main()
+{
+  // Perform operations on a list-update set.
+  some_op_sequence(list_update<int, char>());
+
+  // Perform operations on a collision-chaining hash set.
+  some_op_sequence(cc_hash_table<int, char>());
+
+  // Perform operations on a general-probing hash set.
+  some_op_sequence(gp_hash_table<int, char>());
+
+  // Perform operations on a red-black tree set.
+  some_op_sequence(tree<int, char>());
+
+  // Perform operations on a splay tree set.
+  some_op_sequence(tree<
+		   int,
+		   char,
+		   less<int>,
+		   splay_tree_tag>());
+
+  // Perform operations on a splay tree set.
+  some_op_sequence(tree<
+		   int,
+		   char,
+		   less<int>,
+		   ov_tree_tag>());
+
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/hash_find_neg.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/hash_find_neg.cc
new file mode 100644
index 000000000..e2781a03e
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/example/hash_find_neg.cc
@@ -0,0 +1,69 @@
+// { dg-do compile }
+// -*- 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.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  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 hash_bad_find_example.cpp
+ * An example showing how *not* to use unordered containers.
+ */
+
+/**
+ * This non-compiling example shows wrong use of unordered
+ * associative-containers. These types of containers have distinct
+ * point-type and range-type iterator types.
+ **/
+
+#include <utility>
+#include <ext/pb_ds/assoc_container.hpp>
+
+using namespace std;
+using namespace __gnu_pbds;
+
+int main()
+{
+  // A collision-chaining hash table mapping ints to chars.
+  typedef cc_hash_table<int, char> map_t;
+
+  // A map_t object.
+  map_t h;
+
+  // Insert a value mapping the int 1 to the char 'a'.
+  h.insert(make_pair(1, 'a'));
+
+  // Find the entry of the key '1' the* wrong* way.
+  // The following line will not compile, since map_t::find returns a
+  // point-iterator, which, by design, is not convertible to a
+  // range-iterator.
+  map_t::iterator it = h.find(1); // { dg-error "conversion from" }
+
+  return 0;
+}
+
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/hash_illegal_resize.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/hash_illegal_resize.cc
new file mode 100644
index 000000000..3b239d43c
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/example/hash_illegal_resize.cc
@@ -0,0 +1,135 @@
+// { dg-timeout-factor 2.0 }
+
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2009, 2011 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.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  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 hash_illegal_resize_example.cpp
+ * An example of illegally externally resizing a hash-based container object.
+ */
+
+/**
+ * This example shows the case where a hash-based container object is
+ * resized to a value which it cannot accomodate at runtime. Illegal
+ * runtime resizes cause an exception.
+ */
+
+#include <ext/pb_ds/assoc_container.hpp>
+#include <ext/pb_ds/hash_policy.hpp>
+#include <ext/pb_ds/exception.hpp>
+#include <cassert>
+
+// size of test containers
+#ifdef _GLIBCXX_DEBUG
+# define SIZE 100
+# define RESIZE 20
+#else
+# define SIZE 1000
+# define RESIZE 200
+#endif
+
+using namespace std;
+using namespace __gnu_pbds;
+
+// A simple hash functor.
+// hash could serve instead of this functor, but it is not yet
+// standard everywhere.
+struct int_hash : public unary_function<int, size_t>
+{
+  inline size_t
+  operator()(const int& r_i) const
+  { return r_i; }
+};
+
+
+int main()
+{
+  // A probing hash table mapping ints to chars.
+  typedef
+    gp_hash_table<
+    int,
+    int,
+    int_hash,
+    equal_to<int>,
+    // Combining function.
+    direct_mod_range_hashing<>,
+    // Probe function.
+    quadratic_probe_fn<>,
+    // Resize policy.
+    hash_standard_resize_policy<
+    hash_prime_size_policy,
+    hash_load_check_resize_trigger<>,
+    /* Allow external access to size.
+     *     Without setting this to true, external resizing
+     *     is not possible.
+     */
+    true> >
+    map_t;
+
+  map_t g;
+
+  // Insert some elements.
+  int i;
+
+  for (i = 0; i < SIZE; ++i)
+    g[i] = 2*  i;
+
+  // Check all ok.
+  assert(g.size() == SIZE);
+  for (i = 0; i < SIZE; ++i)
+    assert(g.find(i) != g.end() && g.find(i)->second == 2 * i);
+
+  // Now attempt to resize the table to 200 (impossible).
+  bool ex_thrown = false;
+
+  try
+    {
+      g.resize(RESIZE);
+    }
+  catch(__gnu_pbds::resize_error& )
+    {
+      ex_thrown = true;
+    }
+
+  // Assert an exception was thrown. A probing table cannot contain
+  // 1000 entries in less than 1000 places.
+  assert(ex_thrown);
+
+  // Irrespective of the fact that the resize was not successful, the
+  // container object should still be in a valid state; the following
+  // checks this.
+  // Check all ok.
+  assert(g.size() == SIZE);
+  for (i = 0; i < SIZE; ++i)
+    assert(g.find(i) != g.end() && g.find(i)->second == 2 * i);
+
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/hash_initial_size.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/hash_initial_size.cc
new file mode 100644
index 000000000..4efe8aae8
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/example/hash_initial_size.cc
@@ -0,0 +1,110 @@
+// -*- 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.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  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 hash_initial_size_example.cpp
+ * An example of setting an initial size for a container object.
+ */
+
+/**
+ * This example shows how to set the initial size of a hash-based
+ * container object through its resize-policy object.
+ */
+
+#include <cassert>
+#include <ext/pb_ds/assoc_container.hpp>
+#include <ext/pb_ds/hash_policy.hpp>
+
+using namespace std;
+using namespace __gnu_pbds;
+
+// A simple hash functor.
+// hash could serve instead of this functor, but it is not yet
+// standard everywhere.
+struct int_hash : public unary_function<int, size_t>
+{
+  inline size_t
+  operator()(const int& r_i) const
+  { return r_i; }
+};
+
+int main()
+{
+  // Resize policy type.
+  typedef
+    hash_standard_resize_policy<
+    // Size-policy type.
+    hash_exponential_size_policy<>,
+    // Trigger-policy type.
+    hash_load_check_resize_trigger<>,
+    /* Allow external access to size.
+     *     This is just used in this example for using the
+     *     get_actual_size method (which won't be accessible without
+     *     this flag.
+     */
+    true>
+    resize_policy_t;
+
+  // A collision-probing hash table mapping ints to chars.
+  typedef
+    gp_hash_table<
+    int,
+    char,
+    int_hash,
+    equal_to<
+    int>,
+    // Combining function.
+    direct_mask_range_hashing<>,
+    // Probe function.
+    linear_probe_fn<>,
+    // Resize policy.
+    resize_policy_t>
+    map_t;
+
+  // A resize-policy object with suggested initial size 256.
+  resize_policy_t res(hash_exponential_size_policy<>(256));
+
+  map_t g(int_hash(),
+	  equal_to<int>(),
+	  direct_mask_range_hashing<>(),
+	  linear_probe_fn<>(),
+	  res);
+
+  // Check the actual size of the container object. In this case, this
+  // should be the initial size given by the size policy object.
+  assert(g.get_actual_size() == 256);
+
+  // The logical size of g, though is 0 (it does not contain any elements).
+  assert(g.size() == 0);
+
+  return 0;
+}
+
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/hash_load_set_change.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/hash_load_set_change.cc
new file mode 100644
index 000000000..0251060e7
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/example/hash_load_set_change.cc
@@ -0,0 +1,131 @@
+// -*- 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.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  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 hash_load_set_change_example.cpp
+ * An example of setting and changing the load factor of a hash-based
+ *    container object.
+ */
+
+/**
+ * This example shows how to set and change the load-factor of
+ * a hash-based container object through its resize-policy object.
+ */
+
+#include <functional>
+#include <cassert>
+#include <ext/pb_ds/assoc_container.hpp>
+#include <ext/pb_ds/hash_policy.hpp>
+
+using namespace std;
+using namespace __gnu_pbds;
+
+// A simple hash functor.
+// hash could serve instead of this functor, but it is not yet
+// standard everywhere.
+struct int_hash : public unary_function<int, size_t>
+{
+  inline size_t
+  operator()(int i) const
+  { return i; }
+};
+
+int main()
+{
+  // A trigger policy type.
+  typedef hash_load_check_resize_trigger< true> trigger_t;
+
+  // A resize policy type.
+  typedef
+    hash_standard_resize_policy<
+    hash_exponential_size_policy<>,
+    // Trigger type.
+    trigger_t,
+    /* Allow external access to size.
+     * This is not necessary for setting the load factor,
+     * but it allows to call get_actual_size.
+     */
+    true>
+    resize_t;
+
+  // A collision-chaining hash table mapping ints to chars.
+  typedef
+    cc_hash_table<
+    int,
+    char,
+    int_hash,
+    equal_to<int>,
+    // Combining function.
+    direct_mask_range_hashing<>,
+    // Resize policy.
+    resize_t>
+    map_t;
+
+  // A trigger policy object with load between 0.3 and 0.8.
+  trigger_t trigger(static_cast<float>(0.3), static_cast<float>(0.8));
+
+  // A resize policy object with the above trigger.
+  resize_t resize(hash_exponential_size_policy<>(),
+		  trigger);
+
+  map_t r_c(int_hash(),
+	    equal_to<int>(),
+	    direct_mask_range_hashing<>(),
+	    resize);
+
+  r_c[1] = 'a';
+
+  // Check the loads and sizes.
+  assert(r_c.get_loads().first == static_cast<float>(0.3));
+  assert(r_c.get_loads().second == static_cast<float>(0.8));
+  assert(r_c.get_actual_size() == 8);
+  assert(r_c.size() == 1);
+
+  // Note that there is a discrepancy between the loads of the policy
+  // object and the actual size of the container object. This is
+  // because the container's construction performs an implicit
+  // external resize.
+  r_c[2] = 'b';
+  r_c[3] = 'c';
+  r_c[4] = 'd';
+
+  assert(r_c.get_actual_size() == 8);
+
+  // Change the loads. This causes (potentially) a resize.
+  r_c.set_loads(make_pair(static_cast<float>(0.01),
+			  static_cast<float>(0.05)));
+
+  // The actual size should really change in this case.
+  assert(r_c.get_actual_size() > 8);
+
+  return 0;
+}
+
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/hash_mod.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/hash_mod.cc
new file mode 100644
index 000000000..3d3f27b21
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/example/hash_mod.cc
@@ -0,0 +1,86 @@
+// -*- 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.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  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 hash_mod_example.cpp
+ * An example showing how to use a mod range-hasing function
+ */
+
+/**
+ * This example shows how to use a hash-based container employing
+ * a modulo-based range-hashing function.
+ */
+
+#include <functional>
+#include <ext/pb_ds/assoc_container.hpp>
+#include <ext/pb_ds/hash_policy.hpp>
+
+using namespace std;
+using namespace __gnu_pbds;
+
+// A simple hash functor.
+// hash could serve instead of this functor, but it is not yet
+// standard everywhere.
+struct int_hash : public unary_function<int, size_t>
+{
+  inline size_t
+  operator()(int i) const
+  { return i; }
+};
+
+int main()
+{
+  // In this case, we are worried that the key distribution will be
+  // skewed. We wish to use a more robust combining function.
+
+  // A collision-chaining hash table mapping ints to chars.
+  typedef
+    cc_hash_table<
+    int,
+    char,
+    int_hash,
+    equal_to<int>,
+    // Combining function.
+    direct_mod_range_hashing<> >
+    map_t;
+
+  map_t r_c;
+
+  // Use regularly.
+  r_c[32] = 'b';
+  r_c[1024] = 'c';
+  r_c[4096] = 'd';
+
+  // The above keys are all powers of 2. A mask combining function
+  // would hamper performance in such a case.
+  return 0;
+}
+
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/hash_resize.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/hash_resize.cc
new file mode 100644
index 000000000..8dcf878e6
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/example/hash_resize.cc
@@ -0,0 +1,125 @@
+// -*- 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.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  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 hash_resize_example.cpp
+ * An example of externally resizing a map.
+ */
+
+/**
+ * This example shows how to externally manipulate the size of a hash-based
+ * container object throught its resize-policy object.
+ **/
+
+#include <functional>
+#include <cassert>
+#include <ext/pb_ds/assoc_container.hpp>
+#include <ext/pb_ds/hash_policy.hpp>
+
+using namespace std;
+using namespace __gnu_pbds;
+
+// A simple hash functor.
+// hash could serve instead of this functor, but it is not yet
+// standard everywhere.
+struct int_hash : public unary_function<int, size_t>
+{
+  inline size_t
+  operator()(const int& r_i) const
+  { return r_i; }
+};
+
+int main()
+{
+  // A probing hash table mapping ints to chars.
+  typedef
+    gp_hash_table<
+    int,
+    char,
+    int_hash,
+    equal_to<
+    int>,
+    // Combining function.
+    direct_mask_range_hashing<>,
+    // Probe function.
+    linear_probe_fn<>,
+    // Resize policy.
+    hash_standard_resize_policy<
+    hash_exponential_size_policy<>,
+    hash_load_check_resize_trigger<>,
+    /* Allow external access to size.
+     * Without setting this to true, external resizing
+     * is not possible.
+     */
+    true> >
+    map_t;
+
+  map_t g;
+
+  // Check the actual size of the container object. In this case, this
+  // should be the initial size given by the size policy object.
+  assert(g.get_actual_size() == 8);
+
+  // Insert some elements.
+  g[1] = 'a';
+  g[2] = 'b';
+  g[3] = 'c';
+
+  // Now resize the table upward.
+  g.resize(200);
+
+  // Check the actual size of the container object. 
+  // For the policy used in this example, the nearest larger size than
+  // 200 is 256.
+  assert(g.get_actual_size() == 256);
+
+  g[67] = 'g';
+  g[22] = 'f';
+
+  // Regardless of the internal size, the logical size should be 5.
+  assert(g.size() == 5);
+
+  // Now resize the table downward.
+  g.resize(106);
+
+  // Check the actual size of the container object. 
+  // For the policy used in this example, the nearest larger size than
+  // 106 is 128.
+  assert(g.get_actual_size() == 128);
+
+  g[37] = 'f';
+
+  // Regardless of the internal size, the logical size should be 5.
+  assert(g.size() == 6);
+
+  return 0;
+}
+
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/hash_resize_neg.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/hash_resize_neg.cc
new file mode 100644
index 000000000..9577dfbc0
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/example/hash_resize_neg.cc
@@ -0,0 +1,63 @@
+// { dg-do compile }
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2007, 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.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  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 hash_bad_resize_example.cpp
+ * An example showing how *not* to resize a hash-based container.
+ */
+
+/**
+ * This non-compiling example shows wrong use of hash-based
+ * containers. By default, resize policies don't allow external size
+ * access.
+ **/
+
+#include <ext/pb_ds/assoc_container.hpp>
+
+using namespace std;
+using namespace __gnu_pbds;
+
+int main()
+{
+  // A collision-chaining hash table mapping ints to chars.
+  typedef cc_hash_table< int, char> map_t;
+
+  // A map_t object.
+  map_t h;
+
+  // The following line won't compile. The resize policy needs to be
+  // configured to allow external resize (by default, this is not
+  // available).
+  h.resize(20); // { dg-error "instantiated from" }
+}
+
+// { dg-error "invalid" "" { target *-*-* } 187 } 
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/hash_shift_mask.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/hash_shift_mask.cc
new file mode 100644
index 000000000..1abe25f67
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/example/hash_shift_mask.cc
@@ -0,0 +1,108 @@
+// -*- 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.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  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 hash_shift_mask_example.cpp
+ * An example showing how to write a range-hasing functor.
+ */
+
+/**
+ * In some rare cases, advance knowledge of the distribution of keys allows
+ * writing more efficient hash-related policies.
+ * In the rather simplistic case of the example, it is known in advance that
+ * all keys have 0 two lowest bits. The example shows how to write
+ * a range-hashing function disregarding the two lowest bits of the hash value.
+ */
+
+#include <functional>
+#include <ext/pb_ds/assoc_container.hpp>
+#include <ext/pb_ds/hash_policy.hpp>
+
+using namespace std;
+using namespace __gnu_pbds;
+
+// A simple hash functor. hash could serve instead of this functor,
+// but it is not yet standard everywhere.
+struct simple_int_hash : public unary_function<int, size_t>
+{
+  inline size_t
+  operator()(int i) const
+  { return i; }
+};
+
+// A range-hashing function which shifts 2 bits right and then masks.
+class shift_two_mask_range_hashing : private direct_mask_range_hashing<>
+{
+public:
+  typedef size_t size_type;
+
+  // Swaps with a different instant.
+  void
+  swap(shift_two_mask_range_hashing& other)
+  { direct_mask_range_hashing<>::swap(other); }
+
+  // Called by the container when internally resized.
+  void
+  notify_resized(size_type size)
+  { direct_mask_range_hashing<>::notify_resized(size); }
+
+  // Given a hash value, returns a number in the range of the internal
+  // size of the container.
+  inline size_type
+  operator()(size_type hash) const
+  { return direct_mask_range_hashing<>::operator()(hash >> 2); }
+};
+
+int
+main()
+{
+  // A collision-chaining hash table mapping ints to chars.
+  typedef
+    cc_hash_table<
+    int,
+    char,
+    // Hash function.
+    simple_int_hash,
+    equal_to<int>,
+    // Range hashing function.
+    shift_two_mask_range_hashing>
+    map_t;
+
+  map_t h;
+
+  // Use normally.
+  h[16] = 'a';
+  h[256] = 'e';
+  h[4] = 'z';
+
+  return 0;
+}
+
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/priority_queue_container_traits.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/priority_queue_container_traits.cc
new file mode 100644
index 000000000..007c19f43
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/example/priority_queue_container_traits.cc
@@ -0,0 +1,200 @@
+// -*- 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.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  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 priority_queue_container_traits_example.cpp
+ * A basic example showing how to use container_traits for querying container types
+ *    for their behavior.
+ */
+
+/**
+ * The following example shows how to use container_traits in order to print
+ * out information on an priority queue's behavior, e.g., its underlying
+ * data structure.
+ */
+
+#include <iostream>
+#include <ext/pb_ds/priority_queue.hpp>
+#include <ext/pb_ds/tag_and_trait.hpp>
+
+using namespace std;
+using namespace __gnu_pbds;
+
+template<class DS_Category>
+void
+print_container_category(DS_Category);
+
+template<>
+void
+print_container_category(binary_heap_tag)
+{ cout << "Binary heap:" << endl; }
+
+template<>
+void
+print_container_category(binomial_heap_tag)
+{ cout << "Binomial heap:" << endl; }
+
+template<>
+void
+print_container_category(rc_binomial_heap_tag)
+{ cout << "Redundant-counter binomial heap:" << endl; }
+
+template<>
+void
+print_container_category(pairing_heap_tag)
+{ cout << "Pairing heap:" << endl; }
+
+template<>
+void
+print_container_category(thin_heap_tag)
+{ cout << "Thin heap:" << endl; }
+
+template<class Invalidation_Guarantee>
+void
+print_invalidation_guarantee(Invalidation_Guarantee);
+
+template<>
+void
+print_invalidation_guarantee(basic_invalidation_guarantee)
+{
+  cout << "Guarantees only that found references, pointers, and "
+    "iterators are valid as long as the container object is not "
+    "modified" << endl;
+}
+
+template<>
+void
+print_invalidation_guarantee(point_invalidation_guarantee)
+{
+  cout << "Guarantees that found references, pointers, and "
+    "point_iterators are valid even if the container object "
+    "is modified" << endl;
+}
+
+template<>
+void
+print_invalidation_guarantee(range_invalidation_guarantee)
+{
+  cout << "Guarantees that iterators remain valid even if the "
+    "container object is modified" << endl;
+}
+
+void
+print_split_join_can_throw(bool can)
+{
+  if (can)
+    {
+      cout << "Can throw exceptions if split or joined" << endl;
+      return;
+    }
+  cout << "Cannot throw exceptions if split or joined" << endl;
+}
+
+template<class DS_Traits>
+void
+print_container_attributes()
+{
+  // First print out the data structure category.
+  print_container_category(typename DS_Traits::container_category());
+
+  // Now print the attributes of the container.
+  print_invalidation_guarantee(typename DS_Traits::invalidation_guarantee());
+  print_split_join_can_throw(DS_Traits::split_join_can_throw);
+  cout << endl << endl;
+}
+
+int main()
+{
+  {
+    // Print the attributes of a binary heap.
+    typedef
+      __gnu_pbds::priority_queue<
+      int,
+      std::less<int>,
+      binary_heap_tag>
+      t;
+
+    print_container_attributes<container_traits<t> >();
+  }
+
+  {
+    // Print the attributes of a binomial heap.
+    typedef
+      __gnu_pbds::priority_queue<
+      int,
+      std::less<int>,
+      binomial_heap_tag>
+      t;
+
+    print_container_attributes<container_traits<t> >();
+  }
+
+  {
+    // Print the attributes of a redundant-counter binomial heap.
+    typedef
+      __gnu_pbds::priority_queue<
+      int,
+      std::less<int>,
+      rc_binomial_heap_tag>
+      t;
+
+    print_container_attributes<container_traits<t> >();
+  }
+
+  {
+    // Print the attributes of a pairing heap.
+    typedef
+      __gnu_pbds::priority_queue<
+      int,
+      std::less<int>,
+      pairing_heap_tag>
+      t;
+
+    print_container_attributes<container_traits<t> >();
+  }
+
+  {
+    /**
+     *  Print the attributes of a thin heap.
+     */
+
+    typedef
+      __gnu_pbds::priority_queue<
+      int,
+      std::less<int>,
+      thin_heap_tag>
+      t;
+
+    print_container_attributes<container_traits<t> >();
+  }
+
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/priority_queue_dijkstra.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/priority_queue_dijkstra.cc
new file mode 100644
index 000000000..74fdc0e62
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/example/priority_queue_dijkstra.cc
@@ -0,0 +1,157 @@
+// -*- 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.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  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 priority_queue_dijkstra_example.cpp
+ * A basic example showing how to cross reference a vector and a
+ * priority-queue for modify.
+ */
+
+/**
+ * This example shows how to cross-reference priority queues
+ * and a vector. I.e., using a vector to
+ * map keys to entries in a priority queue, and using the priority
+ * queue to map entries to the vector. The combination
+ * can be used for fast modification of keys.
+ *
+ * As an example, a very simple form of Diskstra's algorithm is used. The graph
+ * is represented by an adjacency matrix. Nodes and vertices are size_ts, and
+ * it is assumed that the minimal path between any two nodes is less than 1000.
+ */
+
+
+
+#include <vector>
+#include <iostream>
+#include <ext/pb_ds/priority_queue.hpp>
+
+using namespace std;
+using namespace __gnu_pbds;
+
+// The value type of the priority queue.
+// The first entry is the node's id, and the second is the distance.
+typedef std::pair<size_t, size_t> pq_value;
+
+// Comparison functor used to compare priority-queue value types.
+struct pq_value_cmp : public binary_function<pq_value, pq_value, bool>
+{
+  inline bool
+  operator()(const pq_value& r_lhs, const pq_value& r_rhs) const
+  {
+    // Note that a value is considered smaller than a different value
+    // if its distance is* larger*. This is because by STL
+    // conventions, "larger" entries are nearer the top of the
+    // priority queue.
+    return r_rhs.second < r_lhs.second;
+  }
+};
+
+int main()
+{
+  enum
+    {
+      // Number of vertices is hard-coded in this example.
+      num_vertices = 5,
+      // "Infinity".
+      graph_inf = 1000
+    };
+
+  // The edge-distance matrix.
+  // For example, the distance from node 0 to node 1 is 5, and the
+  // distance from node 1 to node 0 is 2.
+  const size_t a_a_edge_legnth[num_vertices][num_vertices] =
+    {
+      {0, 5, 3, 7, 6},
+      {2, 0, 2, 8, 9},
+      {2, 1, 0, 8, 0},
+      {1, 8, 3, 0, 2},
+      {2, 3, 4, 2, 0}
+    };
+
+  // The priority queue type.
+  typedef __gnu_pbds::priority_queue< pq_value, pq_value_cmp> pq_t;
+
+  // The priority queue object.
+  pq_t p;
+
+  // This vector contains for each node, a find-iterator into the
+  // priority queue.
+  vector<pq_t::point_iterator> a_it;
+
+  // First we initialize the data structures.
+
+  // For each node, we push into the priority queue a value
+  // identifying it with a distance of infinity.
+  for (size_t i = 0; i < num_vertices; ++i)
+    a_it.push_back(p.push(pq_value(i, graph_inf)));
+
+  // Now we take the initial node, in this case 0, and modify its
+  // distance to 0.
+  p.modify(a_it[0], pq_value(0, 0));
+
+  // The priority queue contains all vertices whose final distance has
+  // not been determined, so to finish the algorithm, we must loop
+  // until it is empty.
+  while (!p.empty())
+    {
+      // First we find the node whose distance is smallest.
+      const pq_value& r_v = p.top();
+      const size_t node_id = r_v.first;
+      const size_t dist = r_v.second;
+
+      // This is the node's final distance, so we can print it out.
+      cout << "The distance from 0 to " << node_id 
+	   << " is " << dist << endl;
+
+      // Now we go over the node's neighbors and "relax" the
+      // distances, if applicable.
+      for (size_t neighbor_i = 0; neighbor_i < num_vertices; ++neighbor_i)
+        {
+	  // Potentially, the distance to the neighbor is the distance
+	  // to the currently-considered node + the distance from this
+	  // node to the neighbor.
+	  const size_t pot_dist = dist + a_a_edge_legnth[node_id][neighbor_i];
+
+	  if (a_it[neighbor_i] == a_it[0])
+	    continue;
+
+	  // "Relax" the distance (if appropriate) through modify.
+	  if (pot_dist < a_it[neighbor_i]->second)
+	    p.modify(a_it[neighbor_i], pq_value(neighbor_i, pot_dist));
+        }
+
+      // Done with the node, so we pop it.
+      a_it[node_id] = a_it[0];
+      p.pop();
+    }
+
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/priority_queue_erase_if.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/priority_queue_erase_if.cc
new file mode 100644
index 000000000..0f3ca1fb4
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/example/priority_queue_erase_if.cc
@@ -0,0 +1,67 @@
+// -*- 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.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  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 priority_queue_erase_if.cpp
+ * Example showing how to conditionally erase values from a priority queue.
+ */
+
+/**
+ * This example shows how to erase from a priority queue using erase_if.
+ */
+
+#include <functional>
+#include <iostream>
+#include <cassert>
+#include <ext/pb_ds/priority_queue.hpp>
+
+using namespace std;
+using namespace __gnu_pbds;
+
+int
+main()
+{
+  __gnu_pbds::priority_queue<int> p;
+
+  // First we insert some values into the container.
+  for (int i = 0; i < 1000; ++i)
+    p.push(i);
+
+  assert(p.top() == 999);
+
+  // Now we erase all values that satisfy some predicate, in this case
+  // one that returns true for all those larger than 500.
+  p.erase_if(bind1st(less<int>(), 500));
+
+  // The largest value should be now 500.
+  assert(p.top() == 500);
+}
+
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/priority_queue_split_join.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/priority_queue_split_join.cc
new file mode 100644
index 000000000..c2d83c0b2
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/example/priority_queue_split_join.cc
@@ -0,0 +1,124 @@
+// -*- 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.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  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 priority_queue_split_join_example.cpp
+ * A basic example showing how to split and join priority queues.
+ */
+
+/**
+ * This example shows how to split and join priority queues.
+ */
+
+#include <functional>
+#include <iostream>
+#include <cassert>
+#include <ext/pb_ds/priority_queue.hpp>
+
+using namespace std;
+using namespace __gnu_pbds;
+
+int
+main()
+{
+  // Two priority queue objects.
+  __gnu_pbds::priority_queue<int> even_p, odd_p;
+
+  // First we insert some values: even ones into even_p, and odd ones
+  // into odd_p.
+  for (size_t i = 0; i < 10; ++i)
+    {
+      even_p.push(2*  i);
+      odd_p.push(2*  i + 1);
+    }
+
+  // Check that each one contains the appropriate 10 values.
+  assert(even_p.size() == 10);
+  assert(even_p.top() == 18);
+
+  // Print out the values.
+  cout << "Initial values in even priority queue:" << endl;
+  __gnu_pbds::priority_queue<int>::const_iterator it;
+  for (it = even_p.begin(); it != even_p.end(); ++it)
+    cout <<* it << endl;
+
+  assert(odd_p.size() == 10);
+  assert(odd_p.top() == 19);
+
+  // Print out the values.
+  cout << "Initial values in odd priority queue:" << endl;
+  for (it = odd_p.begin(); it != odd_p.end(); ++it)
+    cout <<* it << endl;
+
+  // Now join the queues.
+  even_p.join(odd_p);
+
+  // Check that each one contains the appropriate values.
+
+  assert(even_p.size() == 20);
+  assert(even_p.top() == 19);
+
+  // Print out the values.
+  cout << "After-join values in even priority queue:" << endl;
+  for (it = even_p.begin(); it != even_p.end(); ++it)
+    cout <<* it << endl;
+
+  assert(odd_p.size() == 0);
+
+  // Print out the values.
+  cout << "After-join values in odd priority queue:" << endl;
+  for (it = odd_p.begin(); it != odd_p.end(); ++it)
+    cout <<* it << endl;
+
+  // Now split the queues.
+  even_p.split(bind2nd(modulus<int>(), 2), odd_p);
+
+  // Check that each one contains the appropriate 10 values.
+
+  assert(even_p.size() == 10);
+  assert(even_p.top() == 18);
+
+  // Print out the values.
+  cout << "After-split values in even priority queue:" << endl;
+  for (it = even_p.begin(); it != even_p.end(); ++it)
+    cout <<* it << endl;
+
+  assert(odd_p.size() == 10);
+  assert(odd_p.top() == 19);
+
+  // Print out the values.
+  cout << "After-split values in odd priority queue:" << endl;
+  for (it = odd_p.begin(); it != odd_p.end(); ++it)
+    cout <<* it << endl;
+
+  return 0;
+}
+
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/priority_queue_xref.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/priority_queue_xref.cc
new file mode 100644
index 000000000..690814091
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/example/priority_queue_xref.cc
@@ -0,0 +1,210 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2007, 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.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  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 priority_queue_xref_example.cpp
+ * A basic example showing how to cross-reference priority queues and other
+ *    containers for erase.
+ */
+
+/**
+ * This example shows how to cross-reference priority queues
+ * and other containers. I.e., using an associative container to
+ * map keys to entries in a priority queue, and using the priority
+ * queue to map entries to the associative container. The combination
+ * can be used for fast operations involving both priorities and
+ * arbitrary keys.
+ *
+ * The most useful examples of this technique are usually from the
+ * field of graph algorithms (where erasing or modifying an arbitrary
+ * entry of a priority queue is sometimes necessary), but a full-blown
+ * example would be too long. Instead, this example shows a very simple
+ * version of Dijkstra's
+ */
+
+#include <iostream>
+#include <cassert>
+#include <ext/pb_ds/priority_queue.hpp>
+#include <ext/pb_ds/assoc_container.hpp>
+
+using namespace std;
+using namespace __gnu_pbds;
+
+// A priority queue of integers, which supports fast pushes,
+// duplicated-int avoidance, and arbitrary-int erases.
+class mapped_priority_queue
+{
+public:
+
+  // Pushes an int into the container. If the key is already in, this
+  // is a no-op.
+  void
+  push(const int& r_str);
+
+  // Returns a const reference to the largest int in the container.
+  int
+  top() const
+  {
+    assert(!empty());
+    return m_pq.top();
+  }
+
+  // Erases the largest int in the container.
+  void
+  pop();
+
+  // Erases an arbitrary int. If the int is not in the container, this
+  // is a no-op, and the return value is false.
+  bool
+  erase(const int& r_str);
+
+  bool
+  empty() const
+  { return m_pq.empty(); }
+
+  size_t
+  size() const
+  { return m_pq.size(); }
+
+private:
+  // A priority queue of strings.
+  typedef __gnu_pbds::priority_queue< int> pq_t;
+
+  // A hash-table mapping strings to point_iterators inside the
+  // priority queue.
+  typedef cc_hash_table< int, pq_t::point_iterator> map_t;
+
+  pq_t m_pq;
+  map_t m_map;
+};
+
+void
+mapped_priority_queue::
+push(const int& r_str)
+{
+  // First check if the int is already in the container. If so, just return.
+  if (m_map.find(r_str) != m_map.end())
+    return;
+
+  // Push the int into the priority queue, and store a point_iterator to it.
+  pq_t::point_iterator pq_it = m_pq.push(r_str);
+
+  try
+    {
+      // Now make the map associate the int to the point_iterator.
+      m_map[r_str] = pq_it;
+    }
+  catch(...)
+    {
+      // If the above failed, we need to remove the int from the
+      // priority queue as well.
+      m_pq.erase(pq_it);
+      throw;
+    }
+}
+
+void
+mapped_priority_queue::
+pop()
+{
+  assert(!empty());
+
+  // Erase the int from the map.
+  m_map.erase(m_pq.top());
+
+  // ...then from the priority queue.
+  m_pq.pop();
+}
+
+bool
+mapped_priority_queue::
+erase(const int& r_str)
+{
+  map_t::point_iterator map_it = m_map.find(r_str);
+
+  // If the int is not in the map, this is a no-op.
+  if (map_it == m_map.end())
+    return false;
+
+  // Otherwise, we erase it from the priority queue.
+  m_pq.erase(map_it->second);
+
+  // ...then from the map.
+  m_map.erase(r_str);
+
+  return true;
+}
+
+int main()
+{
+  // Push some values into the container object.
+  mapped_priority_queue m;
+  m.push(1);
+  m.push(2);
+
+  // The following four operations are no-ops: 2 and 1 are already in
+  // the container.
+  m.push(2);
+  m.push(2);
+  m.push(2);
+  m.push(1);
+
+  m.push(10);
+  m.push(11);
+  m.push(12);
+
+  // The size should be 5, since m contains the set {1, 2, 10, 11, 12}.
+  assert(m.size() == 5);
+
+  // The largest value should be 12.
+  assert(m.top() == 12);
+
+  // Now erase some values.
+
+  // Erasing 1 actually erases a value.
+  assert(m.erase(1));
+
+  // ...but erasing 1 again is a no-op.
+  assert(!m.erase(1));
+
+  // The size should be 5, since m contains the set {2, 10, 11, 12}.
+  assert(m.size() == 4);
+
+  // Now print the values in the container.
+  while (!m.empty())
+    {
+      cout << m.top() << endl;
+      m.pop();
+    }
+
+  return 0;
+}
+
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/ranged_hash.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/ranged_hash.cc
new file mode 100644
index 000000000..e9f33b113
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/example/ranged_hash.cc
@@ -0,0 +1,151 @@
+// -*- 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.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  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 ranged_hash_example.cpp
+ * A basic example showing how to write a ranged-hash functor.
+ */
+
+/**
+ * In some cases it is beneficial to write a hash function which determines
+ * hash values based on the size of the container object.
+ * The example shows an example of a string-hashing function which
+ * uses a fast method for hashing strings when the number of strings
+ * in the container object is small, and a slower but more careful method
+ * for hashing strings when the number of strings in the container object
+ * is large.
+ */
+
+#include <functional>
+#include <cassert>
+#include <string>
+#include <ext/pb_ds/assoc_container.hpp>
+#include <ext/pb_ds/hash_policy.hpp>
+
+using namespace std;
+using namespace __gnu_pbds;
+
+/**
+ * A (somewhat simplistic) ranged-hash function for strings.
+ * It uses the size of the container object to determine
+ * the hashing method. For smaller sizes it uses a simple hash function;
+ * for larger sizes it uses a more complicated hash function.
+ */
+class simple_string_ranged_hash_fn 
+  : public unary_function<string, size_t>
+{
+public:
+  typedef size_t size_type;
+
+  simple_string_ranged_hash_fn() : m_container_size(0) { }
+
+  // Called to notify that the size has changed.
+  void
+  notify_resized(size_t size)
+  { m_container_size = size; }
+
+  // Called for hashing a string into a size_t in a given range.
+  size_t
+  operator()(const string& r_string)
+  {
+    /*
+     *  This (simplified) hash algorithm decides that if there are
+     *  fewer than 100 strings in the container it will hash
+     *  a string by summing its characters; otherwise, it will
+     *  perform a more complicated operation in order to produce
+     *  hash values with fewer collisions.
+     */
+    string::const_iterator it = r_string.begin();
+    size_t hash = 0;
+    if (m_container_size < 100)
+      {
+	// For this size, perform an accumulate type of operation.
+	while (it != r_string.end())
+	  hash += static_cast<size_t>(*it++);
+      }
+    else
+      {
+	// For this size, perform a different operation.
+	while (it != r_string.end())
+	  {
+	    hash += static_cast<size_t>(*it++);
+	    hash *= 5;
+	  }
+      }
+
+    // The function must, by whatever means, return a size in the
+    // range 0 to m_container_size.
+    return hash % m_container_size;
+  }
+
+  // Swaps content.
+  void
+  swap(simple_string_ranged_hash_fn& other)
+  {
+    std::swap(m_container_size, other.m_container_size);
+  }
+
+private:
+  // Records the size of the container object.
+  size_t m_container_size;
+};
+
+int
+main()
+{
+  // A collision-chaining hash table storing strings.
+  typedef
+    cc_hash_table<
+    string,
+    null_mapped_type,
+    null_hash_fn,
+    equal_to<string>,
+    simple_string_ranged_hash_fn>
+    set_t;
+
+  // Note that in the above, the library determines a resize policy
+  // appropriate for modulo-based range hashing.
+  set_t h;
+
+  // Use the table normally.
+  h.insert("Hello, ");
+  h.insert("world");
+
+  assert(h.size() == 2);
+
+  assert(h.find("Hello, ") != h.end());
+  assert(h.find("world") != h.end());
+
+  assert(h.find("Goodbye, oh cruel world!") == h.end());
+
+  return 0;
+}
+
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/store_hash.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/store_hash.cc
new file mode 100644
index 000000000..f762bfdb2
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/example/store_hash.cc
@@ -0,0 +1,97 @@
+// -*- 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.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  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 store_hash_example.cpp
+ * An example showing how to store hash-values with
+ *     each entry in a hash-based container.
+ */
+
+/**
+ * This example shows how to configure a hash-based container to store
+ * the hash value of each key along with each entry. This technique
+ * is useful for complex keys (e.g., strings in this example), since
+ * it lowers the cost of collisions. For simpler types (e.g., integers),
+ * where the cost of comparing keys is of the same order as the cost
+ * of comparing hash values, this technique adds unnecessary overhead.
+ */
+
+#include <functional>
+#include <string>
+#include <ext/pb_ds/assoc_container.hpp>
+#include <ext/pb_ds/hash_policy.hpp>
+
+using namespace std;
+using namespace __gnu_pbds;
+
+// A string hash functor.
+struct string_hash : public unary_function<string, size_t>
+{
+  inline size_t
+  operator()(string str) const
+  {
+    string::const_iterator b = str.begin();
+    string::const_iterator e = str.end();
+
+    size_t hash = 0;
+    while (b != e)
+      {
+	hash *= 5;
+	hash += static_cast<size_t>(*b);
+	++b;
+      }
+    return hash;
+  }
+};
+
+int main()
+{
+  // A collision-chaining hash table mapping strings to ints.
+  typedef
+    cc_hash_table<
+    string,
+    int,
+    string_hash,
+    equal_to<string>,
+    direct_mask_range_hashing<>,
+    hash_standard_resize_policy<>,
+    true>
+    map_t;
+
+  map_t h;
+
+  // Use regularly.
+  h["Hello, "] = 0;
+  h["world"] = 1;
+
+  return 0;
+}
+
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/tree_intervals.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/tree_intervals.cc
new file mode 100644
index 000000000..406ab8e0c
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/example/tree_intervals.cc
@@ -0,0 +1,212 @@
+// -*- 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.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  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 tree_intervals_example.cpp
+ * An example showing how to augment a trees to support operations involving
+ *    line intervals.
+ */
+
+/**
+ * In some cases tree structure can be used for various purposes other
+ * than storing entries by key order.  This example shows how a
+ * tree-based container can be used for geometric-line intersection
+ * determination. That is, the key of the container is a pair of
+ * numbers representing a line interval. The container object can be
+ * used to query whether a line interval intersects any line interval
+ * it currently stores.
+ *
+ * This type of problem arises not only in geometric applications, but
+ * also sometimes in distributed filesystems. Assume that "leases" are
+ * taken for parts of files or LUNs. When a new lease is requested, it
+ * is necessary to check that it does not conflict with a lease
+ * already taken. In this case a file or LUN can be envisioned as a
+ * line segment; leases requested and granted for contiguous parts of
+ * the file or LUN can be represented as line intervals as well.
+ */
+
+#include <cassert>
+#include <cstdlib>
+#include <ext/pb_ds/assoc_container.hpp>
+
+using namespace std;
+using namespace __gnu_pbds;
+
+// Following are definitions of line intervals and functors operating
+// on them. As the purpose of this example is node invariants, and not
+// computational-geometry algorithms per-se, some simplifications are
+// made (e.g., intervals are defined by unsigned integers, and not by
+// a parameterized type, data members are public, etc.).
+
+// An interval of unsigned integers.
+typedef pair< unsigned int, unsigned int> interval;
+
+// Functor updating maximal endpoints of entries. Algorithm taken from
+// "Introduction to Algorithms" by Cormen, Leiserson, and Rivest.
+template<class Const_Node_Iterator,
+	 class Node_Iterator,
+	 class Cmp_Fn,
+	 class Allocator>
+struct intervals_node_update
+{
+public:
+  // The metadata that each node stores is the largest endpoint of an
+  // interval in its subtree. In this case, this is an unsigned int.
+  typedef unsigned int metadata_type;
+
+  // Checks whether a set of intervals contains at least one interval
+  // overlapping some interval. Algorithm taken from "Introduction to
+  // Algorithms" by Cormen, Leiserson, and Rivest.
+  bool
+  overlaps(const interval& r_interval)
+  {
+    Const_Node_Iterator nd_it = node_begin();
+    Const_Node_Iterator end_it = node_end();
+
+    while (nd_it != end_it)
+      {
+	// Check whether r_interval overlaps the current interval.
+	if (r_interval.second >= (*nd_it)->first&&
+	    r_interval.first <= (*nd_it)->second)
+	  return true;
+
+	// Get the const node iterator of the node's left child.
+	Const_Node_Iterator l_nd_it = nd_it.get_l_child();
+
+	// Calculate the maximal endpoint of the left child. If the
+	// node has no left child, then this is the node's maximal
+	// endpoint.
+	const unsigned int l_max_endpoint =(l_nd_it == end_it)?
+	  0 : l_nd_it.get_metadata();
+
+	// Now use the endpoint to determine which child to choose.
+	if (l_max_endpoint >= r_interval.first)
+	  nd_it = l_nd_it;
+	else
+	  nd_it = nd_it.get_r_child();
+      }
+
+    return false;
+  }
+
+protected:
+  // Update predicate: nd_it is a node iterator to the node currently
+  // updated; end_nd_it is a const node iterator to a just-after leaf
+  // node.
+  inline void
+  operator()(Node_Iterator nd_it, Const_Node_Iterator end_nd_it)
+  {
+    // The left maximal endpoint is 0 if there is no left child.
+    const unsigned int l_max_endpoint =(nd_it.get_l_child() == end_nd_it)?
+      0 : nd_it.get_l_child().get_metadata();
+
+    // The right maximal endpoint is 0 if there is no right child.
+    const unsigned int r_max_endpoint =(nd_it.get_r_child() == end_nd_it)?
+      0 : nd_it.get_r_child().get_metadata();
+
+    // The maximal endpoint is the endpoint of the node's interval,
+    // and the maximal endpoints of its children.
+    const_cast<unsigned int&>(nd_it.get_metadata()) =
+      max((*nd_it)->second, max<unsigned int>(l_max_endpoint, r_max_endpoint));
+  }
+
+  virtual Const_Node_Iterator
+  node_begin() const = 0;
+
+  virtual Const_Node_Iterator
+  node_end() const = 0;
+
+  virtual
+  ~intervals_node_update()
+  { }
+};
+
+// The following function performs some operation sequence on a
+// generic associative container supporting order statistics. It
+// inserts some intervals, and checks for overlap.
+template<class Cntnr>
+void
+some_op_sequence(Cntnr r_c)
+{
+  // Insert some entries.
+  r_c.insert(make_pair(0, 100));
+  r_c.insert(make_pair(150, 160));
+  r_c.insert(make_pair(300, 1000));
+  r_c.insert(make_pair(10000, 100000));
+  r_c.insert(make_pair(200, 100200));
+
+  // Test overlaps.
+
+  // Overlaps 150 - 160
+  assert(r_c.overlaps(make_pair(145, 165)) == true);
+  // Overlaps 150 - 160
+  assert(r_c.overlaps(make_pair(145, 155)) == true);
+  assert(r_c.overlaps(make_pair(165, 175)) == false);
+  assert(r_c.overlaps(make_pair(100201, 100203)) == false);
+
+  // Erase an interval
+  r_c.erase(make_pair(150, 160));
+
+  // Test overlaps again.
+  assert(r_c.overlaps(make_pair(145, 165)) == false);
+  assert(r_c.overlaps(make_pair(165, 175)) == false);
+  assert(r_c.overlaps(make_pair(0, 300000)) == true);
+}
+
+int main()
+{
+  // Test a red-black tree.
+  some_op_sequence(tree<
+		   interval,
+		   null_mapped_type,
+		   less<interval>,
+		   rb_tree_tag,
+		   intervals_node_update>());
+
+  // Test an ordered-vector tree.
+  some_op_sequence(tree<
+		   interval,
+		   null_mapped_type,
+		   less<interval>,
+		   ov_tree_tag,
+		   intervals_node_update>());
+
+  // Test a splay tree.
+  some_op_sequence(tree<
+		   interval,
+		   null_mapped_type,
+		   less<interval>,
+		   splay_tree_tag,
+		   intervals_node_update>());
+
+  return 0;
+}
+
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/tree_join.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/tree_join.cc
new file mode 100644
index 000000000..5953804f5
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/example/tree_join.cc
@@ -0,0 +1,112 @@
+// -*- 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.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  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 tree_join_example.cpp
+ * An example showing how to join splay_tree_map objects.
+ *    The code in the example is relevant to red-black trees as well.
+ */
+
+/**
+ * This example shows how to join tree based containers, i.e., taking two
+ *     objects with non-overlapping sets of keys and combining them into
+ *    a single object.
+ */
+
+// For tree
+#include <ext/pb_ds/assoc_container.hpp>
+// For join_error exception.
+#include <ext/pb_ds/exception.hpp>
+// For assert
+#include <cassert>
+
+using namespace std;
+using namespace __gnu_pbds;
+using namespace __gnu_pbds;
+
+int main()
+{
+  /*
+   *  
+   */
+  // A splay tree table mapping ints to chars.
+  typedef tree<int, char, less<int>, splay_tree_tag> map_t;
+
+  // Two map_t object.
+  map_t h0, h1;
+
+  // Insert some values into the first table.
+  for (int i0 = 0; i0 < 100; ++i0)
+    h0.insert(make_pair(i0, 'a'));
+
+  // Insert some values into the second table.
+  for (int i1 = 0; i1 < 100; ++i1)
+    h1.insert(make_pair(1000 + i1, 'b'));
+
+  // Since all the elements in h0 are smaller than those in h1, it is
+  // possible to join the two tables. This is exception free.
+  h0.join(h1);
+
+  // Check that h0 should now contain all entries, and h1 should be empty.
+  assert(h0.size() == 200);
+  assert(h1.empty());
+
+
+  // Two other map_t objects.
+  map_t h2, h3;
+
+  h2[1] = 'a';
+  h2[3] = 'c';
+
+  h3[2] = 'b';
+
+  // Now perform an illegal join.
+  // It is not true that all elements in h2 are smaller than those in
+  // h3, nor is it true that they are all larger. Hence, attempting to
+  // join h2, and h3 should result in an exception.
+  bool exception_thrown = false;
+  try
+    {
+      h2.join(h3);
+    }
+  catch (__gnu_pbds::join_error& )
+    {
+      exception_thrown = true;
+    }
+  assert(exception_thrown);
+
+  // Since the operation was not performed, the tables should be unaltered.
+  assert(h2.size() == 2);
+  assert(h3[2] == 'b');
+
+  return 0;
+}
+
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/tree_order_statistics.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/tree_order_statistics.cc
new file mode 100644
index 000000000..584574030
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/example/tree_order_statistics.cc
@@ -0,0 +1,124 @@
+// -*- 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.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  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 tree_order_statistics_example.cpp
+ * An example showing how to use functors for order-statistics
+ *    in tree-based containers.
+ */
+
+/**
+ * In some cases tree structure can be used for various purposes asides
+ *    from storing entries by key order.
+ *    This example shows how a tree-based container can be used for
+ *    order-statistics, i.e., for determining the order of each key
+ *     in the (ordered) sequence of keys stored within the container object.
+ */
+
+#include <cassert>
+#include <ext/pb_ds/assoc_container.hpp>
+#include <ext/pb_ds/tree_policy.hpp>
+
+using namespace std;
+using namespace __gnu_pbds;
+
+// A red-black tree table storing ints and their order
+// statistics. Note that since the tree uses
+// tree_order_statistics_node_update as its update policy, then it
+// includes its methods by_order and order_of_key.
+typedef
+tree<
+  int,
+  null_mapped_type,
+  less<int>,
+  rb_tree_tag,
+  // This policy updates nodes' metadata for order statistics.
+  tree_order_statistics_node_update>
+set_t;
+
+int main()
+{
+  // Insert some entries into s.
+  set_t s;
+  s.insert(12);
+  s.insert(505);
+  s.insert(30);
+  s.insert(1000);
+  s.insert(10000);
+  s.insert(100);
+
+  // The order of the keys should be: 12, 30, 100, 505, 1000, 10000.
+  assert(*s.find_by_order(0) == 12);
+  assert(*s.find_by_order(1) == 30);
+  assert(*s.find_by_order(2) == 100);
+  assert(*s.find_by_order(3) == 505);
+  assert(*s.find_by_order(4) == 1000);
+  assert(*s.find_by_order(5) == 10000);
+  assert(s.find_by_order(6) == s.end());
+
+  // The order of the keys should be: 12, 30, 100, 505, 1000, 10000.
+  assert(s.order_of_key(10) == 0);
+  assert(s.order_of_key(12) == 0);
+  assert(s.order_of_key(15) == 1);
+  assert(s.order_of_key(30) == 1);
+  assert(s.order_of_key(99) == 2);
+  assert(s.order_of_key(100) == 2);
+  assert(s.order_of_key(505) == 3);
+  assert(s.order_of_key(1000) == 4);
+  assert(s.order_of_key(10000) == 5);
+  assert(s.order_of_key(9999999) == 6);
+
+  // Erase an entry.
+  s.erase(30);
+
+  // The order of the keys should be: 12, 100, 505, 1000, 10000.
+  assert(*s.find_by_order(0) == 12);
+  assert(*s.find_by_order(1) == 100);
+  assert(*s.find_by_order(2) == 505);
+  assert(*s.find_by_order(3) == 1000);
+  assert(*s.find_by_order(4) == 10000);
+  assert(s.find_by_order(5) == s.end());
+
+  // The order of the keys should be: 12, 100, 505, 1000, 10000.
+  assert(s.order_of_key(10) == 0);
+  assert(s.order_of_key(12) == 0);
+  assert(s.order_of_key(100) == 1);
+  assert(s.order_of_key(505) == 2);
+  assert(s.order_of_key(707) == 3);
+  assert(s.order_of_key(1000) == 3);
+  assert(s.order_of_key(1001) == 4);
+  assert(s.order_of_key(10000) == 4);
+  assert(s.order_of_key(100000) == 5);
+  assert(s.order_of_key(9999999) == 5);
+
+  return 0;
+}
+
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/tree_order_statistics_join.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/tree_order_statistics_join.cc
new file mode 100644
index 000000000..18b47c134
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/example/tree_order_statistics_join.cc
@@ -0,0 +1,90 @@
+// -*- 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.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  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 tree_order_statistics_join_example.cpp
+ * An example showing how to augment a splay tree to support order statistics.
+ */
+
+// This example shows how join operations still maintain node
+// invariants. Specifically, it shows how the objects of containers
+// supporting order statistics can be joined into an object supporting
+// order statistics.
+// While the example does not show this, the same holds for split operations.
+
+#include <cassert>
+#include <ext/pb_ds/assoc_container.hpp>
+#include <ext/pb_ds/tree_policy.hpp>
+
+using namespace std;
+using namespace __gnu_pbds;
+
+// A splay tree table mapping ints to chars and storing the ints order
+// statistics.
+typedef
+tree<int, char, less<int>,
+     splay_tree_tag,
+     tree_order_statistics_node_update>
+tree_map_t;
+
+int main()
+{
+  // Insert some entries into s0.
+  tree_map_t s0;
+  s0.insert(make_pair(12, 'a'));
+  s0.insert(make_pair(505, 'b'));
+  s0.insert(make_pair(30, 'c'));
+
+  // The order of the keys should be: 12, 30, 505.
+  assert(s0.find_by_order(0)->first == 12);
+  assert(s0.find_by_order(1)->first == 30);
+  assert(s0.find_by_order(2)->first == 505);
+
+  // Insert some entries into s1.
+  tree_map_t s1;
+  s1.insert(make_pair(506, 'a'));
+  s1.insert(make_pair(1222, 'b'));
+  s1.insert(make_pair(3004, 'a'));
+
+  // Now join s0 and s1.
+  s0.join(s1);
+
+  // The order of the keys should be: 12, 30, 505, 506, 1222, 3004.
+  assert(s0.find_by_order(0)->first == 12);
+  assert(s0.find_by_order(1)->first == 30);
+  assert(s0.find_by_order(2)->first == 505);
+  assert(s0.find_by_order(3)->first == 506);
+  assert(s0.find_by_order(4)->first == 1222);
+  assert(s0.find_by_order(5)->first == 3004);
+
+  return 0;
+}
+
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/trie_dna.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/trie_dna.cc
new file mode 100644
index 000000000..28c895680
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/example/trie_dna.cc
@@ -0,0 +1,118 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2007, 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.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  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 trie_dna_example.cpp
+ * An example showing how to use a trie for storing DNA strings.
+ */
+
+/**
+ * This example shows how to use a PATRICIA trie for storing
+ DNA strings. The main point is writing element-access traits
+ for these strings.
+*/
+
+#include <cassert>
+#include <iostream>
+#include <cstdlib>
+#include <ext/pb_ds/assoc_container.hpp>
+#include <ext/pb_ds/trie_policy.hpp>
+
+using namespace std;
+using namespace __gnu_pbds;
+
+// DNA is represented by a string.
+typedef string dna_t;
+
+// Following is an element access traits for a DNA string.
+struct dna_string_e_access_traits
+{
+public:
+  typedef size_t size_type;
+  typedef dna_t key_type;
+  typedef const key_type& const_key_reference;
+  typedef char e_type;
+  typedef string::const_iterator const_iterator;
+
+  enum
+    {
+      // Number of distinct elements. This is 4 = |{'A', 'C', 'G', 'T'}|
+      max_size = 4
+    };
+
+  // Returns a const_iterator to the firstelement of r_key.
+  inline static const_iterator
+  begin(const_key_reference r_key)
+  { return r_key.begin(); }
+
+  // Returns a const_iterator to the after-lastelement of r_key.
+  inline static const_iterator
+  end(const_key_reference r_key)
+  { return r_key.end(); }
+
+  // Maps an element to a position.
+  inline static size_t
+  e_pos(e_type e)
+  {
+    switch(e)
+      {
+      case 'A':
+	return 0;
+      case 'C':
+	return 1;
+      case 'G':
+	return 2;
+      case 'T':
+	return 3;
+      default:
+	std::abort();
+      };
+  }
+};
+
+// A PATRICIA trie with DNA string element-access traits.
+typedef dna_string_e_access_traits traits_type;
+typedef trie<dna_t, string, traits_type> trie_type;
+
+int main()
+{
+  trie_type t;
+
+  // Now map some DNAs to diseases in namespace STD.
+  t["ACCGGTTACTGGTA"] = "gonorrhea";
+  t["CCGTTATCGGTA"] = "syphlis";
+
+  // Check gonorrhea already contracted.
+  assert(t.find("ACCGGTTACTGGTA") != t.end());
+
+  return 0;
+}
+
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/trie_prefix_search.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/trie_prefix_search.cc
new file mode 100644
index 000000000..98b99a76a
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/example/trie_prefix_search.cc
@@ -0,0 +1,110 @@
+// -*- 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.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  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 trie_prefix_search_example.cpp
+ * An example showing how to use a trie for searching
+ *    for words with a given prefix.
+ */
+
+/**
+ * This example shows how to use a PATRICIA trie for searching
+ * for words with a given prefix.
+ */
+
+#include <cassert>
+#include <iostream>
+#include <ext/pb_ds/assoc_container.hpp>
+#include <ext/pb_ds/trie_policy.hpp>
+#include <ext/pb_ds/tag_and_trait.hpp>
+
+using namespace std;
+using namespace __gnu_pbds;
+
+// A PATRICIA trie with a prefix-search node-updator type. Note that
+// since the node updator is trie_prefix_search_node_update, then the
+// container includes its method prefix_range.
+typedef null_mapped_type		mapped_type;
+typedef string_trie_e_access_traits<> 	cmp_fn;
+typedef pat_trie_tag 			tag_type;
+
+typedef trie<string, mapped_type, cmp_fn, tag_type, 
+	     trie_prefix_search_node_update> trie_type;
+
+// The following helper function takes a trie object and r_key, a
+// const reference to a string, and prints all entries whose key
+// includes r_key as a prefix.
+void
+print_prefix_match(const trie_type& t, const string& key)
+{
+  typedef trie_type::const_iterator 		const_iterator;
+  typedef pair<const_iterator, const_iterator> 	pair_type;
+
+  cout << "All keys whose prefix matches \"" << key << "\":" << endl;
+
+  const pair_type match_range = t.prefix_range(key);
+  for (const_iterator it = match_range.first; it != match_range.second; ++it)
+    cout << *it << ' ';
+  cout << endl;
+}
+
+int main()
+{
+  trie_type t;
+
+  // Insert some entries.
+  assert(t.insert("I").second == true);
+  assert(t.insert("wish").second == true);
+  assert(t.insert("that").second == true);
+  assert(t.insert("I").second == false);
+  assert(t.insert("could").second == true);
+  assert(t.insert("ever").second == true);
+  assert(t.insert("see").second == true);
+  assert(t.insert("a").second == true);
+  assert(t.insert("poem").second == true);
+  assert(t.insert("lovely").second == true);
+  assert(t.insert("as").second == true);
+  assert(t.insert("a").second == false);
+  assert(t.insert("trie").second == true);
+
+  // Now search for prefixes.
+  print_prefix_match(t, "");
+  print_prefix_match(t, "a");
+  print_prefix_match(t, "as");
+  print_prefix_match(t, "ad");
+  print_prefix_match(t, "t");
+  print_prefix_match(t, "tr");
+  print_prefix_match(t, "trie");
+  print_prefix_match(t, "zzz");
+
+  return 0;
+}
+
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/trie_split.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/trie_split.cc
new file mode 100644
index 000000000..c08eb9c98
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/example/trie_split.cc
@@ -0,0 +1,85 @@
+// -*- 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.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  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 trie_split_example.cpp
+ * A basic example showing how to split trie-based container objects.
+ */
+
+/**
+ * This example shows how to split trie based containers, i.e., the opposite
+ * of a join operation.
+ */
+
+#include <string>
+#include <cassert>
+#include <ext/pb_ds/assoc_container.hpp>
+
+using namespace std;
+using namespace __gnu_pbds;
+
+int main()
+{
+  // A PATRICIA trie table mapping strings to chars.
+  typedef trie<string, char> map_type;
+
+  // A map_type object.
+  map_type r;
+
+  // Inserts some entries into r.
+  for (int i = 0; i < 100; ++ i)
+    r.insert(make_pair(string(i, 'a'), 'b'));
+
+  // Now split r into a different map_type object.
+
+  // larger_r will hold the larger values following the split.
+  map_type larger_r;
+
+  // Split all elements with key larger than 'a'^1000 into larger_r.
+  // This is exception free.
+  r.split(string(1000, 'a'), larger_r);
+
+  // Since there were no elements with key larger than 'a'^1000, r
+  // should be unchanged.
+  assert(r.size() == 100);
+  assert(r.begin()->first == string(""));
+
+  // Now perform a split which actually changes the content of r.
+
+  // Split all elements with key larger than "aaa" into larger_r.
+  r.split(string("aaa"), larger_r);
+
+  assert(r.size() == 4);
+  assert(larger_r.begin()->first == string("aaaa"));
+
+  return 0;
+}
+
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/regression/associative_containers.cc b/libstdc++-v3/testsuite/ext/pb_ds/regression/associative_containers.cc
new file mode 100644
index 000000000..26dec124d
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/regression/associative_containers.cc
@@ -0,0 +1,165 @@
+// -*- 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.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  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_link_regression_test_1.cpp
+ * A linkage regression test.
+ */
+
+
+#include <ext/pb_ds/assoc_container.hpp>
+#include <iostream>
+#include <cassert>
+
+using namespace std;
+using namespace __gnu_pbds;
+
+/**
+ * The following function performs a sequence of operations on an
+ * associative container object mapping integers to characters.
+ */
+template<typename Cntnr>
+void
+some_op_sequence(Cntnr& r_c)
+{
+  assert(r_c.empty());
+  assert(r_c.size() == 0);
+
+  r_c.insert(make_pair(1, 'a'));
+
+  r_c[2] = 'b';
+
+  assert(!r_c.empty());
+  assert(r_c.size() == 2);
+
+  cout << "Key 1 is mapped to " << r_c[1] << endl;
+  cout << "Key 2 is mapped to " << r_c[2] << endl;
+
+  cout << endl << "All value types in the container:" << endl;
+  for (typename Cntnr::const_iterator it = r_c.begin(); it != r_c.end(); ++it)
+    cout << it->first << " -> " << it->second << endl;
+
+  cout << endl;
+
+  r_c.clear();
+
+  assert(r_c.empty());
+  assert(r_c.size() == 0);
+}
+
+void
+assoc_link_regression_test_0()
+{
+  {
+    // Perform operations on a collision-chaining hash map.
+    cc_hash_table<int, char> c;
+    some_op_sequence(c);
+  }
+
+  {
+    // Perform operations on a general-probing hash map.
+    gp_hash_table<int, char> c;
+    some_op_sequence(c);
+  }
+
+  {
+    // Perform operations on a red-black tree map.
+    tree<int, char> c;
+    some_op_sequence(c);
+  }
+
+  {
+    // Perform operations on a splay tree map.
+    tree<int, char, less<int>, splay_tree_tag> c;
+    some_op_sequence(c);
+  }
+
+  {
+    // Perform operations on a splay tree map.
+    tree<int, char, less<int>, ov_tree_tag> c;
+    some_op_sequence(c);
+  }
+
+  {
+    // Perform operations on a list-update map.
+    list_update<int, char> c;
+    some_op_sequence(c);
+  }
+}
+
+
+void
+assoc_link_regression_test_1()
+{
+  {
+    // Perform operations on a collision-chaining hash map.
+    cc_hash_table<int, char> c;
+    some_op_sequence(c);
+  }
+
+  {
+    // Perform operations on a general-probing hash map.
+    gp_hash_table<int, char> c;
+    some_op_sequence(c);
+  }
+
+  {
+    // Perform operations on a red-black tree map.
+    tree<int, char> c;
+    some_op_sequence(c);
+  }
+
+  {
+    // Perform operations on a splay tree map.
+    tree<int, char, less<int>, splay_tree_tag> c;
+    some_op_sequence(c);
+  }
+
+  {
+    // Perform operations on a splay tree map.
+    tree<int, char, less<int>, ov_tree_tag> c;
+    some_op_sequence(c);
+  }
+
+  {
+    // Perform operations on a list-update map.
+    list_update<int, char> c;
+    some_op_sequence(c);
+  }
+}
+
+int
+main()
+{
+  assoc_link_regression_test_0();
+  assoc_link_regression_test_1();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/regression/hash_data_map_rand.cc b/libstdc++-v3/testsuite/ext/pb_ds/regression/hash_data_map_rand.cc
new file mode 100644
index 000000000..5656a5b29
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/regression/hash_data_map_rand.cc
@@ -0,0 +1,73 @@
+// { dg-require-time "" }
+// This can take long on simulators, timing out the test.
+// { dg-options "-DITERATIONS=5" { target simulator } }
+// { dg-timeout-factor 2.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.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  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 hash_data_map_rand_regression_test.cpp
+ * Contains a random-operation test for maps and sets.
+ */
+
+#define PB_DS_REGRESSION
+
+#include <regression/rand/assoc/rand_regression_test.hpp>
+#include <regression/common_type.hpp>
+
+#ifndef ITERATIONS
+# ifdef _GLIBCXX_DEBUG
+#  define ITERATIONS 100
+# else
+#  define ITERATIONS 5000
+#endif
+#endif
+
+#ifndef KEYS
+# ifdef _GLIBCXX_DEBUG
+#  define KEYS 200
+# else
+#  define KEYS 10000
+# endif
+#endif
+
+int
+main(int argc, char* a_p_argv[])
+{
+  using namespace __gnu_pbds::test;
+  typedef hash_map_tl_t map_tl_t;
+
+  return rand_regression_test(ITERATIONS, KEYS,
+			      "hash_data_map_rand_regression_test",
+			      map_tl_t());
+}
+
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/regression/hash_no_data_map_rand.cc b/libstdc++-v3/testsuite/ext/pb_ds/regression/hash_no_data_map_rand.cc
new file mode 100644
index 000000000..e0530f579
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/regression/hash_no_data_map_rand.cc
@@ -0,0 +1,72 @@
+// { dg-require-time "" }
+// This can take long on simulators, timing out the test.
+// { dg-options "-DITERATIONS=5" { target simulator } }
+// { dg-timeout-factor 2.0 }
+
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2009, 2011 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.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  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 hash_no_data_map_rand_regression_test.cpp
+ * Contains a random-operation test for maps and sets.
+ */
+
+#define PB_DS_REGRESSION
+
+#include <regression/rand/assoc/rand_regression_test.hpp>
+#include <regression/common_type.hpp>
+
+#ifndef ITERATIONS
+# ifdef _GLIBCXX_DEBUG
+#  define ITERATIONS 100
+# else
+#  define ITERATIONS 5000
+#endif
+#endif
+
+#ifndef KEYS
+# ifdef _GLIBCXX_DEBUG
+#  define KEYS 200
+# else
+#  define KEYS 10000
+# endif
+#endif
+
+int
+main(int argc, char* a_p_argv[])
+{
+  using namespace __gnu_pbds::test;
+  typedef hash_set_tl_t map_tl_t;
+
+  return rand_regression_test(ITERATIONS, KEYS,
+			      "hash_no_data_map_rand_regression_test",
+			      map_tl_t());
+}
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/regression/list_update_data_map_rand.cc b/libstdc++-v3/testsuite/ext/pb_ds/regression/list_update_data_map_rand.cc
new file mode 100644
index 000000000..8bd77816c
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/regression/list_update_data_map_rand.cc
@@ -0,0 +1,54 @@
+// { dg-require-time "" }
+
+// -*- 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.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  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 lu_data_map_rand_regression_test.cpp
+ * Contains a random-operation test for maps and sets.
+ */
+
+#define PB_DS_REGRESSION
+
+#include <regression/rand/assoc/rand_regression_test.hpp>
+#include <regression/common_type.hpp>
+
+int
+main(int argc, char* a_p_argv[])
+{
+  using namespace __gnu_pbds::test;
+  typedef lu_map_tl_t map_tl_t;
+
+  return rand_regression_test(50, 10, 
+			      "lu_data_map_rand_regression_test",
+			      map_tl_t());
+}
+
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/regression/list_update_no_data_map_rand.cc b/libstdc++-v3/testsuite/ext/pb_ds/regression/list_update_no_data_map_rand.cc
new file mode 100644
index 000000000..72273a8bc
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/regression/list_update_no_data_map_rand.cc
@@ -0,0 +1,54 @@
+// { dg-require-time "" }
+
+// -*- 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.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  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 lu_no_data_map_rand_regression_test.cpp
+ * Contains a random-operation test for maps and sets.
+ */
+
+#define PB_DS_REGRESSION
+
+#include <regression/rand/assoc/rand_regression_test.hpp>
+#include <regression/common_type.hpp>
+
+int
+main(int argc, char* a_p_argv[])
+{
+  using namespace __gnu_pbds::test;
+  typedef lu_set_tl_t map_tl_t;
+
+  return rand_regression_test(50, 10,
+			      "lu_no_data_map_rand_regression_test",
+			      map_tl_t());
+}
+
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/regression/priority_queue_rand.cc b/libstdc++-v3/testsuite/ext/pb_ds/regression/priority_queue_rand.cc
new file mode 100644
index 000000000..b21f486d6
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/regression/priority_queue_rand.cc
@@ -0,0 +1,61 @@
+// { dg-require-time "" }
+// This can take long on simulators, timing out the test.
+// { dg-options "-DITERATIONS=5" { target simulator } }
+// { dg-timeout-factor 2.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.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  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 priority_queue_rand_regression_test.cpp
+ * Contains a random-operation test for priority queues.
+ */
+
+#define PB_DS_REGRESSION
+
+#include <regression/rand/priority_queue/rand_regression_test.hpp>
+#include <regression/common_type.hpp>
+
+#ifndef ITERATIONS
+#define ITERATIONS 5000
+#endif
+#ifndef KEYS
+#define KEYS 10000
+#endif
+int
+main(int argc, char* a_p_argv[])
+{
+  using namespace __gnu_pbds::test;
+  return rand_regression_test(ITERATIONS, KEYS,
+			      "pq_no_data_map_rand_regression_test", 
+			      pq_tl_t());
+}
+
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/regression/priority_queues.cc b/libstdc++-v3/testsuite/ext/pb_ds/regression/priority_queues.cc
new file mode 100644
index 000000000..713c887a1
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/regression/priority_queues.cc
@@ -0,0 +1,184 @@
+// -*- 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.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  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.
+
+/**
+ * This example shows how to use priority queues. It defines a
+ *    function performing a sequence of operations on
+ *    a generic container. It then calls this function with some containers.
+ */
+
+#include <ext/pb_ds/priority_queue.hpp>
+#include <iostream>
+#include <cassert>
+
+using namespace std;
+using namespace __gnu_pbds;
+using namespace __gnu_pbds;
+
+template<typename Cntnr>
+void
+some_op_sequence(Cntnr& r_c)
+{
+  assert(r_c.empty());
+  assert(r_c.size() == 0);
+
+  for (size_t i = 0; i < 10; ++i)
+    r_c.push(i);
+
+  cout << endl << "All values in the container:" << endl;
+  for (typename Cntnr::const_iterator it = r_c.begin(); it != r_c.end();
+       ++it)
+    cout <<* it << endl;
+
+  assert(!r_c.empty());
+  assert(r_c.size() == 10);
+
+  cout << "Popping all values: " << endl;
+
+  while (!r_c.empty())
+    {
+      cout << r_c.top() << endl;
+
+      r_c.pop();
+    }
+
+  assert(r_c.empty());
+  assert(r_c.size() == 0);
+
+  cout << endl;
+}
+
+void
+priority_queue_link_regression_test_0()
+{
+  {
+    /*
+     *  Perform operations on a pairing-heap queue.
+     */
+    cout << "Pairing heap" << endl;
+    __gnu_pbds::priority_queue<int, less<int>, pairing_heap_tag> c;
+    some_op_sequence(c);
+  }
+
+  {
+    /*
+     *  Perform operations on a binomial-heap queue.
+     */
+    cout << "Binomial heap" << endl;
+    __gnu_pbds::priority_queue<int, less<int>, binomial_heap_tag> c;
+    some_op_sequence(c);
+  }
+
+  {
+    /*
+     *  Perform operations on a binomial-heap queue.
+     */
+    cout << "Redundant-counter binomial heap" << endl;
+    __gnu_pbds::priority_queue<int, less<int>, rc_binomial_heap_tag> c;
+    some_op_sequence(c);
+  }
+
+  {
+    /*
+     *  Perform operations on a binomial-heap queue.
+     */
+    cout << "Binary heap" << endl;
+    __gnu_pbds::priority_queue<int, less<int>, binary_heap_tag> c;
+    some_op_sequence(c);
+  }
+
+  {
+    /*
+     *  Perform operations on a thin-heap queue.
+     */
+    cout << "Thin heap" << endl;
+    __gnu_pbds::priority_queue<int, less<int>, thin_heap_tag> c;
+    some_op_sequence(c);
+  }
+}
+
+
+void
+priority_queue_link_regression_test_1()
+{
+  {
+    /*
+     *  Perform operations on a pairing-heap queue.
+     */
+    cout << "Pairing heap" << endl;
+    __gnu_pbds::priority_queue<int, less<int>, pairing_heap_tag> c;
+    some_op_sequence(c);
+  }
+
+  {
+    /*
+     *  Perform operations on a binomial-heap queue.
+     */
+    cout << "Binomial heap" << endl;
+    __gnu_pbds::priority_queue<int, less<int>, binomial_heap_tag> c;
+    some_op_sequence(c);
+  }
+
+  {
+    /*
+     *  Perform operations on a binomial-heap queue.
+     */
+    cout << "Redundant-counter binomial heap" << endl;
+    __gnu_pbds::priority_queue<int, less<int>, rc_binomial_heap_tag> c;
+    some_op_sequence(c);
+  }
+
+  {
+    /*
+     *  Perform operations on a binomial-heap queue.
+     */
+    cout << "Binary heap" << endl;
+    __gnu_pbds::priority_queue<int, less<int>, binary_heap_tag> c;
+    some_op_sequence(c);
+  }
+
+  {
+    /*
+     *  Perform operations on a thin-heap queue.
+     */
+    cout << "Thin heap" << endl;
+    __gnu_pbds::priority_queue<int, less<int>, thin_heap_tag> c;
+    some_op_sequence(c);
+  }
+}
+
+int
+main()
+{
+  priority_queue_link_regression_test_0();
+  priority_queue_link_regression_test_1();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/regression/tree_data_map_rand.cc b/libstdc++-v3/testsuite/ext/pb_ds/regression/tree_data_map_rand.cc
new file mode 100644
index 000000000..01751e39f
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/regression/tree_data_map_rand.cc
@@ -0,0 +1,72 @@
+// { dg-require-time "" }
+// This can take long on simulators, timing out the test.
+// { dg-options "-DITERATIONS=5" { target simulator } }
+// { dg-timeout-factor 2.0 }
+
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2009, 2011 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.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  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 tree_data_map_rand_regression_test.cpp
+ * Contains a random-operation test for maps and sets.
+ */
+
+#define PB_DS_REGRESSION
+
+#include <regression/rand/assoc/rand_regression_test.hpp>
+#include <regression/common_type.hpp>
+
+#ifndef ITERATIONS
+# ifdef _GLIBCXX_DEBUG
+#  define ITERATIONS 100
+# else
+#  define ITERATIONS 5000
+#endif
+#endif
+
+#ifndef KEYS
+# ifdef _GLIBCXX_DEBUG
+#  define KEYS 200
+# else
+#  define KEYS 10000
+# endif
+#endif
+
+int
+main(int argc, char* a_p_argv[])
+{
+  using namespace __gnu_pbds::test;
+  typedef tree_map_tl_t map_tl_t;
+
+  return rand_regression_test(ITERATIONS, KEYS,
+			      "tree_data_map_rand_regression_test",
+			      map_tl_t());
+}
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/regression/tree_no_data_map_rand.cc b/libstdc++-v3/testsuite/ext/pb_ds/regression/tree_no_data_map_rand.cc
new file mode 100644
index 000000000..c7dadb0d8
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/regression/tree_no_data_map_rand.cc
@@ -0,0 +1,73 @@
+// { dg-require-time "" }
+// This can take long on simulators, timing out the test.
+// { dg-options "-DITERATIONS=5" { target simulator } }
+// { dg-timeout-factor 2.0 }
+
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2009, 2011 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.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  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 tree_no_data_map_rand_regression_test.cpp
+ * Contains a random-operation test for maps and sets.
+ */
+
+#define PB_DS_REGRESSION
+
+#include <regression/rand/assoc/rand_regression_test.hpp>
+#include <regression/common_type.hpp>
+
+
+#ifndef ITERATIONS
+# ifdef _GLIBCXX_DEBUG
+#  define ITERATIONS 100
+# else
+#  define ITERATIONS 5000
+#endif
+#endif
+
+#ifndef KEYS
+# ifdef _GLIBCXX_DEBUG
+#  define KEYS 200
+# else
+#  define KEYS 10000
+# endif
+#endif
+
+int
+main(int argc, char* a_p_argv[])
+{
+  using namespace __gnu_pbds::test;
+  typedef tree_set_tl_t map_tl_t;
+
+  return rand_regression_test(ITERATIONS, KEYS,
+			      "tree_no_data_map_rand_regression_test",
+			      map_tl_t());
+}
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/regression/trie_data_map_rand.cc b/libstdc++-v3/testsuite/ext/pb_ds/regression/trie_data_map_rand.cc
new file mode 100644
index 000000000..8a3902812
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/regression/trie_data_map_rand.cc
@@ -0,0 +1,72 @@
+// { dg-require-time "" }
+// This can take long on simulators, timing out the test.
+// { dg-options "-DITERATIONS=5" { target simulator } }
+// { dg-timeout-factor 2.0 }
+
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2009, 2011 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.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  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 trie_data_map_rand_regression_test.cpp
+ * Contains a random-operation test for maps and sets.
+ */
+
+#define PB_DS_REGRESSION
+
+#include <regression/rand/assoc/rand_regression_test.hpp>
+#include <regression/common_type.hpp>
+
+#ifndef ITERATIONS
+# ifdef _GLIBCXX_DEBUG
+#  define ITERATIONS 100
+# else
+#  define ITERATIONS 5000
+#endif
+#endif
+
+#ifndef KEYS
+# ifdef _GLIBCXX_DEBUG
+#  define KEYS 200
+# else
+#  define KEYS 10000
+# endif
+#endif
+
+int
+main(int argc, char* a_p_argv[])
+{
+  using namespace __gnu_pbds::test;
+  typedef trie_map_tl_t map_tl_t;
+
+  return rand_regression_test(ITERATIONS, KEYS,
+			      "trie_data_map_rand_regression_test",
+			      map_tl_t());
+}
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/regression/trie_no_data_map_rand.cc b/libstdc++-v3/testsuite/ext/pb_ds/regression/trie_no_data_map_rand.cc
new file mode 100644
index 000000000..2414118da
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/regression/trie_no_data_map_rand.cc
@@ -0,0 +1,72 @@
+// { dg-require-time "" }
+// This can take long on simulators, timing out the test.
+// { dg-options "-DITERATIONS=5" { target simulator } }
+// { dg-timeout-factor 2.0 }
+
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2009, 2010, 2011 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.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  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 trie_no_data_map_rand_regression_test.cpp
+ * Contains a random-operation test for maps and sets.
+ */
+
+#define PB_DS_REGRESSION
+
+#include <regression/rand/assoc/rand_regression_test.hpp>
+#include <regression/common_type.hpp>
+
+#ifndef ITERATIONS
+# ifdef _GLIBCXX_DEBUG
+#  define ITERATIONS 100
+# else
+#  define ITERATIONS 5000
+#endif
+#endif
+
+#ifndef KEYS
+# ifdef _GLIBCXX_DEBUG
+#  define KEYS 200
+# else
+#  define KEYS 10000
+# endif
+#endif
+
+int
+main(int argc, char* a_p_argv[])
+{
+  using namespace __gnu_pbds::test;
+  typedef trie_set_tl_t map_tl_t;
+
+  return rand_regression_test(ITERATIONS, KEYS,
+			      "trie_no_data_map_rand_regression_test",
+			      map_tl_t());
+}