bimap/doc/history.qbk

[/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
[@https://www.codeproject.com/Articles/3016/An-STL-like-bidirectional-map#test_suite bimap library]
in 2002. Tons of users have been using it. He then
[@https://lists.boost.org/Archives/boost/2002/10/38123.php 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 enhance 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 beginning 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/ QuickBook] format is
    gaining acceptance within Boost.

    *c.* Complete set of unit tests powered by
    [@http://www.boost.org/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]