1 /* Boost.MultiIndex example: complex searches and foreign keys.
2 *
3 * Copyright 2003-2008 Joaquin M Lopez Munoz.
4 * Distributed under the Boost Software License, Version 1.0.
5 * (See accompanying file LICENSE_1_0.txt or copy at
6 * http://www.boost.org/LICENSE_1_0.txt)
7 *
8 * See http://www.boost.org/libs/multi_index for library home page.
9 */
10
11 #if !defined(NDEBUG)
12 #define BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING
13 #define BOOST_MULTI_INDEX_ENABLE_SAFE_MODE
14 #endif
15
16 #include <boost/multi_index_container.hpp>
17 #include <boost/multi_index/member.hpp>
18 #include <boost/multi_index/ordered_index.hpp>
19 #include <boost/tuple/tuple.hpp>
20 #include <iostream>
21 #include <string>
22
23 using boost::multi_index_container;
24 using namespace boost::multi_index;
25
26 /* This small utility that cascades two key extractors will be
27 * used througout the example.
28 */
29
30 template<class KeyExtractor1,class KeyExtractor2>
31 struct key_from_key
32 {
33 public:
34 typedef typename KeyExtractor1::result_type result_type;
35
key_from_keykey_from_key36 key_from_key(
37 const KeyExtractor1& key1_=KeyExtractor1(),
38 const KeyExtractor2& key2_=KeyExtractor2()):
39 key1(key1_),key2(key2_)
40 {}
41
42 template<typename Arg>
operator ()key_from_key43 result_type operator()(Arg& arg)const
44 {
45 return key1(key2(arg));
46 }
47
48 private:
49 KeyExtractor1 key1;
50 KeyExtractor2 key2;
51 };
52
53 /* tags for accessing several indices defined below */
54
55 struct model{};
56 struct manufacturer{};
57 struct price{};
58
59 /* a manufacturer struct just holds the name of the manufacturer */
60
61 struct car_manufacturer
62 {
63 std::string name;
64
car_manufacturercar_manufacturer65 car_manufacturer(const std::string& name_):name(name_){}
66 };
67
68 /* car_model holds the model of car, its price and a pointer to the
69 * manufacturer. The pointer thing eliminates duplication of the same
70 * data among cars of the same manufacturer.
71 */
72
73 struct car_model
74 {
75 std::string model;
76 const car_manufacturer* manufacturer;
77 int price;
78
car_modelcar_model79 car_model(
80 const std::string& model_,const car_manufacturer* manufacturer_,int price_):
81 model(model_),manufacturer(manufacturer_),price(price_)
82 {}
83
operator <<(std::ostream & os,const car_model & c)84 friend std::ostream& operator<<(std::ostream& os,const car_model& c)
85 {
86 os<<c.manufacturer->name<<" "<<c.model<<" $"<<c.price<<std::endl;
87 return os;
88 }
89 };
90
91 /* see Compiler specifics: Use of member_offset for info on
92 * BOOST_MULTI_INDEX_MEMBER
93 */
94
95 /* Car manufacturers are stored in a multi_index_container with one single
96 * index on the name member. This is functionally equivalent to an std::set,
97 * though in this latter case we woud have to define a non-default comparison
98 * predicate (with multi_index_container, member<> does the work for us.)
99 */
100
101 typedef multi_index_container<
102 car_manufacturer,
103 indexed_by<
104 ordered_unique<
105 BOOST_MULTI_INDEX_MEMBER(car_manufacturer,std::string,name)
106 >
107 >
108 > car_manufacturer_table;
109
110 /* Define a multi_index_container of car_models with following indices:
111 * - a unique index sorted by car_model::model,
112 * - a non-unique index sorted by car_model::manufacturer; note the
113 * non-standard manufacturer_extractor used.
114 * - a non-unique index sorted by car_model::price.
115 */
116
117 typedef multi_index_container<
118 car_model,
119 indexed_by<
120 ordered_unique<
121 tag<model>,BOOST_MULTI_INDEX_MEMBER(car_model,std::string,model)
122 >,
123 ordered_non_unique<
124 tag<manufacturer>,
125 key_from_key<
126 BOOST_MULTI_INDEX_MEMBER(car_manufacturer,const std::string,name),
127 BOOST_MULTI_INDEX_MEMBER(
128 car_model,const car_manufacturer *,manufacturer)
129 >
130 >,
131 ordered_non_unique<
132 tag<price>,BOOST_MULTI_INDEX_MEMBER(car_model,int,price)
133 >
134 >
135 > car_table;
136
137 /* We call a *view* to a multi_index_container storing pointers instead of
138 * actual objects. These views are used in the complex search performed
139 * in the program. Resorting to multi_index of pointers eliminates
140 * unnecessary copying of objects, and provides us with an opportunity
141 * to show how BOOST_MULTI_INDEX_MEMBER can be used with pointer
142 * type elements.
143 * car_table_price_view indexes (pointers to) car_models by price.
144 */
145
146 typedef multi_index_container<
147 const car_model*,
148 indexed_by<
149 ordered_non_unique<BOOST_MULTI_INDEX_MEMBER(car_model,const int,price)>
150 >
151 > car_table_price_view;
152
153 /* car_table_manufacturer_view indexes (pointers to) car_models by
154 * manufacturer
155 */
156
157 typedef multi_index_container<
158 const car_model*,
159 indexed_by<
160 ordered_non_unique<
161 key_from_key<
162 BOOST_MULTI_INDEX_MEMBER(car_manufacturer,const std::string,name),
163 BOOST_MULTI_INDEX_MEMBER(
164 car_model,const car_manufacturer * const,manufacturer)
165 >
166 >
167 >
168 > car_table_manufacturer_view;
169
main()170 int main()
171 {
172 car_manufacturer_table cmt;
173
174 /* Fill the car_manufacturer table and keep pointers to the
175 * elements inserted.
176 */
177
178 const car_manufacturer * cadillac=
179 &*(cmt.insert(car_manufacturer("Cadillac")).first);
180 const car_manufacturer * ford =
181 &*(cmt.insert(car_manufacturer("Ford")).first);
182 const car_manufacturer * bmw =
183 &*(cmt.insert(car_manufacturer("BMW")).first);
184 const car_manufacturer * audi =
185 &*(cmt.insert(car_manufacturer("Audi")).first);
186
187 car_table ct;
188
189 /* Fill the car_model_table. We use the previously initialized
190 * pointers to the elements of cmt.
191 */
192
193 ct.insert(car_model("XLR",cadillac,76200));
194 ct.insert(car_model("SRX",cadillac,38690));
195 ct.insert(car_model("CTS",cadillac,30695));
196 ct.insert(car_model("Escalade",cadillac,54770));
197 ct.insert(car_model("ESV",cadillac,57195));
198 ct.insert(car_model("EXT",cadillac,52045));
199 ct.insert(car_model("Deville",cadillac,45195));
200 ct.insert(car_model("Seville",cadillac,46330));
201
202 ct.insert(car_model("ZX2",ford,15355));
203 ct.insert(car_model("Thunderbird",ford,43995));
204 ct.insert(car_model("Windstar",ford,35510));
205 ct.insert(car_model("Focus",ford,19630));
206 ct.insert(car_model("Taurus",ford,24290));
207 ct.insert(car_model("Mustang",ford,39900));
208 ct.insert(car_model("Crown Victoria",ford,30370));
209
210 ct.insert(car_model("325i",bmw,27800));
211 ct.insert(car_model("545i",bmw,54300));
212 ct.insert(car_model("745i",bmw,68500));
213 ct.insert(car_model("M3 coupe",bmw,46500));
214 ct.insert(car_model("Z4 roadster 3.0i",bmw,40250));
215 ct.insert(car_model("X5 4.4i",bmw,49950));
216
217 ct.insert(car_model("A4 1.8T",audi,25940));
218 ct.insert(car_model("TT Coupe",audi,33940));
219 ct.insert(car_model("A6 3.0",audi,36640));
220 ct.insert(car_model("Allroad quattro 2.7T",audi,40640));
221 ct.insert(car_model("A8 L",audi,69190));
222
223 std::cout<<"enter a car manufacturer"<<std::endl;
224 std::string cm;
225 std::getline(std::cin,cm);
226
227 /* check for manufacturer */
228
229 car_manufacturer_table::iterator icm=cmt.find(cm);
230
231 if(icm==cmt.end()){
232 std::cout<<"no such manufacturer in the table"<<std::endl;
233 return 0;
234 }
235
236 std::cout<<"enter a minimum price"<<std::endl;
237 int min_price;
238 std::cin>>min_price;
239 std::cout<<"enter a maximum price"<<std::endl;
240 int max_price;
241 std::cin>>max_price;
242
243 {
244 /* method 1 */
245
246 /* find all the cars for the manufacturer given */
247
248 boost::multi_index::index<car_table,manufacturer>::type::iterator ic0,ic1;
249 boost::tuples::tie(ic0,ic1)=get<manufacturer>(ct).equal_range(cm);
250
251 /* construct a view (indexed by price) with these */
252
253 car_table_price_view ctpv;
254 while(ic0!=ic1){
255 ctpv.insert(&*ic0);
256 ++ic0;
257 }
258
259 /* select the cars in the range given */
260
261 car_table_price_view::iterator ictpv0=ctpv.lower_bound(min_price);
262 car_table_price_view::iterator ictpv1=ctpv.upper_bound(max_price);
263 if(ictpv0==ictpv1){
264 std::cout<<"no cars in the range given"<<std::endl;
265 return 0;
266 }
267
268 /* list them */
269
270 std::cout<<"listing by method 1"<<std::endl;
271 while(ictpv0!=ictpv1){
272 std::cout<<**ictpv0;
273 ++ictpv0;
274 }
275 std::cout<<std::endl;
276 }
277
278 {
279 /* method 2 will give the same results */
280
281 /* find the cars in the range given */
282
283 boost::multi_index::index<car_table,price>::type::iterator ic0,ic1;
284 ic0=get<price>(ct).lower_bound(min_price);
285 ic1=get<price>(ct).upper_bound(max_price);
286
287 /* construct a view with these */
288
289 car_table_manufacturer_view ctmv;
290 while(ic0!=ic1){
291 ctmv.insert(&*ic0);
292 ++ic0;
293 }
294
295 /* select the cars with given manufacturer */
296
297 car_table_manufacturer_view::iterator ictmv0,ictmv1;
298 boost::tuples::tie(ictmv0,ictmv1)=ctmv.equal_range(cm);
299 if(ictmv0==ictmv1){
300 std::cout<<"no cars in the range given"<<std::endl;
301 return 0;
302 }
303
304 /* list them */
305
306 std::cout<<"listing by method 2"<<std::endl;
307 while(ictmv0!=ictmv1){
308 std::cout<<**ictmv0;
309 ++ictmv0;
310 }
311 std::cout<<std::endl;
312 }
313
314 return 0;
315 }
316