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 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 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::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 <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
}
have you solved this ?
RépondreSupprimer