vector memory leak

[ar2007]

Hi.
I try to create a simulation of a Big Num class, dividing the result in single digits, which represent the elements in the vector "dgt" for each item of "clk" type.
the goal is to be able to operate through a single class with the same type objects:
c = a * b;
or
c = a ^ b;

as regards c = a * b; everything works perfectly, while as regards the power function, the result is guaranteed up to a certain limit.
for example by typing 2 ^ 500, the output is the following:

3273390607896141870013189696827599152216642046043064789483291368096133796404674554883270092325904157150886684127560071009217256545885393053328527589376

while if I type 2 ^ 1000, the result is not always the same ... you create a memory leak problem .. (ideone.com -> *** Error in `./prog ': free (): invalid pointer : 0x08c70ab8 ***)

could you help me to understand where I'm wrong?
Thanks in advance

ps for the calculation by the operator *, I inserted into the clk r_size {r}, the algebraic operation actors, the partial results, and in the end the final result, all with the aim of increasing the speed of code execution, while the object clk t_size {t}, I deliver to the current * this, only the final result of the multiplication ..

#include <iostream>
#include <vector>


class clk
{
public:
	clk() {}

	~clk()
	{
		dgt.clear() ;
	}

	clk( char chx ): ch{ chx } {}

	clk( int size = 1 ): dgt_size{ size }
	{
		dgt.resize( dgt_size , 0 ) ;
	}

	clk( std::string s ): dgt_size{ static_cast< int >( s.length() ) }
	{
		dgt.resize( dgt_size , 0 ) ;
		
		for( int i = 0 ; i < dgt.size() ; ++i )
		{
			dgt.at( i ) = std::stoi( s.substr( dgt_size - 1 - i , 1 ) ) ;
		}
	}

	clk( unsigned int n ): dgt_size{ n_dgts( n ) }
	{
		dgt.resize( dgt_size , 0 ) ;
		scompositrice( n , n_dgts( n ) ) ;
	}


	clk( const clk &a ): dgt_size{ a.dgt_size }
	{
		dgt.resize( dgt_size , 0 ) ;
		for( int i = 0 ; i < dgt.size() ; ++i )
		{
			dgt.at( i ) = a.dgt.at( i ) ;
		}
	}

	clk( clk &&a ): dgt_size{ a.dgt_size }
	{
		dgt.resize( dgt_size , 0 ) ;
		for( int i = 0 ; i < dgt.size() ; ++i )
		{
			dgt.at( i ) = a.dgt.at( i ) ;
		}
		a.dgt.resize( 1 ) ;
	}

	clk& operator = ( const clk &a ) 
	{
		dgt_size = a.dgt_size ;
		dgt.resize( dgt_size , 0 ) ;

		for ( int i = 0 ; i < dgt.size() ; ++i )
		{
			dgt.at( i ) = a.dgt.at( i ) ;
		}

		return *this ;
	}

	clk& operator = ( clk &&a ) 
	{
		dgt_size = a.dgt_size ;
		dgt.resize( dgt_size , 0 ) ;

		for ( int i = 0 ; i < dgt.size() ; ++i )
		{
			dgt.at( i ) = a.dgt.at( i ) ;
		}

		a.dgt_size = 1 ;
		a.dgt.resize( a.dgt_size , 0 ) ;

		return *this ;
	}

	clk& operator * ( const clk &a ) ; 
	clk& operator +( const clk &a ) ;
	clk& operator / ( const clk &a ) ;
	clk& operator - ( const clk &a ) ;
	clk& operator ^ ( const clk &a ) ;

	char peek()
	{
		return ch ;
	}

	size_t power( size_t a , size_t n ) const 
	{
		size_t m = 0, a1 = 1;

		if( n == 0 ) return 1;
		else
			while( m++ < n )
			{
				a1 *= a;
				//++m;
			}
		return a1;
	}

	int n_dgts( int N )
	{
		int m = 0 ;
		if( N == 0 ) return 1;
		else
			while( N >= power( 10 , m )) ++m;
		return m ;
	}

	void scompositrice( int n , int m )   
	{
		if( n < 10 )
			dgt.at( dgt.size() - 1 ) = n;
		else
			while( m >= 1 )
			{
				--m;
				dgt.at( dgt.size() - 1 ) = n / power( 10 , m );
				n = n % power( 10 , m );
				//++dgt_size;
			}
	}

	int ricomponi( const clk &a , int M ) const //ok
	{
		int N = 0 , i = M-1; 
		while ( M > 0 )
		{
			--M;
			N += a.dgt.at( i ) * power( 10 , M );
			--i;
		}
		return  N;
	}

	int summ() const //ok
	{
		int s = 0 ;
		for ( int i = 0 ; i < dgt_size ; ++i )
		{
			s += dgt[ i ] ;
		}
		return s ;
	}

	void printer()
	{
		while( dgt.size() > 1 && dgt.at( dgt.size()-1 ) == 0 )
			dgt.pop_back() ;

		for( size_t i = dgt.size()-1  ; i >= 0 ; --i )
		{
			std::cerr << dgt[ i ] ;
		}
		std::cerr << '\n' ;

	}


private:
    char ch{ '.' } ;
	int dgt_size{ 1 } ;
	std::vector< int > dgt ;


};

clk& clk::operator * ( const clk &a ) 
{
	int x = dgt_size + a.dgt_size ;
	int r_size = x * ( a.dgt_size + 2 ) ;
	int c = 0 , shift = -1 ;

	clk r { r_size } ;

	r.dgt[ r_size ] = { 0 } ;

	for ( int i = 0 ; i < dgt_size ; ++i )
	{
		r.dgt[ i ] = dgt[ i ] ;
	}

	for ( int i = dgt_size ; i < x ; ++i )
	{
		r.dgt[ i ] = a.dgt[ i - dgt_size ] ;
	}

	int n = 1 ;

	for ( int i = dgt_size ; i < x ; ++i )
	{
		++ shift ;
		for ( int j = 0 ; j < x ; ++j )
		{
			if ( j < dgt_size )
			{
				r.dgt[ x * n + j + shift ] = r.dgt[ j ] * r.dgt[ i ] + c ;
				c = 0 ;
				if ( r.dgt[ x * n + j + shift ] > 9 )
				{
					c = r.dgt[ x * n + j + shift ] / 10 ;
					r.dgt[ x * n + j + shift ] = r.dgt[ x * n + j + shift ] % 10 ;
				}
			}
			else
			{
				if ( c != 0 )
				{
					r.dgt[ x * n + j + shift ] = c ;
					c = 0 ;
				}
				else
					r.dgt[ x * n + j + shift ] = 0 ;
			}
		}
		++n ;
	}

	for ( int i = x * ( a.dgt_size + 1 ) ; i < x * ( a.dgt_size + 2 ) ; ++i )
	{
		for ( n = 1 ; n <= a.dgt_size ; ++n  )
		{
			r.dgt[ i ] += r.dgt[ i - n * x ] ;

			if ( r.dgt[ i ] > 9 )
			{
				c += r.dgt[ i ] / 10 ;
				r.dgt[ i ] = r.dgt[ i ] % 10 ;
			}
		}
		if ( c != 0 )
		{
			r.dgt[ i + 1 ] = c ;
			c = 0 ;
		}
	}

	int t_size = x ;
	clk t{ t_size } ;

	for ( int i = x * ( a.dgt_size + 2 ) ; i >= x * ( a.dgt_size + 1 ) ; --i )
	{
		t.dgt[ i - x * ( a.dgt_size + 1 ) ] = r.dgt[ i ] ;
	}

	dgt_size = static_cast< int >( t.dgt.size() ) ;

	dgt.clear() ;
	dgt.resize( dgt_size , 0 ) ;

	*this = clk{ t } ;

	return *this ;
}

clk& clk::operator^( const clk &a )
{
	int n = a.ricomponi( a , a.dgt_size ) ;

	if ( dgt_size == 1 && dgt[ 0 ] == 0 )
	{
		return *this ;
	}
	else if ( n == 0 )
	{
		dgt_size = 1 ;
		dgt[ 0 ] = 1 ;
	}
	else if( n != 0 )
	{
		clk x = clk{ *this } ;
		while ( --n != 0 )
		{
			*this = clk{ *this * x };
		}
	}
	return *this ;
}

clk f1( clk &a , clk &b , clk &c )
{
	switch ( b.peek() )
	{
		//case '+' :
			//return clk{ a + c } ;
		case  '*' :
			return clk{ a *  c } ;
		case '^' :
			return clk{ a ^ c } ;

		default:
		{
			std::cerr << " operatore sconosciuto \n" ;
			return clk{0} ;
		}
	}
}

int main()
{
	char ch = '^' ;

	std::string s[ 2 ] = { "" , "" } ;

	std::cin >> s[ 0 ] >> ch >> s[ 1 ] ;
	clk a{ s[ 0 ] } , b{ ch } , c{ s[ 1 ] } ;

	a = clk { f1( a , b , c ) } ;

	a.printer() ;

	std::cerr << '\n' << a.summ() << '\n' ;

	return 0;
}

[mbozzi]

This is a lot of code.

The first thing I notice is that you're implementing the rule-of-five for no reason, and incorrectly besides. (One issue is that you're implementing move constructors that don't move anything; omit them.)

std::vector will not leak memory; it is correct by construction.

The rule of five (or three, if you prefer) exists as a guideline to make RAII semantics easier to implement. You only need to follow the rule of three in the case where you're managing a resource directly. In this case, your object is composed of a vector, which does the job for you, better.

Since the rule does not apply in this case, you can remove all of your copy constructors, move constructors, copy and move assignment operators, and the destructor.

One other thing -- you should mark your converting constructors explicit.
Give me a bit to look through more of your program.

[mbozzi]

Some more things:

I should mention: errors aren't simply memory leaks. A leak occurs when an allocated resource (for memory leaks the resource is memory) isn't released by the program on time or at all; A leak most likely won't cause any error.

On my computer, your code doesn't terminate.

The binary arithmetic operators should not modify *this in any way. In fact, conventionally they are non-members who accept one parameter by value, operator-assign the copy, and return it.

Canonically the binary operators are non-members implemented in terms of the operator-assignment variant, which is a member function.

Since my Italian is very bad ("operatore sconosciuto" == "unknown operator", right?) I can't guess what "scompotrice" means, which makes this a bit tricky -- without naming to help.

operator^ can be overloaded as an exponent, I suppose -- but the issue is that in client code that mixes clk with integer literals, the meaning will be conflated with XOR, which is the meaning of the operator usually. You need to document that's what you intend, if that's what you intend. I would strongly discourage that -- at the very least, mark your converting constructors explicit if you do this.

Line 162:
The condition in the for-loop is always true, because std::size_t is unsigned.

[ar2007]

mbuozzi Thanks for the reply and advice.

the function "scompositrice", decomposes a number in the single digits to be assigned to "dgt".

operator^, should emulate the function of power between two clk objects.

"operatore sconosciuto" = " unknow operator".

I will try to change the code, eliminating "operator ^", insert the "power" function, for the clk objects.

will transform "operators *" in a global operator, so as to return one of the two objects passed.

see you later.

p.s.- apologize the delay but I was night ...

[coder777]

The member dgt_size shouldn't be there. Just remove it and use dgt.size() instead. That's way more save and you don't need to treat two variables that are basically the same.

Are you sure that something like this r.dgt[ x * n + j + shift ] does not go out of bounds?

There is no memory leak but I would guess you have an out of bounds problem.

[ar2007]

the idea is this:
the operators *, simulates digit by digit multiplication operation;
for example, the extreme condition is given by a multiplication between two integers, the single figure compounds '9'.

Ex. 9999 x 99;
performing this multiplication, we have:

   9999 *         4 digits
     99 =          2 digits

089 991            6 digits 
899 910            6 digits  (here intervenes the 'shift' variable) 
------------ 
989 901            6 digits

the class 'clk', by inserting a string, each algebraic operation actor. after which it is called 'operators *' and then (in my opinion) this happens:
clk A, B clk;
A * B call ---> clk & operator * (const clk & a);
in 'operator *' A becomes the current object (* this), and B becomes the object passed within 'operator *' (const clk & a) ...

It is created inside the operator 'clk' r = {r_size}, who in 'dgt' insert:
- Size of the first operand (ex: 9999 -> dgt_size = 4),
- Size of the second operand (ex: 99 -> A.dgt_size = 2).

x = 6
for entering all the digits, I need r_size is equal to:
r_size = x + a.dgt_size * x + x = x * (a_dgt_size + 2);

The shift variable, does nothing but move left (but being the carrier ordained contrary to shift to the right) to the figures obtained in the partial results.

the final result is given by the simulation of the sum in the column of the individual digits of the partial results.
So the size of 'r', should already be scheduled for construction.

in the end is created 'clk' t, which is only transferred to the final result, content of 'r', in order not to complicate the succeessive multiplication operations from the calculation through 'operators ^'

I hope I was clear and excuse my bad English. :)

[gunnerfunner]

@lastchance - do you remember shortly b4 x-mas (I think) you'd posted a very clever solution to handle extra large numbers that, as far as I can recall, seemed to go beyond C++ limits?

[lastchance]

do you remember shortly b4 x-mas (I think) you'd posted a very clever solution to handle extra large numbers that, as far as I can recall, seemed to go beyond C++ limits? 

Hi @gunnerfunner: it was actually more for fun than anything else (I seem to recall the poster in that thread getting some gentle ribbing) and it is a lot simpler than the present poster's problem. Fundamentally, though, it was just mimicking in computer code what we did on paper in the days before we were allowed calculators. Not sure how much help it would be here, but to avoid drawing unwanted attention to the original thread ...

#include <iostream>
using namespace std;

const int MAXSIZE = 100;

void doubleIt( int *a, int &last )
{
   int i = 0;
   int carry = 0;

   while ( i <= last )
   {
      a[i] = 2 * a[i] + carry;
      carry = a[i] / 10;
      a[i] = a[i] - 10 * carry;
      i++;
   }
   if ( carry > 0 )
   {
      last++;
      a[last] = carry;
   }
}


int main()
{
   int a[MAXSIZE] = { 0 };
   int last = 0;
   
   a[0] = 1;
   for ( int n = 1; n <= 128 ; n++ )
   {
      doubleIt( a, last );
      cout << "2 to the power of " << n << " is ";
      for ( int i = last; i >= 0; i-- ) cout << a[i];
      cout << endl;
   }
}

I did a bit more playing when my in-laws got too much at Christmas and came up with a larger, vectorised version:

#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;


//===== The BigNumber class ============================================


class BigNumber
{
public:
   vector<int> array;

   BigNumber(){};            // no-parameter constructor
   BigNumber( int N );       // construct from integer
};


BigNumber::BigNumber( int N )
{
   int carry;

   if ( N < 0 )
   {
      cout << "Haven't sorted negative numbers yet; watch this space!";
      exit( 1 );
   }
   else if ( N == 0 )
   {
      array.push_back( 0 );
   }
   else
   {
      while ( N > 0 )
      {
         carry = N / 10;
         array.push_back( N - 10 * carry );
         N = carry;
      }
   }
}


//===== Some useful associated functions ===============================


BigNumber multiply( BigNumber a, int m )         // multiply a BigNumber by an int
{
   BigNumber b;
   int i = 0;
   int carry = 0;
   int last = a.array.size()-1;
   int temp;

   while ( i <= last || carry > 0 )
   {
      temp = carry;    if ( i <= last ) temp += m * a.array[i];
      carry = temp / 10;
      b.array.push_back( temp - 10 * carry );
      i++;
   }
   return b;
}


ostream & operator<< ( ostream &stream, BigNumber b )
{
   for ( int i = b.array.size() - 1; i >= 0; i-- ) stream << b.array[i];
   return stream;
}


//======================================================================


int main()
{
   vector<BigNumber> elements;
   int first, m, ntimes;
   int i;

   cout << "Input a number to start? (default is 1): "           ;   cin >> first;
   cout << "What do you want to multiply it by? (default is 2): ";   cin >> m;
   cout << "How many times? (default is 63): "                   ;   cin >> ntimes;
   cout << endl;

   elements.push_back( BigNumber( first ) );
   for ( i = 1; i <= ntimes ; i++ ) elements.push_back( multiply( elements[i-1], m ) );
   for ( i = 0; i <= ntimes ; i++ ) cout << i << ":  " << elements[i] << endl;

   cout << endl;


   BigNumber b = 1;
   int N;
   cout << "How many factorials do you want? (> 1): " << endl;   cin >> N;


   for ( i = 1; i <= N ; i++ )
   {
      b = multiply( b, i );
      cout << i << " factorial is " << b << "\n\n";
   }
}

[ar2007]

thx @gunnerfunner && @lastchance but it is not what I intended realize

[ar2007]

solved !!
in line 252, (for loop) I had forgotten a "-1", which on paper was present.

	for ( int i = x * ( a.dgt_size + 2 ) - 1 ; i >= x * ( a.dgt_size + 1 ) ; --i )
	{
		t.dgt[ i - x * ( a.dgt_size + 1 ) ] = r.dgt[ i ] ;
	}

Now it works well. to improve instead of code to create the type clk r and t objects, r and t, I created them with vector of size_t type.

I can also compute 123456789 ^ 9000

thx all for the reply.