libstdc++-v3/testsuite/ext/pb_ds/example/erase_if.cc

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the terms
   7 // of the GNU General Public License as published by the Free Software
   8 // Foundation; either version 2, or (at your option) any later
   9 // version.
  10
  11 // This library is distributed in the hope that it will be useful, but
  12 // WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 // General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License
  17 // along with this library; see the file COPYING.  If not, write to
  18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
  19 // MA 02111-1307, USA.
  20
  21 // As a special exception, you may use this file as part of a free
  22 // software library without restriction.  Specifically, if other files
  23 // instantiate templates or use macros or inline functions from this
  24 // file, or you compile this file and link it with other files to
  25 // produce an executable, this file does not by itself cause the
  26 // resulting executable to be covered by the GNU General Public
  27 // License.  This exception does not however invalidate any other
  28 // reasons why the executable file might be covered by the GNU General
  29 // Public License.
  30
  31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  32
  33 // Permission to use, copy, modify, sell, and distribute this software
  34 // is hereby granted without fee, provided that the above copyright
  35 // notice appears in all copies, and that both that copyright notice
  36 // and this permission notice appear in supporting documentation. None
  37 // of the above authors, nor IBM Haifa Research Laboratories, make any
  38 // representation about the suitability of this software for any
  39 // purpose. It is provided "as is" without express or implied
  40 // warranty.
  41
  42 /**
  43  * @file erase_if_example.cpp
  44  * A basic example showing how to use erase_if.
  45  */
  46
  47 /**
  48  * The following example shows how to use a conditional-erase
  49  * method of associative containers to erase some of their entries.
  50  */
  51
  52 #include <iostream>
  53 #include <cassert>
  54 #include <ext/pb_ds/assoc_container.hpp>
  55
  56 using namespace std;
  57 using namespace __gnu_pbds;
  58
  59 // The following functor takes a map's value-type object and returns
  60 // whether its key is between two numbers.
  61 struct between : public unary_function<pair<const int, char>, bool>
  62 {
  63   // Constructor taking two numbers determining a range.
  64   between(int b, int e) : m_b(b), m_e(e)
  65   { assert(m_b < m_e); }
  66
  67   // Operator determining whether a value-type object's key is within
  68   // the range.
  69   inline bool
  70   operator()(const pair<const int, char>& r_val)
  71   { return r_val.first >= m_b&&  r_val.first < m_e; }
  72
  73 private:
  74   const int m_b;
  75   const int m_e;
  76 };
  77
  78 /**
  79  * The following function performs a sequence of operations on an
  80  * associative container object mapping integers to characters. Specifically
  81  * it inserts 100 values and then uses a conditional-erase method to erase
  82  * the values whose key is between 10 and 90.
  83  */
  84 template<class Cntnr>
  85 void
  86 some_op_sequence(Cntnr r_c)
  87 {
  88   assert(r_c.empty());
  89   assert(r_c.size() == 0);
  90
  91   for (int i = 0; i < 100; ++i)
  92     r_c.insert(make_pair(i, static_cast<char>(i)));
  93   assert(r_c.size() == 100);
  94
  95   // Erase all values whose key is between 10 (inclusive) and 90
  96   // (non-inclusive).
  97   r_c.erase_if(between(10 , 90));
  98
  99   assert(!r_c.empty());
 100   assert(r_c.size() == 20);
 101 }
 102
 103 int main()
 104 {
 105   // Perform operations on a list-update set.
 106   some_op_sequence(list_update<int, char>());
 107
 108   // Perform operations on a collision-chaining hash set.
 109   some_op_sequence(cc_hash_table<int, char>());
 110
 111   // Perform operations on a general-probing hash set.
 112   some_op_sequence(gp_hash_table<int, char>());
 113
 114   // Perform operations on a red-black tree set.
 115   some_op_sequence(tree<int, char>());
 116
 117   // Perform operations on a splay tree set.
 118   some_op_sequence(tree<
 119                    int,
 120                    char,
 121                    less<int>,
 122                    splay_tree_tag>());
 123
 124   // Perform operations on a splay tree set.
 125   some_op_sequence(tree<
 126                    int,
 127                    char,
 128                    less<int>,
 129                    ov_tree_tag>());
 130
 131   return 0;
 132 }