2

gnasher729's solution is often a good one, from a pragmatic perspective. It achieves linear time iteration as long as you ensure that the load factor of the hash table is bounded below by a constant. Another alternative is to maintain a doubly-linked list of all of the hash slots. In other words, each hash slot also has a "next" and "prev&...


2

In most implementations slots must be clearly recognisable as either "never used", "previously used but not used anymore" or "used, containing a hash value". So you just iterate over the stored hash values and use those that are neither "never used" nor "not used anymore". Execution time is linear in the ...


1

A stack can be, and usually is, implemented using an array and a top-of-stack pointer. It isn't an alternative to an array, but just another (more abstract) way of talking about the array and the specific access pattern needed for this task. The reason for using two stacks is probably that the undo and redo information for the same change may have different ...


Only top voted, non community-wiki answers of a minimum length are eligible