CODEWITHSUNDEEP
c++dictionarystl
Matei Florescu
Matei Florescu

Reputation: 1195

Cannot understand behavior of STL map

I have a STL map declared like this:

std::map< std::pair<int, int>, long long> m;

If I do: 

m.insert( make_pair( make_pair(1,1), 1000ll ));

followed by:

cout << m[make_pair(1,1)] << endl;

it writes 0 at the terminal.

However:

m[make_pair(1,1)] = 1000ll;

works fine.

As I know, the first way of inserting elements in a map is the recommended one. What am I missing?

EDIT:

#include <vector>
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
using namespace std;

long long max_partition(    vector<long long> numbers, int numbers_size, int partition_number, map<pair<int, int>, long long> &subproblems)
{
    long long v = subproblems[make_pair(numbers_size, partition_number)];
    if( v ){
        cout << "SP" << endl;
        return v;
    }

    if(partition_number == 1) {
        long long s = accumulate(numbers.begin(), numbers.begin() + numbers_size, 0ll);
        subproblems.insert(make_pair( make_pair(numbers_size, partition_number), s) ); 
        return s;
    }

    if(numbers_size == 0) {
        subproblems.insert(make_pair( make_pair(numbers_size, partition_number), numbers[0])); 
        return numbers[0];
    }

    long long max_p = 500 * 10000000l;

    for(int i = partition_number - 1; i < numbers_size; i++) {
        long long acc = accumulate(numbers.begin() + i, numbers.begin() + numbers_size, 0ll) ;  
        long long mp = max_partition(numbers, i, partition_number - 1, subproblems);
        max_p = min(max_p, max(mp, acc));
    }

    subproblems.insert(make_pair( make_pair(numbers_size, partition_number), max_p) ); 
    //subproblems[make_pair(numbers_size, partition_number)] = max_p;
    return max_p;
}


int main(int argc, char **argv)
{
    map<pair<int, int>, long long> subproblems;
    long long arr[] = {50, 50, 50, 50, 50}; //, 40, 50};
    vector<long long> p(arr, arr + 5);
    max_partition(p, 5, 4, subproblems);

    map<pair<int, int>, long long>::iterator it;

    for(it = subproblems.begin(); it != subproblems.end(); it++)
        cout << "val: " << it->second << endl;


    return 0;
}

Upvotes: 0

Views: 130

Answers (1)

David Rodr&#237;guez - dribeas
David Rodr&#237;guez - dribeas

Reputation: 208323

The beginning of your function already inserts the element into the map (operator[] will insert the element for you if it did not exist before):

long long v = subproblems[make_pair(numbers_size, partition_number)];

You later try to insert the element again with:

subproblems.insert(make_pair( make_pair(numbers_size, partition_number), max_p) );

But that insert fails, as the element already exists, and the contract of std::map<>::insert is that if it is already there it will be left untouched.

The first check seems to be attempting to test whether the element was present in the map before the call to this function, if that is the case, you can use find:

iterator it=subproblems.find(make_pair(numbers_size,partition_number));
if (it != subproblems.end()) {
   return it->second;
}

Although that will require a second lookup when you do the real insert. An alternative is to directly attempt the insert in the beginning, and using the result to test whether the element already existed and as the iterator to use:

pair<iterator,bool> r = subproblems.insert(
                           make_pair(make_pair(numbers_size,partition_number),0));
if (!r.second) {             // existed before
    return r.first->second;  // return that value
}
...
r.first->second = numbers[0]; // replaces the insert in your code

Upvotes: 4

Related Questions