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 basic_multimap_example.cpp 34 * A basic example showing how to use multimaps. 35 */ 36 37/** 38 * This example shows how to use "multimaps" in the context of a simple 39 * bank account application. Each customer holds a bank account 40 * (or more than one) which holds some balance. 41 */ 42 43#include <iostream> 44#include <string> 45#include <cassert> 46#include <ext/pb_ds/assoc_container.hpp> 47 48using namespace std; 49using namespace __gnu_pbds; 50 51// A simple hash functor. 52// hash could serve instead of this functor, but it is not yet 53// standard everywhere. 54struct string_hash : public unary_function<string, size_t> 55{ 56 inline size_t 57 operator()(const string& r_s) const 58 { 59 size_t ret = 0; 60 string::const_iterator b = r_s.begin(); 61 string::const_iterator e = r_s.end(); 62 while (b != e) 63 { 64 ret *= 5; 65 ret += static_cast<size_t>(*(b++)); 66 } 67 return ret; 68 } 69}; 70 71int main() 72{ 73 // Each customer is identified by a string. 74 typedef string customer; 75 76 // Each account is identified by an unsigned long. 77 typedef unsigned long account_id; 78 79 // The balance in the account is a floating point. 80 typedef float balance_t; 81 82 /* 83 * This is the data structure type used for storing information 84 * about accounts. In this case the primary key is the customer, 85 * and the secondary key is the account id. 86 * 87 * A hash-based container maps each customer to a list-based 88 * container that maps each account to the balance it holds. 89 * 90 * Note that we could use any combination of primary and secondary 91 * associative-containers. In this case we choose a hash-based 92 * container for the primary keys, since we do not need to store 93 * customers in a sorted order; we choos a list-based container for 94 * the secondary keys, since we expect that the average number of 95 * accounts per customer will be small. 96 */ 97 typedef 98 cc_hash_table< 99 customer, 100 list_update< 101 account_id, 102 balance_t>, 103 string_hash> 104 accounts_t; 105 106 // This object will hold all information. 107 accounts_t acc; 108 109 // Customer "a" opens empty account 12. 110 acc["a"][12] = 0; 111 112 // Customer "a" deposits 45 into account 12. 113 acc["a"][12] += 45; 114 115 // Customer "b" opens account 13 with balance 12.3. 116 acc["b"][13] = 12.3; 117 118 // Customer "c" opens empty account 14. 119 acc["c"][14] = 0; 120 121 // Customer "a" opens account 160 with balance 142. 122 // Note that "a" already holds account 12. 123 acc["a"][160] = 142; 124 125 // Verify the number of accounts that "a" holds. 126 accounts_t::const_point_iterator it = acc.find("a"); 127 assert(it != acc.end()); 128 assert(it->second.size() == 2); 129 130 // The begining of the month has arrived. We need to give a 3% 131 // interest to all accounts with a positive balance. 132 133 // First we loop over all customers. 134 accounts_t::iterator cust_it; 135 for (cust_it = acc.begin(); cust_it != acc.end(); ++cust_it) 136 { 137 // For each customer, we loop over the customer's accounts. 138 accounts_t::mapped_type::iterator it; 139 for (it = cust_it->second.begin(); it != cust_it->second.end(); ++it) 140 if (it->second > 0) 141 it->second *= 1.03; 142 } 143 144 // Customer "a" closes all accounts. 145 acc.erase("a"); 146 147 // The bank now has only 2 customers. 148 assert(acc.size() == 2); 149 150 return 0; 151} 152 153