Double free or corruption memory dump

[vaderboi]

When compiling my program, I continue to get this error message: "***Error in `./TwoSum': double error or corruption (fasstop)...". I don't know how to read assembly code readouts but I know that the problem occurs when "solutionValues" is returned because the print outs end right before "return solutionValues".

Does anyone know why the core is dumping?

#include <vector>
#include <iostream>

using namespace std;

vector<int> twoSum( vector<int>& nums, int target );

int main()
{
	vector<int> nums { 502, 1000, 1, 15, 40, 8, 40, 100 };
	int target = 9;

	vector<int> newVector(twoSum( nums, target ));

	return 0; 
}

vector<int> twoSum( vector<int>& nums, int target)
{

        if( nums.size() == 1 )
        {
             vector<int> singleElementVector ( nums );
             return singleElementVector;
        }

	for( unsigned int i = 0; i < nums.size() - 1; i++ )
	{
		if( (nums[0] + nums[i + 1]) == target )
		{
			cout << "If condition met" << endl;
			vector<int> solutionValues;

			cout << "Vector initialized" << endl;
			solutionValues.push_back( nums[0] );
			solutionValues.push_back( nums[i + 1] );

			cout << "Values pushed in to vector" << endl;
			return solutionValues;
		}
	}
	
        cout << "for loop exited" << endl;
	vector<int> newVector ( nums );
	newVector.erase( newVector.begin() );
	twoSum( newVector, target );
	
}

[helios]

1. You forgot to return something if the for loop exits. Did you maybe intend to return the return value of the recursive call?
2. If there are no values in nums that add up to target, twoSum() recurses infinitely.
3. This is a less serious problem, but there are much more efficient ways to implement this.

[vaderboi]

I forgot to add the if-condition. With the if-condition, there doesn't need to be a return value in the for loop. Even with the if-condition, I get the same memory dump.

[TheIdeasMan]

Hi,

The compiler says:

In function 'std::vector<int> twoSum(std::vector<int>&, int)':
42:1: warning: control reaches end of non-void function [-Wreturn-type]

This happens because of the if statement on line 23, if it is false no value is returned, hence the warning.

I didn't get the error you mentioned, what was the full text of that error, verbatim? In future always post the full error message.

I don't like the look of line 13, it looks too much like a function declaration.

I also would prefer not to have the same variable name inside the function newVector as the one in main on the line which calls the function.

Why did you mention assembly code readouts?

Line 23 is the base case for the recursion, It may be helpful to comment it as such, and comment the function itself as being recursive.

The target parameter should be const in the function definition.

[jonnin]

looks like its under control but FYI if you set null after a delete or free, the next time you do it is safe (defensive coding technique).

[vaderboi]

@TheIdeasMan-

I don't get the same compiler error that you do.

The compiler prints out a section called "backtrace" which lists the executable and then specific memory addresses. Then it prints out a section called "memory map" which lists a bunch of code I don't recognize. All of these errors would take me forever to copy and paste here from the compiler terminal and I don't know how to copy paste from the terminal in to the Google environment. I mentioned assembly code readouts because I don't know what else to call what the compiler printed out to the console.

Line 13 still adheres to the C++ standard and is in fact the example given for how to copy values from one vector to another in the documentation. I don't really feel compelled to change it because of that reason, unless you have found it to be confusing to other programmers in your experience.

Why would I need to change the variable name in main()? Wouldn't it existing in a different scope be enough for someone to not be confused?

I feel like it is pretty clear that it is recursion since it calls itself. Once again, I am confused by this suggestion.

I will comment in the base case. Also, yes, "const" would be more specific and I will apply it to my code.

I appreciate your input, but don't necessarily agree with all of your suggestions. I am, however, willing to hear any arguments you have for why you think your suggestions should be implemented. I hope this doesn't come across as hostile. I just don't understand the purpose of some of your suggestions.

[helios]

There's still the matter that if control flow reaches this part:

        cout << "for loop exited" << endl;
	vector<int> newVector ( nums );
	newVector.erase( newVector.begin() );
	twoSum( newVector, target );
	
}

the behavior is undefined. It's a non-void function with a control path without a return statement.

[vaderboi]

@helios- I am such a fool. I forgot that you need to return the recursive call. I added it and now the errors disappear.

Also, you said you know a more efficient way to implement this function. What would it be? My code runs a smaller for loop every recursive call so at the very worst it is O(N), right? Or is it O(log N)? Or something different?

[helios]

Your code runs in O(n^2) time, which I believe it's the best time for this problem (someone correct me if I'm wrong), but it runs in O(n^2) space:
If the input vector is [a, b, c, d, e], at the first recursive level you allocate [b, c, d, e], at the second you allocate [c, d, e], etc.

This could be solved in O(1) space using two nested loops.

[TheIdeasMan]

@vaderboi

I don't get the same compiler error that you do.

Maybe you don't have the same warnings turned on. I used cpp.sh with all 3 warning levels turned on.

The compiler prints out a section called "backtrace" which lists the executable and then specific memory addresses. Then it prints out a section called "memory map" which lists a bunch of code I don't recognize.

It seems you are using the debugger, not a compiler. It's a really good idea to compile with different compilers, and realize that you are not finished until all the warnings are gone. Warnings are your friend, just like a human with a medical problem, they diagnose potential / likely problems. Then use the debugger to solve any logic / run time errors.

Line 13 still adheres to the C++ standard ....

That's fine :+)

Why would I need to change the variable name in main()? Wouldn't it existing in a different scope be enough for someone to not be confused?

Sure, it's different scope, I just don't like it. These sorts of things lead to other kinds of errors when one forgets they are in a different scope.

I feel like it is pretty clear that it is recursion since it calls itself. Once again, I am confused by this suggestion.

Again, it is something that is technically unnecessary but I find really helpful. Especially for the base case, it is something a recursive function must have, so I find it helpful to comment it.

Regards :+)

[vaderboi]

@TheIdeasMan

Maybe you don't have the same warnings turned on. I used cpp.sh with all 3 warning levels turned on.

That may be so. I haven't turned on all the warnings flags.

It seems you are using the debugger, not a compiler. It's a really good idea to compile with different compilers, and realize that you are not finished until all the warnings are gone. Warnings are your friend, just like a human with a medical problem, they diagnose potential / likely problems. Then use the debugger to solve any logic / run time errors.

I don't think so. I have been compiling with g++ in the Unix command line.

[TheIdeasMan]

I haven't turned on all the warnings flags.

it's really good idea to compile with at least this:

g++ -std=c++17 - Wall -Wextra -pedantic-errors .......

There are zillions of other options with g++, it's worth reading the manual to find other helpful ones.

I have been compiling with g++ in the Unix command line.

Just that it's the debugger which does a backtrace, maybe your system is configured to do that whenever there is a segmentation fault. And one would have to run the program in order for that to happen. Maybe you compiled and run all in one command, by using the && in between compile and the run? in a shell the && means that if the first command is successful, then run the second command.

Seen as you are using Linux, another compiler to use would be clang++ , it's very similar to use as g++, but it sometimes gives slightly different results in some circumstances.

[dhayden]

twoSum() will crash if you pass it an empty vector. Change line 21 to if (nums.size() <= 1). Also, since you're returning the vector by value, lines 23 & 24 could just be return nums;. The compiler will automatically make a copy of nums for the return vector.

This could be done in O(n*log(n)) time and O(n) space as follows:
- pass nums by value
- sort nums
- starting with the first value in nums:
- search backward from the end of nums for target-value
- if you don't find target-value then move up from the left to the next value in nums
- move back from the right, looking for the target - (new value).
- repeat until you find a matching pair or the left & right meet in the middle.

[vaderboi]

For some reason I thought it would run in O(log n) but that doesn't make any sense. If I use the summation formula to figure out how many iterations there would be the number of iterations would come out to (1/2 * n^2) which still has a time complexity of O(n^2).

@TheIdeasMan- I will keep that in mind. I get pretty lazy with the flags but that's a bad habit. I didn't use the && command. I compiled it and then ran it separately.

@dhayden- Thank you. I should have put a check for that condition. And yeah, I'll probably have to do a merge sort. Plus, if one of the halves, once sorted, has an integer at arrayHalf[0] that is more than the target value then the entire array can be deleted since it doesn't have to be considered anymore.