Assignment: interval_map — implement assign Use std::map. Goal: Implement the member function assign for the class template interval_map. The class holds a piecewise-constant mapping from K to V. The internal data structure is: - V m_valBegin; // value for all keys before the first change - std::map m_map; // stores changes of value at certain keys (key -> value starting there) Example representation: For interval_map: M.m_valBegin == 'A' M.m_map == { (1,'B'), (3,'A') } This means the mapping is: key: … -2 -1 0 1 2 3 4 5 … val: A A A B B A A A I.e., values are ‘A’ up to key 1, ‘B’ on [1,3), then back to ‘A’ from 3 onward. You must keep m_map as compact as possible (no redundant entries like ..., (3,'A'), (5,'A'), ... that don’t represent real changes). Constraints: - K must be usable as a key in std::map (requires a strict weak ordering via operator<). - V must be equality-comparable (operator==). Skeleton: #include #include #include template class interval_map { friend void IntervalMapTest(); V m_valBegin; std::map m_map; public: // constructor associates whole range of K with val template interval_map(V_forward&& val) : m_valBegin(std::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. template void assign(K const& keyBegin, K const& keyEnd, V_forward&& val) requires (std::is_same, V>::value) { // TODO: implement } // 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 std::prev(it)->second; } } };
