| [/license |
| |
| Boost.Bimap |
| |
| Copyright (c) 2006-2007 Matias Capeletto |
| |
| Distributed under the Boost Software License, Version 1.0. |
| (See accompanying file LICENSE_1_0.txt or copy at |
| http://www.boost.org/LICENSE_1_0.txt) |
| |
| ] |
| |
| [/ QuickBook Document version 1.4 ] |
| |
| [section History] |
| |
| [section The long path from Code Project to Boost] |
| |
| [variablelist |
| [[2002 - bimap at Code Project] |
| [ |
| Joaquin Lopez Muñoz posted his first |
| [@http://www.codeproject.com/vcpp/stl/bimap.asp#test_suite bimap library] |
| in 2002. Tons of users have been using it. He then |
| [@http://aspn.activestate.com/ASPN/Mail/Message/boost/1404881 asked the |
| list for interest] in his library in 2003. Luckily, there was a lot of |
| interest and Joaquin started to boostify the code. At some point all the |
| developers seemed to agree that, rather than a bidirectional map, it would |
| be better to work on an N-indexed set that contained Joaquin's library as a |
| particular case. |
| ]] |
| |
| [[2003 - multiindex_set] |
| [ |
| The library grew enormously and was ready for a formal review in |
| 2003. At this point, the container was a lot more powerful, but |
| everything comes with a price and this new beast lacked the simplicity |
| of the original bimap. |
| ]] |
| |
| [[2004 - indexed_set] |
| [ |
| In 2004, the formal review ended well for the new multi-indexed |
| container. This Swiss army knife introduced several new features, such |
| as non-unique indexes, hashed indices and sequenced indices. In the list |
| of improvements to the library, it was mentioned that a bidirectional |
| map should be coded in top of this container. |
| ]] |
| |
| [[2005 - multi_index_container] |
| [ |
| Once in Boost, the library switched to the now familiar name |
| "Boost.MultiIndex". Late in 2004, it formally became a member of Boost. |
| Joaquin continued to enchance the library and added new features such as |
| composite keys and random-access indices. |
| ]] |
| |
| [[2006 - Multi Index Specialized Containers SoC project] |
| [ |
| In 2006, during the formal review of Boost.Property_tree, the need |
| for a bidirectional map container built on top of Boost.MultiIndex arose |
| again. Boost entered the Google SoC 2006 as a mentor organization at the |
| same time. Joaquin put himself forward as a mentor. He proposed to build |
| not only a bidirectional map, but a myriad multi-indexed specialized |
| containers. Matias Capeletto presented an application to code Boost.Misc |
| for the SoC and was elected, along with nine other students. Matias's and |
| Joaquin's SoC project ends with a working implementation of the bimap |
| library that was presented in an informal review. By the end of the year |
| the library was queued for a formal review. |
| ]] |
| |
| [[2007 - Boost.Bimap] |
| [ |
| The formal review took place at the beggining of the year and Boost.Bimap |
| was accepted in Boost. |
| ]] |
| ] |
| |
| [endsect] |
| |
| [section MultiIndex and Bimap] |
| |
| This is the conversation thread that began during Boost.PropertyTree formal |
| review process. The review was very interesting and very deep topics were |
| addressed. It is quite interesting and it is now part of this library history. |
| Enjoy! |
| |
| |
| [*Marcin] |
| [:[' |
| The biggest virtue of property_tree is easy to use interface. |
| If we try to make generic tree of it, it will be compromised. |
| ]] |
| |
| [*Gennadiy] |
| [:[' |
| IMO the same result (as library presents) could be achieved |
| just by using multi_index. |
| ]] |
| |
| [*Marcin] |
| [:[' |
| Could you elaborate more on that? I considered use of |
| multi_index to implement indexing for properties, but it only affected the |
| implementation part of library, not interface, and because I already had a |
| working, exception safe solution, I didn't see the reason to dump it and add |
| another dependency on another library. |
| ]] |
| |
| [*Gennadiy] |
| [:[' |
| I mean why do I need this half baked property_tree as another |
| data structure? Property tree supports nothing in itself. It's just a data |
| structure. You have parsers that produce property tree out of different sources. |
| But you mat as well produce maps or something else. Here for example All that |
| I need to do to "implement" similar functionality as your property tree: |
| ]] |
| |
| `` |
| // Data structure itself |
| template<typename ValueType,typename KeyType> |
| struct Node; |
| template<typename ValueType,typename KeyType> |
| struct ptree_gen { |
| typedef std::pair<KeyType,Node<ValueType,KeyType> > mi_value; |
| typedef multi_index_container<mi_value, indexed_by<...> > type; |
| }; |
| template<typename ValueType,typename KeyType> |
| struct Node { |
| ValueType v; |
| ptree_gen<ValueType,KeyType>::type children; |
| }; |
| // serialization support |
| template<class Archive,typename ValueType,typename KeyType> |
| void serialize(Archive & ar, Node<ValueType,KeyType>& n, |
| const unsigned int version) |
| { |
| ar & n.v; |
| ar & n.children; |
| } |
| // some access methods |
| template<typename ValueType,typename KeyType> |
| ValueType const& |
| get( string const& keys, ptree_gen<ValueType,KeyType>::type const& src ) |
| { |
| std::pait<string,string> sk = split( keys, "." ); |
| Node const& N = src.find( sk.first ); |
| return sk.second.empty() ? N.v : get( sk.second, N.children ); |
| } |
| `` |
| |
| [:[' |
| Use it like this: |
| ]] |
| |
| `` |
| ptree_gen<string,string>::type PT; |
| boost::archive::text_iarchive ia( std::ifstream ifs("filename") ); |
| ia >> PT; |
| string value = get( "a.b.c.d", PT ); |
| `` |
| |
| [:[' |
| Now tell me how property_tree interface is easier? And what is the value in |
| 50k of Code you need to implement this data structure. |
| ]] |
| |
| [*Thorsten] |
| [:[' |
| Seriously Gennadiy, do you really see newbies writing |
| the code you just did? |
| ]] |
| |
| [*Marcin] |
| [:[' |
| What you just implemented is stripped down, bare bones version |
| of property_tree that, among other things, does not allow you to produce human |
| editable XML files. Now add more interface (aka get functions), add more |
| archives to serialization lib, add customization, add transparent |
| translation from strings to arbitrary types and vice versa. Spend some weeks |
| trying to get all the corner cases right, and then some more weeks trying to |
| smooth rough edges in the interface. Then write tests. Write docs. At the |
| end, I believe you will not get much less code than there is in the library |
| already. Maybe you get some savings by using multi_index instead of manual |
| indexing. |
| ]] |
| [:[' |
| The reason why ptree does not use multi index is because implementation |
| existed long before I considered submitting to boost, probably before even I |
| knew of multi index existence. It was working well. Later, when I was |
| improving it during pre-review process, I seriously considered using |
| multi-index. But I decided it is not worth throwing everything out. |
| ]] |
| [:[' |
| Although ptree has large interface with many functions modifying state of |
| the tree, it uses "single point of change" approach. Every insert eventually |
| goes through one function, which takes care of exception safety and keeping |
| index in sync with data. The same applies to erase. This function has 9 |
| lines of code in case of insert, and (by coincidence) also 9 in case of |
| erase. By using multi index these functions would obviously be simplified, |
| maybe to 4 lines each. Net gain: 10 lines of code (out of several hundred in |
| ptree_implementation.hpp). |
| ]] |
| [:[' |
| I'm aware that there are performance gains to be reaped as well, but at that |
| time I was rather focusing on getting the interface right. |
| ]] |
| |
| [*Dave] |
| [:[' |
| That's perfectly reasonable, but (through no fault of yours) |
| it misses the point I was trying to make. I guess I should have said, |
| "...that demonstrates it to be the best implementation." |
| ]] |
| [:[' |
| All I'm saying is that the extent to which a Boost library |
| implementation should leverage other Boost libraries is not a question |
| that can always be decided based on following simple guidelines, and |
| that if this library is accepted, it's worth revisiting your decision. |
| ]] |
| |
| [*Thorsten] |
| [:[' |
| I think it is important to focus on the interface in |
| the review, but I also see several benefits of an implementation that builds on |
| Boost.MultiIndex:' |
| ]] |
| [:['- fewer bugs like the one Joaquin found]] |
| [:['- better space efficiency]] |
| [:['- exception-safety guarantees are immediately full-filled (I haven't |
| looked, but I suspect that there are several bugs in this area)]] |
| |
| [*Daniel] |
| [:[' |
| Multi_index supports everything a bimap would, but its |
| interface is more cumbersome. I for one won't use a W3DOM-like library |
| if we get one, but I would happily use property_tree. I've also only |
| used multi_index once, and that was to use it as a bidirectional map. |
| Property_tree covers other areas as well as being a potential subset of |
| an XML library, but I still hold there is value in such a subset. |
| ]] |
| |
| [*Boris] |
| [:[' |
| I haven't used program_options yet. But if I understand |
| correctly both libraries seem to support storing and accessing data with |
| strings that might describe some kind of hierarchy. This seems to be the core |
| idea of both libraries - is this correct? |
| ]] |
| [:[' |
| Then it wouldn't matter much what container is used. However a generic tree |
| which can store data hierarchically probably makes most sense. If I |
| understand correctly both libraries could make use of such a class? |
| ]] |
| |
| [*Marcin] |
| [:[' |
| I think generic tree container is material for another library. |
| Whether property_tree should be based on it or not is a matter of internal |
| implementation, and generally of little interest to users. The biggest value |
| of property_tree is in its easy to use interface, that should not be |
| compromised, if at all possible. I have been already reassured in this view |
| by quite many people who took their time to review the library. |
| ]] |
| |
| [*Boris] |
| [:[' |
| I was trying to see the big picture: I rather prefer a C++ |
| standard based on a few well-known concepts like containers, iterators, |
| algorithms etc. instead of having a C++ standard with hundreds of components |
| which are tailored for specific needs, collaborate with only a handful of other |
| components and think they provide an easy-to-use interface while all the |
| easy-to-use interfaces make the whole standard less easy-to-use. |
| ]] |
| [:[' |
| That said I have used your property tree library myself to read and write a |
| configuration file. It was indeed very easy to use. However it would have |
| been even easier if it was something I had known before like eg. an |
| iterator. For now I will definitely use your property tree library but would |
| appreciate if existing concepts were reused many C++ developers are familiar |
| with. My opinion is that your library should be a part of Boost but should |
| be more generalized in the future. |
| ]] |
| |
| [*Thorsten] |
| [:[' |
| Well, I think we need both. Boost.MultiIndex is a great |
| library and can do all kinds of wonderful things. But I would still like to see |
| a bidirectional map (boost::bimap) written as a wrapper around it to |
| get an easy and specialized interface. |
| ]] |
| |
| [*Pavel] |
| [:[' |
| Bimap is available in libs/multi-index/examples/bimap.cpp. |
| ]] |
| |
| [*Thorsten] |
| [:[' |
| Right, but the real value comes when somebody designs a nice |
| STL-like interface and write docs etc, at least that was my point. |
| ]] |
| |
| [*Dave] |
| [:[' |
| IMO Thorsten is exactly right. This is precisely the sort of |
| thing that could be added to the library as part of its ongoing maintenance |
| and development (without review, of course). |
| ]] |
| |
| [*Joaquin] |
| [:[' |
| Thorsten, we have talked about this privately in the past, |
| but I feel like bringing it to the list in the hope of getting the attention |
| of potential contributors: |
| ]] |
| [:[' |
| There are some data structures buildable with B.MI which are regarded as |
| particularly useful or common, like for instance the bidirectional map or |
| bimap. A lean and mean implementation is provided in the aforementioned |
| example, but certainly a much carefully crafted interface can be provided |
| keeping B.MI as the implementation core: operator\[\], selection of |
| 1-1/1-N/N-1/N-N variants, hashing/ordering, etc. |
| ]] |
| [:[' |
| I'm afraid I don't have the time to pursue this, as the current roadmap for |
| core features of B.MI is taking all the spare time I can dedicate to the |
| library. For this reason, I would love to see some volunteer jumping in who |
| can develop this and other singular containers using B.MI (a cache container |
| comes to mind) and then propose the results here either as a stand alone |
| library of as part of B.MI --I'd prefer the former so as to keep the size |
| of B.MI bounded. |
| ]] |
| [:[' |
| If there's such a volunteer I can provide her with some help/mentoring. I also |
| wonder whether this is a task suitable to be proposed for Google Summer of |
| Code. |
| ]] |
| |
| [*Thorsten] |
| [:[' |
| I think it would be good for SOC. All the really hard things |
| are taken care of by B.MI, and so it seems reasonable for a student to be able |
| to fill in the details. |
| ]] |
| |
| [*Dave] |
| [:[' |
| Great! |
| ]] |
| |
| [*Jeff] |
| [:[' |
| Please write a proposal! |
| ]] |
| |
| [*Joaquin] |
| [:[' |
| I've just done so: |
| ]] |
| |
| [blurb *Specialized containers with Boost.MultiIndex* |
| |
| *Introduction* |
| |
| Boost.MultiIndex allows the construction of complex data structures involving |
| two or more indexing mechanisms on the same set of elements. Out of the |
| unlimited range of possible data structures specifiable within |
| Boost.MultiIndex, some particular configurations arise recurrently: |
| |
| *a.* A bidirectional map or bimap is a container of elements of type pair<T,Q> |
| where fast look up is provided both for the T and the Q field, |
| in contrast with a regular STL map which only allows for fast look up on T. |
| |
| *b.* An MRU (most recently used) list keeps the n last referenced elements: |
| when a new item is inserted and the list has reached its maximum length, the |
| oldest element is erased, whereas if an insertion is tried of a preexistence |
| element, this gets promoted to the first position. MRU lists can be used to |
| implement dynamic caches and the kind of behavior exhibited by programs |
| featuring a "Recent files" menu command, for instance. |
| |
| Although Boost.MultiIndex provides the mechanisms to build these common structures, |
| the resulting interface can be cumbersome and too general in comparison with |
| specialized containers focusing on such particular structures. |
| |
| *Goal* |
| |
| To write a library of specialized containers like the ones described above, using |
| Boost.MultiIndex as the implementation core. Besides bimap and MRU list, the student |
| can also propose other specialized containers of interest in the community. It is |
| expected that the library meets the standards of quality required by Boost for an |
| eventual inclusion in this project, which implies a strong emphasis on interface |
| design, documentation and unit testing; the mentor will be guiding the student |
| through the complete cycle from specification and requirements gathering to |
| documentation and actual coding. The final result of the project must then contain: |
| |
| *a.* Source code following |
| [@http://boost.org/more/lib_guide.htm#Guidelines Boost programming guidelines]. |
| |
| *b.* User documentation. Requirements on the format are loose, though the |
| [@http://www.boost.org/tools/quickbook/doc/html/index.html QuickBook] format is |
| gaining acceptance within Boost. |
| |
| *c.* Complete set of unit tests powered by |
| [@http://boost.sourceforge.net/boost-build2/ Boost Build System V2]. |
| |
| *Requirements* |
| |
| *a.* Intermediate-to-high level in C++, with emphasis in generic programming |
| (templates). |
| |
| *b.* Knowledge of the STL framework and design principles. Of course, knowledge |
| of Boost in general and Boost.MultiIndex in particular is a big plus. |
| |
| *c.* Acquaintance with at least two different C++ programming environments. |
| |
| *d.* Some fluency in the English language; subsequent reviews of the documentation |
| can help smooth rough edges here, though. |
| |
| *e.* A mathematical inclination and previous exposure to a formal Algorithms course |
| would help very much. |
| |
| *f.* A craving for extreme quality work. |
| |
| *Benefits for the student* |
| |
| The student taking on this project will have the opportunity to learn the complete |
| process of software production inside a highly regarded C++ open source institution, |
| and even see her work included in Boost eventually. The completion of the project |
| involves non-trivial problems in C++ interface design and so-called modern C++ |
| programming, high quality user documentation and unit testing. The student will |
| also learn, perhaps to her surprise, that most of the time will be spent gathering |
| and trying ideas and, in general, thinking, rather than writing actual code. |
| ] |
| |
| [*Matias] |
| [:[' |
| I am planning to submit an application to SoC. I will love to make real |
| the specialized containers you mention and try to include some useful others. |
| ]] |
| |
| [:[^ |
| And then... after long hours of coding (and fun) this library saw the light. |
| ]] |
| |
| [:__BOOST_BIMAP_LOGO__] |
| |
| [endsect] |
| |
| [endsect] |