1// -*- C++ -*- 2 3// Copyright (C) 2005, 2006, 2009 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 3, 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 COPYING3. If not see 18// <http://www.gnu.org/licenses/>. 19 20 21// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 22 23// Permission to use, copy, modify, sell, and distribute this software 24// is hereby granted without fee, provided that the above copyright 25// notice appears in all copies, and that both that copyright notice 26// and this permission notice appear in supporting documentation. None 27// of the above authors, nor IBM Haifa Research Laboratories, make any 28// representation about the suitability of this software for any 29// purpose. It is provided "as is" without express or implied 30// warranty. 31 32/** 33 * @file erase_if_example.cpp 34 * A basic example showing how to use erase_if. 35 */ 36 37/** 38 * The following example shows how to use a conditional-erase 39 * method of associative containers to erase some of their entries. 40 */ 41 42#include <iostream> 43#include <cassert> 44#include <ext/pb_ds/assoc_container.hpp> 45 46using namespace std; 47using namespace __gnu_pbds; 48 49// The following functor takes a map's value-type object and returns 50// whether its key is between two numbers. 51struct between : public unary_function<pair<const int, char>, bool> 52{ 53 // Constructor taking two numbers determining a range. 54 between(int b, int e) : m_b(b), m_e(e) 55 { assert(m_b < m_e); } 56 57 // Operator determining whether a value-type object's key is within 58 // the range. 59 inline bool 60 operator()(const pair<const int, char>& r_val) 61 { return r_val.first >= m_b&& r_val.first < m_e; } 62 63private: 64 const int m_b; 65 const int m_e; 66}; 67 68/** 69 * The following function performs a sequence of operations on an 70 * associative container object mapping integers to characters. Specifically 71 * it inserts 100 values and then uses a conditional-erase method to erase 72 * the values whose key is between 10 and 90. 73 */ 74template<class Cntnr> 75void 76some_op_sequence(Cntnr r_c) 77{ 78 assert(r_c.empty()); 79 assert(r_c.size() == 0); 80 81 for (int i = 0; i < 100; ++i) 82 r_c.insert(make_pair(i, static_cast<char>(i))); 83 assert(r_c.size() == 100); 84 85 // Erase all values whose key is between 10 (inclusive) and 90 86 // (non-inclusive). 87 r_c.erase_if(between(10 , 90)); 88 89 assert(!r_c.empty()); 90 assert(r_c.size() == 20); 91} 92 93int main() 94{ 95 // Perform operations on a list-update set. 96 some_op_sequence(list_update<int, char>()); 97 98 // Perform operations on a collision-chaining hash set. 99 some_op_sequence(cc_hash_table<int, char>()); 100 101 // Perform operations on a general-probing hash set. 102 some_op_sequence(gp_hash_table<int, char>()); 103 104 // Perform operations on a red-black tree set. 105 some_op_sequence(tree<int, char>()); 106 107 // Perform operations on a splay tree set. 108 some_op_sequence(tree< 109 int, 110 char, 111 less<int>, 112 splay_tree_tag>()); 113 114 // Perform operations on a splay tree set. 115 some_op_sequence(tree< 116 int, 117 char, 118 less<int>, 119 ov_tree_tag>()); 120 121 return 0; 122} 123