用c++实现2d数组，内存更少

I need an 2d array that is a field of the class. x is width and y is height.

我需要一个二维数组，它是类的一个字段。x是宽度，y是高度。

I have written code like this:

我写过这样的代码:

#include <iostream>

int main(){
    char ** tab;
    int x, y;
    std::cin >> x >> y;
    tab = new char* [x+2];
    for (int i = 0; i < x+2; i++) {
        tab[i] = new char [y+2];
    }
}

And it works. The problem is it takes too much memory (the example data requires 16kb and I can use only 5kb) is there a easy (or uneasy) way to implement this?

和它的工作原理。问题是它占用了太多的内存(示例数据需要16kb，而我只能使用5kb)。

The only solution I can think of is working on tab[(x+2)*(y+2)], but I would have to change the whole program and fill it with simple arithmetic to compute position in an array, but it would require rewriting huge chunk of code so I want to avoid that.

我能想到的唯一的解决方案是处理tab[(x+2)*(y+2)]，但是我必须改变整个程序，并用简单的算术来填充它，以计算数组中的位置，但是它需要重写大量的代码，所以我想避免这种情况。

edit: 5kb is requirement because it's project for school :) the program runs perfectly on 96 tests (out of 100), but on this one it stops because of memory. edit2: how can I store multiple valueas in one char? would it be very complicated?

编辑:5kb是需要的，因为它是学校的项目:)这个程序在96个测试(100个)中完美运行，但是在这个测试中它会因为内存而停止运行。edit2:如何在一个char中存储多个valueas ?会很复杂吗?

5 个解决方案

#1

I think the best way is to encapsulate it to 2d array class. It would work with the one dimensional array, but you would access it through getters and setters with your indices of choice. That's the easiest and most elegant solution that I can think of.

我认为最好的方法是将它封装到2d数组类中。它可以使用一维数组，但是你可以通过你选择的索引的getter和setter来访问它。这是我能想到的最简单、最优雅的解决方案。

#2

Edit: I got tired of seeing too many incorrect answers getting upvotes so I did some actual experiments to show the validity of my claims and rewrote my answer.

编辑:我厌倦了看到太多不正确的答案，所以我做了一些实际的实验来证明我的观点是正确的，并重写了我的答案。

tl;dr tab is an array of pointers to char. That means tab isn't storing char (which take 8 bits each) but rather is storing x pointers which take (generally) 64 bits each. You need to find a way to use tab as a pointer to a single array of char: char * tab

dr选项卡是指向char的指针数组。这意味着制表符不是存储char(每个char占用8位)，而是存储x个指针，每个(通常)占用64位。您需要找到一种方法来使用tab作为指向char: char * tab数组的指针

---

The Problem

In this loop:

在这个循环:

for (int i = 0; i < x+2; i++) {
  tab[i] = new char [y+2];
}

You are running new x+2 times (btw, why +2??). As you should know, new returns pointers not chars. It allocates memory for the data type you are requesting i.e. char and then returns a pointer to that memory address. The call to new in the loop thus allocates 8-bits. Since new returns a memory address, you need to store it somewhere. Thankfully you've allocated space to store that address with this line:

你正在运行新的x+2次(顺便说一下，为什么+2??)你应该知道，新的返回指针不是chars。它为您所请求的数据类型(例如char)分配内存，然后返回一个指向该内存地址的指针。循环中对new的调用因此分配了8位。因为new返回一个内存地址，所以需要将它存储在某个地方。谢天谢地，您已经分配了空间来存储这行地址:

tab = new char* [x+2];

Now you are not asking new to reserve space for an array of char but rather you are asking for it to reserve space for an array of pointers to char.

现在您不是要求new为char数组保留空间，而是要求它为指向char的指针数组保留空间。

On most modern architectures, pointers require 64 bits. Those pointers are being stored on the heap in the memory address that tab is pointing to. i.e. tab[0] holds the first pointer to char, tab[1] holds the second, etc... These pointers hold the locations of yet additional memory that has been allocated to hold the chars.

在大多数现代架构中，指针需要64位。这些指针存储在堆中，位于标签所指向的内存地址中。即tab[0]持有第一个指向char的指针，tab[1]持有第二个指针，等等……这些指针保存了分配给chars的额外内存的位置。

So in total, you are allocating room for x+2 pointers with this line:

因此，总的来说，你给x+2分的空间分配了这条线:

tab = new char* [x+2];

and (x+2)*(y+2) chars with this line:

(x+2)*(y+2)曲线为:

tab[i] = new char [y+2];

If you do the math, that's (x+2)*8B for the pointers plus (x+2)*(y+2)*1B for the chars. From looking at the equations, you'll see that for a given number of chars i.e for any x*y you'll see more memory usage if x is larger than y.

如果你算一下，这是(x+2)*8B的指针加上(x+2)*(y+2)*1B。通过看这些方程，你会发现对于给定的数个chars i。对于任何x*y，如果x大于y，你会看到更多的内存使用。

To test this, I ran the valgrind massif tool on your code (except I got rid of the +2 with the following results:

为了测试这个，我在您的代码上运行了valgrind massif工具(除了我去掉了+2，结果如下:

|  x | y |useful-heap(B)|
|----|---|--------------|
|  0 | 1 |       0      |
|  1 | 0 |       8      |
|  1 | 1 |       9      |
|  1 | 2 |      10      |
|  1 | 3 |      11      |
|  2 | 0 |      16      |
|  2 | 1 |      18      |
|  2 | 2 |      20      |
|  3 | 0 |      24      |
|  3 | 1 |      27      |
| 20 | 0 |     160      |
|100 | 0 |     800      |   

look at how memory usage increases by 8B each time x increases. This is the allocation of space to store your array of pointers. Note that for the y=0 cases there are no chars stored at all... so when x=100 and y=0 you are using 800B of memory for absolutely nothing.

看看每次x增加时内存使用量如何增加8B。这是用来存储指针数组的空间分配。注意，对于y=0的情况，根本不存储任何字符……当x=100 y=0时，你用了800B的内存。

fyi, massif also reports extra allocations that the system made on your behalf due to minimum allocation size, efficiency, etc. but the numbers I gave above are the exact amounts that massif claims you asked for

顺便提一下，massif还报告了系统为您所做的额外的分配，由于最小的分配大小，效率等等，但是我上面给出的数字是massif要求的确切的数量

---

how to fix it?

The key is going to be to rearrange how you're storing the chars and how you address them. You are storing chars so you could make one big array of chars and find a different way to index them. That would require no heap allocation other than the chars themselves.

关键是重新安排如何存储这些字符以及如何处理它们。您正在存储chars，以便您可以创建一个大的chars数组，并找到一种不同的方法对它们进行索引。这将不需要堆分配，除了chars本身。

I'd also recommend staying away from raw arrays and pointers and using std::array or std::vector instead but I assume you've been specifically told to use them for an assignment...

我还建议不要使用原始数组和指针，而应该使用std::array或std:::vector，但我假设您已经被特别告知要使用它们进行作业……

#3

If you compile the code with '-Os' flag it will optimize for memory.

如果您使用“-Os”标志编译代码，它将对内存进行优化。

This is not very C++-ish but you can use a macro to access and array like a matrix:

这不是非常c++ -ish，但是您可以使用宏来访问和数组，就像一个矩阵:

#define TAB(col,row) tab[col*column_length+row]

The correct way will be to create a class for encapsulate all this.

正确的方法是创建一个类来封装所有这些。

#4

You haven't specified what your input 2D array size is (what are x and y in your test).

您还没有指定输入的2D数组大小(测试中的x和y是什么)。

Be aware that "new" has a minimum allocation size.

请注意“new”具有最小的分配大小。

If invoke a bunch of new char[1] arrays (say x = 1, y = 10000), then you are allocating min malloc size * 10000; not 1 * 10000. I believe the min size is something like 32 or 64 bytes.

如果调用一组新的char[1]数组(假设x = 1, y = 10000)，那么您正在分配min malloc大小* 10000;不是1 * 10000。我认为最小大小大概是32或64字节。

You will minimize the amount of memory needed if you can allocate it all at once (as a single array allocation). e.g. new char [x * y]

如果您可以一次分配所有内存(作为单个数组分配)，那么您将最小化所需的内存数量。新的char [x * y]

#5

i believe you answered your own question, i don't think there is a way to make it take up less space since the variable size of a char would determine it.

我相信你已经回答了你自己的问题，我不认为有什么方法可以使它占用更少的空间，因为字符的可变大小将决定它的大小。