libstdc++, libc++, and MSVC's STL all implement it as a red-black tree.

Even if it's not required to be a red-black tree, it is de facto a red-black tree on every major compiler.

Moreover, this doesn't really change the parent's point. It must be some sort of ordered associative container, meaning that it's not going to have the performance characteristics of a hash table.