8000 Support an additional (optional) key in iddqd::IdOrdMap (“BiOrdMap”) · Issue #19 · oxidecomputer/iddqd · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

Support an additional (optional) key in iddqd::IdOrdMap (“BiOrdMap”) #19

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Open
jkneer opened this issue May 24, 2025 · 1 comment
Open

Support an additional (optional) key in iddqd::IdOrdMap (“BiOrdMap”) #19

jkneer opened this issue May 24, 2025 · 1 comment

Comments

@jkneer
Copy link
jkneer commented May 24, 2025 •
edited
Loading

I love this crate, thank you for all the work!

Quick notice: I’m happy to help drive this feature, but my bandwidth is very limited for the next 6 weeks.

Background
IdOrdMap<K,V> today maintains exactly one sorted key. I need one primary index (sorted) and a secondary key for fast lookup, without being forced to rebuild maps or sort on the fly.

I began this on Reddit but it’s complex enough to merit an in-repo API discussion.

Options

  1. Only primary sorted + secondary lookup
    • Simple, but if you later need to sort by the second key, you’re back to ad-hoc sorting or a separate map.
  2. Two always-sorted keys
    • Two B-trees under the hood; higher memory & insertion/removal cost.
  3. Primary sorted + optional sorted
    • Zero-cost if you don’t invoke the second sort.
    • API is trickier: needs either builders/constructors or trait-gated impls.

API Questions
• Should one hard-code a .with_secondary_index() constructor, or infer “sortable” from K: Ord + Clone?
• Does one expose separate .iter_by_primary()/.iter_by_secondary() methods, or a unified .iter(Index)?
• Is it better to have separate BiOrdMap vs. a single generic type with optional indices?

Initial Proposal
Introduce a BiOrdMap<K1, K2, V> that always provides:
• Primary sorted index on K1
• Secondary unsorted lookup by K2

This stays close to the existing API, provides a playground to refine constructors, method names, and performance trade-offs, and lays groundwork for an optional‐sort variant later.

Feedback and real-world use cases welcome!
@jkneer jkneer changed the title Support an additional (optional) key in iddrd::IdOrdMap (“BiOrdMap”) Support an additional (optional) key in iddqd::IdOrdMap (“BiOrdMap”) May 24, 2025
@sunshowers
Copy link
Collaborator
sunshowers commented May 25, 2025 •
edited
Loading

Thanks for the feature request!

• Is it better to have separate BiOrdMap vs. a single generic type with optional indices?

Strongly recommend a separate type here, even though I'm aware it's a lot more boilerplate (this project is pretty mechanical in many ways but already has boilerplate). An important part of API design is that there's only a certain strangeness budget available, and trying to model these kinds of optional indexes with generics risks iddqd becoming unapproachable. I think we've all seen Rust crates which suffer from over-genericity.

I like the idea to just have one ordered key for now. I think it keeps the API simple and easy to understand (iter sort order is by the only sorted key, for example). For more flexibility, multi_index_map is always available.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@sunshowers @jkneer
0