copy constructors for hash tables

Question

Im having trouble with writing a copy constructor for my hashtable. I already have trouble with copy constructors with linked objects alone. How can I implement a copy constructor and a assignment operator with the following functions:

//copy constructor
Apple::Apple(const Apple& anotherApple){


}

//assignment operator
Apple& Apple::operator = (const Apple& anotherApple){


}

I know it would be something along the lines of:

tableSize = anotherApple.tableSize;
count = anotherApple.count;
array = new *anotherApple.array; //idk if this is right for dynamically created array of pointers

array = new Node*[tableSize]. But you need to know the number of elements which will be put in each row. For doing deep copy, you must iterate over anotherApple.array and copy all elements one by one for each row. Does it makes sense for you? — Pravar Jawalekar, Dec 28 '15 at 04:50
@pravar how would you make a deep copy. Because I need to copy each linked nodes at each index of the array? — programmingblues, Dec 28 '15 at 04:52
Advice -- concentrate on the copy constructor only for now. The assignment operator can be easily written once the copy constructor (and destructor) are working correctly. Second, your array has to know how many items to allocate first, and that should be available from `anotherApple`. — PaulMcKenzie, Dec 28 '15 at 04:59
@programmingblues How do you know how much to allocate for each `Node*`? If `tableSize` is the number of `Node*`, then allocating the "outer" array by just doing `array = new Node*[tableSize];`. But it has to go beyond that. For each `Node*`, you have to copy each one from `anotherApple` to the new object. For that, we don't have enough information from your post. — PaulMcKenzie, Dec 28 '15 at 05:06
@programmingblues please see my answer below. I know code is not clear but it might give some idea about how to approach for writting a copy constructor for Apple class you mentioned in question. — Pravar Jawalekar, Dec 28 '15 at 05:08
@programmingblues Do you have a function that "adds" an item to your hash map? If so, then the easiest thing would be to utilize it in your copy constructor by "adding" each item from `anotherApple` to the new object's map. Maybe you don't even need to allocate anything in your copy constructor, and all you need to do is set `array` to NULL at the beginning, and then in a loop, call the "add" function, adding each item from `anotherApple` to the new object. In other words, reuse code that already works. — PaulMcKenzie, Dec 28 '15 at 05:09
@PaulMcKenzie can you show me some pseudocode for that, i don't quite understand. don't you need to allocate memory if your making a deep copy? — programmingblues, Dec 28 '15 at 06:21
@programmingblues You also need a function that can iterate through the map and retrieve the values. Once you have that, then just call `this->addValue()` in a loop, using each value from the `anotherApple` map. This way you're not writing code that already exists. If you don't have such a function to get the value, then you really need to write it, as the map is almost useless if one cannot determine what the keys and values are in a map. — PaulMcKenzie, Dec 28 '15 at 12:39

Pravar Jawalekar · Answer 1 · 2015-12-28T05:40:09.243

1

Apple::Apple(Apple const & anotherApple)
{
     // allocate an array to hold pointers to Node
     array = new Node*[tableSize];

     for(int i=0; i<tableSize; i++)
     {
        Node* src = anotherApple.array[i];
        Node* dest;

        if (src == NULL)
        {
           array[i] = NULL;
           continue; // no data to copy, continue to next row
        }


        // set array[i] since there is at-least one element
        dest = new Node;
        dest->data = src->data;

        array[i] = dest;
        src = src->next;

        while(src != NULL)
        {
           Node* n = new Node;
           dest->next = n;
           dest = n;

           dest->data = src->data;

           src = src->next;
        }

        dest->next = NULL;
     }
  }

edited Dec 28 '15 at 05:40

answered Dec 28 '15 at 05:07

Pravar Jawalekar

605
1
6
18

If the OP has an "add" function, almost all of that code can be eliminated. – PaulMcKenzie Dec 28 '15 at 05:08
Yes. But I didn't assumed anything. But sure it can be much simplified. It's quite messy now. – Pravar Jawalekar Dec 28 '15 at 05:09
@pravar sorry, but can you comment your code so I can easily follow what your trying to do? – programmingblues Dec 28 '15 at 05:20
@PaulMcKenzie yes there is an add value function & also do you know a good webpage where I can learn about deep copy for arrays of linked nodes? – programmingblues Dec 28 '15 at 05:29
@programmingblues I just did so in above comment. Did you find it useful or you have any problems in understanding it? – Pravar Jawalekar Dec 28 '15 at 05:29
@pravar so your iterating through the for loop, starting at the first index of the array of ptrs, then create a ptr pointing to the original array & create a ptr that's going to create your copy array... Can you explain these lines of code: `dest->data = src->data;` `n->data = src->data;` – programmingblues Dec 28 '15 at 05:38
@pravar, PaulMcKenzie mentioned that you can do this using the addValue func? How will that work? – programmingblues Dec 28 '15 at 05:39
@programmingblues I edited my comment. Now it should be more clear to understand. Basically, I am doing nothing but copying a linked-list to another if object passed as argument to copy-constructor have an array which have non-empty list. – Pravar Jawalekar Dec 28 '15 at 05:44
Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/99091/discussion-between-programmingblues-and-pravar). – programmingblues Dec 28 '15 at 05:44
@PaulMcKenzie Thank you, saved me a ton of time with the way assignment operator was implemented. Any drawbacks with the way assignment op. was implemented below? – programmingblues Dec 28 '15 at 17:38
@programmingblues You mean the one I implemented? The only drawback is that it handles self-assignment correctly, but will needlessly make a copy (that can be easily corrected). Otherwise it is vastly superior to writing an assignment operator the "long way", i.e. write the same code for the assignment operator as you did for the constructor. The basic reason why the copy/swap method is better, if the copy constructor for `temp` fails, then the assignment doesn't leave the object in a half-baked state. In other words, the assignment operator is exception safe. – PaulMcKenzie Dec 28 '15 at 20:28

score 1 · Answer 2 · edited May 23 '17 at 11:52

Theoretically, your copy constructor can be written in a loop, providing that the proper functions exist in retrieving from a hash table, and adding a value to a hash table. If these functions currently don't exist, then it would be worth a lot more if you did write these functions anyway, as the hash table would be very restrictive if there was no way to iterate through all of the values.

Assume that you have such functions, where you retrieve a Node* in the get functions. Also assume that getFirst() retrieves the head node, and getNext() retrieves the next node, given a Node* value to start from. The copy constructor would look something like this:

Apple::Apple(const Apple& anotherApple)
{
    Node* curNode = anotherApple.getFirst();
    while (curNode)
    {
       addValue(curNode->key, curNode->value);
       curNode = anotherApple.getNext(curNode);
    }
}

This requires that your implementation has a way to get the first value in the table using something like getFirst(), and iterate to the next entry of the current node by a function called getNext(). If no more nodes, then getNext() would return a NULL.

The advantage to writing the copy constructor this way is that you reuse code that hopefully has been tested, namely the addValue function, instead of having to basically rewrite addValue over again. In addition, there is little to no chance of an error occurring, since you're just calling functions that exist already.

The disadvantage to writing the copy constructor this way is that the complexity in terms of runtiime may be slower than attempting to create the entire internals "from scratch" using a lot of pointer manipulation (like one of the previous answers has done).

So weigh the differences, safety over speed. Maybe there is no speed issues using the safe approach.

For the assignment operator, if you have a working copy constructor and a working destructor, then this is all you need to do:

#include <algorithm>
//...
Apple& Apple::operator=(const Apple& anotherApple)
{
    Apple temp(anotherApple);
    std::swap(temp.array, array);
    std::swap(temp.tableSize, tableSize);
    std::swap(temp.count, count);
    return *this;
}

This uses the copy / swap idiom. Again, this requires a correct copy constructor and a correct destructor (no bugs whatsoever in these two functions).

copy constructors for hash tables

2 Answers2