2

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

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?

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.

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?

Improve this question
6
  • I doubt the overhead can be reduced to the extent that what takes 16kb can fit into 5 kb. Commented Apr 17, 2015 at 20:34
  • Guess you'll have to find a way to have only part of the data at any given time. Commented Apr 17, 2015 at 20:34
  • What are you using the char to represent? Depending on the dataset you are represent you can use a single char to hold multiple values (eg 1x8bit char to hold 8 boolean values, rather than 8x8bit chars ). That would require us to know the data domain we are working with. Commented Apr 17, 2015 at 20:48
  • 3
    Unless you're programming on a microcontroller (unlikely since you're using iostreams and new), 16 kB is an insanely small amount of memory on modern machines. In fact, the underlying memory allocator for new char[] will by itself probably reserve more than 16 kB to satisfy future memory requests. Why is 16 kB such a problem, and why is 5 kB your limit? Commented Apr 17, 2015 at 20:50
  • 1
    I suspect the point of the exercise is to process only small chunks of the data at a time, in which case there is no way we can answer this question. Commented Apr 17, 2015 at 21:10

5 Answers 5

Reset to default
2

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

How does encapsulation make more efficient use of memory?
it doesn't, encapsulation is for ease of use, because otherwise when accesing the array element you would need to translate indices to some [actualY*width+actualX]. It's not pretty and it's easy to make a mistake
Agreed, and you're hunting at the right solution that op and somehow all of the answers missed - that he has one too many levels of redirection in the array. I agree that encapsulation can help to find these problems and is generally the way to go anyhow.
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

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:

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.

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.

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

tab = new char* [x+2];

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

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.

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

|  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.

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

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.

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...

Improve this answer

Comments

1

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

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

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

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

Improve this answer

6 Comments

this is preprocessor, right? would it work if I'll write TAB(4,6) too?
Right way to access the array bit #defines are almost universally frowned upon and add no benefit here. Why not have a class or function instead?
the compiler can't optimize out the calls to new that are consuming memory.
@WilliamCode Yes, this is preprocessor magic. To access that array use something like this x=TAB(4,6);
@evan I did recommend a class as the correct way. No compiler in the would will optimize out a array, the best it can do is to identify and create some sort of cache warm system (template meta programming would help the compiler in that case, but I would need more information to recommend it)
|
0

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

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

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.

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]

Improve this answer

Comments

-1

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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.