用Boost.Bimap替换向量和哈希表

Question

用Boost.Bimap替换向量和哈希表

c++data-structuresboostunordered-mapbimap

8

我想要用boost::bimap替换一个将字符串映射为前者索引的vector<string>和一个将字符串映射为索引大小的boost::unordered_map<string, size_t>。

我应该使用哪种bimap实例化？目前，我想到了以下这种：

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

但我不确定我是否已经颠倒了集合类型。此外，我想知道是否应该更改关系集合类型。是选择vector_of_relation最好，还是选择set_of_relation，或者仅使用默认设置？

- Fred Foo

1

添加一些关于您计划如何使用数据的信息，以便我们确定实现所需的约束条件。 - Andrew Hundt

我想要一个 size_t 和 string 对象之间的双射，同时具有 O(1) 的访问时间，并且需要最小或适度的内存需求。 - Fred Foo

@rep_movsd：是的，它们是。最终我通过使用Boost.MultiIndex解决了这个问题，我发现它更容易理解。（结果我需要数据的第三个视图：https://dev59.com/2VHTa4cB1Zd3GeqPWf9-。）不过，仍然欢迎提供答案。 - Fred Foo

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- MGwynne · Accepted Answer

为了在 size_t 和 std::string 之间获得一个双向映射，您需要使用 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";
  }

}

返回：

1 Cheese
2 Cheese2

unordered_set是set的boost版本，它使用哈希表而不是树来存储元素，详见Boost无序文档。

从Bimap示例的评论中可以看到：

左地图视图的工作原理类似于std :: unordered_map ，给定国家名称，我们可以使用它在常数时间内搜索人口。