This was the original content that frek overwrote in the first post.
I don't remember what the original thread title was.
interval_map<K,V> 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<K, V> is implemented on top of std::map. For more information on std::map, you may refer to cppreference.com.
Each keyvaluepair (k,v) in interval_map<K,V>::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<K,V>::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<int,char> where
M.m_valBegin=='A',
M.m_map=={ (1,'B'), (3,'A') },
then M represents the mapping
...
2 > 'A'
1 > 'A'
0 > 'A'
1 > 'B'
2 > 'B'
3 > 'A'
4 > 'A'
5 > 'A'
...
The representation in the std::map must be canonical, that is, consecutive map entries must not contain the same value: ..., (3,'A'), (5,'A'), ... 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<K,V> data structure.
Key type K
besides being copyable and assignable, is lessthan comparable via operator<
does not implement any other operations, in particular no equality comparison or arithmetic operators
Value type V
besides being copyable and assignable, is equalitycomparable via operator==
does not implement any other operations
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

#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)
: m_valBegin(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 ) {
// PUT YOUR CODE HERE
}
// lookup 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 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.
 
This was his attempt:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

void assign(K const& keyBegin, K const& keyEnd, V const& val) {
// !(keyBegin < keyEnd) indicates an empty interval, so the function simply returns
if (!(keyBegin < keyEnd)) return;
// Search for the lower bound of keyBegin to see if the container includes the keyBegin
auto beginIter = m_map.lower_bound(keyBegin);
if (beginIter>first != keyBegin) {
// the container doesn't already contain an element with an
// equivalent key, so insert the element into the container
beginIter = m_map.insert(beginIter, std::pair<K, V>(keyBegin, val));
// The element at begin_iter already has the correct the value
++beginIter;
}
// Search for the lower bound of keyEnd and use it as the
// exclusive upper boundary
auto endIter = m_map.lower_bound(keyEnd);
// Overwrite previous values within the range [beginIter, endIter)
while (beginIter != endIter) {
beginIter>second = val;
++beginIter;
}
}
 