But AFAICT, the pop and restore operations stop working once you call del. But if your algorithm only ever adds and backtraces, you should be fine (if you know how many elements you will add or are happy to realloc your arrays from time to time, making add logarithmic).
The "set stack" and map ideas down at the bottom suggest a variant since I was just reading about A* search: a "set priority queue" that keeps the Ullman map's parallel members and values arrays in heap order according to the values. I'm thinking this might be good for A* when the search nodes can be denoted by dense-integer keys but the distances vary over a wider range.
No, it's correct -- you can see that by induction on the add operation. If you're allowed to increase n without first ensuring the invariant on the first n members, then it can break, yes.
You can only store integers and they must be in the range of [0, n>.
The simple operations are O(1), because you can just map the positions of all integers based on their value in a second array of size n.
You're not using it to replace a container ADT. You're using it for a low-overhead fast membership test. When things only store integer keys, usually that implies that you have a fast integer-keyed store for the rest of the information. Most trie implementations work the same way.
