частичный поиск в карте значения ключа, где сам ключ является картой значения ключа

Question

Предположим, у нас есть структура данных, которая является картой значения ключа, где сам ключ снова является картой значения ключа.Например:

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

Теперь предположим, что мы хотим запросить все ключи / значения верхнего уровня на этой карте, соответствующие определенному подмножеству значений ключа ключа.Пример:

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

И наш запрос «дайте мне все значения ключа, где ключ содержит { "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

Я бы остановился на аналогии с индексом базы данных.В этой аналогии индексированный поиск не использует общий поиск типа k = v, а просто кортеж со значениями для элементов (обычно столбцов), которые составляют индекс.Затем база данных возвращается к сканированию для других параметров k = v, которых нет в индексе.

В этой аналогии у вас будет фиксированное количество ключей, которые могут быть представлены в виде массива или строк (фиксированный размер).Хорошая новость заключается в том, что затем установить тривиальный порядок ключей можно тривиально, а благодаря методу std::map::upper_bound также тривиально найти итератор сразу после частичного ключа.

Итак, получениеполный ключ немедленно: просто извлеките его с помощью find, at или operator [].И получить все элементы для частичного ключа по-прежнему просто:

• найти итератор, начинающийся над частичным ключом, с upper_bound
• итерацией вперед, пока элемент соответствует частичному ключу

Но для этого требуется, чтобы вы изменили свой начальный тип на std::map<std::array<string, N>, string>

Вы можете построить API для этого контейнера, используя std::map<string, string> в качестве входных значений, извлечь фактический полный или частичный ключ изи итерируйте, как указано выше, сохраняя только элементы, соответствующие парам k, v, которых нет в индексе.

Answer 2

std::map реализован в виде сбалансированного двоичного дерева, которое имеет поиск O (nlgn).Вместо этого вам нужно std::unordered_map, которое реализовано в виде хеш-таблицы, то есть O (1) поиска.

Теперь позвольте мне перефразировать вашу формулировку, вы хотите:

И наш запрос "дать мне все значения ключа, где ключ содержит {" k1 ":" v1 "} ион вернул бы первое и третье значение.

Что означает:

Если указанная пара ключ-значение находится во внутренней карте, верните мне ее значение.По сути, вам нужен двойной поиск, в котором std :: unordered_map excel.

Вот кодовая цепочка, которая решает вашу проблему со стандартной библиотекой (не требуется сложный код)

#include <iostream>
#include <unordered_map>
#include <string>

int main() {
  using elemType = std::pair<std::string, std::string>;
  using innerMap = std::unordered_map<std::string, std::string>;
  using myMap = std::unordered_map<std::string, innerMap>;

  auto table = myMap{ { "value1", { {"k1", "v1"}, {"k2", "v2"} } },
                      { "value2", { {"k1", "v3"}, {"k2", "v4"} } },
                      { "value3", { {"k1", "v1"}, {"k2", "v5"} } } };

  //First we set-up a predicate lambda                                                                                                                                                                      
  auto printIfKeyValueFound = [](const myMap& tab, const elemType& query) {
                                // O(n) for the first table and O(1) lookup for each, O(n) total                                                                                                           
                                 for(const auto& el : tab) {
                                   auto it = el.second.find(query.first);
                                   if(it != el.second.end()) {
                                     if(it->second == query.second) {
                                       std::cout << "Element found: " << el.first << "\n";
                                      }
                                    }
                                  }
                                 };

  auto query = elemType{"k1", "v1"};

  printIfKeyValueFound(table, query);

Вывод: Value3, Value1

Для запросов произвольного размера вы можете:

//First we set-up a predicate lambda                                                                                                                                                                      
auto printIfKeyValueFound = [](const myMap& tab, const std::vector<elemType>& query) {
                               // O(n) for the first table and O(n) for the query O(1) search                                                                                                             
                               // O(n^2) total                                                                                                                                                            
                               for(const auto& el : tab) {
                                 bool found = true;
                                 for(const auto& queryEl : query) {
                                   auto it = el.second.find(queryEl.first);
                                   if(it != el.second.end() && it->second != queryEl.second) {
                                       found = false;
                                       break;
                                   }
                                 }
                                 if(found)
                                   std::cout << el.first << "\n";
                                 }
                              };


auto query = std::vector<elemType>{ {"k1", "v1"}, {"k2", "v2"} };

output Value1

Answer 3

Вы можете сделать это за один (частичный) проход через каждый элемент с упорядоченным запросом, возвращая как можно раньше.Черпая вдохновение из std::set_difference, мы хотим знать, является ли query подмножеством data, что позволяет нам выбирать записи внешней карты.

// Is the sorted range [first1, last1) a subset of the sorted range [first2, last2)
template<class InputIt1, class InputIt2>
bool is_subset(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2)
{
    while (first1 != last1) {
        if (first2 == last2) return false; // Reached the end of data with query still remaing

        if (*first1 < *first2) {
            return false; // didn't find this query element
        } else {
            if (! (*first2 < *first1)) {
                ++first1; // found this query element
            }
            ++first2;
        }
    }
    return true; // reached the end of query
}

// find every element of "map-of-maps" [first2, last2) for which the sorted range [first1, last1) is a subset of it's key
template<class InputIt1, class InputIt2, class OutputIt>
OutputIt query_data(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first)
{
    auto item_matches = [=](auto & inner){ return is_subset(first1, last1, inner.first.begin(), inner.first.end()); };
    return std::copy_if(first2, last2, d_first, item_matches);
}

Answer 4

Я считаю, что эффективность различных методов будет зависеть от фактических данных.Тем не менее, я хотел бы рассмотреть возможность создания «кэша» итераторов для внешних элементов карты для конкретных пар "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);

Теперь вам нужно собрать все найденные пары "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;

в этом случае дает value3.

Живая демонстрация: https://wandbox.org/permlink/S9Zp8yofSvjfLokc.

---

Обратите внимание, что сложность этапа пересечения довольно велика, поскольку кэшированные итераторы не отсортированы.Если вместо этого вы используете указатели, вы можете отсортировать векторы или сохранить указатели на карте, что позволит вам быстрее находить пересечения, например, с помощью std::set_intersection.

.

Answer 5

Вы можете использовать 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 

Живой пример