2
\$\begingroup\$
    #ifndef VECTOR_H
    #define VECTOR_H

    /**
    * A minimal vector that can dynamically store multiple objects
    */
    template <class T>
    class Vector
    {
    public:
        /**
        * Create an initial vector
        */
        Vector();

        /**
        * Delete memory allocated resources
        */
        ~Vector();

        /**
        * Copy constructor
        */
        Vector(const Vector& other);

        /**
         * Assignment operator
         * \param other Object to assign from
         * \return A reference to this
         */
        Vector& operator=(const Vector& other);

        /**
        * Add a new element at the end of the list
        * @param element item to be added
        */
        void push_back(T element);

        /**
        * Return the number of items stored in the vector
        * @return size
        */
        int size();

        /**
        * Get an element from a specific index
        * @param i index
        * @return element
        */
        T get(int i);

        /**
        * Check if the element is in the list
        * @return true if it is, otherwise false
        */
        bool contains(T element);

    private:

        /**
        * Stores the current number of elements
        */
        unsigned int numElements;

        /**
        * Stores the maximum number of elements that can be stored
        */
        unsigned int capacity;

        /**
        * A dynamically allocated list where to store items
        */
        T *elements;

        /**
        * Doubles the size of the vector
        */
        void expand();
    };

    template <class T>
    Vector<T>::Vector()
    {
        numElements = 0;
        capacity = 10;
        elements = new T[capacity];
    }

    template <class T>
    Vector<T>::~Vector()
    {
        delete[] elements;
    }

    template <class T>
    void Vector<T>::push_back(T element)
    {
        if (numElements >= capacity)
        {
            expand();
        }

        elements[numElements] = element;
        numElements++;
    }

    template <class T>
    int Vector<T>::size()
    {
        return numElements;
    }

    template <class T>
    T Vector<T>::get(int i)
    {
        return elements[i];
    }

    template <class T>
    void Vector<T>::expand()
    {
        T *tempElements = new T[capacity * 2];

        for (int i = 0; i < capacity; i++)
        {
            tempElements[i] = elements[i];
        }

        delete[] elements;
        elements = tempElements;
        capacity *= 2;
    }

    template <class T>
    bool Vector<T>::contains(T element)
    {
        for (int i = 0; i < numElements; i++)
        {
            if (elements[i] == element)
            {
                return true;
            }
        }

        return false;
    }

    #endif

Please give me any comments you can, one doubt I have in particular is do I leave the parameters that take T element as is, or should it be T *element or T &element, it's a very confusing topic for me.

And also, how would one privatize a struct that is defined outside the class, rather than posting more unreadable code, since I don't want the client to edit the root/node values himself.

    /**
    @class BinarySearchTree.h
    @brief is class which deals with the BST insertion, deletion, searching, getting, etc

    @author Aashish Pandav
    @date 27/7/2016

    */

    #ifndef BINARYSEARCHTREE_H
    #define BINARYSEARCHTREE_H

    /**
    * A node to link together and form a binary search tree
    */
    template <class T>
    struct Node
    {
        T element;
        Node<T> *left;
        Node<T> *right;
    };

    /**
    * A binary search tree to store elements in sorted order
    */
    template <class T>
    class BinarySearchTree
    {
    public:
        /**
        * Create an empty binary search tree
        */
        BinarySearchTree();

        /**
        * Delete all memory allocated objects
        */
        ~BinarySearchTree();

        /**
        * Insert a new element in the binary search tree
        * @param element New element to be inserted
        */
        void insert(T element);

        /**
        * Check if the element is in the tree
        * @param element Target element
        * @return true if it is, otherwise false
        */
        bool contains(T element);

        /**
        * Get an item from a particular index
        * @param index target index
        * @return element
        */
        T get(int index);

        /**
        * Get the number of items stored in the binary tree
        * @return size
        */
        int size();
    private:
        /**
        * Holds the root reference
        */
        Node<T> *root;

        /**
        * Recursively delete a binary search tree
        * @param current current element to destroy
        */
        void destroy(Node<T>* &current);

        /**
        * Recursively count the number of items stored
        * @param current current node being counted
        * @return number of elements
        */
        int size(Node<T> *current);
    };

    template <class T>
    BinarySearchTree<T>::BinarySearchTree()
    {
        root = NULL;
    }

    template <class T>
    BinarySearchTree<T>::~BinarySearchTree()
    {
        destroy(root);
    }

    template <class T>
    int BinarySearchTree<T>::size()
    {
        return size(root);
    }

    template <class T>
    int BinarySearchTree<T>::size(Node<T> *current)
    {
        if (current == NULL)
        {
            return 0;
        }

        return 1 + size(current->left) + size(current->right);
    }

    template <class T>
    T BinarySearchTree<T>::get(int index)
    {
        Node<T> *node = root;
        int position = size(root->left);

        while (position != index)
        {
            if (index > position)
            {
                node = node->right;
                position = position + 1 + size(node->left);
            }
            else
            {
                node = node->left;
                position = position - 1 - size(node->right);
            }
        }

        return node->element;
    }

    template <class T>
    void BinarySearchTree<T>::destroy(Node<T>* &current)
    {
        if (current != NULL)
        {
            destroy(current->left);
            destroy(current->right);
            delete current;
            current = NULL;
        }
    }

    template <class T>
    void BinarySearchTree<T>::insert(T element)
    {
        Node<T> *newNode = new Node<T>();
        newNode->element = element;
        newNode->left = NULL;
        newNode->right = NULL;

        if (root == NULL)
        {
            root = newNode;
        }
        else
        {
            Node<T> *previous = NULL;
            Node<T> *current = root;

            while (current != NULL)
            {
                previous = current;

                if (current->element == element)
                {
                    // Duplicate
                    delete newNode;
                    return;
                }
                else if (current->element > element)
                {
                    current = current->left;
                }
                else if (current->element < element)
                {
                    current = current->right;
                }
            }

            if (previous->element > element)
            {
                previous->left = newNode;
            }
            else if (previous->element < element)
            {
                previous->right = newNode;
            }
        }
    }

    template <class T>
    bool BinarySearchTree<T>::contains(T element)
    {
        Node<T> *current = root;

        while (current != NULL)
        {
            if (current->element == element)
            {
                return true;
            }
            else if (element > current->element)
            {
                current = current->right;
            }
            else if (element < current->element)
            {
                current = current->left;
            }
        }

        return false;
    }

    #endif
\$\endgroup\$
2
\$\begingroup\$

Design

Your storage requires that T has a default constructor.

T *elements;

// Allocation is 
elements = new T[capacity];   // Creates `capacity` elements 
                              // But also constructs them.

There are a couple of problems with this.

  1. Your type T needs a default constructor.
  2. If the constructor is expensive then you are constructing a bunch of object temporally that you may never use.

What you want to do is allocate enough memory to store capacity objects to be created but not actually create them until you need them. For this you will need to understand Placement new.

Rule of three

You declare the copy constructor and copy assignment operator but I don't see a definition. So it is hard to tell if they work.

Pass by reference.

void Vector<T>::push_back(T element)

Here you pass element by value. This means you copy the value into the parameter. Then you copy the value into the storage element (using copy assignment).

What you need to do is pass by reference:

void Vector<T>::push_back(T const& element)
                      //    ^^^^^^  

This prevents one copy.
You may also want to add a move assignment operator.

void Vector<T>::push_back(T&& element) noexcept;

Const Correctness

Any method that does not change the state of the object should be marked const. This allows the method to be called from a const context (ie when passed as a parameter as a const reference).

int Vector<T>::size() const
                  //  ^^^^^ add const here.

Return by reference

T Vector<T>::get(int i)

Here you are returning by value. Which means that the returned value is copied out of the object. What you should do is return a reference to the object

T& Vector<T>::get(int i);
 ^^  Return a reference. This allows you to read the value.
     But also modify the object in place.

Note: This will not work in a const context. So you should also have a version where you can read a value (ie it does not allow modification). This version can be used in const context.

T const& Vector<T>::get(int i) const;
                           //  ^^^^^ This function does not modify the state of the objet.
//^^^^^^                             We return a const reference to the object.
//                                   This allows you to read it but not modify it.

Stop using NULL

    root = NULL;

C++ has a better literal. nullptr is the literal that represents a null.

More Info

Vector - Resource Management Allocation
Vector - Resource Management Copy Swap
Vector - Resize
Vector - Simple Optimizations
Vector - the Other Stuff

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.