2

I'm trying to make my own map implementation. MyMap.h :

#pragma once

#include <set>
#include <list>
#include <utility>

template <class Key, class Value> class MyMap
{
public:
    MyMap();
    ~MyMap();
    int count(Key&);
    Value& operator[](Key&);
private:
    std::set<Key> m_keys;
    std::list<std::pair<Key, Value*> > m_kvList;
};

MyMap.cpp

#include "stdafx.h"
#include "MyMap.h"

MyMap<class Key, class Value>::MyMap()
{

}


MyMap<class Key, class Value>::~MyMap()
{

}

int MyMap<class Key, class Value>::count(Key& k)
{
    if (m_keys.find(k) != m_keys.end())
        return 1;
    return 0;
}

Value& MyMap<class Key, class Value>::operator[](Key& k)
{
    if (count(k) == 0)
    {
        m_keys.insert(k);
        Value* pValue;
        std::pair<Key, Value*> kvPair(k, pValue);
        m_kvList.push_back(kvPair);
        return *pValue;
    }
    std::list<std::pair<Key, Value*> >::const_iterator it;
    for (it = m_kvList.begin(); it != m_kvList.end(); it++)
    {
        if ((*it).first == k)
            return *(*it).second;
    }
}

main code cpp

#include "stdafx.h"
#include <iostream>
#include <string>
#include "MyMap.h"

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
    MyMap<int, int> m1;
    m1[3] = 60;
    m1[1] = 30;
    m1[2] = 95;
    return 0;
}

The problem is in the assignment of the values in the map, it tells me

no operators "[]" matches these operands. operand types are MyMap<int, int> [int]

I don't really understand what's wrong with what I wrote because the overloading of the [] operator takes a Key and the Key in this example is set as int and so I pass an int value to the [] operator and the compiler still complains.

dikson231
  • 201
  • 5
  • 10
  • 2
    You need to take keys by `const` reference: `Value& operator[](const Key&);`. Non-const lvalue references cannot bind to rvalues. – juanchopanza Oct 09 '14 at 15:45
  • 2
    My eyes may be bad, but how is that `operator[]` going to work if you return a dereferenced uninitialized pointer `pValue`? – PaulMcKenzie Oct 09 '14 at 15:51
  • I think you have a design problem: You're currently using the `set` only to guarantee uniqueness, as it seems. Then, you use a `list` to store the actual key/value pairs. This has O(N) complexity for access, so your data structure is more like a unique list then a map. – dyp Oct 09 '14 at 15:53
  • juachopanza didn't know about this thanks for letting me know, PaulMcKenzie thanks didn't notice this, dyp I have to use set in my implementation so what would you suggest me to do ? – dikson231 Oct 09 '14 at 15:56
  • @dikson231 - When your map class needs to implement a `find`, how are you going to search? Is it by using the `list` inspecting each pair until you find the item? If so, then what you have is not a map. – PaulMcKenzie Oct 09 '14 at 15:58
  • @PaulMcKenzie See the `for` loop in `operator[]`. – dyp Oct 09 '14 at 15:58
  • 2
    You can use `std::set` to implement a `map`, though I don't quite understand the point of doing so: you can write a custom key/value pair struct, and provide a custom comparator that only compares the keys of two such struct objects. – dyp Oct 09 '14 at 15:59
  • @dyp - `See the for loop in operator` Then what you have is not a map in terms of complexity. If I load your map with 1,000 items, it should take no more than 10 attempts to find the item. – PaulMcKenzie Oct 09 '14 at 16:01
  • @PaulMcKenzie This is exactly what I meant in my [earlier comment](http://stackoverflow.com/questions/26282616/map-implementation#comment41237201_26282616). – dyp Oct 09 '14 at 16:01
  • 1
    @dikson231 Also note implementation in a separate `.cpp` file won't work: [Why can templates only be implemented in the header file?](http://stackoverflow.com/questions/495021/why-can-templates-only-be-implemented-in-the-header-file) – πάντα ῥεῖ Oct 09 '14 at 16:03
  • @dyp - Sorry, meant the comment for dikson231. – PaulMcKenzie Oct 09 '14 at 16:04
  • @PaulMcKenzie I don't know what definition of "map" you are using, but a map is just an abstract data type associating a key with a value, where each key can appear at most once. This is indeed a map, albeit one that will perform terribly. – cdhowie Oct 09 '14 at 16:08
  • @πάνταῥεῖ thanks for the correction. dyp I need to implement it with a set unfortunately this is what I'm being asked to do so no work arounds. PaulMcKenzie just so I would know, what would you do then if you need to implement find() ? – dikson231 Oct 09 '14 at 17:04
  • @cdhowie The complexity guarantees are part of the definition of list, map vector, etc under C++. If he's trying for an alternative implementation of map I would assume that includes the complexity and iterator validity guarantees, unless specifically told otherwise. Element insert, find, and remove must be amortized O(log(N)) for a C++ map – Speed8ump Oct 09 '14 at 17:20
  • I recommend you use a *Red/Black* tree or minimally a Binary Search Tree. – Thomas Matthews Oct 09 '14 at 17:21
  • If you are allowed to use `std::set`, then consider using `std::set,...>` instead. You'll need to provide a comparison function in that `...` part, which I leave as an exercise to the reader :) – Speed8ump Oct 09 '14 at 17:26
  • @Speed8ump For the `std::map` type, yes. For the general "map" data structure, no. I think it's pretty clear here that he is trying to implement a map, as in the general data structure concept, solely for practice. – cdhowie Oct 09 '14 at 17:45

0 Answers0