Is std::map exception safe with custom comparator?

Question

What std::map will do if custom comparator throw an exception during rebalancing? Apparently, it should remember all the previous turns and return everything to its original state. Is it true?

Answer 1

See [associative.reqmts.except]:

For associative containers, no clear() function throws an exception. erase(k) does not throw an exception unless that exception is thrown by the container’s Compare object (if any).

For associative containers, if an exception is thrown by any operation from within an insert or emplace function inserting a single element, the insertion has no effect.

For associative containers, no swap function throws an exception unless that exception is thrown by the swap of the container’s Compare object (if any).

So you're basically right (in the case of single element insertions), but it doesn't mean the container must "remember all the previous turns" in order to "return everything to its original state". Assuming that associative containers are implemented using a self-balancing binary search tree (I'm not sure if there are any other possibilities) comparisons are only done in order to walk down the tree to find the location at which the new node must be inserted. If a comparison exits via an exception during this process, the tree hasn't been modified yet, so all the container has to do is deallocate memory it has allocated for the new element at this point (if any). The rebalancing step that follows cannot generate an exception, because it merely involves performing a bunch of tree rotations and updating internal bookkeeping data such as whether nodes are red or black.