如何在 C++ 中正确处理动态分配的多维数组 [英] How to properly work with dynamically-allocated multi-dimensional arrays in C++

问题描述

如何在 C++ 中定义动态多维数组?比如二维数组?我尝试使用指向指针的指针，但不知何故它失败了.

How do I define a dynamic multi-dimensional array in C++? For example, two-dimensional array? I tried using a pointer to pointer, but somehow it is failing.

推荐答案

首先应该意识到 C++ 中没有多维数组支持，无论是作为语言特性还是标准库.所以我们可以在其中做的任何事情都是对它的模仿.我们如何模拟二维整数数组?这里有不同的选项，从最不适合到最适合.

The first thing one should realize that there is no multi-dimensional array support in C++, either as a language feature or standard library. So anything we can do within that is some emulation of it. How can we emulate, say, 2-dimensional array of integers? Here are different options, from the least suitable to the most suitable.

如果使用指向类型的指针来模拟数组，那么二维数组肯定应该使用指向该类型的指针的指针来模拟吗?像这样吗?

If an array is emulated with pointer to the type, surely two-dimensional array should be emulated with a pointer to pointer to the type? Something like this?

int** dd_array = new int[x][y];

这是一个编译器错误.没有 new [][] 操作符，所以编译器很乐意拒绝.好的，那怎么样?

That's a compiler error right away. There is no new [][] operator, so compiler gladly refuses. Alright, how about that?

int** dd_array = new int*[x];
dd_array[0][0] = 42;

编译通过.执行时，它会因令人不快的消息而崩溃.出了点问题，但什么?当然！我们确实为第一个指针分配了内存——它现在指向一个内存块，其中包含 x 个指向 int 的指针.但是我们从未初始化这些指针！让我们再试一次.

That compiles. When being executed, it crashes with unpleasant messages. Something went wrong, but what? Of course! We did allocate the memory for the first pointer - it now points to a memory block which holds x pointers to int. But we never initialized those pointers! Let's try it again.

int** dd_array = new int*[x];
for (std::size_t i = 0; i < x; ++i)
   dd_array[i] = new int[y];

dd_array[0][0] = 42;

这不会产生任何编译错误，并且程序在执行时不会崩溃.任务完成?没那么快.请记住，每次我们调用 new 时，我们必须调用 delete.所以，给你:

That doesn't give any compilation errors, and program doesn't crash when being executed. Mission accomplished? Not so fast. Remember, every time we did call a new, we must call a delete. So, here you go:

for (std::size_t i = 0; i < x; ++i)
    delete dd_array[i];
delete dd_array;

现在，这太可怕了.语法很丑，所有这些指针的手动管理......不.让我们放下一切，做一些更好的事情.

Now, that's just terrible. Syntax is ugly, and manual management of all those pointers... Nah. Let's drop it all over and do something better.

好的.我们知道在 C++ 中我们不应该真正使用手动内存管理，并且这里有一个方便的 std::vector .那么，我们可以这样做吗?

Ok. We know that in C++ we should not really use manual memory management, and there is a handy std::vector lying around here. So, may be we can do this?

std::vector<std::vector<int> > dd_array;

这显然还不够——我们从未指定这些数组的大小.所以，我们需要这样的东西:

That's not enough, obviously - we never specified the size of those arrays. So, we need something like that:

std::vector<std::vector<int> > dd_array(x);
for(auto&& inner : dd_array)
    inner.resize(y);

dd_array[0][0] = 42;

那么，现在好了吗?没那么多.首先，我们仍然有这个循环，这让眼睛很痛.更重要的是，我们严重损害了应用程序的性能.由于每个单独的内部向量都是独立分配的，因此循环如下:

So, is it good now? Not so much. Firstly, we still have this loop, and it is a sore to the eye. What is even more important, we are seriously hurting performance of our application. Since each individual inner vector is independently allocated, a loop like this:

int sum = 0;
for (auto&& inner : dd_array)
    for (auto&& data : inner)
       sum += data;

将导致对许多独立分配的内部向量进行迭代.而且由于 CPU 只会缓存连续内存，因此无法完全缓存那些小的独立向量.无法缓存时会影响性能！

will cause iteration over many independently allocated inner vectors. And since CPU will only cache continuous memory, those small independent vectors cann't be cached altogether. It hurts performance when you can't cache!

那么，我们该怎么做呢?

So, how do we do it right?

我们根本就没有！当情况需要二维向量时，我们只需以编程方式使用一维向量并使用偏移量访问它的元素！我们就是这样做的:

We simply don't! When situation calls for 2-dimensional vector, we just programmatically use single-dimensional vector and access it's elements with offsets! This is how we do it:

vector<int> dd_array(x * y);
dd_array[k * x + j] = 42; // equilavent of 2d dd_array[k][j]

这给了我们美妙的语法、性能和所有的荣耀.为了让我们的生活稍微好一点，我们甚至可以在一维向量的基础上构建一个适配器 - 但这留给家庭作业.

This gives us wonderful syntax, performance and all the glory. To make our life slightly better, we can even build an adaptor on top of a single-dimensional vector - but that's left for the homework.

这篇关于如何在 C++ 中正确处理动态分配的多维数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！