|
Home | Libraries | People | FAQ | More |
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:
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 Boost programming guidelines.
b. User documentation. Requirements on the format are loose, though the QuickBook format is gaining acceptance within Boost.
c. Complete set of unit tests powered by 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.
