Persistent data structure using a vector of linked lists

[ik1610]

Hello!

I am trying to implement a persistent data structure using a vector of linked lists, but each time I am adding the modified list to the vector, all the old entries seem to be updated... Could you please help me?

Definition of the vector of linked lists (the list is defined as RBTree):

vector<RBTree*> persistentList;

    // Create a copy of the list
    RBTree myRBTreeCopy = *myRBTree;

    // Store the list in the vector persistentList in the "noCopies-1"th position
    persistentList.push_back(&myRBTreeCopy);

    // Increment number of persistent data structures
    noCopies++;

To illustrate what I mean, when I output:

persistentList[0]->print(persistentList[0]->root);

and expect to see an empty linked list, I obtain the final list after I have inserted all the elements.

Thank you in advance for your help and please let me know if any clarification is needed.

[sepp2k]

In your example code you only push one tree into the vector, so that's not enough to reproduce your problem. My guess is that in your real code you have a loop around lines 3 to 10. So at the end of each iteration of the loop, myRBTreeCopy goes out of scope and the pointer you stored in the vector becomes invalid. Then dereferencing that pointer later invokes undefined behavior. Since each instance of the my RBTreeCopy variable presumably reuses the same memory address on your implementation, this undefined behavior manifests itself as all pointers pointing to the same tree.

The easiest way to fix your problem would probably be to store the trees directly in the vector instead of using pointers. If that's not an option, you'll need to use new to allocate the trees on the heap.

PS: An RB tree is not a linked list.

[ik1610]

Thanks for your reply. Yes, sorry, I have indeed a loop around these lines. When I try the following though, I get the same problem:

 // Create a copy of the list
                    RBTree *myRBTreeCopy  = new RBTree;
                    myRBTreeCopy = myRBTree;

                    // Store the list in the vector persistentList in the "noCopies-1"th position
                    persistentList.push_back(*myRBTreeCopy);

                    myRBTreeCopy = NULL;
                    delete myRBTreeCopy;

PS: Yes, I know that an RB tree is not a linked list, but I need to stick in this notation for certain reasons.

[sepp2k]

On line 6 you call push_back with an RBTree as its argument, so does that mean that you changed persistenList to a vector<RBTree>? If so, you don't need to mess around with pointers at all, so you should just get rid of all that.

Especially since it's dangerously wrong. On line 2 you allocate memory on the heap and store the address in myRBTreeCopy. On line 3 you take the address stored in myRBTree and store it in myRBTreeCopy, discarding the heap address from line 2. So that memory is now leaked. On line 9 you delete the memory address stored in myRBTreeCopy, which is the same as myRBTree. If that address is not allocated with new, that's undefined behavior right there. And even if it is, that's undefined behavior on the second iteration of the loop since you're deleteing the same address multiple times.

If you have further problems with your code, I'd appreciate a minimal but complete code sample, that is one that compiles without error and when run exhibits the problem you're asking about.

If you're using a vector<RBTree> and you see the same problems as in the beginning, that might mean that your copy constructor is messed up, so I can't help you until I see that.

Yes, I know that an RB tree is not a linked list, but I need to stick in this notation for certain reasons.

So your RBTree class is really a linked list class, but you need to name it RBTree for ... reasons? That's strange to say the least.

[ik1610]

#include <iostream>
#include <sstream>
#include <vector>

using namespace std;

typedef string keyType;
typedef string telType;

class RBTNode
{
    public:
    keyType key;           
    telType tel;
    RBTNode* next;

}; // RBTNode

class RBTree
{
    public: 
    //int index;
    RBTNode *root;

    // ---------------------------- PRINT ---------------------------
    void print (RBTNode *root)
    {
        while (root !=NULL) // Go through the whole list
        {
            cout<<root->key<<endl<<root->tel<<endl; // Show the data in the linked list
            root = root->next;                                      // Tranfer the address of 'temp->next' to 'temp'
        }
    }

    // ---------------------------- SEARCH ---------------------------
    telType search(vector<RBTree> persistentList, keyType aKey, unsigned int count)
    {   
        // If a non-existant version of the persistent data structure is sought, output -1
        if (count >= persistentList.size())
            return "-1";

        else
        {
            bool found = false;

            RBTNode *searchPtr = new RBTNode;

            cout<<endl<<"count = "<<count<<endl;

            // Find the correct version of the linked list
            root = persistentList[count].root;

            /* Special case empty list */   
            if (root == NULL)
                return "-1";    

            /* Special case it the required item is the first in the list */    
            else if (root->key == aKey)
                return root->tel;

            /* Normal case */
            else 
            {
                found = false;                                              // Boolean variable indicating whether the item has been found 
                searchPtr = root;
                //lastPtr = root;

                while ((searchPtr != NULL)&&(!found))               // Search for the item
                {
                    if ((searchPtr->key) == aKey)           // If the item is found
                    {
                        found = true;                                       // found is true so the iterations stop
                        return searchPtr->tel;                              
                    }
                    else 
                        searchPtr = searchPtr->next;                // Move to the next node
                }

                if (!found)
                    return "-1";
            }
        }
    }

    // ---------------------------- INSERT ---------------------------
    void insert(keyType aKey, telType aTel, RBTNode *&root) // modify with your own code
    {
        bool found = false;                     // Boolean variable to indicate whether the correct position to insert the element has been found

        /* Creation of a new node*/

        RBTNode *newPtr = new RBTNode;
        RBTNode *searchPtr = new RBTNode;
        RBTNode *lastPtr = new RBTNode;
        newPtr->key = aKey;     // The number to be inserted is the numeric field of the new node 
        newPtr->tel = aTel;     // The string to be inserted is the string field of the new node
        newPtr->next = NULL;

        /* Special case of empty list */

        if (root == NULL)
        {
            root = newPtr;          // The inserted element is the only element of the list
            return;
        }

        /* Special case of inserting at the top of the list */

        else if (root->key >= aKey)
        {
            newPtr->next = root;        // Insert the new element before the head of the list
            root = newPtr;
        }

        /* Normal case of insertion */

        else 
        {
            found = false;                      // Initialisation

            searchPtr = root;       // Initialisation of pointers
            lastPtr = root;

            while ((searchPtr != NULL)&&(!found)) // Search for the correct position to insert the element
            {
                if (searchPtr->key == aKey)
                {
                    searchPtr->tel = aTel;  
                    found = true;
                    return;
                }

                else if (searchPtr->key >= aKey)
                    found = true;                       // The correct position is found so exit the loop

                else
                {
                    lastPtr = searchPtr;
                    searchPtr = (searchPtr->next);  // Move to the next node to continue the search
                }
            }

            newPtr->next = searchPtr;   // Relink the item to the correct place
            lastPtr->next = newPtr;
        }
}
};

int main()
{   
    string STR;
    int n;
    int noCopies = 0;
    int pDStructCount = 0;
    cin >>n;
    getline(cin, STR);
    string Ops;
    keyType name;
    telType tel;

    // Initialization of vector to store the persistent data structure
    vector<RBTree> persistentList;

    // Initialization of vector to store the sequences of outputs
    vector<string> outSeq;

    RBTree *myRBTree = new RBTree;
    myRBTree ->root = NULL;

    while(0 < n--)
    {
        // Read input from stdin:
        getline(cin,STR);
        stringstream ss(STR);

        ss>>Ops;

        ss>>name;
        tel = -1;

        if (Ops == "I")
            ss>>tel;

        if (Ops == "I")
        {
            myRBTree->insert(name, tel, myRBTree->root);
            // Create a copy of the list
            RBTree *myRBTreeCopy;
            myRBTreeCopy = myRBTree;

            // Store the list in the vector persistentList in the "noCopies-1"th position
            persistentList.push_back(*myRBTreeCopy);

            //myRBTreeCopy = NULL;
            //delete myRBTreeCopy;

            // Print the first version of the list
            cout<<endl<<"noCopies = 0"<<endl;
            persistentList[0].print(persistentList[0].root);
            cout<<endl;

            // Increment number of persistent data structures
            noCopies++;
        }

        if (Ops == "S")
        {
            //cout <<"S   "<<name<<endl;
            ss>>pDStructCount;

            // Subtract 1, as pDStructCount will function as an index for the vector persistentList
            pDStructCount = pDStructCount -1;

            telType tel = myRBTree->search(persistentList, name, pDStructCount);
            outSeq.push_back(tel);
        };
    }

    for (unsigned int j = 0; j < outSeq.size(); j++)
        cout<<outSeq[j]<<endl;

    //cout<<endl<<"The final tree is: "<<endl;
    //myRBTree->print(myRBTree->root);

    //cout<<endl<<"The tree for 0 is: "<<endl;
    //persistentList[0].print(persistentList[0].root);//->print(myRBTree->root);

    //cout<<endl<<"The tree for 1 is: "<<endl;
    //persistentList[1].print(persistentList[1].root);//->print(myRBTree->root);

    //cout<<endl<<"The tree for 2 is: "<<endl;
    //persistentList[2].print(persistentList[2].root);//->print(myRBTree->root);

    //cout<<endl<<"The tree for 3 is: "<<endl;
    //persistentList[3].print(persistentList[3].root);//->print(myRBTree->root);

    return 0;
}

The whole code is above. The input should be of the form:
9
I HonWai 65161234
I NamNinh 91234567
S NamNinh 1
S NamNinh 2
I Jiangwei 83332324
I HonWai 87654321
S HonWai 3
S HonWai 4
S HonWai 8

The corresponding output for the above input should be:
-1
91234567
65161234
87654321
-1

I also output the initial version of the list for debugging purposes under the line

noCopies = 0;

and the value of

count

Thanks in advance.

[sepp2k]

You don't even have a copy constructor. So of course all the "copies" of your list are going to have a pointer to the same memory. You should read up on pointers and copy constructors.

PS: I would have appreciated it if your minimal but complete code sample (which looks a lot like it's your actual code unmodified to be honest) had been a bit more minimal.