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

Question

假设我们有一个键-值映射的数据结构，其中键本身也是一个键-值映射。例如:

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

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

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

我们的查询是“给我所有key值，其中key包含{“k1”：“v1”}，它将返回第一个和第三个值将返回所有同时具有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

匿名用户

我相信不同方法的效率将取决于实际数据。但是，我会考虑为特定的“kX”，“vY”对制作迭代器的“缓存”，如下所示：

using M = std::map<std::map<std::string, std::string>, std::string>;
M m = {
   { { { "k1", "v1" }, { "k2", "v2" } }, "value1" },
   { { { "k1", "v3" }, { "k2", "v4" } }, "value2" },
   { { { "k1", "v1" }, { "k2", "v5" } }, "value3" }
};

std::map<M::key_type::value_type, std::vector<M::iterator>> cache;
for (auto it = m.begin(); it != m.end(); ++it)
   for (const auto& kv : it->first)
      cache[kv].push_back(it);

现在，您基本上需要获取所有搜索到的< code >“kX”、“vY”对，并为它们找到缓存迭代器的交集:

std::vector<M::key_type::value_type> find_list = { { "k1", "v1" }, { "k2", "v5" } };
std::vector<M::iterator> found;
if (find_list.size() > 0) {
   auto it = find_list.begin();
   std::copy(cache[*it].begin(), cache[*it].end(), std::back_inserter(found));
   while (++it != find_list.end()) {
      const auto& temp = cache[*it];
      found.erase(std::remove_if(found.begin(), found.end(),
            [&temp](const auto& e){ return std::find(temp.begin(), temp.end(), e) == temp.end(); } ),
         found.end());
   }
}

最终输出：

for (const auto& it : found)
   std::cout << it->second << std::endl;

在这种情况下给出值 3。

现场演示:https://wandbox.org/permlink/S9Zp8yofSvjfLokc.

请注意，交集步骤的复杂性非常大，因为缓存的迭代器是未排序的。如果您改用指针，则可以对向量进行排序或将指针存储在地图中，这将使您能够更快地找到交叉点，例如，通过使用 std：：set_intersection。

Answer 2

您可以使用＜code＞std：：includes＜/code＞来检查键映射是否包括查询的键值对的另一个映射。我不知道如何避免检查每个关键地图。也许其他答案有更好的主意。

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 

< kbd >实例

Answer 3

我将继续使用数据库索引类比。在这个类比中，索引搜索不使用一般的k=v类型搜索，而是使用一个元组，其中包含构成索引的元素（通常是列）的值。然后，数据库恢复扫描索引中不存在的其他k=v参数。

在这个类比中，您将有固定数量的键，可以表示为数组或字符串（固定大小）。好消息是，在键上设置全局顺序是微不足道的，而且由于std::map::upper_bound方法，在部分键之后立即找到迭代器也是微不足道的。

因此获得完整的密钥是直接的:只需用< code>find、< code>at或< code>operator []提取它。获取部分键的所有元素仍然很简单:

• 查找从部分键上方开始的迭代器，其中upper_bound
• 元素与部分键匹配时向前迭代

但这需要您将初始类型更改为std::map

您可以使用 std：：map 在此容器上构建一个 API