Working with classes and vectors in C++

[diredragon]

Homework Statement

Write a BinaryTree Class using these specifications:
A Class Node represents a standard node of the tree with fields and a constructor like given below:

    int start, end;
    const Complex* value; //I will provide more information about Complex later because that was the part of another assignment had and is used here also.
    Node *left;
    Node *right;
public:
    Node(int start, int end, const Complex* val);

The function for this constructor i wrote and here it is:

Node::Node(int startt, int endd, const Complex* val) {
    start = startt;
    end = endd;
    value = val; //btw is this ok? Can i lose this val when i leave the function so i would need to do something else here?
    left = nullptr;
    right = nullptr;
}

A BinaryTree class has a field and an appropriate constructor like below:

Node* root;
BinaryTree(vector<Complex*>& numbers);

Explanation to how the Binary Tree is created in the constructor:
A Binary Tree is created from an array of Complex numbers in this manner:
The ROOT has the indexes as the array meaning start equals beginning of array and end equals end of array and the value of the sum of all the numbers in the array. The Node to the LEFT of the ROOT has the indexes from the start to the middle of the array (including middle if odd number of values in array) and the value of the sum of Complex those indexes include. The Node to the RIGHT has the remaining in the same manner. This continues until there are all the values of the array in the tree's leaves, meaning those leaves have the indexes of only one number in the array.

Homework Equations

3. The Attempt at a Solution [/B]
A Little something about Complex which is mentioned here:
Complex is a Class which represents Complex numbers. It has two fields: The REAL part and the IMAGINARY part. You can create a Complex number like this:

Complex number1("23 + 12i");

Important thing about Complex is that it's operator= is deleted meaning you can't change the values one's it's been created. The other is that the constructors of COPY and MOVE work and function ADD and it's operator+ exist so you can add the two Complex Numbers like this:

Complex number3(number1 + number2);

Now let's move on to the problem at hand. I started writing the code for the BinaryTree constructor but got to a problem. I don't know how to sum up all the numbers in the array since my Complex is immutable (and it needs to be btw)

class BinaryTree {
    Node *root;
public:
    BinaryTree(vector<Complex*>& numbers);
};
BinaryTree::BinaryTree(vector<Complex*>& numbers) {
//...
}

I know that the values constructor of the node takes are (0, numbers.size() - 1, Complex* res) but i do not know how to call the constructor here for the root since it's in another class and how do i sum all of these numbers. It would be easy if i could say some result = 0 and then sum in one for loop but here i have immutable type so i cannot do that. Can someone help me with this?

 

[I like Serena]

How about a recursive function so that we only need a copy or move constructor?

 

[Mark44]

Since the heart of this program is the Complex class, it would be useful to see how it is defined. The std namespace in C++ has a template named complex, but the one your program is using seems obviously different. For one thing, the usual complex class doesn't have any constructors that take strings as their arguments.

 

[diredragon]

How about a recursive function so that we only need a copy or move constructor?

Are you talking about a recursive function for the BinaryTree creating or the number summing? If you're talking about the BinaryTree creating it would be much easier that way but sadly it is forbidden to use and i forgot to mention that. I need to write it without the use of recursive function. As for the summing of the numbers i found an easy way to do that using a vector array:

BinaryTree::BinaryTree(vector<Complex*>& numbers) {
    Complex zero("0 + 0i");
    vector<Complex> result = { zero };
    for (int i = 0; i < numbers.size(); i++) {
        result.push_back(result[i] + *numbers[i]); //The sum of all the numbers so far will be the last number of the array
    }
    const Complex* point_res = &result[result.size() - 1];
    root = new Node(0, numbers.size() - 1, point_res); //Here i just call upon the constructor of Node to create the root.
    int n = root->Ending; //This for some reason does not work. I don;t know why.
}

Ending is a method function inside the Node class which return an integer which represents the ending index of array.

class Node {
    int start, end;
    const Complex* value; //I will provide more information about Complex later because that was the part of another assignment had and is used here also.
    Node *left;
    Node *right;
public:
    Node(int start, int end, const Complex* val);
    int Ending() {
    return end;
   }
};

I have no idea why the above mention problem exist but i solved the problem of summing and calling constructors. Now what i have to work out is this problem and the iterative solution to creating a tree. Do you think i need to use a stack? It seems pretty complicated to keep track of all of the nodes i initialized and created.

Since the heart of this program is the Complex class, it would be useful to see how it is defined. The std namespace in C++ has a template named complex, but the one your program is using seems obviously different. For one thing, the usual complex class doesn't have any constructors that take strings as their arguments.

The Complex class is used here only to sum the numbers and use that value in the node because it has a field Complex* val which represents the sum from the starting to the ending index. I have solved that summing problem above and now i have the issue of creating the tree without using the recursive function.
Here I will post the definition of the Complex class but i don't think it resents a problem anymore:

class Complex {
    int *real, *imag;

    Complex& operator=(const Complex& right) = delete;

public:
    //Constructor which creates a complex number. You an create it like this: Complex n("1 + 2i") or Complex n("1 - 2i") or Complex n("-2i") ... you get the idea.
    Complex(char* num);
    //Destructor
    ~Complex() { delete[] real; delete[] imag; };
    //Deep Copy Constructor
    Complex(const Complex& num);
    //Move Copy Constructor
    Complex(Complex&& number);

    //ADD Method Function
    Complex add(Complex* num);

    friend ostream& operator<<(ostream& out, const Complex&);

    friend Complex operator+ (const Complex&, const Complex&);
};

 

[I like Serena]

Alternatively we can use a pointer that we keep freeing and allocating.
I'm just realizing that this is probably why there is a pointer to Complex in your tree.
That is, we can do:

    unique_ptr<Complex> result(new Complex("0"));
    for (const auto& z : numbers)
        result.reset(new Complex(*result + z));

Furthermore, I can see that the Complex class has pointers to arrays to keep multiple values.
So it internally supports arrays of complex numbers that it can add.
I'm guessing that is for vectorized optimization, which would finally make a bit more sense why we would want to use a class like this Complex over std::complex.

 

[diredragon]

Alternatively we can use a pointer that we keep freeing and allocating.
I'm just realizing that this is probably why there is a pointer to Complex in your tree.
That is, we can do:

    unique_ptr<Complex> result(new Complex("0"));
    for (const auto& z : numbers)
        result.reset(new Complex(*result + z));

Furthermore, I can see that the Complex class has pointers to arrays to keep multiple values.
So it internally supports arrays of complex numbers that it can add.
I'm guessing that is for vectorized optimization, which would finally make a bit more sense why we would want to use a class like this Complex over std::complex.

I haven't worked with unique_ptr before. Does this mean that i can use it's last value and add it to something at the same time as resetting and storing the result in the place the last one was?

    unique_ptr<Complex> result(new Complex("0"));
    for (const auto& z : numbers)
        result.reset(new Complex(*result + *z));

I made a small correction as it need to be *z.
And also, the Complex class has pointers to arrays not to store multiple numbers but to not have a type-memory limited real and imaginary field. Like if i said that the real part is a float it would have some limitation but when i use pointers the only limitation is the memory of the hardware. The arrays keep digits (decimals not included) so your real part can have as much digits as you like. It was the specification of the last problem i did. It can't change in this one. I made the changes you suggested:

unique_ptr<Complex> result(new Complex("0"));
    for (const auto& z : numbers)
        result.reset(new Complex(*result + *z));
    const Complex resultt(*result);
    root = new Node(0, values.size() - 1, &resultt)

This seems easier than having to use vectors. For the harder part do you have any suggestions? How to start creating the tree? I need to use the stack right?

 

[I like Serena]

Yes. unique_ptr is a so called smart pointer, meaning that it does the freeing for you. Either when it goes out of scope, or when a new pointer is assigned to it.
I recommend to replace all occurrences of Complex* with it, or alternatively with shared_ptr<Complex>.
Otherwise it will be difficult to figure out where and when a pointer should be freed without making mistakes.

Either way, we can also do:

    const Complex* result(new Complex("0"));
    for (const auto& z : numbers) {
        Complex newResult = *result + *z;
        delete result;
        result = new Complex(newResult);
    }

So now you have a const Complex* as desired.

Or alternatively:

    unique_ptr<Complex> result(new Complex("0"));
    for (const auto& z : numbers)
        result.reset(new Complex(*result + *z));
    const Complex* val = result.get();
    result.release();

This way, we still have the benefit of using unique_ptr, but we convert its value to a const Complex* when needed.
The release() function means that the unique_ptr won't delete its pointer anymore. That is now the responsibility of the code after.

 

[Mark44]

The Complex class is used here only to sum the numbers and use that value in the node because it has a field Complex* val which represents the sum from the starting to the ending index.

class Complex {
   int*real, int * imag;

Why are the real and imag data members pointers? Things would be a lot simpler if these two members weren't pointers, especially in the code for constructors, copy constructors and destructors.

Is the Complex class given to you in this problem, or is it your own design? I don't understand your explanation of this class above.

 

[I like Serena]

Why are the real and imag data members pointers? Things would be a lot simpler if these two members weren't pointers, especially in the code for constructors, copy constructors and destructors.

Is the Complex class given to you in this problem, or is it your own design? I don't understand your explanation of this class above.

the Complex class has pointers to arrays not to store multiple numbers but to not have a type-memory limited real and imaginary field. Like if i said that the real part is a float it would have some limitation but when i use pointers the only limitation is the memory of the hardware. The arrays keep digits (decimals not included) so your real part can have as much digits as you like. It was the specification of the last problem i did. It can't change in this one.

 

[diredragon]

Yes. unique_ptr is a so called smart pointer, meaning that it does the freeing for you. Either when it goes out of scope, or when a new pointer is assigned to it.
I recommend to replace all occurrences of Complex* with it, or alternatively with shared_ptr<Complex>.
Otherwise it will be difficult to figure out where and when a pointer should be freed without making mistakes.

Either way, we can also do:

    const Complex* result(new Complex("0"));
    for (const auto& z : numbers) {
        Complex newResult = *result + *z;
        delete result;
        result = new Complex(newResult);
    }

So now you have a const Complex* as desired.

Or alternatively:

    unique_ptr<Complex> result(new Complex("0"));
    for (const auto& z : numbers)
        result.reset(new Complex(*result + *z));
    const Complex* val = result.get();
    result.release();

This way, we still have the benefit of using unique_ptr, but we convert its value to a const Complex* when needed.
The release() function means that the unique_ptr won't delete its pointer anymore. That is now the responsibility of the code after.

So i tried creating the tree and had an idea of using a stack to go from root, create all the left nodes and keep them in the stack so i can later come back, pick them up and create the right nodes for them. It should work since stack piles data up on the top so i can retrace my steps. This is just the beginning and i have a problem with limiting the auto part of the summing. Also what do you think of the idea?
Bear in mind that setLeft and getLeft are simple method functions of the Node class which i use to set the left and to get the left part respectively.

    unique_ptr<Complex> result(new Complex("0"));
    for (const auto& z : numbers)
        result.reset(new Complex(*result + *z));
   const Complex resultt(*result);
    root = new Node(0, numbers.size() - 1, &resultt);
    result.release();

   Node* lastVisitedNode = nullptr;
    stack<Node*>* unvisitedNodes = new stack<Node*>;
    int n = numbers.size();
    Node* current = root; //Shows the current pointer to node I am using.
    while ((n /= 2) != 1) {
        int start = 0, end = n;
        result.reset(new Complex("0"));
        for (const auto& z : values) //I can't find how to limit this to only sum from x to y position
            result.reset(new Complex(*result + *z));
        const Complex result1(*result);
        root->setLeft(new Node(start, end, &result1));
        unvisitedNodes->push(current); //Pushing the current to the stack so i now that the last in stack is the ROOT
        current = current->getLeft();
    }

Here is how they look like:

void Node::setLeft(Node* node) {
    left = node;
}
Node* Node::getLeft() {
    return left;
}

How do i limit the auto part you suggested earlier so it summes from x to y and not everything?

 

[diredragon]

Why are the real and imag data members pointers? Things would be a lot simpler if these two members weren't pointers, especially in the code for constructors, copy constructors and destructors.

Is the Complex class given to you in this problem, or is it your own design? I don't understand your explanation of this class above.

It's from the assignment i was given before this one and it is supposed to be like this, using pointers so the number of digits u can pass for real and imaginary part is not limited by the amount of space a built in type can have.

 

[I like Serena]

Do you classes 'own' their raw pointers?
That is, delete them upon destruction?
And allocate a copy when a pointer is passed to their constructors?

Because if you don't, your code will access memory that is gone, causing access violations.
Most notably the 'const Complex result1(*result);' inside your while loop will go out of scope even though it will still be referenced in your tree.

So first of, I recommend that instead of declaring 'const Complex result1(*result);', to simply pass 'result.get()', which is already a 'const Complex*'.

And I recommend that the 'Node' constructor makes a copy of the pointer passes to it.
That is:

Node::Node(int start, int end, const Complex* val) {
   value = new Complex(*val);
   ...
}
Node::~Node() {
    delete value;
}

So that ownership is clearly established, and we do not get access violations or memory leaks.
Even better would be to make the argument 'const Complex& val', so that it is clear that we're not transferring ownership of a pointer.

 

[diredragon]

Do you classes 'own' their raw pointers?
That is, delete them upon destruction?
And allocate a copy when a pointer is passed to their constructors?

Because if you don't, your code will access memory that is gone, causing access violations.
Most notably the 'const Complex result1(*result);' inside your while loop will go out of scope even though it will still be referenced in your tree.

So first of, I recommend that instead of declaring 'const Complex result1(*result);', to simply pass 'result.get()', which is already a 'const Complex*'.

And I recommend that the 'Node' constructor makes a copy of the pointer passes to it.
That is:

Node::Node(int start, int end, const Complex* val) {
   value = new Complex(*val);
   ...
}
Node::~Node() {
    delete value;
}

So that ownership is clearly established, and we do not get access violations or memory leaks.
Even better would be to make the argument 'const Complex& val', so that it is clear that we're not transferring ownership of a pointer.

I did have a destructor in the class Node. I also made the change you suggested and that was exactly what i was worried about in the first post i made. Now it creates it's own copy.
Below is the part of the code which creates a tree's all LEFT nodes and also keeps them in the stack so i can later return to them. I also used result.get(). Can you tell me how do i only sum from X to Y using this auto& z : numbers you used? I can't seem to find a way. Here you see the code i commented so you can better understand my idea:

unique_ptr<Complex> result(new Complex("0"));
    Node* lastVisitedNode = nullptr;
    stack<Node*>* unvisitedNodes = new stack<Node*>;
    Node* current = root, *lastNode = nullptr;

    int n = numbers.size() - 1;
    int start, end;
    bool check = false; //Just using this to check something
    while (n != 0) {  //I make the LEFT Nodes until there are no numbers to add.
        if (check == false) { //Only runs on first go.
            start = 0;
            end = n;
           check = true;
        }
        else { //My starting and ending points change depending on what the [I]Mother[/I] Node has as her's. The should be half the size.
            start = lastNode->getStart();
            end = lastNode->getEnd() / 2;
        }
        result.reset(new Complex("0"));
        for (const auto& z : numbers) //The most troublesome part. I seem to find no way to only sum from start to end. Cant find it online.
            result.reset(new Complex(*result + *z));

        current = new Node(start, end, result.get()); //I create my Current Node with the results i have.
        result.release();

        if (check == true)
            lastNode->setLeft(current); //This runs from the second until the end of while loop. It connects the last and the current Node.

        lastNode = current; //The last is now current.
        current =nullptr;
        unvisitedNodes->push(lastNode);//U push the last one on the stack so i can use it later to make the right part. The ROOT is the last node the stack will have.
        n = n / 2;
    }
}

My current problem is the one i bolded above. The auto part. Also what do you think of this so far?

 

[I like Serena]

how do i only sum from X to Y using this auto& z : numbers you used?

The ranged-for loop always loops over the entire collection.
To limit the range just use a regular for-loop:

unique_ptr<Complex> result(new Complex("0"));
for (size_t i = X; i < Y; ++i)
    result.reset(new Complex(*result + *numbers[i]));

 

[diredragon]

The ranged-for loop always loops over the entire collection.
To limit the range just use a regular for-loop:

unique_ptr<Complex> result(new Complex("0"));
for (size_t i = X; i < Y; ++i)
    result.reset(new Complex(*result + *numbers[i]));

I have successfully written a function that creates a tree, thanks to your suggestions. I have a question about the destructor for this tree.
I have a destructor for my Complex class and my Node class in their defintions:

Complex::~Complex() {
   delete[] whole;
   delete[] fraction;
};

Node::~Node() {
    delete value;
}

And I'm trying to write a recursive destructor for my BinaryTree class and something is off. I used a helper function Clear which you see here:

class BinaryTree {
    Node *root;
public:
    //Constructor
    BinaryTreeTree(vector<Complex*>& numbers);
    //Destructor
    ~BinaryTreeTree() {
        Clear(root);
    };
    void Clear(Node*& node);
};void BinaryTree::Clear(Node*& node) {
    if (node == nullptr)
        return;
    if (node->getRight() != nullptr)
        Clear(node->getLeft());
    if (node->getRight() != nullptr)
        Clear(node->getRight());

    delete node;
    node = nullptr;

}

This line Clear(node->getLeft()); and Clear(node->getRight()); give me trouble. The expression inside the parenthesis won't compile and it gives error:
initial value of reference to non-const must be an lvalue
The functions getLeft and getRight are method functions of the Node class and they simply return left and right respectively. Whats the problem here and should this work?

 

[ruskointhehizzy]

that has to do with the way you are passing the node. (function parameters)
from microsoft "Every C++ expression is either an lvalue or an rvalue. An lvalue refers to an object that persists beyond a single expression. You can think of an lvalue as an object that has a name. All variables, including nonmodifiable (const) variables, are lvalues. An rvalue is a temporary value that does not persist beyond the expression that uses it."
That should help clear things up.
A temporary object may not be bound to a non constant reference.
try passing a non-reference. Or try passing a const reference, your choice.
I would go with: void BinaryTree::Clear(Node* const &node)
You might even might want to make that function const.

sorry I am using high contrast settings so can't see reply buttons and stuff like that...

Also the constructor and destructor should be named BinaryTree not BinaryTreeTree but I think that's just a typos