3 ms·
So far I have found no Rust insertion-ordered collections which supports removing items without scrambling items (necessary for editing a key-value INI file) wi
by nyanpasu64 4y ago
So far I have found no Rust insertion-ordered collections which supports removing items without scrambling items (necessary for editing a key-value INI file) with O(log n) reads/writes, though you can use a vector with O(n) accesses which takes O(n^2) to lookup every key, which is probably good enough in most cases.
And non-tree-shaped object graphs are not a library concern, but permeate entire applications; if you want to rewrite an app using shared mutability in Rust, you must either write code awkwardly with Cell/RefCell (and RefCell has runtime overhead), restructure the whole program in one Big Rewrite, or fallback to unsafe accesses (at this point, outside of multithreading C++ is a better Unsafe Rust than Unsafe Rust).
Please respond with a factual rebuttal before downvoting.
- paavohtl 4y agoIt seems that indexmap would fit your bill: Repo: https://github.com/bluss/indexmap https://github.com/bluss/indexmap IndexMap type itself: https://docs.rs/indexmap/latest/indexmap/map/struct.IndexMap.html https://docs.rs/indexmap/latest/indexmap/map/struct.IndexMap... It has amortized O(1) reads and writes, and it supports removal without maintaining order in O(1), or while maintaining order in O(n).
- nyanpasu64 4y agoI was not initially aware of O(n) order-preserving shift_remove[...](). Although likely not a problem in practice, removing a large number of items one by one (eg. when a user is deleting a selection containing many file associations) can result in quadratic behavior. I found that you can avoid that by calling retain() (at the cost of being a higher-order function) to keep/remove every item in the list in a single pass (linear time is fast enough for INI files). So in retrospect IndexMap would be a workable choice, if used carefully.