我正在寻找一种 C++ 数据结构,或者实现一个具有不同的表,并以字符串列表作为名称,每个表使用数字范围作为键。
对性能要求最高的主要操作是两个查找操作:
例如,假设以下地图
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"
有没有现成的解决方案?任何评论表示赞赏。
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 Result (Two, 15): " << query(db, "Two", 15) << std::endl;
std::cout << "Query Result (Three, 30): " << query(db, "Three", 30) << std::endl;
std::cout << "Query Result (One, 65): " << query(db, "One", 65) << std::endl;
return 0;
}
输出:
Query Result (Two, 15): Apple
Query Result (Three, 30): Bard
Query Result (One, 65): Cow