Need suggestion for manipulating memory effectively in C++?

Question

I've written a small program to find the number who is both prime and a factor of a specific number n. I get the number n from a file and print it to another.

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <cstring>
#include <iostream>
#include <fstream>

using namespace std;
bool PrimeFactor(int );
int countSize(int);


char * p_str = "";//store result of prime factor
int size = 0;//length of p_str

int main(int argc, char** argv) {
std::ifstream fin;
fin.open("input.txt");

std::ofstream fout;
fout.open("output.txt", std::ios::app);

int N;//number to factor

while (fin >> N){   
    //Find prime factor
    PrimeFactor(N);
    fout << p_str;// print string storing result
    fout << endl;
}

fin.close();
fout.close();

return 0;
}

bool PrimeFactor( int n ){
int count = 0;// count divisors

for (int i = 2 ; i < n; i++){
    if ( n % i == 0 ){
        // convert integer to string
        char * tmpstr = new char[ countSize(i) ]  ;// allocate according to size of integer (not waste memory)
        sprintf( tmpstr, "%d ", i); // NOTE : if not have the blank after %d -> no space

        // condition : prime and not duplicate existing number in global string
        if ( PrimeFactor(i) && !strstr( p_str, tmpstr ) ){

            char * new_p = new char [ size + countSize(i) ];
            strcpy( new_p, p_str );// copy the global string to new place
            strcat( new_p, tmpstr );// append new integer value
            p_str = new_p ; // let glocal string be renewed with appending new result
            size = size + countSize(i);
            cout << size << endl;
        }
        count ++;
    }
}

if (count > 0)//not prime
    return false;
return true;
}

//counting the number of digit of an integer
int countSize(int n){
    int count = 0;
    if (n < 10)
        return 1;
    while ( n >= 10 ){
        count++;
        n = n/10;
    }
    return count + 1;
}

Using this approach, the result may be duplicated if I don't store the founded numbers in a C-string and check whether the next number is already a number in the string. I choose C-string as it is more challenging than std::string. So the question is about manipulating the string to minimize memory usage. I have to use a global pointer-to-char (as not have to define the size of array of char). It seems that func CountSize() though return what is needed (length of number in string), the string still waste some piece of memory & the size variable is not what I meant it to be. Also I cant get the size by using sizeof() with a pointer-to-char. Any one can help me?

Answer 1

A string is not really an appropriate data structure for what you are trying to do. You seem to be concerned about memory consumption, but why? Are you actually running out of memory with your program? Using a string for this task imposes a lot of unnecessary work: allocating memory, copying the string to append a new number, searching the string for an existing number, converting integers to strings, counting the number of digits in the integer more times than necessary, and so on. Using C strings also makes it easy to introduce bugs: strings that are not null terminated, buffer overflows, etc. For example, when you convert the integer to a string, you don't allocate a byte for the null terminator, so sprintf overflows your buffer.

A more appropriate data structure would be a set of integers. A set can store a value once and only once. You can use the find method to see if an item already exists in the set. Using a set will probably use a little more memory, but your program will be much, much, much faster because you will replace a lot of O(N) operations with O(1) and O(log n) operations.

You cannot use sizeof to get the size of the allocated array. That is because sizeof returns the size of the type, so when you use sizeof on a C string, you get the size of the pointer, not the size of the array. You must track the size of the array yourself.

You mention using C strings instead of std::string because it is more challenging. I commend you for trying challenging things, since it is a great way to strech your limits and learn new things. If I may make a suggestion: do the simplist thing that can possibly work first. Write tests to ensure that it does what you think it is doing. With a working program and a validation test in hand, you can start optimizing memory consumption, performance, or challenging data structures for fun. The test allows you to verify that your optimizations haven't introduced bugs as you optimize.

Answer 2

OK, so you want to use char* strings, presumably to get a handle on them for the future. That is admirable. But you're gonna need a crash-course in the commandments of c-string management first...

Thou shalt pair every new with a delete

Your goal is to attempt to minimize memory usage right? Well, every time you create a string with new, but then don't delete it, you are leaking that memory. This is bad practice in general, but also a definite memory waster. In your case you are allocating with new [] to make an array, and new [] calls must be paired with delete []. So in your PrimeFactor function:

strcpy( new_p, p_str );// copy the global string to new place
strcat( new_p, tmpstr );// append new integer value
// delete original contents of p_str
delete [] p_str;
p_str = new_p ; // let glocal string be renewed with appending new result

You will also need a delete [] at the very end of your program to clean up the memory of p_str before it exits.

Thou shalt always make room for a null-terminator

When the computer is reading a c-string, it doesn't know beforehand how long it is. If you have a char[100] initialized with the contents "Hi", how does the computer known to stop after the 'i', as opposed to the 'H', or the character 5 after 'i'? C-strings are not valid unless they end with a null-terminator, written as '\0'. The null-terminator indicates to the computer, "Ok, we're done here." The string's over. It's kinda nifty, but problems can arise because the null-terminator takes up a spot in the character array. Storing "Hi" requires a char [3]; -- char[0] is 'H', char[1] is 'i', and char[2] is '\0'. So your new string allocation code should look like this:

    char * tmpstr = new char[ countSize(i) + 1 ]  ;// allocate according to size of integer (not waste memory)
    ...
        char * new_p = new char [ size + countSize(i) + 1 ];

Note the + 1s. This is to ensure your strings have room for the Null-terminator.

Thou shalt use string-safe functions

sprintf, strcpy, and strcat (and others) have been deprecated in favor of the new sprintf_s, strcpy_s, and strcat_s functions. The _s stands for "safe". These functions take an extra parameter for the size of the string they are modifying, and ensure that size-limit is not broken. All the string-modifier functions ensure that the prior-mentioned null-terminator is tacked on, but in your code, you weren't giving them the proper room to do that. So the non-string-safe functions were writing one character PAST your declared memory into unknown memory -- bad -- very bad. The string-safe versions of those functions would have instead crashed your program with an error, alerting you that something was wrong and needed fixin'. A string-safe implementation of your functions would look like this:

    int tmpstrSize = countSize( i ); // calculate tmpstrSize once
    char * tmpstr = new char[ tmpstrSize + 1 ]  ;// allocate according to size of integer (not waste memory)
    sprintf_s( tmpstr, tmpstrSize + 1, "%d ", i); // NOTE : if not have the blank after %d -> no space
    ...
        int new_pSize = size + tmpstrSize; // calculate new_pSize once
        char * new_p = new char [ new_pSize + 1 ];
        strcpy_s( new_p, new_pSize, p_str );// copy the global string to new place
        strcat_s( new_p, new_pSize, tmpstr );// append new integer value

Now you are nice and safe, and if something goes wrong, you will know.

Thou shalt write C++ code in a C++ manner

Truth be told, the program you've written above isn't really C++, it's C. Sure, it'll run fine in a C++ environment, but the method is totally C-based. C++ programs use std::strings for strings and std::vectors for lists of integers. So hey, I understand that you want to learn the low-level stuff for the challenge, I've been there myself. But once you know how to do it, the C++ functionality that makes basically everything I described above irrelevant for string-handling is a godsend, and you will never, ever want to go back.

As a small side-note, I recommend checking out the Sieve of Eratosthenes for prime-number checking. It's a good exercise to implement and will give your code a huge performance boost.

Answer 3

Storing integers as strings and you are asking about efficient memory management?