Replace vector and hash table with Boost.Bimap

Question

I'm looking to replace a vector<string> and a boost::unordered_map<string, size_t> mapping string to indices in the former with a boost::bimap.

What instantiation of bimap should I use? So far, I've come up with

typedef bimap<
    unordered_set_of<size_t>,
    vector_of<string>
> StringMap;

but I'm not sure if I've reversed the collection types now. Also, I wonder if I should change the collection of relations type. Would a vector_of_relation be my best choice, or a set_of_relation, or just go with the default?

Answer 1

To get a bimap between size_t and std::string where you have ~constant (up to the cost of hashing and any potential clashes) you need to use unordered_set_of:

#include <boost/bimap.hpp>
#include <boost/bimap/unordered_set_of.hpp>
#include <string>
#include <iostream>
#include <typeinfo>

int main(int argc, char* argv[]) {

  typedef boost::bimap< boost::bimaps::unordered_set_of<size_t>, boost::bimaps::unordered_set_of<std::string> > StringMap;
  StringMap map;
  map.insert(StringMap::value_type(1,std::string("Cheese")));
  map.insert(StringMap::value_type(2,std::string("Cheese2")));

  typedef StringMap::left_map::const_iterator const_iter_type;
  const const_iter_type end = map.left.end();

  for ( const_iter_type iter = map.left.begin(); iter != end; iter++ ) {
    std::cout << iter->first << " " << map.left.at(iter->first) << "\n";
  }

}

returns:

1 Cheese
2 Cheese2

The unordered_set is a boost version of set which uses hash tables instead of trees to store the elements, see Boost Unordered docs.

Looking at the comments from one of the bimap examples at Bimap example, we have:

The left map view works like a std::unordered_map< std::string, long >, given the name of the country we can use it to search for the population in constant time