homepage

Even in the mesh algorithm, we let resizing periodically clean-up the dummies. The idea is to not pay the freeslot tracking cost on every lookup and instead only clean-up periodically (which would likely give better performance for the mesh algorithm as well, since making a single pass clean-up during resizing is cheaper than doing multi-step tracking for every insertion). The slots do get reused, just not immediately.
Also, the idea is to not let the possibility of pop-change-update algorithms create a cost for the more common uses of sets (uniquification, fast membership testing, and set-to-set operations such as union, intersection, and difference).