c++ - 无法理解 STL 映射的行为

Question

我有一个这样声明的 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;

工作正常。

据我所知，在 map 中插入元素的第一种方式是推荐的方式。 我错过了什么？

编辑:

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

Answer 1

函数的开头已经将元素插入到 map 中(如果元素之前不存在，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 的契约(Contract)是如果它已经存在，它将保持不变。

第一个检查似乎是在调用此函数之前尝试测试该元素是否存在于 map 中，如果是这样，您可以使用 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