Return to Revisions

This solution is CORRECT. But it does more than one log(N) time operations on the unordered_map (which uses Red-Balck-Tree implementation in the standard library) and this is a sub-optimal solution:

  void assign(K const& keyBegin, K const& keyEnd, V const& val) {
    if (!(keyBegin < keyEnd))
      return;
    V old_end_value = (*this)[keyEnd];
    m_map.erase(m_map.lower_bound(keyBegin), m_map.upper_bound(keyEnd));
    if (!((*this)[keyBegin] == val)) {
      m_map.insert({keyBegin, val});
    }
    if (!((*this)[keyEnd] == old_end_value)) {
      m_map.insert({keyEnd, old_end_value});
    }
  }

My approach:

1. Save the old end value of the new range endpoint which might be used in the 4th step.
2. Delete all the boundary values in the map, in the interval [keyBegin, keyEnd).
3. Insert the new start value if that position is not covering the same value already.
4. Insert the new end value only if the old end value has changed (after the third step).

This code generally handles all the cases. Trying to handle different cases specifically, you will miss many edge cases.