Data structure with ordered keys and O(log(n)) to find the position of a key

Hi there!

I'm currently dealing with a GraphQL API where I need to have a map (key-value dictionary) I can paginate. Basically I get a key cursor which is where I want to start iterating, and I want to get the next values, ordered by key.

HashMap is not suited for the task as keys aren't ordered, but BTreeMap is perfect. Only problem, I cannot get the position of a key in the map.

Here is an example to make it clearer:

// K implements Ord + Eq +  Hash + Clone, let's use 'char' here
// V implements nothing
let mut map = ImaginaryMap::<char, i32>::new();
map.insert('a', 1);
map.insert('b', 2);
map.insert('c', 3);

// Let's suppose we have a cursor (which is a key from the map)
let cursor: K = 'b';

// I want to find which position the key occupies (e.g. if it's the first key in order, the second, the third, etc.)
// Here, this will return 1 (0 being the very first key)
let pos: Option<usize> = map.find_key_pos(&cursor);

// And then I can iterate in order
let iter = map.values().skip(pos.unwrap());

Are you aware of any structure that does this? I also checked IndexMap but it uses the keys' insertion order instead of their sorting order.

Thanks in advance for your help!

This sounds to me like the nightly BTreeMap::upper_bound API would be suitable for you?

1 Like

Seems like it could! I have a question though: why doesn't Cursor implement Iterator?
The API I'm using requires to make an iterator, I can write my own struct wrapping Cursor but I'm curious as to why it isn't an iterator type itself.

Could BTreeMap::range(cursor..) be a solution? That works on stable. For example (playground):

use std::collections::BTreeMap;

fn main() {

    // K implements Ord + Eq +  Hash + Clone, let's use 'char' here
    // V implements nothing
    let mut map = BTreeMap::<char, i32>::new();
    map.insert('a', 1);
    map.insert('b', 2);
    map.insert('c', 3);

    // Let's suppose we have a cursor (which is a key from the map)
    let cursor = 'b';

    map.range(cursor..).for_each(|(key, value)| {
        eprintln!("{key}: {value}"); 
    });
    
}
2 Likes

That seems like a great solution indeed! I don't have to care about the actual key's index with that.
I'm going to try this, thanks for your help :slight_smile:

Btw the proper name of a search tree where you can obtain the index of an entry in O(log n) is "order-statistics tree". In this case though something like range should be much better.

2 Likes

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.