Untitled

#include <map>
#include <iostream>

using namespace std;

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
	template<typename V_forward>
	interval_map(V_forward&& val)
	: m_valBegin(std::forward<V_forward>(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.
	// 1 operation Log(n) - Rest O(1) - use forward
	template<typename V_forward>
	void assign( K const& keyBegin, K const& keyEnd, V_forward&& val )
		requires (std::is_same<std::remove_cvref_t<V_forward>, V>::value)
	{
        if (!(keyBegin < keyEnd)) return;

        auto itBegin=m_map.lower_bound(keyBegin);
        
		auto itEnd=m_map.upper_bound(keyEnd);
		V oldVal = m_valBegin;
		if(itEnd!=m_map.begin()) {
			oldVal = (--itEnd)->second;
		}
		m_map.insert(std::pair<K,V>(keyEnd, oldVal));
		
		//m_map.erase(itBegin, itEnd);
        m_map.insert(std::pair<K,V>(keyBegin, val));
        m_map.insert(std::pair<K,V>(keyEnd, oldVal));
	}

	// 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 p : m_map) {
            cout << "{" << p.first << ", " << p.second << "}, ";
        }
        cout << endl;
	}
};

// lower_bound: Returns an iterator pointing to the first element in the container whose key is not considered to go before k (i.e., either it is equivalent or goes after).
// An iterator to the the first element in the container whose key is not considered to go before k, or map::end if all keys are considered to go before k.


// upper_bound : Returns an iterator pointing to the first element in the container whose key is considered to go after k.
// An iterator to the the first element in the container whose key is considered to go after k, or map::end if no keys are considered to go after k.

// 

// Many solutions we receive are incorrect. Consider using a randomized test
// to discover the cases that your implementation does not handle correctly.
// We recommend to implement a test function that tests the functionality of
// the interval_map, for example using a map of int intervals to char.

void IntervalMapTest() {
    interval_map<int, char> internalMap('a');
    internalMap.print();
    internalMap.assign(1, 3, 'b');
    internalMap.print();
    internalMap.assign(-3, 7, 'c');
    internalMap.print();
    cout << endl; 
}

int main()
{
 IntervalMapTest();
 return 0;
}