c++data-structuresrangelookup

Look up data by string and range number as keys


I am looking for a data structure in C++ or implement one to have different tables with a list of strings as name and each table uses number ranges as keys.

The main operation where the most of performance is required would be two lookup operations:

  1. Get table by the name in the list.
  2. In each table, get the string value by a number in the specific range.

For example, assuming the following map

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"

when given operation like query("Two", 15):

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

Are there any made solutions? any comments are appreciated.


Solution

  • You can combine a hashmap e.g., std::unordered_map or absl::flat_hash_map, with an interval tree, e.g., 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;
    }
    

    Output:

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