0

次のように宣言された STL マップがあります。

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

私が行った場合：

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

に続く：

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

端末に 0 を書き込みます。

でも：

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

正常に動作します。

私が知っているように、マップに要素を挿入する最初の方法が推奨される方法です。私は何が欠けていますか？

編集：

#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;
}
4

1 に答える 1

4

関数の先頭では、要素が既にマップに挿入されています (要素operator[]が以前に存在しなかった場合は、要素が挿入されます)。

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

後で要素を再度挿入しようとします：

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

std::map<>::insertしかし、要素が既に存在するため、その挿入は失敗します。また、要素が既に存在する場合はそのままになるという契約があります。

最初のチェックは、この関数の呼び出し前に要素がマップに存在するかどうかをテストしようとしているようです。その場合は、次を使用できますfind。

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

ただし、実際のinsert. 別の方法として、最初に挿入を直接試行し、結果を使用して要素が既に存在するかどうかをテストし、使用する反復子として使用することもできます。

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
于 2013-10-31T20:37:12.203 に答える