c++ - 区间图实现

Question

我向一家 IT 公司发送了 C++ 职位的申请。他们给我发了一份测试作业。

任务是实现一个区间图赋值操作。我向他们发送了我的解决方案，但它没有通过第二个要求(正确的行为)。他们没有给出反馈，只是说我的代码没有通过他们所有的测试。现在我想知道我做错了什么。当然，我在发送我的解决方案之前做了一些测试，我能想到的每一个测试都通过了。

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

这是我的代码:

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

您通过递减 map 的开头来获得 UB:

auto beforePrev = prevInterval;
--beforePrev;

Demo

你下面的测试也很奇怪:

if (beforePrev != m_map.end()

beforePrev 不能是 end() 因为你递减它。

看来你可以用

替换那个 block

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

Demo