fork(58) download
copy 
  1. #include <assert.h>
  2. #include <map>
  3. #include<iostream>
  4. #include <limits>
  5.  
  6. using namespace std;
  7.  
  8. template<class K, class V>
  9. class interval_map {
  10.     friend void IntervalMapTest();
  11.  
  12. private:
  13.     std::map<K,V> m_map;
  14.  
  15. public:
  16.     // constructor associates whole range of K with val by inserting (K_min, val)
  17.     // into the map
  18.     void print_map()
  19.     {
  20.     	 typedef typename std::map<K,V>::iterator MapIterator;
  21.      for (MapIterator itr = m_map.begin(); itr != m_map.end(); ++itr)
  22.      std::cout << itr->first << ':' << itr->second << '\n';
  23.      std::cout << std::endl;
  24.     }
  25.     interval_map( V const& val) {
  26.         m_map.insert(m_map.begin(),std::make_pair(std::numeric_limits<unsigned int>::min(),val));
  27.     };
  28.  
  29.     // Assign value val to interval [keyBegin, keyEnd).
  30.     // Overwrite previous values in this interval.
  31.     // Do not change values outside this interval.
  32.     // Conforming to the C++ Standard Library conventions, the interval
  33.     // includes keyBegin, but excludes keyEnd.
  34.     // If !( keyBegin < keyEnd ), this designates an empty interval,
  35.     // and assign must do nothing.
  36.     void assign( K const& keyBegin, K const& keyEnd, const V& val ) {
  37. // INSERT YOUR SOLUTION HERE
  38.      // On encountering empty interval, assign must do nothing
  39.        typedef typename std::map<K,V>::iterator MapIterator;
  40.        MapIterator it = m_map.find(keyEnd);
  41.        if (it == m_map.end() && it->second == val)
  42.        return;
  43. for(K kitr=keyBegin;kitr<keyEnd;kitr++)
  44. {
  45.  auto ret = m_map.insert(make_pair(kitr, val));
  46.     if (!ret.second){
  47.         m_map[kitr] = val;
  48.     }
  49. }
  50.  
  51.                                                                     }
  52.     // look-up of the value associated with key
  53.     V const& operator[]( K const& key ) const {
  54.         return ( --m_map.upper_bound(key) )->second;
  55.     }
  56. };
  57.  
  58. // Many solutions we receive are incorrect. Consider using a randomized test
  59. // to discover the cases that your implementation does not handle correctly.
  60. // We recommend to implement a function IntervalMapTest() here that tests the
  61. // functionality of the interval_map, for example using a map of unsigned int
  62. // intervals to char.
  63.  
  64. void IntervalMapTest() {
  65.     interval_map<unsigned int,char> test_map('a');
  66.     //test corner cases
  67.     test_map.assign(1, 4, 'b');
  68.     test_map.print_map();
  69.     test_map.assign(2, 3, 'c');
  70.    test_map.print_map();
  71.     test_map.assign(std::numeric_limits<unsigned int>::min(), 5, 'a');
  72.     test_map.print_map();
  73.     //print_map();
  74.     test_map.assign(1, 2, 'a');
  75.     test_map.print_map();
  76.     //print_map();
  77.     test_map.assign(1, 3, 'b');
  78.     test_map.print_map();
  79.     //print_map();
  80.     test_map.assign(2, 4, 'a');
  81.     test_map.print_map();
  82.     //print_map();
  83.     test_map.assign(0, std::numeric_limits<unsigned int>::max() + 1, 'b');
  84.     test_map.print_map();
  85.     test_map.assign(-1, 0, 'b');
  86.     test_map.print_map();
  87.     //print_map();
  88.  
  89.     //test random
  90.     test_map.assign(std::numeric_limits<unsigned int>::min(),
  91.             std::numeric_limits<unsigned int>::max(), 'a');
  92. test_map.print_map();
  93.   //  srand (time(NULL));
  94.  
  95.  
  96. }
  97.  
  98. int main(int argc, char* argv[]) {
  99.  
  100.     IntervalMapTest();
  101.     return 0;
  102. }
  103. #include <iostream>
  104. using namespace std;
  105.  
  106. int main() {
  107. 	// your code goes here
  108. 	return 0;
  109. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp: In function 'int main()':
prog.cpp:106:10: error: conflicting declaration of C function 'int main()'
 int main() {
          ^
prog.cpp:98:5: note: previous declaration 'int main(int, char**)'
 int main(int argc, char* argv[]) {
     ^
stdout
copy 
Standard output is empty
https://ideone.com/5rBI2L
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!