5 Copyright (c) 2006-2007 Matias Capeletto
7 Distributed under the Boost Software License, Version 1.0.
8 (See accompanying file LICENSE_1_0.txt or copy at
9 http://www.boost.org/LICENSE_1_0.txt)
13 [/ QuickBook Document version 1.4 ]
17 [section The long path from Code Project to Boost]
20 [[2002 - bimap at Code Project]
22 Joaquin Lopez Muñoz posted his first
23 [@http://www.codeproject.com/vcpp/stl/bimap.asp#test_suite bimap library]
24 in 2002. Tons of users have been using it. He then
25 [@http://aspn.activestate.com/ASPN/Mail/Message/boost/1404881 asked the
26 list for interest] in his library in 2003. Luckily, there was a lot of
27 interest and Joaquin started to boostify the code. At some point all the
28 developers seemed to agree that, rather than a bidirectional map, it would
29 be better to work on an N-indexed set that contained Joaquin's library as a
33 [[2003 - multiindex_set]
35 The library grew enormously and was ready for a formal review in
36 2003. At this point, the container was a lot more powerful, but
37 everything comes with a price and this new beast lacked the simplicity
38 of the original bimap.
43 In 2004, the formal review ended well for the new multi-indexed
44 container. This Swiss army knife introduced several new features, such
45 as non-unique indexes, hashed indices and sequenced indices. In the list
46 of improvements to the library, it was mentioned that a bidirectional
47 map should be coded in top of this container.
50 [[2005 - multi_index_container]
52 Once in Boost, the library switched to the now familiar name
53 "Boost.MultiIndex". Late in 2004, it formally became a member of Boost.
54 Joaquin continued to enhance the library and added new features such as
55 composite keys and random-access indices.
58 [[2006 - Multi Index Specialized Containers SoC project]
60 In 2006, during the formal review of Boost.Property_tree, the need
61 for a bidirectional map container built on top of Boost.MultiIndex arose
62 again. Boost entered the Google SoC 2006 as a mentor organization at the
63 same time. Joaquin put himself forward as a mentor. He proposed to build
64 not only a bidirectional map, but a myriad multi-indexed specialized
65 containers. Matias Capeletto presented an application to code Boost.Misc
66 for the SoC and was elected, along with nine other students. Matias's and
67 Joaquin's SoC project ends with a working implementation of the bimap
68 library that was presented in an informal review. By the end of the year
69 the library was queued for a formal review.
74 The formal review took place at the beginning of the year and Boost.Bimap
75 was accepted in Boost.
81 [section MultiIndex and Bimap]
83 This is the conversation thread that began during Boost.PropertyTree formal
84 review process. The review was very interesting and very deep topics were
85 addressed. It is quite interesting and it is now part of this library history.
91 The biggest virtue of property_tree is easy to use interface.
92 If we try to make generic tree of it, it will be compromised.
97 IMO the same result (as library presents) could be achieved
98 just by using multi_index.
103 Could you elaborate more on that? I considered use of
104 multi_index to implement indexing for properties, but it only affected the
105 implementation part of library, not interface, and because I already had a
106 working, exception safe solution, I didn't see the reason to dump it and add
107 another dependency on another library.
112 I mean why do I need this half baked property_tree as another
113 data structure? Property tree supports nothing in itself. It's just a data
114 structure. You have parsers that produce property tree out of different sources.
115 But you mat as well produce maps or something else. Here for example All that
116 I need to do to "implement" similar functionality as your property tree:
120 // Data structure itself
121 template<typename ValueType,typename KeyType>
123 template<typename ValueType,typename KeyType>
125 typedef std::pair<KeyType,Node<ValueType,KeyType> > mi_value;
126 typedef multi_index_container<mi_value, indexed_by<...> > type;
128 template<typename ValueType,typename KeyType>
131 ptree_gen<ValueType,KeyType>::type children;
133 // serialization support
134 template<class Archive,typename ValueType,typename KeyType>
135 void serialize(Archive & ar, Node<ValueType,KeyType>& n,
136 const unsigned int version)
141 // some access methods
142 template<typename ValueType,typename KeyType>
144 get( string const& keys, ptree_gen<ValueType,KeyType>::type const& src )
146 std::pait<string,string> sk = split( keys, "." );
147 Node const& N = src.find( sk.first );
148 return sk.second.empty() ? N.v : get( sk.second, N.children );
157 ptree_gen<string,string>::type PT;
158 boost::archive::text_iarchive ia( std::ifstream ifs("filename") );
160 string value = get( "a.b.c.d", PT );
164 Now tell me how property_tree interface is easier? And what is the value in
165 50k of Code you need to implement this data structure.
170 Seriously Gennadiy, do you really see newbies writing
171 the code you just did?
176 What you just implemented is stripped down, bare bones version
177 of property_tree that, among other things, does not allow you to produce human
178 editable XML files. Now add more interface (aka get functions), add more
179 archives to serialization lib, add customization, add transparent
180 translation from strings to arbitrary types and vice versa. Spend some weeks
181 trying to get all the corner cases right, and then some more weeks trying to
182 smooth rough edges in the interface. Then write tests. Write docs. At the
183 end, I believe you will not get much less code than there is in the library
184 already. Maybe you get some savings by using multi_index instead of manual
188 The reason why ptree does not use multi index is because implementation
189 existed long before I considered submitting to boost, probably before even I
190 knew of multi index existence. It was working well. Later, when I was
191 improving it during pre-review process, I seriously considered using
192 multi-index. But I decided it is not worth throwing everything out.
195 Although ptree has large interface with many functions modifying state of
196 the tree, it uses "single point of change" approach. Every insert eventually
197 goes through one function, which takes care of exception safety and keeping
198 index in sync with data. The same applies to erase. This function has 9
199 lines of code in case of insert, and (by coincidence) also 9 in case of
200 erase. By using multi index these functions would obviously be simplified,
201 maybe to 4 lines each. Net gain: 10 lines of code (out of several hundred in
202 ptree_implementation.hpp).
205 I'm aware that there are performance gains to be reaped as well, but at that
206 time I was rather focusing on getting the interface right.
211 That's perfectly reasonable, but (through no fault of yours)
212 it misses the point I was trying to make. I guess I should have said,
213 "...that demonstrates it to be the best implementation."
216 All I'm saying is that the extent to which a Boost library
217 implementation should leverage other Boost libraries is not a question
218 that can always be decided based on following simple guidelines, and
219 that if this library is accepted, it's worth revisiting your decision.
224 I think it is important to focus on the interface in
225 the review, but I also see several benefits of an implementation that builds on
228 [:['- fewer bugs like the one Joaquin found]]
229 [:['- better space efficiency]]
230 [:['- exception-safety guarantees are immediately full-filled (I haven't
231 looked, but I suspect that there are several bugs in this area)]]
235 Multi_index supports everything a bimap would, but its
236 interface is more cumbersome. I for one won't use a W3DOM-like library
237 if we get one, but I would happily use property_tree. I've also only
238 used multi_index once, and that was to use it as a bidirectional map.
239 Property_tree covers other areas as well as being a potential subset of
240 an XML library, but I still hold there is value in such a subset.
245 I haven't used program_options yet. But if I understand
246 correctly both libraries seem to support storing and accessing data with
247 strings that might describe some kind of hierarchy. This seems to be the core
248 idea of both libraries - is this correct?
251 Then it wouldn't matter much what container is used. However a generic tree
252 which can store data hierarchically probably makes most sense. If I
253 understand correctly both libraries could make use of such a class?
258 I think generic tree container is material for another library.
259 Whether property_tree should be based on it or not is a matter of internal
260 implementation, and generally of little interest to users. The biggest value
261 of property_tree is in its easy to use interface, that should not be
262 compromised, if at all possible. I have been already reassured in this view
263 by quite many people who took their time to review the library.
268 I was trying to see the big picture: I rather prefer a C++
269 standard based on a few well-known concepts like containers, iterators,
270 algorithms etc. instead of having a C++ standard with hundreds of components
271 which are tailored for specific needs, collaborate with only a handful of other
272 components and think they provide an easy-to-use interface while all the
273 easy-to-use interfaces make the whole standard less easy-to-use.
276 That said I have used your property tree library myself to read and write a
277 configuration file. It was indeed very easy to use. However it would have
278 been even easier if it was something I had known before like eg. an
279 iterator. For now I will definitely use your property tree library but would
280 appreciate if existing concepts were reused many C++ developers are familiar
281 with. My opinion is that your library should be a part of Boost but should
282 be more generalized in the future.
287 Well, I think we need both. Boost.MultiIndex is a great
288 library and can do all kinds of wonderful things. But I would still like to see
289 a bidirectional map (boost::bimap) written as a wrapper around it to
290 get an easy and specialized interface.
295 Bimap is available in libs/multi-index/examples/bimap.cpp.
300 Right, but the real value comes when somebody designs a nice
301 STL-like interface and write docs etc, at least that was my point.
306 IMO Thorsten is exactly right. This is precisely the sort of
307 thing that could be added to the library as part of its ongoing maintenance
308 and development (without review, of course).
313 Thorsten, we have talked about this privately in the past,
314 but I feel like bringing it to the list in the hope of getting the attention
315 of potential contributors:
318 There are some data structures buildable with B.MI which are regarded as
319 particularly useful or common, like for instance the bidirectional map or
320 bimap. A lean and mean implementation is provided in the aforementioned
321 example, but certainly a much carefully crafted interface can be provided
322 keeping B.MI as the implementation core: operator\[\], selection of
323 1-1/1-N/N-1/N-N variants, hashing/ordering, etc.
326 I'm afraid I don't have the time to pursue this, as the current roadmap for
327 core features of B.MI is taking all the spare time I can dedicate to the
328 library. For this reason, I would love to see some volunteer jumping in who
329 can develop this and other singular containers using B.MI (a cache container
330 comes to mind) and then propose the results here either as a stand alone
331 library of as part of B.MI --I'd prefer the former so as to keep the size
335 If there's such a volunteer I can provide her with some help/mentoring. I also
336 wonder whether this is a task suitable to be proposed for Google Summer of
342 I think it would be good for SOC. All the really hard things
343 are taken care of by B.MI, and so it seems reasonable for a student to be able
344 to fill in the details.
354 Please write a proposal!
362 [blurb *Specialized containers with Boost.MultiIndex*
366 Boost.MultiIndex allows the construction of complex data structures involving
367 two or more indexing mechanisms on the same set of elements. Out of the
368 unlimited range of possible data structures specifiable within
369 Boost.MultiIndex, some particular configurations arise recurrently:
371 *a.* A bidirectional map or bimap is a container of elements of type pair<T,Q>
372 where fast look up is provided both for the T and the Q field,
373 in contrast with a regular STL map which only allows for fast look up on T.
375 *b.* An MRU (most recently used) list keeps the n last referenced elements:
376 when a new item is inserted and the list has reached its maximum length, the
377 oldest element is erased, whereas if an insertion is tried of a preexistence
378 element, this gets promoted to the first position. MRU lists can be used to
379 implement dynamic caches and the kind of behavior exhibited by programs
380 featuring a "Recent files" menu command, for instance.
382 Although Boost.MultiIndex provides the mechanisms to build these common structures,
383 the resulting interface can be cumbersome and too general in comparison with
384 specialized containers focusing on such particular structures.
388 To write a library of specialized containers like the ones described above, using
389 Boost.MultiIndex as the implementation core. Besides bimap and MRU list, the student
390 can also propose other specialized containers of interest in the community. It is
391 expected that the library meets the standards of quality required by Boost for an
392 eventual inclusion in this project, which implies a strong emphasis on interface
393 design, documentation and unit testing; the mentor will be guiding the student
394 through the complete cycle from specification and requirements gathering to
395 documentation and actual coding. The final result of the project must then contain:
397 *a.* Source code following
398 [@http://boost.org/more/lib_guide.htm#Guidelines Boost programming guidelines].
400 *b.* User documentation. Requirements on the format are loose, though the
401 [@http://www.boost.org/tools/quickbook/ QuickBook] format is
402 gaining acceptance within Boost.
404 *c.* Complete set of unit tests powered by
405 [@http://www.boost.org/boost-build2/ Boost Build System V2].
409 *a.* Intermediate-to-high level in C++, with emphasis in generic programming
412 *b.* Knowledge of the STL framework and design principles. Of course, knowledge
413 of Boost in general and Boost.MultiIndex in particular is a big plus.
415 *c.* Acquaintance with at least two different C++ programming environments.
417 *d.* Some fluency in the English language; subsequent reviews of the documentation
418 can help smooth rough edges here, though.
420 *e.* A mathematical inclination and previous exposure to a formal Algorithms course
421 would help very much.
423 *f.* A craving for extreme quality work.
425 *Benefits for the student*
427 The student taking on this project will have the opportunity to learn the complete
428 process of software production inside a highly regarded C++ open source institution,
429 and even see her work included in Boost eventually. The completion of the project
430 involves non-trivial problems in C++ interface design and so-called modern C++
431 programming, high quality user documentation and unit testing. The student will
432 also learn, perhaps to her surprise, that most of the time will be spent gathering
433 and trying ideas and, in general, thinking, rather than writing actual code.
438 I am planning to submit an application to SoC. I will love to make real
439 the specialized containers you mention and try to include some useful others.
443 And then... after long hours of coding (and fun) this library saw the light.
446 [:__BOOST_BIMAP_LOGO__]