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

Question

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.

Your error doesn't match your code.

T.C.
– T.C.

2015-06-19 16:52:03 +00:00
Commented Jun 19, 2015 at 16:52 — T.C.
– T.C., Commented Jun 19, 2015 at 16:52

sebhtml · Accepted Answer · 2015-06-19 16:53:54Z

2

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.

answered Jun 19, 2015 at 16:53

sebhtml

513 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

SirParselot · Accepted Answer · 2015-06-19 16:51:25Z

1

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

answered Jun 19, 2015 at 16:51

SirParselot

2,6532 gold badges23 silver badges32 bronze badges

3 Comments

Ami Tavory Over a year ago

That makes sense. However, why is the OP getting the error?

AliciaBytes Over a year ago

I'd recommend map.find() if you need the iterator to the element and map.count() if you only want to know if the key exists.

SirParselot Over a year ago

Doesn't OP need to set the iterator to the beginning of the map?

Sergey Kalinichenko · Accepted Answer · 2015-06-19 16:57:40Z

1

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.

edited Jun 19, 2015 at 16:57

answered Jun 19, 2015 at 16:52

Sergey Kalinichenko

729k85 gold badges1.2k silver badges1.6k bronze badges

1 Comment

user2249683 Over a year ago

A nice trick, not described well. The operator [] might be nasty in other situations.

MisterC · Accepted Answer · 2015-06-19 16:52:49Z

0

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.

answered Jun 19, 2015 at 16:52

MisterC

2491 silver badge5 bronze badges

Collectives™ on Stack Overflow

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

4 Answers 4

Comments

3 Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

3 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related