尝试初始化矩阵C++时分配错误

Question

我正在尝试将一个2d矩阵放入一个AVL树中。然而，我一直收到“在抛出一个bad_alloc实例后调用终止”。错误，然后程序崩溃。下面是我的代码：

struct Node
{
  int key;
  struct Node *left;
  struct Node *right;
  int height;
  int **M;
};

struct Node* newNode(int key)
{
 struct Node* node = new struct Node;
 node->key   = key;
 node->left   = NULL;
 node->right  = NULL;
 node->height = 1;  

if(key == (0 % 3)){
    cout <<"Matrix" <<endl;
    int n = pow(2, 20);
    node->M = new int*[n];
    for (int i = 0; i < n; i++){
        node->M[i] = new int[n];
    }     
//  freemat(node, n);
}
 else if (key == (1 % 3)){
    cout <<"Matrix" <<endl;
    int n = pow(2, 19) + pow(2, 18);
    node->M = new int*[n];
    for (int i = 0; i < n; i++){
        node->M[i] = new int[n];
    }    
//  freemat(node, n);
}
else if(key == (2 % 3)){
    cout <<"Matrix" <<endl;
    int n = pow(2, 18) + pow(2, 17);
    node->M = new int*[n];
    for (int i = 0; i < n; i++){
        node->M[i] = new int[n];
    }   
  //    freemat(node, n);
  }
  return(node);
}

freemat是我创建来释放矩阵的函数，因为我认为这就是问题所在，但即使在“释放”矩阵之后，我仍然有问题。

int freemat(struct Node *N, int n){
  for(int i = 0; i < n; ++i)
    delete [] N->M[i];
  delete [] N->M;
}

该程序编译，打印出‘Matrix’这个词，然后在下面打印错误。

Answer 1

bad_alloc通常是由内存不足引起的。您有没有尝试过在gdb下运行它以查看实际效果? 2^20 *2^20 * sizeof(int)大约是8TB！

此外，还有一些不请自来的评论(请随意忽略)：根据freemat函数和初始化结构的方式，您看起来像是来自C语言背景。与C的malloc方法不同，如果不能分配请求的内存，则返回NULL，而C++的新函数抛出bad_alloc。

最后，您对(key == (1%3))的检查没有意义。1%3始终为1，因此除非您打算检查(key == 1)，否则您可能需要(key %3 == 1)。

Answer 2

这不是问题的答案--对不起，评论太长了。

一种摆脱所有分支的方法

static const powers[] = 
{
    1 << 20,
    1 << 19 + 1 << 18
    1 << 18
};

std::cout << "Matrix\n";

int n = powers[key % sizeof(powers)];
node->M = new int*[n];
for (int i = 0; i < n; ++i)
    node->M[i] = new int[n];

这仍然会分配大量的内存，并且仍然会损坏你的计算机，使它着火。