interval_map<K, V> is implemented on top of std::map. In case you are not entirely sure which functions std::map provides, what they do and which guarantees they provide, we provide an excerpt of the C++ standard here:

Each key-value-pair (k,v) in the std::map means that the value v is associated with the interval from k (including) to the next key (excluding) in the std::map.

Example: the std::map (0,'A'), (3,'B'), (5,'A') represents the mapping

0 -> 'A'

1 -> 'A'

2 -> 'A'

3 -> 'B'

4 -> 'B'

5 -> 'A'

6 -> 'A'

7 -> 'A'

... all the way to numeric_limits<int>::max()

The representation in the std::map must be canonical, that is, consecutive map entries must not have the same value: ..., (0,'A'), (3,'A'), ... is not allowed. Initially, the whole range of K is associated with a given initial value, passed to the constructor of the interval_map<K,V> data structure.

Key type K

besides being copyable and assignable, is less-than comparable via operator<

is bounded below, with the lowest value being std::numeric_limits<K>::lowest()

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

Value type V

besides being copyable and assignable, is equality-comparable via operator==

does not implement any other operations

You are given the following source code:

#include <map> #include <limits> template<typename K, typename V> class interval_map { std::map<K,V> m_map; public: // constructor associates whole range of K with val by inserting (K_min, val) // into the map interval_map( V const& val) { m_map.insert(m_map.end(),std::make_pair(std::numeric_limits<K>::lowest(),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 ) {