键值映射中的部分查找,其中键本身是键值映射

Question

假设我们有一个数据结构,它是一个键值映射,其中键本身也是一个键值映射.例如:

map<map<string,string>>, string>

现在,假设我们要查询此映射中与键的键值的某个子集匹配的所有顶级键/值.例:

map = { { "k1" : "v1", "k2 : "v2" } : "value1",
  { "k1" : "v3", "k2 : "v4" } : "value2",
  { "k1" : "v1", "k2 : "v5" } : "value3"
}

我们的查询是"给我所有key-values,其中key包含{ "k1" : "v1" },它将返回第一个和第三个值.同样,查询{ "k1" : "v3", "k2" : "v4" }将返回所有具有两个k1=v3和的键值,并k2=v4产生第二个值.显然我们可以搜索关于每个查询的完整地图,但我正在寻找比这更有效的东西.

我环顾四周,但找不到一个高效,易用的C++解决方案.在查询键值对的子集时,Boost multi_index似乎没有这种灵活性.

有些数据库有办法创建可以完全回答这类查询的索引.例如,Postgres有GIN指数(广义倒排索引),可以让你问

SELECT * FROM table WHERE some_json_column @> '{"k1":"v1","k2":"v2"}'
-- returns all rows that have both k1=v1 and k2=v2

但是,我正在寻找一种只在C++中没有数据库的解决方案.是否有任何库或数据结构可以完成这样的事情？如果没有,有关自定义实现的一些指示？

Answer 1

您可以用来std::includes检查键映射是否包含查询的键值对的另一个映射。但我不确定如何避免检查每个键映射。也许其他答案有更好的主意。

template <typename MapOfMapsIt, typename QueryMapIt>
std::vector<MapOfMapsIt> query_keymap_contains(
    MapOfMapsIt mom_fst,
    MapOfMapsIt mom_lst,
    QueryMapIt q_fst,
    QueryMapIt q_lst)
{
    std::vector<MapOfMapsIt> out;
    for(; mom_fst != mom_lst; ++mom_fst)
    {
        const auto key_map = mom_fst->first;
        if(std::includes(key_map.begin(), key_map.end(), q_fst, q_lst))
            out.push_back(mom_fst);
    }
    return out;
}

用法：

typedef std::map<std::string, std::string> StrMap;
typedef std::map<StrMap, std::string> MapKeyMaps;
MapKeyMaps m = {{{{"k1", "v1"}, {"k2", "v2"}}, "value1"},
                {{{"k1", "v3"}, {"k2", "v4"}}, "value2"},
                {{{"k1", "v1"}, {"k2", "v5"}}, "value3"}};
StrMap q1 = {{"k1", "v1"}};
StrMap q2 = {{"k1", "v3"}, {"k2", "v4"}};
auto res1 = query_keymap_contains(m.begin(), m.end(), q1.begin(), q1.end());
auto res2 = query_keymap_contains(m.begin(), m.end(), q2.begin(), q2.end());
std::cout << "Query1:    ";
for(auto i : res1) std::cout << i->second << " ";
std::cout << "\nQuery2:    ";
for(auto i : res2) std::cout << i->second << " ";

输出：

Query1:    value1 value3 
Query2:    value2 

Live Example