C++ object get a residual value after a for loop

Question

I created a class for queue an I'm using an object of that class in a loop. After an iteration the value of the first element in queue change to a residual value. Why is that and how can I fix it? Here's the .h file:

#ifndef QUEUE_H
#define QUEUE_H

#include "headers.h"

template <class T> 
class Queue
{
    public:

        Queue();
        ~Queue();

        void Push(T value);                                     // Insert a new element at the end of the queue.
        void Display();                                         // Display the queue.

        T Pop();                                                // Delete the top of the queue and returns it.
        T Peek();                                               // Returns the top of the queue.

        T GetPositionValue(uint pos);                           // Returns the value found on the specified position.

        T GetMin();                                             // Returns the lowest value in the queue.
        T GetMax();                                             // Returns the highest value in the queue.

        uint Distance(T value);                                 // Returns -1 if the value isn't in the queue, else returns the distance from the top.
        uint GetSize() const { return size; }                   // Returns the number of elements found in the stack.

        bool IsEmpty() { return (first == nullptr); }           // Returns true if the queue is empty.
        bool HasValue(T value);                                 // Returns true if the value is in the queue.
        bool HasPosition(uint pos);                             // Returns true if pos is found in queue. Position 0 is top.

    private:
        struct Node
        {
            T value;
            Node *next;
        };

        Node *first, *last;
        uint size;

        Node *GetPositionAddress(uint pos);
        Node *GetValueAddress(T value);
};

template <class T>
class Deque
{
    public:

        Deque();
        ~Deque();

        void PushBack(T value);
        void PushFront(T value);

        void Display();

        T PopFront();
        T PeekFront();
        T PopEnd();
        T PeekEnd();

        T GetPositionValue(uint pos);

        T GetMin();
        T GetMax();

        uint Distance(T value);
        uint GetSize() const { return size; }

        bool IsEmpty() { return (first == nullptr); }
        bool HasValue(T value);
        bool HasPosition(uint pos);

    private:
        struct Node
        {
            T value;
            Node *next;
        };

        Node *first, *last;
        uint size;

        Node *GetPositionAddress(uint pos);
        Node *GetValueAddress(T value);
};

#include "Queue.cpp"

#endif

Here's where the queue is used.

#include "../Headers/queue.h"

// Simple linked list of queues
struct SLLQ
{
    Deque<int> deq;
    SLLQ *next;
};

void CreateStorage(SLLQ *&head, SLLQ *&tail)
{
    SLLQ *elem = new SLLQ;
    elem->next = NULL;

    if (!head)
    {
        head = elem;
        tail = elem;
    }
    else
    {
        tail->next = elem;
        tail = elem;
    }
}

int main()
{
    std::ifstream f("Inputs/hw4p7.in");

    int k, k2, n;

    Queue<int> laneIN, laneOUT;
    SLLQ *sqf = NULL, *sql = NULL;

    f >> k;
    k2 = k;
    f >> n;

    for (int i = 0; i < n; i++)
    {
        int value;
        f >> value;
        laneIN.Push(value);
    }

    k--;
    CreateStorage(sqf, sql);
    sqf->deq.PushBack(laneIN.Pop());

    // Inserting the wagons in the storage lines
    for (int i = 1; i < n; i++)
    {
        if (sqf->deq.PeekEnd() < laneIN.Peek())
            sqf->deq.PushBack(laneIN.Pop());
        else
        {
            SLLQ *temp = sqf;

            bool pushed = false;
            while (!pushed)
            {
                if (!temp->next)
                {
                    // End the program if he use to much storage lanes
                    if (!k)
                    {
                        std::cout << "There's no strategy with " << k2 << " storage lanes.";
                        _getch();
                        return;
                    }

                    k--;
                    CreateStorage(sqf, sql);
                    temp = temp->next;

                    temp->deq.PushBack(laneIN.Pop());
                    pushed = true;
                }
                else
                {
                    temp = temp->next;

                    if (temp->deq.PeekEnd() < laneIN.Peek())
                    {
                        temp->deq.PushBack(laneIN.Pop());
                        pushed = true;
                    }
                }
            }
        }
    }

    // Inserting the wagons in the out lane
    for (int i = 0; i < n; i++)
    {
        SLLQ *temp = sqf;
        Deque<int> mina = temp->deq;
        temp = temp->next;
        while (temp)
        {
            if (temp->deq.PeekFront() < mina.PeekFront())
                mina = temp->deq;
            temp = temp->next;
        }

        SLLQ *minadd = sqf;
        SLLQ *predminadd = sqf;
        while (minadd && (minadd->deq.PeekFront() != mina.PeekFront()))
        {
            minadd = minadd->next;

            if (predminadd->next != minadd)
                predminadd = predminadd->next;
        }

        laneOUT.Push(minadd->deq.PopFront());

        if (minadd->deq.IsEmpty())
        {
            delete minadd;
            predminadd->next = nullptr;
        }
    }

    laneOUT.Display();

    _getch();
    return 0;
}

Here's the .cpp file with queue members definitions:

#include "queue.h"

template<class T>
Queue<T>::Queue()
{
    first = last = nullptr;
    size = 0;
}

template<class T>
Queue<T>::~Queue()
{
    while (first)
    {
        typename Queue<T>::Node *del = first;
        first = first->next;
        delete del;
    }
    first = last = nullptr;
    size = 0;
}

template <class T> 
void Queue<T>::Push(T value)
{
    typename Queue<T>::Node *elem = new Node;
    elem->value = value;
    elem->next = nullptr;

    if (first)
        last->next = elem;
    else
        first = elem;

    last = elem;
    size++;
}

template <class T> 
void Queue<T>::Display()
{
    typename Queue<T>::Node *temp = first;
    while (temp)
    {
        std::cout << temp->value << "\n";

        temp = temp->next;
    }
}

template <class T> 
T Queue<T>::Pop()
{
    if (IsEmpty())
        return T(-1);

    T value = first->value;

    typename Queue<T>::Node *temp = first;
    first = first->next;
    delete temp;

    if (first == nullptr)
        last = nullptr;

    size--;
    return value;
}

template <class T> 
T Queue<T>::Peek()
{
    if (IsEmpty())
        return T(-1);

    return first->value;
}

template <class T> 
T Queue<T>::GetPositionValue(uint pos)
{
    if (IsEmpty() || !HasPosition(pos))
        return T(-1);

    typename Queue<T>::Node *temp = first;
    for (uint i = 1; i < pos; i++)
        temp = temp->next;

    return temp->value;
}

template <class T> 
uint Queue<T>::Distance(T value)
{
    uint distance = 0;

    if (!HasValue(value))
        return -1;

    typename Queue<T>::Node *temp = first;
    while (temp && temp->value != value)
    {
        temp = temp->next;
        distance++;
    }

    return distance;
}

template <class T> 
T Queue<T>::GetMin()
{
    if (IsEmpty())
        return T();

    T min = first->value;

    typename Queue<T>::Node *temp = first;
    while (temp->next)
    {
        temp = temp->next;

        if (temp->value < min)
            min = temp->value;
    }

    return min;
}

template <class T> 
T Queue<T>::GetMax()
{
    if (IsEmpty())
        return T();

    T max = first->value;

    typename Queue<T>::Node *temp = first;
    while (temp->next)
    {
        temp = temp->next;

        if (temp->value > max)
            max = temp->value;
    }

    return max;
}

template <class T> 
bool Queue<T>::HasValue(T value)
{
    typename Queue<T>::Node *temp = first;
    while (temp && temp->value != value)
        temp = temp->next;

    if (!temp)
        return false;
    else
        return true;
}

template <class T> 
bool Queue<T>::HasPosition(uint pos)
{
    if (IsEmpty())
        return false;

    uint i = 1;

    typename Queue<T>::Node *temp = first;
    while (temp && i < pos)
    {
        temp = temp->next;
        i++;
    }

    if (i == pos)
        return true;
    else
        return false;
}

// Private members

template <class T> 
typename Queue<T>::Node *Queue<T>::GetPositionAddress(uint pos)
{
    if (IsEmpty() || !HasPosition(pos))
        return nullptr;

    Node *temp = first;
    for (uint i = 1; i < pos; i++)
        temp = temp->next;

    return temp;
}

template <class T> 
typename Queue<T>::Node *Queue<T>::GetValueAddress(T value)
{
    if (IsEmpty() || !HasValue(value))
        return nullptr;

    Node *temp = first;
    while (temp->value != value)
        temp = temp->next;

    return temp;
}

// Deque

template <class T>
Deque<T>::Deque()
{
    first = last = nullptr;
    size = 0;
}

template <class T>
Deque<T>::~Deque()
{
    while (first)
    {
        typename Deque<T>::Node *del = first;
        first = first->next;
        delete del;
    }
    first = last = nullptr;
    size = 0;
}

template <class T>
void Deque<T>::PushBack(T value)
{
    typename Deque<T>::Node *elem = new Node;
    elem->value = value;
    elem->next = nullptr;

    if (first)
        last->next = elem;
    else
        first = elem;

    last = elem;
    size++;
}

template <class T>
void Deque<T>::PushFront(T value)
{
    typename Deque<T>::Node *elem = new Node;
    elem->value = value;
    elem->next = nullptr;

    if (first)
        elem->next = first;
    else
        last = elem;

    first = elem;
    size++;
}

template <class T>
void Deque<T>::Display()
{
    typename Deque<T>::Node *temp = first;
    while (temp)
    {
        std::cout << temp->value << "\n";

        temp = temp->next;
    }
}

template <class T>
T Deque<T>::PopFront()
{
    if (IsEmpty())
        return T(-1);

    T value = first->value;

    typename Deque<T>::Node *temp = first;
    first = first->next;
    delete temp;

    if (first == nullptr)
        last = nullptr;

    size--;
    return value;
}

template <class T>
T Deque<T>::PeekFront()
{
    if (IsEmpty())
        return T(-1);

    return first->value;
}

template <class T>
T Deque<T>::PopEnd()
{
    if (IsEmpty())
        return T(-1);

    if (first == last)
        return PopFront();

    T value = last->value;
    typename Deque<T>::Node *temp = first;

    while (temp && temp->next != last)
        temp = temp->next;
    delete last;

    last = temp;
    size--;

    return value;
}

template <class T>
T Deque<T>::PeekEnd()
{
    if (IsEmpty())
        return T(-1);

    return last->value;
}

template <class T>
T Deque<T>::GetPositionValue(uint pos)
{
    if (IsEmpty() || !HasPosition(pos))
        return T(-1);

    typename Deque<T>::Node *temp = first;
    for (uint i = 1; i < pos; i++)
        temp = temp->next;

    return temp->value;
}

template <class T>
uint Deque<T>::Distance(T value)
{
    uint distance = 0;

    if (!HasValue(value))
        return -1;

    typename Deque<T>::Node *temp = first;
    while (temp && temp->value != value)
    {
        temp = temp->next;
        distance++;
    }

    return distance;
}

template <class T>
T Deque<T>::GetMin()
{
    if (IsEmpty())
        return T();

    T min = first->value;

    typename Deque<T>::Node *temp = first;
    while (temp->next)
    {
        temp = temp->next;

        if (temp->value < min)
            min = temp->value;
    }

    return min;
}

template <class T>
T Deque<T>::GetMax()
{
    if (IsEmpty())
        return T();

    T max = first->value;

    typename Deque<T>::Node *temp = first;
    while (temp->next)
    {
        temp = temp->next;

        if (temp->value > max)
            max = temp->value;
    }

    return max;
}

template <class T>
bool Deque<T>::HasValue(T value)
{
    typename Deque<T>::Node *temp = first;
    while (temp && temp->value != value)
        temp = temp->next;

    if (!temp)
        return false;
    else
        return true;
}

template <class T>
bool Deque<T>::HasPosition(uint pos)
{
    if (IsEmpty())
        return false;

    uint i = 1;

    typename Deque<T>::Node *temp = first;
    while (temp && i < pos)
    {
        temp = temp->next;
        i++;
    }

    if (i == pos)
        return true;
    else
        return false;
}

// Private members

template <class T>
typename Deque<T>::Node *Deque<T>::GetPositionAddress(uint pos)
{
    if (IsEmpty() || !HasPosition(pos))
        return nullptr;

    Node *temp = first;
    for (uint i = 1; i < pos; i++)
        temp = temp->next;

    return temp;
}

template <class T>
typename Deque<T>::Node *Deque<T>::GetValueAddress(T value)
{
    if (IsEmpty() || !HasValue(value))
        return nullptr;

    Node *temp = first;
    while (temp->value != value)
        temp = temp->next;

    return temp;
}

The problem is at line 114(third for) where the queue is used, precisely: "laneOUT.Push(minadd->deq.PopFront());" It puts the value in laneOUT but at next iteration it changes to a residual value.

This isn't the problem, but names that begin with an underscore followed by a capital letter (`_QUEUE_H`) and names that contain two consecutive underscores are reserved to the implementation. Don't use them. — Pete Becker, Feb 02 '16 at 15:53
1) Use the debugger to debug your code. 2) Use a small test suite so that you can follow what is going on ( like 4 or 5 values) 3) `main` returns `int`, not `void`. 4) Those `goto`'s are burning my eyes. 5) *I don't think the .cpp file for queue functions is needed.* -- Why not? — PaulMcKenzie, Feb 02 '16 at 15:56
I got rid of goto's. Also I got to mention that sometimes, but not every time the programs crash to _CrtIsValidHeapPointer. I can't see/understand the problem with the debugger. — Victor Laurentiu, Feb 02 '16 at 17:12
_"I already [...] debugged the code"_ - Problem solved, then! :-p — Toby Speight, Feb 02 '16 at 17:13
Since the problem occurs at runtime, instead of reading the input from a file, please post the test data in a simple array so that others can see what you're using. Something like this: `int testValues[] = { 10, 1, 45, 100, 1, 34 };` — PaulMcKenzie, Feb 03 '16 at 10:50
In addition, why did you not test your Queue and Deque classes with simple data first? Also, you should write a legitimate singly linked list class and test it (your `SLLQ` class) and not do a dance with allocating and deallocating memory in the `main` function -- that is probably where your program breaks down. Basically the bottom line is that all of these classes you wrote should have been tested independently with simple data, pushing, popping, etc. and making sure they are bulletproof. Once that is established, **then** you use these classes in a larger program. — PaulMcKenzie, Feb 03 '16 at 11:09

score 1 · Accepted Answer · answered Sep 11 '18 at 14:05

After almost three years I came across this old question of mine and remembered I wasn't able to fix this code back then, so I thought I would give it a try now that I know so much more.

A big no no can be spotted right away in the second statement of the third for-loop from the main function:

Deque<int> mina = temp->deq;

This code performs a copy, but the Deque class has no copy-constructor implemented explicitly although it manage resources.

The implicit copy-constructor will perform a shallow copy and after the first iteration of the for-loop, the mina object will be destroyed but the memory deallocated is still pointed to by temp->deq used to initialize mina, in the first iteration, without any knowledge that the memory it points to is deallocated.

The Rule of Three (Five in C++11) must be respected when a class manages resources.

The solution for the initial question would be to have "mina" being a pointer or reference instead of a value. But there are other problems in the code that will prevent the program from doing what it was meant to do, like the last statement in the third for-loop which assigns a nullptr. If "minadd" is not the last storage lane in the list of deques(sqf variable) it would lose all "next" storage lanes. — Victor Laurentiu, Sep 12 '18 at 14:00

C++ object get a residual value after a for loop

1 Answers1