Initializing a global 2 D array with -1 in C++

user_13403510 0
Viewed 86

I Want to initialize a global 2d array with -1, currently, I'm able to declare a global 2d array and initialize it with -1 in the main function by below approach;

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int dp[10][100];

int knapsack(vector<int>wt,vector<int>val,int w,int n){
    if(w==0 || n==0){
        return 0;
    }
    if(dp[n][w]!=-1){
        return dp[n][w];
    }
    if(wt[n-1]<=w){
        return dp[n][w]=max(val[n-1]+knapsack(wt,val,w-wt[n-1],n-1), knapsack(wt,val,w,n-1))
    }
    else{
        return dp[n][w]=knapsack(wt,val,w,n-1);
    }

}
int main(){
    vector<int>val={60,100,120};
    vector<int>wt={10,20,30};
    int w=60;
    int n=val.size();
    for(int i=0;i<10;i++){
        for(int j=0;j<100;j++){
            dp[i][j]=-1;
        }
    }
    cout<<knapsack(wt,val,w,n);
}

To initialize with -1 outside main function i tried to modify my code as below but it resulted in an error;

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int dp[10][100];
for(int i=0;i<10;i++){
        for(int j=0;j<100;j++){
            dp[i][j]=-1;
        }
}
int knapsack(vector<int>wt,vector<int>val,int w,int n){
    if(w==0 || n==0){
        return 0;
    }
    if(dp[n][w]!=-1){
        return dp[n][w];
    }
    if(wt[n-1]<=w){
        return dp[n][w]=max(val[n-1]+knapsack(wt,val,w-wt[n-1],n-1), knapsack(wt,val,w,n-1));
    }
    else{
        return dp[n][w]=knapsack(wt,val,w,n-1);
    }

}
int main(){
    vector<int>val={60,100,120};
    vector<int>wt={10,20,30};
    int w=60;
    int n=val.size();
    cout<<knapsack(wt,val,w,n);
}

How to initialize my 2D array outside the main function, as sometimes we have to write just function and we are not able to modify code inside main. kindly looking for help.

dynamic-programming heap-memory data-structures arrays c++
2 Answers

The array will take up a fixed place in memory anyway, so why not do the initialization at compile time instead of at runtime. You can do this with a constexpr function template like this (C++20, requires constexpr std::array) :

#include <array>

template<typename type_t, std::size_t N, std::size_t M>
static constexpr auto create_2D_array(const type_t& initial_value)
{
    std::array<std::array<type_t, M>, N> values;
    for (auto& row : values)
    {
        for (auto& value : row) value = initial_value;
    }

    return values;
}

int main()
{
    static constexpr auto values = create_2D_array<int,3,3>(-1);
    static constexpr auto value = values[1][1];
    static_assert(value == -1);
    return value;
}
user_166495500

To directly initialize, you need to list the elements of it. However, to simply have the arrays filled with -1, you can use the bool initializer trick:

int dp[10][100];
 
const bool init_dp = []() {
    for(int i=0;i<10;i++){
            for(int j=0;j<100;j++){
                dp[i][j]=-1;
            }
    }
    return true;
}();

dp and init_dp must be in the same compilation unit and in this order; then it's guaranteed that, after this point in the static initialization, dp will be filled with -1.

If you don't like the bool init trick, but ok to define an object to reach dp, you can get very similar behavior:

#include <iostream>
#include <type_traits>
#include <utility>

template<typename, typename>
struct AA {};
 
template<size_t... is, size_t... js>
struct AA<std::index_sequence<is...>, std::index_sequence<js...>> {
    int a[sizeof...(is)][sizeof...(js) + 1] = {{(int(js) * 0 - 1)..., int(is) * 0 - 1}...};
};
 
using DP = AA<std::make_index_sequence<10>, std::make_index_sequence<100 - 1>>; // NOTE: 100 - 1 = 99 is needed here
static_assert(std::is_same<decltype(DP::a), int[10][100]>::value);
 
// now you can define DP dp; and use dp.a
 
int main() {
    // your code goes here
    DP dp;
    return 0;
}
user_62926210
Related