Joaquin Lopez Muñoz posted his first bimap library in 2002. Tons of users have been using it. He then 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.
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.
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.
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.
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.
The formal review took place at the beginning of the year and Boost.Bimap was accepted in Boost.