1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Working with classes and vectors in C++

  1. Dec 8, 2017 #1

    diredragon

    User Avatar
    Gold Member

    1. The problem statement, all variables and given/known data
    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:
    Code (C):

        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:
    Code (C):

    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:
    Code (C):

    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.
    2. Relevant equations
    3. The attempt at a solution

    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:
    Code (C):

    Complex number1("23 + 12i");
     
    Important thing about Complex is that it's operator= is deleted meaning you cant 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:
    Code (C):

    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)
    Code (C):

    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?
     
  2. jcsd
  3. Dec 8, 2017 #2

    I like Serena

    User Avatar
    Homework Helper

    How about a recursive function so that we only need a copy or move constructor?
     
  4. Dec 8, 2017 #3

    Mark44

    Staff: Mentor

    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.
     
  5. Dec 9, 2017 #4

    diredragon

    User Avatar
    Gold Member

    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:
    Code (C):

    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.
    Code (C):

    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.

    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:
    Code (C):

    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&);
    };
     
  6. Dec 9, 2017 #5

    I like Serena

    User Avatar
    Homework Helper

    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:
    Code (C):

        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.
     
  7. Dec 9, 2017 #6

    diredragon

    User Avatar
    Gold Member

    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?
    Code (C):

        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:
    Code (C):

    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?
     
  8. Dec 9, 2017 #7

    I like Serena

    User Avatar
    Homework Helper

    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:
    Code (C):

        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:
    Code (C):

        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.
     
  9. Dec 9, 2017 #8

    Mark44

    Staff: Mentor

    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.
     
  10. Dec 9, 2017 #9

    I like Serena

    User Avatar
    Homework Helper

     
  11. Dec 9, 2017 #10

    diredragon

    User Avatar
    Gold Member

    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.
    Code (C):

        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 im 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:
    Code (C):

    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?
     
  12. Dec 9, 2017 #11

    diredragon

    User Avatar
    Gold Member

    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.
     
  13. Dec 10, 2017 #12

    I like Serena

    User Avatar
    Homework Helper

    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:
    Code (C):

    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.
     
  14. Dec 10, 2017 #13

    diredragon

    User Avatar
    Gold Member

    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 cant seem to find a way. Here you see the code i commented so you can better understand my idea:
    Code (C):

    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?
     
  15. Dec 10, 2017 #14

    I like Serena

    User Avatar
    Homework Helper

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

    unique_ptr<Complex> result(new Complex("0"));
    for (size_t i = X; i < Y; ++i)
        result.reset(new Complex(*result + *numbers[i]));
     
     
  16. Dec 11, 2017 #15

    diredragon

    User Avatar
    Gold Member

    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:
    Code (C):

    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:
    Code (C):

    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?
     
  17. Dec 26, 2017 #16
    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
     
    Last edited by a moderator: Dec 26, 2017
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Working with classes and vectors in C++
  1. C++ card class errors (Replies: 28)

  2. C++ class function (Replies: 2)

Loading...