interval map implementation

Question

I sent an application on a C++ position in one of IT companies. They sent me a test assignment.

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.

Now I can't sleep without knowing where could I screw it up.

Here is my code:

void assign (const K & keyBegin, const K & keyEnd, const V & val )
{
    if (!(keyBegin < keyEnd))
        return;
    auto nextInterval = --m_map.upper_bound(keyEnd);
    auto inserted1 = m_map.end();
    auto inserted2 = m_map.end();
    if (nextInterval->second == val)
        ++nextInterval;
    else if (nextInterval->first < keyEnd)
    {
        const V & nextValue = nextInterval->second;
        ++nextInterval;
        inserted1 = nextInterval = m_map.emplace_hint(nextInterval, keyEnd, nextValue);
    }
    try
    {
        auto prevInterval = nextInterval;
        --prevInterval;
        if (keyBegin < prevInterval->first)
            prevInterval = --m_map.upper_bound(keyBegin);
        if (!(prevInterval->second == val))
        {
            if (prevInterval->first < keyBegin)
            {
                ++prevInterval;
                inserted2 = prevInterval = m_map.emplace_hint(prevInterval, keyBegin, val);
            }
            else
            {
                auto beforePrev = prevInterval;
                --beforePrev;
                if (beforePrev != m_map.end() && beforePrev->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;
    }
}

Could you help me find a mistake?

Answer 1

You have UB by decrementing begin of the map:

auto beforePrev = prevInterval;
--beforePrev;

Demo

your following test is also strange:

if (beforePrev != m_map.end()

beforePrev cannot be end() as you decrement it.

it seems you can replace that block by

prevInterval->second = val;
if (prevInterval != m_map.begin() && !((--prevInterval)->second == val)){
    ++prevInterval;
} 

Demo