history.qbk

Boost provides free peer-reviewed portable C++ source libraries. We emphasize libraries that work

[/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:'