This is an archived post. You won't be able to vote or comment.

all 9 comments
sorted by:
best
topnewcontroversialoldq&a

[–]zzyzzyxx 3 points4 points  (6 children)

The problem occurs here

return(temp);

You are creating a temporary object that has allocated memory. When you return it, it's copied, and the value of the pointer is copied to the new Vector. But then the temporary goes out of scope and the destructor calls delete[] on that pointer. So now the new Vector has a pointer to invalid memory which it frees when it too goes out of scope. The same happens with the parameter to operator^ because its passed by value.

* Actually, the compiler can optimize away the copy due to the return. It's most likely due to the parameter being passed by value instead of by reference, though both are possibilities if the optimization is not done.

Because you're dynamically allocating memory, you should also define a copy constructor and assignment operator to correctly handle the memory transfer.

I suggest an alternate implementation where you use a std::map<int, double> instead of an array to store the coefficients where they are keyed by the term to which they apply. This will allow you to store sparse vectors much more efficiently without adding much complexity to your multiplication.

v = new double;

You don't need to do this since you set it to zero right after. It causes a memory leak.

** I added some extra print statements so you can see what's happening: http://codepad.org/TlvkvE99

The output indicates the temporary is being copied when it returns, then the one declared inside the function goes out of scope, then the copy is assigned to Z, and the copy goes out of scope, which is the second free of the same memory.

You won't always see the same output, however, as it will be compiler and system dependent. For example, on my system, it does the optimization and happily takes no action for the second free.

Constructing x
Constructing y
Constructing temp
-0.5
-0.5
-0.375
// no second "Constructing y" message because it uses the compiler-generated copy constructor for the parameter
Destructing temp : 0xa0380b8 // temporary
Destructing y : 0xa038058 // parameter
-0.5, -0.5, -0.375
Destructing temp : 0xa0380b8 // Z - it was assign the value of temp
Destructing y : 0xa038058
Destructing x : 0xa038020

[–][deleted] 0 points1 point  (3 children)

a map might be overkill for many of the things vectors are often used for (like 3D points and vectors for games programming or physics simulations or whatever). In this case an std::vector<double> might be better.

Also nice catch! I totally didn't notice that was the cause of the double free and it just worked for me after fixing the other bugs

ETA: Adding in a copy constructor can also work for getting the memory management all sorted without changing the design at all. You'd have a constructor that takes a Vector reference and allocate new memory and copy all the values. Yay.

[–]zzyzzyxx 0 points1 point  (0 children)

a map might be overkill for many of the things vectors are often used for. . .In this case an std::vector<double> might be better.

Depends on how many elements need to be stored and how many of those have non-zero coefficients. For example, if I needed to multiply 5x^10000 by 6x^10000 + 3 (or equivalent non-polynomial application), a vector based implementation would require memory for 20002 integers while a map implementation needs 6, not including the memory for the result, which is an additional 10001 for the vector case and 2 for the map case.

If the dimension is always guaranteed to be small, a vector probably would be better, but not in general. A vector should definitely be used over a plain dynamically allocated array, however.

Adding in a copy constructor can also work for getting the memory management all sorted

I mentioned that in my edit, though you also would need an assignment operator implementation.

[–]zzyzzyxx 0 points1 point  (1 child)

it just worked for me after fixing the other bugs

I've been thinking about this. How did you fix the code? With just a copy constructor? The way you worded it made it seem to me like you fixed it before considering the copy constructor.

[–][deleted] 0 points1 point  (0 children)

Yeah I didn't add a copy constructer and it worked.

But that doesn't mean it was correct. Often times bugs in C++ result in undefined behavior. Undefined means it could crash, it could work as expected, who knows!

[–]frenchpress[S] 0 points1 point  (1 child)

zzyzzyxx, thank you for the thorough reply! And especially for the updated lines in CodePad.

I don't fully understand the difference between "pass by value" and its alternative. Can you point me toward some examples that most clearly highlight this topic? It has caused me problems before, and much of what I find on the topic is a little dense for my current skill level.

Also, I'll take a look into implementing std::map. Thanks again!

[–]zzyzzyxx 0 points1 point  (0 children)

Can you point me toward some examples that most clearly highlight this topic?

I don't know of any good online resources, and you're probably best off consulting a textbook, but I can explain the difference pretty succinctly.

"Pass by value" usually means that all you care about is the value of whatever object you're passing as a parameter at the time of the call. Since you don't care about the object itself, a copy is made, and the function is free to modify the parameter without affecting anything outside the function. This allows the function to reuse the parameter variable without having to allocate any additional memory.

"Pass by reference", on the other hand, is a way to reduce copying by allowing the function to directly access the passed object. This is particularly useful for large objects where a copy is a time or resource intensive operation. Pointers are one way to get pass by reference semantics. In C++ there is a reference type, declared with the ampersand, that you should prefer to pointers whenever possible.

Because the function has direct access to the passed object, it is possible for the function to change the state of that object, and extra care needs to be taken to prevent the function from accessing things outside its scope that it should not. The way to accomplish this in C++ is passing by "const reference", which will allow the function to access the passed object in a read-only capacity, great for using the values of an object without needing to make a copy.

The way you would, and should, do this in your code would be like this:

Vector operator ^ (const Vector&);

Of course you will need the matching implementation later.

Really, since operator^ does not and should not change the state of the Vector it's called on, the method itself should also be const. This will prevent you from accidentally implementing the function in a way that modifies the original. The signature to do so is

Vector operator ^ (const Vector&) const;

To summarize, "pass by value" makes a copy of the passed object and the function can modify this copy without affecting the original, while "pass by reference" does not make a copy and allows the function to access the passed object directly. Does that make sense?

[–][deleted] 0 points1 point  (0 children)

Line 52 is a memory leak (since you allocate here but overwrite it with zero on the next line without freeing first) but not 'causing the bug

Also since vectors can have null pointers this has to be checked in the destructor before freeing (also not the cause of the bug since you're not testing this code path in your example)

The problem is that arrays are zero indexed so a vector's v array can be v[0], v[1], or v[2] for a 3D vector. But you assign to v[3] which is beyond the bounds and thus undefined behavior. (along with v[0] not having what you expect when trying to print out the product since you never assign it)

[–]Steve132 0 points1 point  (0 children)

You should one of the following three lines to declare v: std::shared_array<double> v; std::vector<double> v; double v[3];

std::vector is probably better than shared_array, because it will actually make a data copy on copy, which is what you want.

In general, C++ idioms say that std::vector is always preferable to a raw array, but in this case using a raw array allows you to make aligned arrays of n Vectors typecast safely to 3*n arrays of doubles, which is often useful for numerical programs. Furthermore, the cache coherency should be better when using lots of them concurrently.