使用C++11中的std::fill函数填充一个动态分配的二维数组

Question

一个类似的讨论可以在这个问题中找到，另外还有一个问题，但我的情况略有不同，因为我处理的是动态分配的内存。

同时请注意，memset不能很好地用于double类型的值。

总之，我正在尝试使用std::fill来填充一个动态分配的二维数组--

#include <iostream>
#include <algorithm>

using std::cout ; using std::endl ;
using std::fill ;

int main()
{
    double **data ;
    int row = 10, col = 10 ;
    data = new double*[row] ;
    for(int i = 0 ; i < col ; i++)
        data[i] = new double[col];

    // fill(&(data[0][0]), 
    //      &(data[0][0]) + (row * col * sizeof(double)), 1); // approach 1
    // fill(&(data[0][0]), &(data[0][0]) + (row * col), 1);   // approach 2
    // fill(data, data + (row * col * sizeof(double)), 1);    // approach 3
    // fill(&(data[0][0]), 
    //      &(data[0][0]) + 
    //       ((row * sizeof(double*)) + 
    //        (col * sizeof(double))), 1);                    // approach 4

    for(int i = 0 ; i < row ; i++) {
        for(int j = 0 ; j < col ; j++)
            cout << data[i][j] << " " ;
        cout << endl ;
    }

    for(int i = 0 ; i < row ; i++)
        delete [] data[i] ;
    delete [] data ;
}

方法1： 根据我的理解，方法1应该是正确的代码，我从开头 &(data[0][0]) 开始，数组的结尾应该位于 &(data[0][0]) + (row * col * sizeof(double))，但运行时，我遇到了这个错误，但数组已经被填充--

1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 
*** Error in `./test': free(): invalid next size (fast): 0x0000000000da3070 ***
Aborted (core dumped)

方法二：然而，根据这个帖子，推荐使用方法二，但是我不太理解这段代码，因为sizeof(double)缺失，而且我得到了这个输出--

1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 
1 1 1 1 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
*** Error in `./test': free(): invalid next size (fast): 0x0000000000bf5070 ***
Aborted (core dumped)

方法三：我不确定为什么这段代码不能编译，data和&(data[0][0])应该是同义的，对吗？

方法四：我不确定这是否正确。

1. 我该如何实现？
2. std::fill与两个嵌套循环相比是否有额外的好处？

- ramgorur

Answer 1

与堆栈分配的二维数组不同，动态二维数组不能保证是一个连续的范围。但它是指针的连续范围，但数组中每个指针可能指向非连续的内存区域。换句话说，data + i + 1 的第一个元素可能不一定跟由 data + i 指向的数组的最后一个元素相邻。如果你想知道为什么堆栈分配的二维数组是连续的，那是因为当你声明类似于下面的语句时：

double data[10][20];

然后编译器将其理解为一个由10个（连续的）元素组成的数组，每个元素类型为double[20]。后者也是一个数组，保证了连续的元素，因此double[20]元素（即20个double依次排列）在内存中相互堆叠。 double[10][20]与double**截然不同。

这就是为什么std::fill或std::memset会让您头痛的原因，因为它们都假设存在连续的范围。因此，在您的情况下，嵌套循环似乎是填充数组最简单的方法。

通常，更好的方法是使用1D数组，在其中“模拟”2D访问，正如上面提到的那样：数据局部性。数据局部性意味着较少的缓存未命中和更好的整体性能。

- vsoftco

Answer 2

指针算术要求指针只能增加到仍然指向同一数组（或末尾之后的一个元素）的程度。

在for循环中，你需要将每一行分配为单独的数组：

for(int i = 0 ; i < col ; i++)
    data[i] = new double[col]; // this creates a distinct array for each row

由于您分配的每个行数组都是col元素，因此可以合法地将&(data[0][0])添加的最大值为col。但在您使用std::fill的每个示例中，您添加的指针超出了允许的范围。

考虑到您分配数组的方式，无法通过单个std::fill调用传递原始指针以初始化整个二维数组。您要么必须使用多个std::fill调用（这违背了使用std::fill的初衷），要么必须创建一个知道如何处理每行单独分配的迭代器类型，或者您必须更改分配数组的方式。

我建议一次性分配整个数组作为单个维数组，然后编写一些额外的代码使其像二维数组一样工作。这有很多好处:

• 标准库包含一种方便动态分配单个维数组的方法：std::vector
• 使用std::vector意味着您不再需要使用裸的new和delete，这解决了您的代码存在的异常安全问题。
• 单个分配通常具有比多个分配更好的性能特征（当然，有些情况下单独的分配更好）。

以下是一个简单的包装类，使1D数组看起来像2D数组：

class Matrix {
  std::vector<double> data;
  int cols;

public:
  Matrix(int row, int col)
    : data(row * col)
    , cols(col)
  {}

  auto begin() { return data.begin(); }
  auto end() { return data.end(); }

  struct index_type { int row; int col; };

  double &operator[](index_type i) {
    return data[i.row * cols + i.col];
  }

  int row_count() const { return data.size()/cols; }
  int column_count() const { return cols; }
};

使用这个工具，您可以重写您的代码：

#include "Matrix.h"

#include <iostream>
#include <algorithm>

using std::cout ; using std::endl ;
using std::fill ;

int main()
{
    Matrix data(10, 10);

    fill(data.begin(), data.end(), 1.0);

    for(int i = 0 ; i < data.row_count() ; i++) {
        for(int j = 0 ; j < data.column_count() ; j++)
            cout << data[{i, j}] << " " ;
        cout << endl ;
    }
}

std::fill相比两个嵌套循环是否有额外的好处？

使用循环不够可读，因为循环可以做许多其他事情，你必须花更多时间弄清楚任何特定的循环在做什么。因此，在所有其他条件相等的情况下，应始终优先使用STL算法而不是手动循环。

---

// fill(&(data[0][0]), 
//      &(data[0][0]) + (row * col * sizeof(double)), 1); // approach 1

指针算术运算会自动考虑数组元素的大小，因此不需要使用sizeof(double)。在这里乘以sizeof(double)与在[]内部乘以sizeof(double)是相同的。你不会这样做：data[i * sizeof(double)]，所以也不要这样做：data + (i * sizeof(double))。

---

你的示例代码使用了&(data[0][0])。请思考这个表达式和data[0]是否相同或不同，考虑它们的类型和值。

- bames53

---

点赞。我也会写'const'版本的operator[]。使用自定义索引而不是std::pair或两个size_t参数的特定原因是什么？ - vsoftco

@vsoftco 我把 const 成员移除了，只是因为它们在这里不需要，并且我想保持代码简单。但是，在真实的代码中，它们应该存在（以及其他一堆东西）。 - bames53

@vsoftco 我使用了自定义索引类型，既是为了自定义成员名称（而不是 .first、.second），也是因为这样静态类型可以防止像混淆 Matrix::index_type 和 SomethingElse::index_type 这样的问题。有时过多地使用通用类型如 std::pair 可能会导致“字符串类型”问题。使用两个索引参数将要求我放弃 [] 重载，这没关系，只是我偏好不这样做。 - bames53

好的，谢谢！我仍然认为应该向标准中提出一个基本的矩阵类。C++可能是唯一缺乏它的主要语言。当然有 Boost multiarray，但仍未进入标准。 - vsoftco

@vsoftco 我认为array_view proposal涵盖了大部分所需内容。 - bames53

Answer 3

我同意上述评论。您已分配了10个单独的数组，因此无法使用单个std :: fill调用对其进行初始化。 此外，当您对非void类型的指针执行算术运算时，编译器会自动将结果乘以给定类型的sizeof。但是，当您使用像memset或memcpy这样的函数时，实际上必须将元素数量乘以给定类型的sizeof，并将其传递给其中一个函数。这是因为这些函数操作字节，并且它们接受void类型的指针。因此，编译器无法处理大小的调整，因为void类型没有指定的大小。

- Wojciech Jabłoński