为什么这个程序会报错？

Question

#include<vector>
#include<list>
#include<string>
#include<iostream>
#include<numeric>
#include<set>
#include<algorithm>
#include<map>
#include<utility>
#include<unordered_map>
#include<unordered_set>
using namespace std;

/*
题目是Leetcode算法题（1655，分配不同整数）
报错表述：can't dereference value-initialized vector iterator 
程序在我标明处崩了，但我不知道为什么？
但暂且我可以确定，if_dte()这个函数是没有问题的
*/

bool if_dte(vector<int> nums, int way, int demend) {
        set<int> st;
        multiset<int> set;

        for (int i = 0; i < nums.size(); i++) {
            if ((1 << i & way) == 0) continue;
            set.insert(nums[i]);
            st.insert(nums[i]);
        }

        vector<int> tmp;
        for (auto it = st.begin(); it != st.end(); it++) {
            tmp.push_back(set.count(*it));
        }

        return (*max_element(tmp.begin(), tmp.end())) >= demend;
    }

    bool canDistribute(vector<int>& nums, vector<int>& quantity) {
        int n = nums.size();
        
        vector<vector<bool>> dp(quantity.size(), vector<bool>(1 << n, false));

        system("pause");
        dp[0][0] = if_dte(nums, 3, quantity[0]);
        system("pause");
        //我知道问题就出在这个循环，但不知道为什么真的太奇怪了///////////////////////////////////////////////////
        for (int j = 0; j < (1 << n); j++) {
            dp[0][j] = if_dte(nums, j, quantity[0]);
        }
        system("pause");

        for (int j = 0; j < (1 << n); j++) cout << "dp[0][" << j << "]=" << dp[0][j] << endl;

        for (int i = 0; i < quantity.size(); i++) {
            for (int j = 0; j < (1 << n); j++) {
                dp[i][j] = false;
                for (int s = 0; s <= j; s++) {
                    if ((s | j) != j) continue;
                    dp[i][j] == dp[i][j] || (dp[i - 1][j - s] && if_dte(nums, s, quantity[i]));
                }
            }
        }


        return dp[quantity.size() - 1][1 << n];

    }

int main() {


	vector<int> t1 = { 1,2,2,4,4,4 };
	vector<int> t2 = { 2,1 };
	cout << s.canDistribute(t1, t2);
	return 0;
}

Answer 1

 

问题在函数if_dte里。我加了一些打印语句跟踪，在第二次调用改函数的时候vector tmp是空的，但是函数返回语句求最大值后试图dereference出错。可以先检测是否为空，为空时返回false:  return tmp.size() > 0 && (*max_element(tmp.begin(), tmp.end())) >= demend;。

另外函数 canDistribute返回语句 return dp[quantity.size() - 1][1 << n] 也会数组越界，应该 return dp[quantity.size() - 1][(1 << n) -1]; 

#include<vector>
#include<list>
#include<string>
#include<iostream>
#include<numeric>
#include<set>
#include<algorithm>
#include<map>
#include<utility>
#include<unordered_map>
#include<unordered_set>
using namespace std;
/*
题目是Leetcode算法题（1655，分配不同整数）
报错表述：can't dereference value-initialized vector iterator 
程序在我标明处崩了，但我不知道为什么？
但暂且我可以确定，if_dte()这个函数是没有问题的
*/
bool if_dte(vector<int> nums, int way, int demend) {
        cout << "if_dte begin: way = " << way << ", demend = " << demend << endl;
        set<int> st;
        multiset<int> set;
        for (int i = 0; i < nums.size(); i++) {
            cout << "if_dte: i = " << i << endl;
            if ((1 << i & way) == 0) continue;
            cout << "inserting nums[" << i <<"] " << nums[i] << " into both set and mulset" << endl;
            set.insert(nums[i]);
            st.insert(nums[i]);
        }
        cout << "if_dte: vector tmp" << endl;
        vector<int> tmp;
        for (auto it = st.begin(); it != st.end(); it++) {
            cout << "*it = " << *it << ", set.count(*it): " << set.count(*it) << endl;
            tmp.push_back(set.count(*it));
        }
        cout << "tmp.size(): " << tmp.size() << endl;
        return (*max_element(tmp.begin(), tmp.end())) >= demend;
    }
bool canDistribute(vector<int>& nums, vector<int>& quantity) {
        int n = nums.size();
        vector<vector<bool>> dp(quantity.size(), vector<bool>(1 << n, false));
        cout << "dp size: " << quantity.size() << ", " << (1 << n) << endl;
        //system("pause");
        dp[0][0] = if_dte(nums, 3, quantity[0]);
        //system("pause");
        //我知道问题就出在这个循环，但不知道为什么真的太奇怪了///////////////////////////////////////////////////
        for (int j = 0; j < (1 << n); j++) {
            cout << "Accessing dp[0][" << j << "]" << endl;
            dp[0][j] = if_dte(nums, j, quantity[0]);
        }
        system("pause");
        for (int j = 0; j < (1 << n); j++) cout << "dp[0][" << j << "]=" << dp[0][j] << endl;
        for (int i = 0; i < quantity.size(); i++) {
            for (int j = 0; j < (1 << n); j++) {
                cout << "setting dp[" << i << "][" << j << "] as false" << endl;
                dp[i][j] = false;
                for (int s = 0; s <= j; s++) {
                    if ((s | j) != j) continue;
                    cout << "setting dp[" << i << "][" << j << "] or" << endl;
                    cout << "reading dp[" << i - 1 << "][" << j - s << "]" << endl;
                    dp[i][j] == dp[i][j] || (dp[i - 1][j - s] && if_dte(nums, s, quantity[i]));
                }
            }
        }
 
        cout << "returning dp[" << quantity.size() - 1 << "][" << (1 << n) - 1 << "]" << endl;
        return dp[quantity.size() - 1][(1 << n) - 1];
    }
int main() {
 
	vector<int> t1 = { 1,2,2,4,4,4 };
	vector<int> t2 = { 2,1 };
	cout << canDistribute(t1, t2);
	return 0;
}
 
// Output
dp size: 2, 64                                                                                                                                                                       
if_dte begin: way = 3, demend = 2                                                                                                                                                    
if_dte: i = 0                                                                                                                                                                        
inserting nums[0] 1 into both set and mulset                                                                                                                                         
if_dte: i = 1                                                                                                                                                                        
inserting nums[1] 2 into both set and mulset                                                                                                                                         
if_dte: i = 2                                                                                                                                                                        
if_dte: i = 3                                                                                                                                                                        
if_dte: i = 4                                                                                                                                                                        
if_dte: i = 5                                                                                                                                                                        
if_dte: vector tmp                                                                                                                                                                   
*it = 1, set.count(*it): 1                                                                                                                                                           
*it = 2, set.count(*it): 1                                                                                                                                                           
tmp.size(): 2                                                                                                                                                                        
if_dte finish: max_element(tmp.begin(), tmp.end()) = 1, demend = 2                                                                                                                   
Accessing dp[0][0]                                                                                                                                                                   
if_dte begin: way = 0, demend = 2                                                                                                                                                    
if_dte: i = 0                                                                                                                                                                        
if_dte: i = 1                                                                                                                                                                        
if_dte: i = 2                                                                                                                                                                        
if_dte: i = 3                                                                                                                                                                        
if_dte: i = 4                                                                                                                                                                        
if_dte: i = 5                                                                                                                                                                        
if_dte: vector tmp                                                                                                                                                                   
tmp.size(): 0                                                                                                                                                                        
Segmentation fault (core dumped)