0
$\begingroup$

I am looking for a functional data structure that would work in this role.

Adding items to the struct happens often. Removing items from the struct happens as often as adding them but I have no way of knowing what order the deletion happens in. Over the long term addions will equal removal Rarely I need all items currently in the struct

I thought of using a queue but out of order removal from a queue is expensive.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

My recommendation is a straightforward hash map. If you have a good hash function for your distribution of keys, the time complexity for adding and removing (with an arbitrary key) is amortized $O(1)$.

EDIT: Hash maps can be purely functional if you want (example), they just become a whole lot less efficient. I don't think it's theoretically possible to get lower than $O(\log n)$, which is what you get from using a red-black tree as the backend. The linked HAMT implementation is also $O(\log n)$, just with a significantly smaller hidden constant.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Hash maps are good but I'm looking for a functional data structure rather then an imperative one. $\endgroup$
    – Q the Platypus
    May 17, 2019 at 1:33
  • $\begingroup$ @QthePlatypus Hashmaps can be functional, they just stop being $O(1)$ (because functional-ness usually makes things less efficient). Added a note on that with an example. $\endgroup$
    – Draconis
    May 17, 2019 at 1:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.