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