将碎片动态分配转换为连续

Question

我应该创建一个动态分配二维数组的函数，如下所示（对于 n=3）：

1

2 1 2

3 2 1 2 3

我编写的代码可以正常工作。但是，我使用了片段动态分配。你能解释一下我如何修改它以使用连续动态分配吗？动态分配对我来说是新的，我有点困惑。能解释一下吗？

#include <cstdlib>
#include <iostream>
#include <new>
#include <stdexcept>
int **MakeTriangle(int n) {
  if (n <= 0)
    throw std::domain_error("Number of rows must be positive");
  int **mat = nullptr;

  mat = new int *[n];

  for (int i = 0; i < n; i++)
    mat[i] = nullptr;
  try {
    for (int i = 0; i < n; i++)
      mat[i] = new int[2 * i + 1];

    for (int i = 0; i < n; i++)
      for (int j = 0; j < 2 * i + 1; j++)
        mat[i][j] = abs(j - i) + 1;
  }

  catch (std::bad_alloc) {
    for (int i = 0; i < n; i++)
      delete[] mat[i];
    delete[] mat;
    throw std::bad_alloc();
  }

  return mat;
}
int main() {
  std::cout << "How many rows you want: ";
  int n;
  std::cin >> n;

  try {
    int **mat = nullptr;
    mat = MakeTriangle(n);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < 2 * i + 1; j++)
        std::cout << mat[i][j] << " ";
      std::cout << std::endl;
    }
    for (int i = 0; i < n; i++)
      delete[] mat[i];
    delete[] mat;
  } catch (const std::bad_alloc e) {
    std::cout << "Exception: Not enough memory";
  } catch (const std::domain_error e) {
    std::cout << "Exception: " << e.what();
  }

  return 0;
}

Answer 1

你基本上有两个选择。要么分配 n * (2 * n + 1) 个元素并浪费其中或多或少的一半，要么分配三角形所需的确切元素数量并在访问它们时小心：

#include <cstddef>
#include <iostream>

int** make_triangle_frag(std::size_t n) {
    int** memory = new int*[n];
    for (std::size_t i = 0; i < n; ++i) {
        std::size_t const count = 2 * i + 1;
        memory[i] = new int[count];
        for (std::size_t j = 0; j < i + 1; ++j) {
            int const val = i - j + 1;
            memory[i][j] = val;
            memory[i][count - j - 1] = val;
        }
    }

    return memory;
}

int* make_triangle_cont_square(std::size_t n) {
    auto const rowCount = 2 * n + 1;
    int* memory = new int[n * (2 * n + 1)];
    for (std::size_t i = 0; i < n; ++i) {
        std::size_t const count = 2 * i + 1;
        for (std::size_t j = 0; j < i + 1; ++j) {
            int const val = i - j + 1;
            memory[rowCount * i + j] = val;
            memory[rowCount * i + count - j - 1] = val;
        }
    }

    return memory;
}

std::size_t count_elems(std::size_t n) {
    std::size_t count{0};
    for (std::size_t i = 0; i != n; ++i) count += 2 * n + 1;

    return count;
}

int* make_triangle_cont_tri(std::size_t n) {
    auto const elemCount = count_elems(n);
    int* memory = new int[elemCount];

    std::size_t offset{0};
    for (std::size_t i = 0; i < n; ++i) {
        std::size_t const count = 2 * i + 1;
        for (std::size_t j = 0; j < i + 1; ++j) {
            int const val = i - j + 1;
            memory[offset + j] = val;
            memory[offset + count - j - 1] = val;
        }

        offset += count;
    }

    return memory;
}

int main() {
    std::size_t const n{10};

    {
        int** mat = make_triangle_frag(n);
        for (std::size_t i = 0; i < n; i++) {
            for (std::size_t j = 0; j < 2 * i + 1; j++)
                std::cout << mat[i][j] << " ";
            std::cout << std::endl;
        }

        for (int i = 0; i < 10; ++i) delete[] mat[i];

        delete[] mat;
    }

    {
        // Cons: You waste more or less half the elements you have allocated.
        // Pros: It's still easy to access the elements.
        int* mat = make_triangle_cont_square(n);

        for (std::size_t i = 0; i < n; i++) {
            for (std::size_t j = 0; j < 2 * i + 1; j++)
                std::cout << mat[i * (2 * n + 1) + j] << " ";
            std::cout << std::endl;
        }

        delete[] mat;
    }

    {
        // Cons: Accessing the triangle elements becomes tricky.
        // Pros: You don't allocate more memory than you need.
        int* mat = make_triangle_cont_tri(n);

        std::size_t offset{0};
        for (std::size_t i = 0; i < n; ++i) {
            std::size_t const count = 2 * i + 1;
            for (std::size_t j = 0; j < count; j++)
                std::cout << mat[offset + j] << " ";
            std::cout << '\n';
            offset += count;
        }

        delete[] mat;
    }
}

输出：

1 
2 1 2 
3 2 1 2 3 
4 3 2 1 2 3 4 
5 4 3 2 1 2 3 4 5 
6 5 4 3 2 1 2 3 4 5 6 
7 6 5 4 3 2 1 2 3 4 5 6 7 
8 7 6 5 4 3 2 1 2 3 4 5 6 7 8 
9 8 7 6 5 4 3 2 1 2 3 4 5 6 7 8 9 
10 9 8 7 6 5 4 3 2 1 2 3 4 5 6 7 8 9 10 
1 
2 1 2 
3 2 1 2 3 
4 3 2 1 2 3 4 
5 4 3 2 1 2 3 4 5 
6 5 4 3 2 1 2 3 4 5 6 
7 6 5 4 3 2 1 2 3 4 5 6 7 
8 7 6 5 4 3 2 1 2 3 4 5 6 7 8 
9 8 7 6 5 4 3 2 1 2 3 4 5 6 7 8 9 
10 9 8 7 6 5 4 3 2 1 2 3 4 5 6 7 8 9 10 
1 
2 1 2 
3 2 1 2 3 
4 3 2 1 2 3 4 
5 4 3 2 1 2 3 4 5 
6 5 4 3 2 1 2 3 4 5 6 
7 6 5 4 3 2 1 2 3 4 5 6 7 
8 7 6 5 4 3 2 1 2 3 4 5 6 7 8 
9 8 7 6 5 4 3 2 1 2 3 4 5 6 7 8 9 
10 9 8 7 6 5 4 3 2 1 2 3 4 5 6 7 8 9 10

请注意，只有在第三种情况下，矩阵元素才会连续排列。这是内存布局的实际样子：

mat[0] ->  { 1 }
mat[1] ->  { 2, 1, 2 }
mat[2] ->  { 3, 2, 1, 2, 3 }

mat { 1, ?, ?, ?, ?, 2, 1, 2, ?, ?, 3, 2, 1, 2, 3 }

mat { 1, 2, 1, 2, 3, 2, 1, 2, 3 }

注2：如果你真的需要一个int**，你可以试试这个：

int* memory = make_triangle_cont_tri(n);
int** mat = new int*[n];

{
    // Init mat
    std::size_t offset{0};
    for (std::size_t i = 0; i < n; ++i) {
        std::size_t const count = 2 * i + 1;
        mat[i] = memory + offset;
        offset += count;
    }
}

for (std::size_t i = 0; i < n; ++i) {
    for (std::size_t j = 0; j < 2 * i + 1; j++)
        std::cout << mat[i][j] << " ";
    std::cout << '\n';
}

delete[] mat;
delete[] memory;

输出：

1 
2 1 2 
3 2 1 2 3 
4 3 2 1 2 3 4 
5 4 3 2 1 2 3 4 5 
6 5 4 3 2 1 2 3 4 5 6 
7 6 5 4 3 2 1 2 3 4 5 6 7 
8 7 6 5 4 3 2 1 2 3 4 5 6 7 8 
9 8 7 6 5 4 3 2 1 2 3 4 5 6 7 8 9 
10 9 8 7 6 5 4 3 2 1 2 3 4 5 6 7 8 9 10

将碎片动态分配转换为连续

Convert fragmental dynamic allocation into continuous

c++

dynamic-memory-allocation