8

I tried to use Rust collections such as BTreeMap to store key-value pairs for use as a sorted list, but I found that it matched the exact key only. For example, in a phone book case, I can find the item with exact key "David", but not item start with "Dav":

use std::collections::BTreeMap;

fn main() {
    let mut map = BTreeMap::new();
    map.insert("Daniel", "798-1364");

    // FOUND WITH EXACT MATCH ONLY
    //  like map.get(&"Daniel"), Not Found Here
    match map.get(&"Dan") {
        Some(&number) => println!("Found: {}", number),
        _ => println!("Not Found."),
    }
}

Can I do partial matching of the string prefix using collections such as BTreeMap?

Furthermore, if my keys are i64s, can I find a range of items such as when the key is greater than 1000? I know how to iterate through all the items, but I want to iterate just the range of items found.

Can I access the items by index, to do binary search manually?

Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
Roger
  • 83
  • 1
  • 3
  • Note that `map.get` wouldn't make sense, because multiple entries might have the same prefix. It needs to be able to return zero-or-more. – Shepmaster Dec 07 '14 at 17:14

1 Answers1

13

You can do parts of what you like with BTreeMap::range:

use std::collections::BTreeMap;

fn main() {
    let mut map = BTreeMap::new();

    map.insert("Alexia", "123-4567");
    map.insert("Daniel", "798-1364");
    map.insert("Miranda", "987-6543");

    for (k, v) in map.range("Dan"..) {
        println!("Found: {}: {}", k, v);
    }
}

This prints:

Found: Daniel: 798-1364
Found: Miranda: 987-6543

You can extend the loop to have a "starts-with" check that will exit once you are no longer matching a prefix:

for (k, v) in map.range("Dan"..).take_while(|(k, _)| k.starts_with("Dan")) {
    println!("Found: {}: {}", k, v);
}

This concept extends to the integer key case, but you can also specify a complete range to limit the search to:

map.range("Dan".."E")

map.range(0..=1)
Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
  • The keys in your example are &str-s, this will not work if your keys are String-s. – Calmarius Jun 12 '22 at 10:24
  • @Calmarius the simplest thing you can do there is [also use a `String` in the call to `range`](https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=90d7a47a3822352a7eb3a687d2d887b1). See also [How to avoid temporary allocations when using a complex key for a HashMap?](https://stackoverflow.com/q/36480845/155423) ([one version applied](https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=3ea26c46f2818c76bcd83c018ae07adb)) – Shepmaster Jun 21 '22 at 16:54