How to overwrite [first, last) in std::map

My goal is to overwrite [first, last) in std::map<int, char> with only 1 amortized O(log N), the rest should be O(1) operations.

Honestly, I want to know how to build a good algorithm with other optimization technique. I am stuck with the flowchart technique and can't squeeze more performance out of this.

The specification:

1. The map have initial value. so when you create it i.e. abcMap<int, char> map{'A'}, and access is M[0] it will return 'A'
2. The stored entry must be canonical i.e. map == { {1, 'A'}, {3, 'B'} } is legal. However, map == { {1, 'A'}, {3, 'A'} } is illegal. Also, if the initial value is 'A' then map == { {1, 'A'} } is illegal.
3. The stored entry is a checkpoint i.e. map == { {1, 'A'}, {2, 'A'}, {3, 'B'} } is illegal. It should be map == { {1, 'A'}, {3, 'B'} }.

For example

abcMap<int, char> map{'A'};

map.assign(0, 1, 'B'); // map == { {0, 'B'} }
map[-1] == 'A'
map[0] == 'B'
map[1] == 'B'

The problem:

1. std::prev or std::next is O(N) operation.
2. std::map::lower_bound is O(log N) operation. So can't do first = map.lower_bound(first), last = map.lower_bound(last).
3. std::map::insert_or_assign is O(log N).
4. std::map::erase log(c.size()) + std::distance(first, last) operation.

What I've tried:

1. worse case 2 O(N) operations + 1 O(log N) operation + log(N) + std::distance(first, last) operation.

flowchart

The interface

#pragma once

template<typename K, typename V>
class abcMap
{
    friend void abcMapTest();
    V m_valBegin;
    std::map<K,V> m_map;
public:
    // constructor associates whole range of K with val
    abcMap(V const& val);

    // Assign value val to interval [keyBegin, keyEnd).
    // Overwrite previous values in this interval.
    // Conforming to the C++ Standard Library conventions, the interval
    // includes keyBegin, but excludes keyEnd.
    // If !( keyBegin < keyEnd ), this designates an empty interval,
    // and assign must do nothing.
    void assign( K const& keyBegin, K const& keyEnd, V const& val );
    V const& operator[]( K const& key ) const;
    void print();
};

#include "abcMap.inl"

The implementation

#include "abcMap.hpp"

template<typename K, typename V>
abcMap<K,V>::abcMap(V const& val) : m_valBegin(val) {}

template<typename K, typename V>
void abcMap<K,V>::assign( K const& keyBegin, K const& keyEnd, V const& val ) {
    using mapitr_t = typename decltype(m_map)::iterator;
    mapitr_t eraseIteratorFirst;
    
    if (keyBegin > keyEnd) return;

    auto size = m_map.size();
    if (size == 0)
    {
        if (m_valBegin == val) return;
        else
        {
            m_map.insert_or_assign(m_map.end(), keyBegin, val);
            return;
        }
    }
    else if (size == 1)
    {
        auto begin = m_map.begin();
        if (begin->first == keyBegin)
        {
            if (m_valBegin == val) return;
            else
            {
                m_map.insert_or_assign(m_map.begin(), keyBegin, val);
                return;
            }
        }
        else if (begin->first > keyBegin)
        {
            if (m_valBegin == val)
            {
                eraseIteratorFirst = m_map.begin();
                // goto erase
            }
            else
            {
                eraseIteratorFirst = m_map.insert_or_assign(begin, keyBegin, val);
                ++eraseIteratorFirst;
                // goto erase
            }
        }
        else
        {
            if (begin->second == val) return;
            else
            {
                m_map.insert_or_assign(m_map.end(), keyBegin, val);
                return;
            }
        }
    }
    else
    {
        auto begin = m_map.begin();
        if (begin->first >= keyBegin)
        {
            if (m_valBegin == val)
            {
                eraseIteratorFirst = m_map.begin();
                // goto erase
            }
            else
            {
                eraseIteratorFirst = m_map.insert_or_assign(begin, keyBegin, val);
                ++eraseIteratorFirst;
                // goto erase
            }
        }
        else
        {
            auto last = std::prev(m_map.end());
            if (last->first == keyBegin)
            {
                auto beforeLast = std::prev(last);
                if (beforeLast->second == val)
                {
                    m_map.erase(last);
                    return;
                }
                else
                {
                    m_map.insert_or_assign(last, keyBegin, val);
                    return;
                }
            }
            else if (last->first < keyBegin)
            {
                if (last->second == val) return;
                else
                {
                    m_map.insert_or_assign(last, keyBegin, val);
                    return;
                }
            }
            else
            {
                auto itBegin = m_map.lower_bound(keyBegin);
                if (std::prev(itBegin)->second == val)
                {
                    eraseIteratorFirst = itBegin;
                    // goto erase
                }
                else
                {
                    eraseIteratorFirst = m_map.insert_or_assign(itBegin, keyBegin, val);
                    ++eraseIteratorFirst;
                    // goto erase
                }
            }
        }
    }

    // erase
    auto last = std::prev(m_map.end());
    if (last->first == keyEnd)
    {
        m_map.erase(eraseIteratorFirst, last);
        return;
    }
    else if (last->first < keyEnd)
    {
        m_map.erase(eraseIteratorFirst, m_map.end());
        return;
    }
    else
    {
        m_map.erase(eraseIteratorFirst, m_map.lower_bound(keyEnd));
        return;
    }
}

template<typename K, typename V>
V const& abcMap<K,V>::operator[]( K const& key ) const {
    auto it=m_map.upper_bound(key);
    if(it==m_map.begin()) {
        return m_valBegin;
    } else {
        return (--it)->second;
    }
}

template<typename K, typename V>
void abcMap<K,V>::print()
{
    std::cout<< "{";
    for (auto&&[key,val] : m_map)
    {
        std::cout << " {" << key << ",\'" << val << "\'},";
    }
    std::cout << "}\n";
}

The test

#include "abcMap.hpp"
#include <iostream>

void abcMapTest()
{
    const auto start = std::chrono::steady_clock::now();

    using map_t = abcMap<int, char>;

    std::map<int, char> expected_map;

    // MARK: M

    // std::cout << "MARK: M" << std::endl;

    map_t M{'A'};

    assert(M[-2] == 'A');
    assert(M[-1] == 'A');
    assert(M[0] == 'A');

    M.assign(1, 3, 'B');
    // M.print(); // [1:'B'];
    expected_map = { {1,'B'} };
    assert(M.m_map == expected_map);

    assert(M[1] == 'B');
    assert(M[2] == 'B');

    M.assign(3, 5, 'A');
    // M.print(); // [1:'B'][3:'A'];
    expected_map = { {1,'B'}, {3,'A'} };
    assert(M.m_map == expected_map);

    M.assign(5, 7, 'A');
    // M.print(); // [1:'B'][3:'A'];
    expected_map = { {1,'B'}, {3,'A'} };
    assert(M.m_map == expected_map);

    assert(M[3] == 'A');
    assert(M[4] == 'A');
    assert(M[5] == 'A');

    M.assign(2, 4, 'B');
    // M.print(); // [1:'B']
    expected_map = { {1,'B'} };
    assert(M.m_map == expected_map);

    M.assign(-2, 1, 'C');
    // M.print(); // [-2:'C'][1,'B']
    expected_map = { {-2,'C'}, {1,'B'} };
    assert(M.m_map == expected_map);

    // MARK: M1

    // std::cout << "MARK: M1" << std::endl;

    map_t M1{'A'};

    M1.assign(0, 0, 'A');
    // M1.print();
    expected_map = {};
    assert(M1.m_map == expected_map);

    // MARK: M2

    // std::cout << "MARK: M2" << std::endl;

    map_t M2{'A'};

    M2.assign(3, 5, 'B');
    // M2.print(); // [3:B]
    expected_map = { {3,'B'} };
    assert(M2.m_map == expected_map);

    M2.assign(0, 7, 'A');
    // M2.print(); //
    expected_map = {};
    assert(M2.m_map == expected_map);

    // MARK: M3

    // std::cout << "MARK: M3" << std::endl;
    
    map_t M3{ 'a' };

    M3.assign(3, 5, 'b');
    // M3.print(); // [3:b]
    expected_map = { {3, 'b'} };
    assert(M3.m_map == expected_map);

    M3.assign(2, 3, 'c');
    // M3.print(); // [2:c][3:b]
    expected_map = { {2, 'c'}, {3, 'b'} };
    assert(M3.m_map == expected_map);

    M3.assign(2, 3, 'd');
    // M3.print(); // [2:d][3:b]
    expected_map = { {2, 'd'}, {3, 'b'} };
    assert(M3.m_map == expected_map);

    M3.assign(2, 4, 'e');
    // M3.print(); // [2:e]
    expected_map = { {2, 'e'} };
    assert(M3.m_map == expected_map);

    M3.assign(4, 18, 'f');
    // M3.print(); // [2:e][4:f]
    expected_map = { {2, 'e'}, {4, 'f'} };
    assert(M3.m_map == expected_map);

    M3.assign(2, 8, 'g');
    // M3.print(); // [2:g]
    expected_map = { {2, 'g'} };
    assert(M3.m_map == expected_map);

    M3.assign(0, 10, 'a');
    // M3.print(); // 
    expected_map = {};
    assert(M3.m_map == expected_map);

    M3.assign(0, 20, 'a');
    // M3.print(); // 
    expected_map = {};
    assert(M3.m_map == expected_map);

    M3.assign(0, 30, 'a');
    // M3.print(); // 
    expected_map = {};
    assert(M3.m_map == expected_map);

    M3.assign(0, 1, 'a');
    // M3.print(); //
    expected_map = {};
    assert(M3.m_map == expected_map);

    // MARK: M4

    // std::cout << "MARK: M4" << std::endl;

    map_t M4{'A'};
    for (int i=0; i < 1000000; i++)
    {
        M4.assign(i, i+1, i % 2 == 0 ? 'A' : 'B');
        M4.assign(i, i-1, i % 2 == 0 ? 'A' : 'B');
        M4.assign(i+1, i, i % 2 == 0 ? 'A' : 'B');
        M4.assign(i-1, i, i % 2 == 0 ? 'A' : 'B');
        M4.assign(i+1, i+1, i % 2 == 0 ? 'A' : 'B');
        M4.assign(i+1, i-1, i % 2 == 0 ? 'A' : 'B');
        M4.assign(i-1, i+1, i % 2 == 0 ? 'A' : 'B');
        M4.assign(i-1, i-1, i % 2 == 0 ? 'A' : 'B');

        M4.assign(i, i+1, i % 2 == 0 ? 'B' : 'A');
        M4.assign(i, i-1, i % 2 == 0 ? 'B' : 'A');
        M4.assign(i+1, i, i % 2 == 0 ? 'B' : 'A');
        M4.assign(i-1, i, i % 2 == 0 ? 'B' : 'A');
        M4.assign(i+1, i+1, i % 2 == 0 ? 'B' : 'A');
        M4.assign(i+1, i-1, i % 2 == 0 ? 'B' : 'A');
        M4.assign(i-1, i+1, i % 2 == 0 ? 'B' : 'A');
        M4.assign(i-1, i-1, i % 2 == 0 ? 'B' : 'A');
    }

    const auto end = std::chrono::steady_clock::now();
    const std::chrono::duration<double> elapsed_seconds = end - start;
    std::cout << "abcMap elapsed time: " << elapsed_seconds.count() << std::endl;
}