samedi 24 mars 2018

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 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

}

1 commentaire: