Home > Software engineering >  Convert fragmental dynamic allocation into continuous
Convert fragmental dynamic allocation into continuous

Time:04-11

I should make a function that dynamically allocates two-dimensional array that looks like this (for n=3):

1

2 1 2

3 2 1 2 3

I have written code which works correct. However, I used fragmental dynamic allocation. Could you explain me how could I modify this to use continuous dynamic allocation? Dynamic allocation is new to me, and I'm confused a little bit. Could you give any explanation?

#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;
}

CodePudding user response:

You basically have two options. Either you allocate n * (2 * n 1) elements and waste more or less half of them or allocate the exact number of elements you need for your triangle and be careful when accessing them:

#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;
    }
}

Output:

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 

Please note that you'll have your matrix elements layed out contiguously only in the third case. Here you are what the memory layouts actually look like:

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 }

Note 2: If you really need an int**, you may try this:

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;

Output:

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 
  • Related