Create a dummy data for search in templates

Question

I am trying to implementing a map using vector. I am stuck in the find functionality since I am using a struct with key and value and while searching user will only provide the key and I have to use a dummy in the value field which I currently cannot do since it is a template.

Help is appreciated. :)

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

//coll.insert(std::make_pair("otto",22.3));
using namespace std;

template<class T1, class T2>
class MyMap
{
    protected:
    struct mapNode
    {
        T1 key;
        T2 value;

        //Ctor
        mapNode(T1 t1, T2 t2): key(t1), value(t2)
        {
        }

        //getters
        const T1& first() const
        {
            return key;
        }

        const T2& second() const
        {
            return value;
        }

        //operators
        bool operator==(const mapNode& rhs)const
        {
            return key == rhs.key;
        }

        bool operator<(const mapNode& rhs) const
        {
            return key < rhs.key;
        }

        mapNode& operator=(const mapNode& rhs)
        {
            key = rhs.key;
            value = rhs.value;
        }
    };

    //data
    vector<mapNode> TheMap;

    public:

    void insert(const T1& k, const T2& v)
    {
        mapNode mn(k, v);
        TheMap.push_back(mn);
    }

    int size() const
    {
        return TheMap.size();
    }

    const T1& getKeyAt(int i) const
    {
        return TheMap[i].first();
    }

    const T2& getValueAt(int i) const
    {
        return TheMap[i].second();
    }

    mapNode& find(const T1& key) const
    {
        //create the data type first needed for searching.
        mapNode tmp(key, ); //This is the issue.

        typename vector<mapNode>::const_iterator pos;
        find(TheMap.begin(), TheMap.end(), key);
        //if(pos != TheMap.end() )
            //return *pos;
    }
};

int main()
{
    MyMap<int, string> m_MyMap;
    m_MyMap.insert(1, "abc");
    m_MyMap.insert(2, "def");
    m_MyMap.insert(3, "ghi");

    for(int i = 0; i < m_MyMap.size(); i++)
    {
        cout<<m_MyMap.getKeyAt(i)<<":"<<m_MyMap.getValueAt(i)<<endl;
    }

    m_MyMap.find(2);

    return 0;

}

Why don't you just compare your mapNode.key with the key? I don't think you should create dummy structs. You can do it for example with std::find_if — Melkon, Sep 09 '15 at 09:34
but the find algorithm will expect the struct since that is what the vector contains. — Tanvir, Sep 09 '15 at 09:37
returning the reference to a local variable is not a good idea. See http://stackoverflow.com/questions/6441218/can-a-local-variables-memory-be-accessed-outside-its-scope — Gombat, Sep 09 '15 at 09:40
@Gombat: OP doesn't return reference of local variable, but dereference an iterator. — Jarod42, Sep 09 '15 at 10:08

score 0 · Answer 1 · answered Sep 09 '15 at 10:00

Using find_if is a good idea.

To do so, you need a function or e.g. struct with overloaded members. Add following struct to your class, like you did with mapNode:

struct HasKey
{
public:
  explicit HasKey( const T1& key )
  { m_key = key; }
  inline bool operator()( const mapNode& node ) const
  { return node.first() == m_key; }
private:
  T1 m_key;
};

As i wrote in the comment, it is not a good idea to return the reference to a local variable, so I revised your find method:

T2 find(const T1& key) const
{
  vector<MyMap<T1,T2>::mapNode>::const_iterator it = 
    find_if(TheMap.begin(), TheMap.end(), HasKey( key ) );

  if ( it == TheMap.end() )
    throw std::runtime_error( "The map does not contain searched key!" );
  else
    return it->second();
}

I solved the error part using an exception, which means you need to wrap the find call in a try catch block:

string val;
try 
{ val = m_MyMap.find(2); } 
catch (std::exception &e)
{ std::cout << e.what() << std::endl; return 1; }

std::cout << "Searching for key (" << 2 << ") results in (" << val << ")!" << std::endl;
return 0;

Afaik, I would recommend to return an iterator or const_iterator, so that you can easily check if it points to the end, but this is of course not possible, if the mapNode type is protected and your MyMap would have to provide a end() method returning the iterator or const_iterator the TheMaps end() iterator.

Additionally, your operator= has to return *this at the end to work.

Returning `const T2&` is fine (as long that we don't insert/remove element in vector.) — Jarod42, Sep 09 '15 at 10:10
Right. But I still would recommend to use an iterator since then you don't have need for an exception handling. — Gombat, Sep 09 '15 at 10:14
@Gombat: I have a question here, when we pass a unary predicate to find_if why should we create a separate struct, can we not also write only a function to overload operator(), which approach is the better one, writing the struct or on the operator() function. — Tanvir, Sep 10 '15 at 06:32
@tan: How do you pass the key variable you are searching for to the function? If the function can decide which element you are searching for, it works, but as far as I know, to find a specific value, which is not known to write it into the function as constant, you have to create a struct to pass it. — Gombat, Sep 10 '15 at 07:38

Create a dummy data for search in templates

1 Answers1