通过字符串和范围编号作为键查找数据

Question

我正在寻找一种 C++ 数据结构，或者实现一个具有不同的表，并以字符串列表作为名称，每个表使用数字范围作为键。

对性能要求最高的主要操作是两个查找操作：

1. 通过列表中的名称获取表格。
2. 在每个表中，通过特定范围内的数字获取字符串值。

例如，假设以下地图

Table1 name = ["One", "Two"]
    [ 5, 20] -> "Apple"
    [25, 50] -> "Boat"
    [60, 100] -> "Cow"

Table2 name = ["Three"]
    [ 5, 20] -> "Air"
    [25, 50] -> "Bard"
    [60, 100] -> "Camera"

当给出类似

query("Two", 15)

的操作时：

"Two" -> Table1
15 -> "Apple"

有没有现成的解决方案？任何评论表示赞赏。

Answer 1

您可以将哈希图（例如，

std::unordered_map

或

absl::flat_hash_map

）与间隔树（例如，

boost::icl::interval_map

:

）相结合

#include <iostream>
#include <unordered_map>
#include <boost/icl/interval_map.hpp>

using boost::icl::interval;
using Table = boost::icl::interval_map<int, std::string>;
using Database = std::unordered_map<std::string, Table>;

std::string Query(Database& db, const std::string& table_name, int number) {
  auto table_it = db.find(table_name);
  if (table_it != db.end()) {
    auto& table = table_it->second;
    auto range_it = table.find(number);
    if (range_it != table.end()) {
      return range_it->second;
    }
  }
  return "Not Found";
}

int main() {
  Database db;
  db["One"].insert(std::make_pair(interval<int>::closed(5, 20), "Apple"));
  db["One"].insert(std::make_pair(interval<int>::closed(25, 50), "Boat"));
  db["One"].insert(std::make_pair(interval<int>::closed(60, 100), "Cow"));
  db["Two"] = db["One"];
  db["Three"].insert(std::make_pair(interval<int>::closed(5, 20), "Air"));
  db["Three"].insert(std::make_pair(interval<int>::closed(25, 50), "Bard"));
  db["Three"].insert(std::make_pair(interval<int>::closed(60, 100), "Camera"));
  std::cout << "Query(Two, 15): " << Query(db, "Two", 15) << '\n';
  std::cout << "Query(Three, 30): " << Query(db, "Three", 30) << '\n';
  std::cout << "Query(One, 65): " << Query(db, "One", 65) << '\n';
  return 0;
}

输出：

Query(Two, 15): Apple
Query(Three, 30): Bard
Query(One, 65): Cow