Implements a hash table with constant-time insertion and removal, and iteration in some consistent order across runs. Two copies of each element are kept, one is stored in a std::vector for random access iteration, and one is used as a key in a DenseMap, which contains indexes to the vector.
The extra copy of each value is a bit unfortunate, but it would be a lot of work to fix (you'd basically have to reimplement DenseMap), and it's not a big deal for pointer-sized keys, so should be fine to leave that as-is for now.
I guess this is fine, unless someone else has a better suggestion.
We already have SetVector which is widely used for these patterns. If we need both, we need a clear explanation of the difference and why we need both (IE, why users of one can't use the other).
Assuming we end up with two ADTs, we'll need: better names, clear header documentation of what's different, and an explanation in https://llvm.org/docs/ProgrammersManual.html.
Personally, I'd be in favour of changing MapVector to just do this, since it already has an index. I'd also be in favour of adding an index to SetVector to match. There'd be some work to do in auditing/updating users, but I doubt there are many calls to erase() and I'm skeptical that anyone relies on the current order for something other than determinism.
I think we should not change MapVector. Its underlying data structure is a vector with <key,value> pairs but we only need to store a single value. Moreover, both MapVector and SetVector provide insertion order iteration and their users might rely on that. I am not sure we should change that. SmallSet might be a good alternative for lower insertion/deletion complexity, but at the moment it does not provide iteration over the underlying data structures. It uses a SmallVector for small data sets and expands it to an std::set if it grows too much. Is there a way to abstract those underlying iterators? If not I think we should keep this new ADT and rename/document it properly.
I like @dexonsmith's suggestion. @labrinea, you don't have to change MapVector, but I think it's worth changing SetVector to maintain the vector indices in its map and to make erase O(1). Refactoring them to use the same implementation and implementing this optimization for MapVector can be done later.