CODEWITHSUNDEEP
c++
Argus
Argus

Reputation: 911

How to check if a value exists within a C++ Map

I'm trying to use Dynamic Programming to implement fibonacci. Here's my .h file: 

#ifndef DYNAMICPROGRAMMING_H
#define DYNAMICPROGRAMMING_H
#include <map>

class DynamicProgramming
{
    public:
        DynamicProgramming ();
        ~DynamicProgramming ();
        int Fibonacci(int value);
    private:
};

#endif // DYNAMICPROGRAMMING_H

Here's the relevant part in my .cpp file:

    int DynamicProgramming::Fibonacci(int value)
{
    int result;
    std::map<int,int>fibonacci_storage;
    std::map<int,int>::iterator valueFinder;
    if (value == valueFinder->second){
        return fibonacci_storage[value];
    }

    if (value <= 2 ){
        result = 1;
    } else {
        result = Fibonacci(value - 1) + Fibonacci(value - 2);
    }
    fibonacci_storage.insert(std::pair<int,int>(value,result));
    return result;
}

My error is coming from this line: if (value == valueFinder->second). This is what it says:

could not convert '((DynamicProgramming*)this)->DynamicProgramming::fibonacci_storage.std::map<_Key, _Tp, _Compare, _Alloc>::find [with _Key = int, _Tp = int, _Compare = std::less<int>, _Alloc = std::allocator<std::pair<const int, int> >, std::map<_Key, _Tp, _Compare, _Alloc>::iterator = std::_Rb_tree_iterator<std::pair<const int, int> >, std::map<_Key, _Tp, _Compare, _Alloc>::key_type = int]((*(const key_type*)(& value)))' from 'std::map<int, int>::iterator {aka std::_Rb_tree_iterator<std::pair<const int, int> >}' to 'bool'

It looks to me like this is a very simple error, but I'm not sure what all that stuff means. Can someone help me out, I'd really like to master this language, it seems like it would be very useful.

Upvotes: 2

Views: 21433

Answers (4)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726509

There are several issues with your code.

The biggest one is not syntax, it's the placement of the cache: since fibonacci_storage is a local variable, each recursive invocation of Fibonacci will have its own cache, meaning that there would be no caching at all. You need to move fibonacci_storage into the private: section of your class.

As far as fixing the syntax goes, a common trick used to implement searching of cache is to store the result of [] in a reference, like this:

int DynamicProgramming::Fibonacci(int value)
{
    int &result = fibonacci_storage[value];
    if (result) {
        return result;
    }
    if (value <= 2 ){
        return (result = 1);
    }
    return (result = Fibonacci(value - 1) + Fibonacci(value - 2));
}

Variable result holds a reference to the value inside the map, so when you update it in one of the two assign-return statements the corresponding value inside the map gets updated automatically.

Demo.

Upvotes: 1

sebhtml
sebhtml

Reputation: 51

To check if a key exists in a C++ map, you can use std::map::count. It returns 0 (the key is absent) or 1 (the key is present).

To check if a value exists in a C++ map, I think that you have to iterate over all pairs.

It seems that your question is more about a compilation error though.

There are several issues in the code above.

  • Your iterator valueFinder is not iterating over anything. To iterate, you need to call the begin() method on a map.
  • The variable fibonacci_storage is basically useless because it is not a member of the object and thus there is a different instance of that variable for each call to the Fibonacci method.
  • Technically, you don't have to iterate because the indices of your Fibonacci sequence are the keys in the map, and the values of your Fibonacci sequence are the values in your map.

Upvotes: 2

MisterC
MisterC

Reputation: 249

valueFinder is just an iterator for the type std::map<int,int> that is not associated to any instance of that type.
To associate it to an instance (here fibonacci_storage) you have to assign it to that instance, i.e.

valueFinder = fibonacci_storage.begin();

Finding an element can be done with source

valueFinder = fibonacci_storage.find(value);

where value is the key you are searching for. Now you check if value is in the map:

if( valueFinder != fibonacci_storage.end() )
{
    // value found
}

and you're done.

Upvotes: 0

SirParselot
SirParselot

Reputation: 2700

As far as I know the only way to search through maps values is to iterate through. If you are trying to see if the key exists then you can use 

map.find()

Upvotes: 1

Related Questions