Return to Answer

When implementing, I imagined the assign function as painting a new color over an existing color in a strip. The map here contains only the starting point and the color (i.e. value) in the strip for each painted region.

FYI, I also wrote a verify function that can be called after each assign to verify the validity of the whole map.

template <typename K, typename V>
void interval_map<K, V>::_verify(const K& keyBegin, const K& keyEnd, const V& val) const
{
    // 1. m_map should be non-empty.
    assert( m_map.begin() != m_map.end() );

    auto it = m_map.begin();
    V prev_val = it->second;
    while ( ++it != m_map.end() )
    {
        // 2. Adjacent intervals should have different values.
        assert( prev_val != it->second );
        prev_val = it->second;
    }

    auto it0 = --m_map.upper_bound(keyBegin);
    auto it1 = --m_map.lower_bound(keyEnd);
    // 3. There should be only one interval that convers [keyBegin, keyEnd).
    assert( it0 == it1 );

    // 4. The interval should have the disired value.
    assert( val == it0->second );
}

FYI, I also wrote a verify function that can be called after each assign to verify the validity of the whole map. Hope this can help to understand the property of the map to satisfy across assign operations.

template <typename K, typename V>
void interval_map<K, V>::_verify(const K& keyBegin, const K& keyEnd, const V& val) const
{
    // 1. m_map should be non-empty.
    assert( m_map.begin() != m_map.end() );

    auto it = m_map.begin();
    V prev_val = it->second;
    while ( ++it != m_map.end() )
    {
        // 2. Adjacent intervals should have different values.
        assert( prev_val != it->second );
        prev_val = it->second;
    }

    auto it0 = --m_map.upper_bound(keyBegin);
    auto it1 = --m_map.lower_bound(keyEnd);
    // 3. There should be only one interval that covers [keyBegin, keyEnd).
    assert( it0 == it1 );

    // 4. The interval should have the disired value.
    assert( val == it0->second );
}

FYI, I also wrote a verify function that can be called after each assign to verify the validity of the whole map.

template <typename K, typename V>
void interval_map<K, V>::_verify(const K& keyBegin, const K& keyEnd, const V& val) const
{
    // 1. m_map should be non-empty.
    assert( m_map.begin() != m_map.end() );

    auto it = m_map.begin();
    V prev_val = it->second;
    while ( ++it != m_map.end() )
    {
        // 2. Adjacent intervals should have different values.
        assert( prev_val != it->second );
        prev_val = it->second;
    }

    auto it0 = --m_map.upper_bound(keyBegin);
    auto it1 = --m_map.lower_bound(keyEnd);
    // 3. There should be only one interval that convers [keyBegin, keyEnd).
    assert( it0 == it1 );

    // 4. The interval should have the disired value.
    assert( val == it0->second );
}