Skip to content

Efficiently iterate over range of keys between [min_key, max_key] #201

@breckognize

Description

@breckognize

The std::collections BTreeMap has a range method that allows for efficiently iterating an adjacent subset of elements between [min_key, max_key]. It would be awesome to have equivalent functionality in this crate where we also have the benefits of structural sharing.

A related request is a remove_range method that removes all the keys between [min key, max key]. I'm not sure if that could be implemented more efficiently in batch vs. just iterating a range and removing the keys one-by-one.

In the meantime, the workaround I see is to call split(min_key) and iterate the right hand side of the split until max_key. But this looks to iterate the entire map, which is prohibitively expensive if we're only interested in a small number of keys:
https://docs.rs/im/11.0.1/src/im/ordmap.rs.html#977

Activity

changed the title [-]Iterate over range of keys[/-] [+]Efficiently iterate over range of keys between [min_key, max_key][/+] on Jun 11, 2022
breckognize

breckognize commented on Jun 11, 2022

@breckognize
Author
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

      Development

      No branches or pull requests

        Participants

        @breckognize

        Issue actions

          Efficiently iterate over range of keys between [min_key, max_key] · Issue #201 · bodil/im-rs