<p>You can solve this with a dictionary, using <code>myptr a = a</code>.</p>

<p>You can get $O(\lg n)$ add and remove in an immutable data structure by using a balanced binary search tree. Enumerate will take $O(n)$ time, but the $i$th element can be made available in $O(i)$ time, so your enumerate result can keep up with any consumption of it.</p>

<p><a href="http://erikdemaine.org/papers/ConfluentTries_Algorithmica/" rel="nofollow">"Confluently Persistent Tries for Efficient Version Control", by Erik D. Demaine, Stefan Langerman, and Eric Price</a> provides a dictionary that is fully persistent, but not immutable. With it, you can get the same bound on enumerate, and a $O(\lg \lg n)$ bound on add and remove.</p>

CC BY-SA 3.0
2013-06-07T15:26:31.737Z
2013-06-07T15:26:31.737Z
jbapple
<p>I'm looking for a bag or set data structure that will allow for the following operations:</p>
<ul>
<li><p><strong>Add</strong> an element to the set, and get a &quot;pointer&quot; to that element.</p>
<p><code>Add :: mystructure a -&gt; a -&gt; (mystructure a, myptr a)</code></p>
</li>
<li><p><strong>Remove</strong> an element for which I have a &quot;pointer&quot;.</p>
<p><code>Remove :: mystructure a -&gt; myptr a -&gt; mystructure a</code></p>
</li>
<li><p><strong>Enumerate</strong> all the elements in the set.
<code>Enumerate :: mystructure a -&gt; [a]</code></p>
</li>
</ul>
<p>Note that I don't really care about duplicate values (the values I enter are already unique), nor the order of elements.</p>
<p>A very simple implementation for this structure would be to use a doubly-linked list, with the standard <strong>Add</strong> returning a pointer to the newly created list node, the standard <strong>Remove</strong> removing such a node from the list, and <strong>Enumerate</strong> simply traversing the list.</p>
<p>However, I need the structure to be <strong>immutable/persistant</strong> (i.e. the <strong>Add</strong> and <strong>Remove</strong> operations don't modify the original data structure). Ideally, the operations would still be <code>O(1)</code>, like with a doubly-linked list. I think finger trees could be used for this, but I don't know them well.</p>

CC BY-SA 3.0
2013-06-07T14:53:52.480Z
I think what you are looking for has sometimes been called a "quasidictionary"; see Hagerup & Raman's "An Efficient Quasidictionary".
jbapple
CC BY-SA 3.0
2013-06-07T14:54:15.077Z
Note that there are some data structures that are persistent without being immutable; immutability is an implementation technique that achieves "full persistence" and more. See [this chapter by Kaplan that explains the differences between immutable/functional, confluently persistent, fully persistent, and partially persistent.](http://www.math.tau.ac.il/~haimk/papers/persistent-survey.ps)
jbapple
<ds.data-structures>
Persistant bag/set with direct access to known elements
Suzanne Soy
# Persistant bag/set with direct access to known elements

(Asked by: username_0 on 2013-06-07)

I'm looking for a bag or set data structure that will allow for the following operations:

* **Add** an element to the set, and get a "pointer" to that element.

  `Add :: mystructure a -> a -> (mystructure a, myptr a)`
* **Remove** an element for which I have a "pointer".

  `Remove :: mystructure a -> myptr a -> mystructure a`
* **Enumerate** all the elements in the set.
  `Enumerate :: mystructure a -> [a]`

Note that I don't really care about duplicate values (the values I enter are already unique), nor the order of elements.

A very simple implementation for this structure would be to use a doubly-linked list, with the standard **Add** returning a pointer to the newly created list node, the standard **Remove** removing such a node from the list, and **Enumerate** simply traversing the list.

However, I need the structure to be **immutable/persistant** (i.e. the **Add** and **Remove** operations don't modify the original data structure). Ideally, the operations would still be `O(1)`, like with a doubly-linked list. I think finger trees could be used for this, but I don't know them well.

**Tags:** ds.data-structures
> **Comments:**
> **username_1**: I think what you are looking for has sometimes been called a "quasidictionary"; see Hagerup & Raman's "An Efficient Quasidictionary".  
> **username_1**: Note that there are some data structures that are persistent without being immutable; immutability is an implementation technique that achieves "full persistence" and more. See [this chapter by Kaplan that explains the differences between immutable/functional, confluently persistent, fully persistent, and partially persistent.](http://www.math.tau.ac.il/~haimk/papers/persistent-survey.ps)  

---

## 1 answers

### Answer by username_1 on 2013-06-07. Score: 3

You can solve this with a dictionary, using `myptr a = a`.

You can get $O(\lg n)$ add and remove in an immutable data structure by using a balanced binary search tree. Enumerate will take $O(n)$ time, but the $i$th element can be made available in $O(i)$ time, so your enumerate result can keep up with any consumption of it.

["Confluently Persistent Tries for Efficient Version Control", by Erik D. Demaine, Stefan Langerman, and Eric Price](http://erikdemaine.org/papers/ConfluentTries_Algorithmica/) provides a dictionary that is fully persistent, but not immutable. With it, you can get the same bound on enumerate, and a $O(\lg \lg n)$ bound on add and remove.


---

