The amount of code you'll need for a correct solution is relatively small, and you'll spend more time thinking than typing. Please provide best solution!

Task Description

interval$\_$map is a data structure that associates keys of type K with values of type V$.$ It is designed to be used efficiently in situations where intervals of consecutive keys are associated with the same value. Your task is to implement the assign member function of this data structure, which is outlined below.

interval$\_$map is implemented on top of std::map. For more information on std::map, you may refer to cppreference.com.

Each key$-$value pair $($k$,$v$)$ in interval$\_$map::m$\_$map means that the value v is associated with all keys from k $($including$)$ to the next key $($excluding$)$ in m$\_$map. The member interval$\_$map::m$\_$valBegin holds the value that is associated with all keys less than the first key in m$\_$map.

Example: Let M be an instance of interval$\_$map where

M$.$m$\_$valBegin$==\text{'}$A$\text{'},$

M$.$m$\_$map$==\{(1,\text{'}$B$\text{'}),(3,\text{'}$A$\text{'})\},$

Then M represents the mapping

$...$

$-2->\text{'}$A$\text{'}$

$-1->\text{'}$A$\text{'}$

$0->\text{'}$A$\text{'}$

$1->\text{'}$B$\text{'}$

$2->\text{'}$B$\text{'}$

$3->\text{'}$A$\text{'}$

$4->\text{'}$A$\text{'}$

$5->\text{'}$A$\text{'}$

$...$

The representation in the std::map must be canonical, that is$,$ consecutive map entries must not contain the same value: $...,(3,\text{'}$A$\text{'}),(5,\text{'}$A$\text{'}),...$ is not allowed. Likewise, the first entry in m$\_$map must not contain the same value as m$\_$valBegin. Initially, the whole range of K is associated with a given initial value, passed to the constructor of the interval$\_$map data structure.

Key type K

supports copy and move construction, as well as copy and move assignment,

is less$-$than comparable via operator$<,$

does not implement any other operations, in particular no equality comparison or arithmetic operators.

Value type V

supports copy and move construction, as well as copy and move assignment,

is equality$-$comparable via operator$==,$

does not implement any other operations.

For using Compiler Output $($GCC $13\mathrm{.}2\mathrm{.}0)$:

You are given the following source code:

#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$)\{$

Here

$\}//$ 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; $\}\}\}$; $//$ Many solutions are incorrect. Consider using a randomized test $//$ to discover the cases that your implementation does not handle correctly. $//$ I recommend to implement a test function that tests the functionality of $//$ the interval$\_$map, for example using a map of int intervals to char.

Task is to implement the function assign. Your implementation is according to the following criteria, in this order:

Type requirements: You must adhere to the specification of the key and value type given above.

Correctness: Your program should produce a working interval$\_$map with the behavior described above. In particular, pay attention to the validity of iterators. It is illegal to dereference end iterators. Consider using a checking STL implementation, such as the one shipped with Visual C$++$ or GCC$.$

Canonicity: The representation in m$\_$map must be canonical.

Running time: Imagine your implementation is part of a library and should therefore be big$-$O optimal:

The assign function should have amortized time complexity of O$($log N$),$ where N is the number of elements in m$\_$map.Minimize the number of copy$-$constructions and copy$-$assignments performed on K and V$.$ Make use of std::forward where applicable.Only one operation may have amortized time complexity of O$($log N$).$ The rest must have amortized time complexity of O$(1).$Given the constraints above, avoid comparing K and V more often than necessary because you don't know how fast these operations are.Otherwise, favor simplicity over minor speed improvements.