#include <iostream>
#include <map>
template<typename K, typename V>
class interval_map {
    friend void IntervalMapTest();
    V m_valBegin;
    std::map<K,V> m_map;
public:
    // constructor associates whole range of K with val
    interval_map(V const& val, K k_range=1000)
    : m_valBegin(val) {
        for(K i=0; i<k_range; ++i)m_map.insert(std::pair<K,V>(i,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 ) {
        K Begin = keyBegin;
        if(Begin < keyEnd) {
            if(Begin < m_map.begin()->first)Begin=m_map.begin()->first;
            auto it_begin = m_map.lower_bound(Begin);
            if(it_begin == m_map.end() || m_map.key_comp()(Begin, (*it_begin).first)) {
                m_map.insert(std::pair<K,V>(Begin, val));
            }else {
                it_begin->second = val;
            }
            if (it_begin != m_map.end())assign((++it_begin)->first, keyEnd, val);
        }
    }

    // look-up of the value associated with key
    V const& operator[]( K const& key ) const {
        auto it=m_map.upper_bound(key);
        if(it==m_map.begin()) {
            return m_valBegin;
        } else {
            return (--it)->second;
        }
    }
    void print() {
        for(auto i : m_map)std::cerr<<"("<<i.first<<","<<i.second<<"),";
        std::cerr<<'\n';
    }
};

int main() {
    interval_map<int, char> m('A', 100);
    m.assign(-10, 50, 'B');
    m.print();
    return 0;
}