区间图实现

Question

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

任务是实现区间映射赋值操作。我向他们发送了我的解决方案，但它没有通过第二个要求（正确的行为）。他们除了声明我的代码没有通过他们的所有测试之外没有给出任何反馈。现在我想知道我可能做错了什么。当然，在发送解决方案之前我做了一些测试，并且我能想到的所有测试都通过了。

现在我睡不着，不知道哪里会搞砸。

这是我的代码：

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;
    }
}

你能帮我找出一个错误吗？

Answer 1

你可以通过减少地图的开头来获得 UB：

auto beforePrev = prevInterval;
--beforePrev;

演示

你的以下测试也很奇怪：

if (beforePrev != m_map.end()

beforePrev 不能end()像你递减它一样。

看来你可以用以下内容替换该块

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

演示