ic-stable-memory
ic-stable-memory copied to clipboard
seniorjoinu
Right data structure for a collection of items indexed by a custom type and supports CRUD and pagination?
I believe the answer is a BTreeMap but the stable variant implemented in this repo is missing a mechanism to get a range of values instead of just an individual value.
My needs are:
- Need to be able to maintain an order sorted by most recent first
- Need to support being able to add and remove items which will update the sort order
- Need to be able to fetch a range of items at a time instead of the entire list
BTreeMap looks ideal for it where I can specify the key to be the insertion time and have it sorted. The Rust std::collection implementation has a range API here
Any plans to expose the same for the stable btreemap?
Hey!
About range. Yes, I'm working on Iter trait implementation for all collections right now. This is on the nearest roadmap, I expect this feature to be added this month.
But ranges for stable collections are kinda unsafe, since theoretically you can define a range that simply wouldn't fit into your heap, if you have big enough stable collection. Or you can hit the gas limit by iterating over a big enough range.
Can you elaborate on your use-case a little bit more? Maybe I can suggest you an alternative. Maybe your use-case can be represented as a composition of stable collections instead of a single one. Ideally we would try to find something that don't require you to iterate over elements.
A good exercise would be to try to implement your use-case by only using standard collections first.
My use case here is a profile's list of followers and the people being followed.
I would need to show the count of it on the profile page.
When clicked on it, it will bring up a list of followers, sorted by most recent first.
Each entry would show the follower's name, their profile picture and will have a button beside that lets you toggle follow/unfollow.
Finally, since this will be a long list, the frontend will show this as a infinite scrollable list.
For the above, a btreemap seems like the right choice, where I would implement PartialEq, PartialOrd traits and store the data that way. The key would be the user's principal and the value stored would be timestamp, username and profile_picture_url.
I could get count by querying the .len() on it
Sorting happens automatically since I implemented the above traits
The follow/unfollow would work with the insert/remove APIs
Finally, the pagination would happen with the range api
Thoughts?
Yes, looks like your solution is incorrect. Your PartialEq and PartialOrd should be implemented by comparing principals of users, but as I understood, you want to compare timestamps. This won't work for unfollows, since you would want to search for principals, and not for following timestamp.
You can continue using BTreeMap (implementing PartialEq and PartialOrd by comparing principals of users, but also storing the timestamp) for this task, but accompany it with a separate vector that will simply store (user principal, timestamp) pairs. When someone follows somebody, you just add the record to the BTree and push a new principal, timestamp pair to the vector. It is guarantied by the system, that your vector (if no asynchronous calls are present during this transaction) will be sorted by timestamp automatically (from old to new). When someone unfollows somebody, you just remove this entry from the BTree and from the vector, by binary-searching the latter for the timestamp.
This will provide you with O(logn) performance, but O(n) additional space to store the index.
You can paginate by simply taking some sequence of elements from this vector.
Hmm... but now I realized, you won't be able to do this either, since stable vectors don't support removing an element from the middle of the collection for now. This is also a planned feature, but it is not present yet.
@seniorjoinu I think the SBTreeMap and SBTreeSet definitely need the ability to fetch a range of values. And stable vectors supporting ability to add/remove items at arbitrary indexes would be a fantastic feature as well
I've implemented iters for all collections in 0.4.0-rc1, but I don't know yet if iter().skip() would work automatically. Gonna keep this issue closed in case it is not.