Untitled
unknown
plain_text
a month ago
2.9 kB
8
Indexable
#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; }
Editor is loading...
Leave a Comment