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 回答