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?

Uncovered

Add some more information about the way in which you plan to use the data so we can determine the constraints for accomplishing what you need. – Boatel

I wanted a bijection between size_t and string objects with O(1) access time for both and minimal or modest memory requirements. – Uncovered

@rep_movsd: yes, they are. I eventually solved the problem by using Boost.MultiIndex, which I found easier to understand. (It turned out I needed a third view of the data: #4218385) An answer is still welcome, though. – Uncovered

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

Axiomatic

But would this give me O(1) access time for the size_t side and "hashed O(1)" from the other side? – Uncovered

Nope it wouldn't have. Although hopefully this is corrected with my recent edit. I doubt either access (size_t or std::string) get O(1) in the worst case in this way, but they should get O(1) average case complexity. – Axiomatic

Ok, accepted. I would recommend MultiIndex to any potential users of Bimap, though. – Uncovered