两个单独的键映射到 std::map 中的单个条目

Question

我正在编写一段具有 objective 快速 "search engine" 的代码。我在一个文件中有一些条目需要在读入整个文件后进行搜索。它们需要通过条目的名称和它从文件开头的偏移量来搜索。我的问题是内存使用问题之一，因为有数百万个条目。目前我使用两个单独的 std::maps 来存储数据，以便可以指定任一搜索词。这导致数据的双重存储，这是我试图减少的。

我使用 valgrind massif 发现内存使用的主要部分是条目的双重存储。

当前存储方式：

struct entry {
    std::string name;
    uint16_t offset;
    uint16_t size;
    bool isConst;
};

nameSearchMap.insert(std::pair<std::string, entry>(s_entry.name, e_entry));
offsetSearchMap.insert(std::pair<uint16_t, SymInfo>(s_entry.offset, s_entry));

有没有一种方法可以制作一张可通过任一类型的键搜索的地图？

Answer 1

您可以考虑使用

std::map<std::string, std::shared_ptr<entry>>

用于将字符串映射到条目，

std::map<uint16_t, std::shared_ptr<entry>>

请注意，通过对值负载使用共享指针（因此对两个映射使用相同的 entry 对象），您可以节省负载的大小。虽然您为两个共享指针付费，但您仍然会为您的特定结构领先。

（感觉像在画图，重点是内存中只有一个entry对象。）

您可能还对boost::bimap感兴趣。

Answer 2

They need to be searchable by both the name of the entry, and it's offset from the beginning of the file.

这向我表明您可以将数据存储在 array/vector 中，并使用映射到 array/vector 中的索引的地图。

std::vector<entry> entries;
std::map<std::string, size_t> map1;
std::map<uint16_t, size_t> map2;

Answer 3

每个条目可以保存三个指针，避免条目重复。但是只有当插入不像获取那么频繁时才可用的方法：

std:vector<std::string> names;
std:vector<entry> entries;
std:map<uint16_t,size_t> offset2pos;

名称和条目必须相同排序，所以名称的位置分别与该名称相等

names[pos] == entries[pos].name

并且map offset2pos可以将offset转换为pos

size_t pos = offset2pos[offset]

使用二进制搜索将名称转换为位置 (std::lower_bound)

size_t pos = names.begin() - std::lower_bound( names.begin(), names.end(), offset )

这种技术适用于插入不如获取频繁的情况。但是 algoritm 并不是那么简单，你需要重新分配 offset2pos（可能 rebuild) 每次插入一个或多个元素时。

在上面的答案中你需要保存每个元素：

std::string，uint16_t，2 * Sptr，4 * Mptr

在我看来：

std::string，uint16_t，Sptr，2 * Mptr

其中： sptr - 是 smaprt 指针对象的内部指针 mptr - 映射二进制三节点左右指针

所以每个条目3个指针就是你的内存利润。

Answer 4

您可以按如下方式使用Boost.MultiIndex：

Live Coliru Demo

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/member.hpp>
#include <cstdint>
#include <string>

struct entry {
  std::string name;
  uint16_t offset;
  uint16_t size;
  bool isConst;
};

using namespace boost::multi_index;

using entry_map=multi_index_container<
  entry,
  indexed_by<
    hashed_unique<tag<struct by_name>,member<entry,std::string,&entry::name>>,
    hashed_unique<tag<struct by_offset>,member<entry,uint16_t,&entry::offset>>
  >
>;

#include <iostream>

int main()
{
  entry_map m={{"hello",0,10,false},{"hi",1,20,true},{"bye",2,15,false}};
  auto&     name_map=m.get<by_name>();
  auto&     offset_map=m.get<by_offset>();

  std::cout<<"size(\"hello\"): "<<name_map.find("hello")->size<<"\n";
  std::cout<<"size(2): "<<offset_map.find(2)->size<<"\n";
}

输出：

size("hello"): 10
size(2): 15

两个单独的键映射到 std::map 中的单个条目

Two separate keys map to a single entry in a std::map

c++

stdmap