How to define assign member function in map ?

I got the following task with limited time for submission, so far I have done the solution but not sure is there anything wrong what must be corrected before I submit, please help me out. Sorry for detail task description.

Task Description

interval_map<K,V> is a data structure that efficiently associates intervals of keys of type K with values of type V. 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. 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++1x draft standard here: "Here other file I didn't paste"

Each key-value-pair (k,v) in the m_map member means that the value v is associated to the interval from k (including) to the next key (excluding) in m_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<key>::max()

The representation in m_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.

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:

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125

#include <assert.h>
#include <map>
#include <limits>
#include <iostream> // I added this was not given am I doing right ?

using namespace std;

template<class K, class V>
class interval_map {
    friend void IntervalMapTest();

private:
    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.begin(),std::make_pair(std::numeric_limits<K>::lowest(),val));
    }

    // Assign value val to interval [keyBegin, keyEnd). 
    // Overwrite previous values in this interval. 
    // Do not change values outside 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 ) {

 // My code strats

if(!(keyBegin < keyEnd))
    return;
    
 //int  it;
 
 //std::map<std::string, int>::iterator it =  m_map.insert();
 
	typename std::map<K,V>::iterator it =m_map.begin();


  for(int j=keyBegin; j<keyEnd; j++)
  {
    it = m_map.find(j);

    if(it==m_map.end())
    {
      m_map.insert(pair<K,V>(j,val));
    }
    else
    { 
      m_map.erase(it);
      m_map.insert(pair<K,V>(j, val));
    }
  }
//end of my code

 }



    // look-up of the value associated with key
    V const& operator[]( K const& key ) const {
        return ( --m_map.upper_bound(key) )->second;
    }


// my code again
void IntervalMapTest()
      {
      
           std::map<char,unsigned int> m_map;
  char c;

  m_map ['A']=0;
  m_map ['A']=1;
  m_map ['A']=2;

  for (c='A'; c<'B'; c++)
  {
    std::cout << c;
    if (m_map.count(c)>0)
      std::cout << " is an element of mymap.\n";
    else 
      std::cout << " is not an element of mymap.\n";
  }
     
      }
//me code ends



};

// 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 function IntervalMapTest() here that tests the
// functionality of the interval_map, for example using a map of unsigned int
// intervals to char.

int main() {

// given IntervalMapTest();

// What I did starts

interval_map <char, unsigned int> test1 ('K');
     
    // instantiation with float and char type
    
 interval_map <unsigned int, char> test2 (5);  
    
    test1.IntervalMapTest();
    
     test2.IntervalMapTest();
    
// What I did ends
    
}
Last edited on
Line 41 assumes that K and V are std::string and int respectively.

Your loop from lines 45-58 may work but it won't leave the map in canonical order. Also,
if you ad an interval from, say 1 to 3 billion, it's going to take a while to insert all 3 billion entries. It seems to me that the point of this exercise is to insert just one entry.

Here's my initial thought on how to approach assign().

If necessary, adjust the map so the interval ending at KeyBegin is correct.
If necessary, adjust the map so the interval beginning at KeyEnd is correct.
Remove existing intervals in the range [KeyBegin, KeyEnd)
Insert the new range for [KeyBegin, KeyEnd)
Finally, canonicalize it: if the range before and/or after [KeyBegin, KeyEnd) has the same value as the new range, then combine them.

As I type this, it occurs to me that for the last part, you might actually start by checking the current value for KeyBegin is equal to the value being inserted. If so, change KeyBegin to be the beginning of the existing range. Do the same with KeyEnd. Now you're guaranteed that the result will be canonical.

Note that the point here is to start by figuring out how to do this on paper. Don't start writing code until you have figured out the algorithm.
Thanks a lot for the reply, actually it would be very kind if anyone can help me out by providing corrected code on existing one since running out of time to figure out by myself, I am sorry for making such a request.
> not sure is there anything wrong what must be corrected before I submit
It seems that you quite misunderstood the assignment.
«We recommend to implement a function IntervalMapTest() here that tests the functionality of the interval_map»
however your `IntervalMapTest()' member (¿?) function makes no mention to the `interval_map' class or any of its members, and such, you had missed flagrant errors like m_map.insert() (glad that you fixed it)
I would expect something like
1
2
3
4
5
6
interval_map<int, std::string> m("foo");
m.assign(2,5) = "hello";
m.assign(7,9) = "world";
for K in range[0, 10:
   print(m[K])
//more intervals and printing 
(they actually suggest a randomized test, but start here. also, think some corner cases)

«Key type K does not implement any other operations, in particular no equality comparison or arithmetic operators»
and yet you do for(int j=keyBegin; j<keyEnd; j++)
as dhayden said, you are not supposed to insert every number in the interval
and `int' is not good enough to hold whatever a key may be.

Look at the example you were given
To represent the intervals
1
2
3
4
[-inf, 0) -> default
[0, 3) -> 'A'
[3, 5) -> 'B'
[5, +inf] -> 'A'
the map only needs to be std::map (0,'A'), (3,'B'), (5,'A')
just three elements.

Let's say that you want to insert the interval [1,2) -> 'x'
first, realise that it goes inside the interval [0, 3), so that will be broken in
1
2
3
[0, 1) -> 'A'
[1, 2) -> 'x'
[2, 3) -> 'A'
to do that, you insert into the map
1
2
m[1] = 'x'; //note, m[keyBegin] = val
m[2] = 'A'; //note, m[keyEnd] = ¿how do you obtain the `A' value? 


suppose that you want to insert [4, 7) -> 'o'
that's between [3, 5) and [5, +inf] and would end
1
2
3
[3, 4) -> 'B'
[4, 7) -> 'o'
[7, +inf) -> 'A'
so you need to do
1
2
3
m[4] = 'o' //again, m[keyBegin] = val
m[7] = 'A' //again, m[keyEnd] = ¿how do you obtain the `A' value?
m.erase(5) //delete everything that's between [keyBegin, keyEnd). look at lower_bound() and upper_bound() 



> help me out by providing corrected code on existing one since running out of
> time to figure out by myself
if you can't do it in the time limit, then fail the assignment
don't worry too much about it.
Last edited on
Registered users can post here. Sign in or register to post.