title: interval map implementation
body: <p>I sent an application on a C++ position in one of IT companies. They sent me a test assignment. </p>
  
  <p>The task is to implement an interval map assignment operation. I sent them my solution, but it did not pass the second requirement (correct behavior). They did not give a feedback more than stating that my code did not pass all their tests. And now I wonder what could I do wrong. Of course I did some testing before sending my solution, and every test I could think of passed.</p>
  
  <p>Now I can't sleep without knowing where could I screw it up.</p>
  
  <p>Here is my code:</p>
  
  <pre><code>void assign (const K &amp; keyBegin, const K &amp; keyEnd, const V &amp; val )
  {
      if (!(keyBegin &lt; keyEnd))
          return;
      auto nextInterval = --m_map.upper_bound(keyEnd);
      auto inserted1 = m_map.end();
      auto inserted2 = m_map.end();
      if (nextInterval-&gt;second == val)
          ++nextInterval;
      else if (nextInterval-&gt;first &lt; keyEnd)
      {
          const V &amp; nextValue = nextInterval-&gt;second;
          ++nextInterval;
          inserted1 = nextInterval = m_map.emplace_hint(nextInterval, keyEnd, nextValue);
      }
      try
      {
          auto prevInterval = nextInterval;
          --prevInterval;
          if (keyBegin &lt; prevInterval-&gt;first)
              prevInterval = --m_map.upper_bound(keyBegin);
          if (!(prevInterval-&gt;second == val))
          {
              if (prevInterval-&gt;first &lt; keyBegin)
              {
                  ++prevInterval;
                  inserted2 = prevInterval = m_map.emplace_hint(prevInterval, keyBegin, val);
              }
              else
              {
                  auto beforePrev = prevInterval;
                  --beforePrev;
                  if (beforePrev != m_map.end() &amp;&amp; beforePrev-&gt;second == val)
                      prevInterval = beforePrev;
                  else
                  {
                      auto hint = m_map.erase(prevInterval);
                      inserted2 = prevInterval = m_map.emplace_hint(hint, keyBegin, val);
                  }
              }
          }
          m_map.erase(++prevInterval, nextInterval);
      }
      catch (...)
      {
          if (inserted1 != m_map.end())
              m_map.erase(inserted1);
          if (inserted2 != m_map.end())
              m_map.erase(inserted2);
          throw;
      }
  }
  </code></pre>
  
  <p>Could you help me find a mistake?</p>