partial lookup in key-value map where key itself is a key-value map

Question

Suppose we have a data structure that is a key-value map, where the key itself is again a key-value map. For example:

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

Now, suppose that we want to query all top-level key/values in this map matching a certain subset of the key-values of the key. Example:

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

And our query is "give me all key-values where key contains { "k1" : "v1" } and it would return the first and third value. Similarly, querying for { "k1" : "v3", "k2" : "v4" } would return all key-values that have both k1=v3 and k2=v4, yielding the second value. Obviously we could search through the full map on every query, but I'm looking for something more efficient than that.

I have looked around, but can't find an efficient, easy-to-use solution out there for C++. Boost multi_index does not seem to have this kind of flexibility in querying subsets of key-value pairs.

Some databases have ways to create indices that can answer exactly these kind of queries. For example, Postgres has GIN indices (generalized inverted indices) that allow you to ask

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

However, I'm looking for a solution without databases just in C++. Is there any library or data structure out there that can accomplish something like this? In case there is none, some pointers on a custom implementation?

Answer 1

I would stay with the database index analogy. In that analogy, the indexed search does not use a generic k=v type search, but just a tuple with the values for the elements (generally columns) that constitute the index. The database then reverts to scans for the other k=v parameters that are not in the index.

In that analogy, you would have a fixed number of keys that could be represented as an array or strings (fixed size). The good news is that it is then trivial to set a global order on the keys, and thanks to the std::map::upper_bound method, it is also trivial to find an iterator immediately after a partial key.

So getting a full key is immediate: just extract it with find, at or operator []. And getting all elements for a partial key is still simple:

• find an iterator starting above the partial key with upper_bound
• iterate forward while the element matches the partial key

But this require that you change your initial type to std::map<std::array<string, N>, string>

You could build an API over this container using std::map<string, string> as input values, extract the actual full or partial key from that, and iterate as above, keeping only elements matching the k,v pairs not present in index.

Answer 2

You could use std::includes to check if key maps include another map of queried key-value pairs. I am unsure how to avoid checking every key-map though. Maybe other answers have a better idea.

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;
}

Usage:

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 << " ";

Output:

Query1:    value1 value3 
Query2:    value2 

Live Example