Priority Queue based on Link List

Question

The method,,add_by_priority" gives me segmentation fault, i know that the problem occurs in the ,,get_prio" method. I tried to solve it or search if it works anywhere else, and for example outside the ,,if" statement it compiles just fine. Also i don't know if i did the whole algorithm of priority insertion correctly(especially 2 lines after while loop)

        #ifndef SNODE_H
        #define SNODE_H
        
        #include <iostream>
        
        template<typename TYPE>
        class SNode
        {
        
        private:
        
        TYPE _elem; //value of element
        
        SNode<TYPE>* _next_elem; //connection to next node
        
        int _prio; //priority
        
        public:
        
        SNode();
        
        SNode(const TYPE & elem, const SNode<TYPE>* next_elem, const int prio);
        
        TYPE &get_elem();
        
        SNode<TYPE>* get_next_elem();
        
        int &get_prio();
        
        void set_elem(const TYPE & elem);
        
        void set_next_elem(SNode<TYPE>& next_elem);
        
        void set_priority(const int & prio);
        
        bool operator<(SNode<TYPE> & Node);
        
        bool operator>(SNode<TYPE> & Node);
        
        };
        
        
        #endif

    #ifndef LINKED_LIST
    #define LINKED_LIST
    
    #include <iostream>
    #include "SNode.h"
    
    
    template<typename TYPE>
    class LinkedList
    {
    private:
    SNode<TYPE>* head;
    public:
    LinkedList(); //konstruktor bezparametryczny
    
    void add_by_priority(const TYPE& Node, const int &prio);
    void removeFront();
    
    void addFront(const TYPE& Node, const int &prio);
    
    const TYPE & front() const;
    bool empty() const;
    void print();
    
    
    
    
    };

    #include "SNode.h"
    
    template<typename TYPE>
    SNode<TYPE>::SNode(){}
    
    template<typename TYPE>
    SNode<TYPE>::SNode(const TYPE & elem, const SNode<TYPE>* next_elem, const int prio)
    {
    _elem=elem;
    
    next_elem= NULL;
    
    _prio = prio;
    }
    
    template<typename TYPE>
    TYPE &SNode<TYPE>::get_elem()
    {
        return _elem;
    }
    
    template<typename TYPE>
    SNode<TYPE>* SNode<TYPE>::get_next_elem()
    {
        return _next_elem;
    }
    
    template<typename TYPE>
    int &SNode<TYPE>::get_prio()
    {
        return _prio;
    
    }
    
    template<typename TYPE>
    void SNode<TYPE>::set_elem(const TYPE & elem)
    {
        _elem=elem;
    }
    
    template<typename TYPE>
    void SNode<TYPE>::set_next_elem( SNode<TYPE>& next_elem)
    {
    _next_elem = &next_elem;
    }
    
    template<typename TYPE>
    void SNode<TYPE>::set_priority(const int & prio)
    {
    _prio = prio;
    }
    
    template<typename TYPE>
    bool SNode<TYPE>::operator<(SNode<TYPE> & Node) 
    {
    if((*this).get_prio() > Node.get_prio())
        return true;
    return false;
    }
    
    template<typename TYPE>
    bool SNode<TYPE>::operator>(SNode<TYPE> & Node)
    {
    return !(*this<Node);
    }

    #include <iostream>
    #include "LinkedList.h"
    
    
    //inicjuje obiekt ktory nie poakzuje na nic (NULL)
    template<typename TYPE>
    LinkedList<TYPE>::LinkedList()
    {
        head = nullptr; 
    }
    
    
    //zwraca 1 element listy
    template<typename TYPE>
    const TYPE & LinkedList<TYPE>::front() const
    {
        return head->get_elem();
    }
    
    
    template<typename TYPE>
    void LinkedList<TYPE>::addFront(const TYPE& Node, const int &prio) 
    {
    
        SNode<TYPE>* temp = new SNode<TYPE>; //tworzymy nowa zmienna do, ktorej przypiszemy wartosc podanego argumentu
        temp->set_elem(Node); //podpisujemy wartosc
        temp->set_priority(prio); //podpisujemy priority
        temp->set_next_elem(*head); //podpisuje pod adres aktualnego poczatku
        head = temp; //nowa inicjalizacja poczatku temp staje sie head
    }
    
    
    template<typename TYPE>
    void LinkedList<TYPE>::removeFront() 
    {
    
        SNode<TYPE>* temp = head; //tworzymy zmienna ktora pokazuje na head zeby nie zgubic pamieci head
        head = head->get_next_elem(); //przestawiamy head na nastepny element
    
    delete temp; //usuwamy pamiec ktora byla pod head
    
    }
    
    
    template<typename TYPE>
    void LinkedList<TYPE>::print()
    {
    SNode<TYPE>* tmp = head; //podpisanie zmiennej pod wartosc i adres head(by od pcozatku printowac liste)
    while(tmp->get_next_elem() !=nullptr ) //jesli lista nie jest pusta
        {
            std::cout << tmp->get_elem() << std::endl;  //print wartosc pod adresem tmp
            tmp = tmp->get_next_elem(); //przestaw na kolejne miejsce
        }
        std::cout << tmp->get_elem() <<std::endl;
    }
    
    
    template<typename TYPE>
    bool LinkedList<TYPE>::empty() const
    {
    if(head == nullptr) //jesli head nie pokazuje na NULL true
        return true;
    else
        return false; //jesli head jest NULL to nie ma elementow bo nic na nic nie pokazuje
    }
    
    
    template<typename TYPE>
    void LinkedList<TYPE>::add_by_priority(const TYPE& Node, const int &prio)
    {
    
    SNode<TYPE>* start_temp; //zmienna pomocnicza by wyszukac odpowiednie miejsce 
    SNode<TYPE>* temp = new SNode<TYPE>; 
    start_temp = head; //ustaw zmienna na head (poczatek listy)
    
    temp->set_elem(Node); //podpisujemy wartosc
    temp->set_priority(prio); //podpisujemy priority
    
    
        if(prio < head->get_prio() || head == nullptr) //jesli head ma wiekszy prio niz nowe podane prio lub lista jest puste
            {

                temp->set_next_elem(*head); // pod temp podpisz head
                head = temp; //temp staje sie head (wstawienie Node) utworzenie i wstawienie nowego node z wyzszym priorytetem
            }
        else
            {

        
                while(start_temp->get_next_elem() != nullptr && start_temp->get_next_elem()->get_prio() < prio) //rob dopoki nie skonczy sie lista 
                {                                                                                     //lub znajdzie priorytet wiekszy od obecnego 
                    start_temp = start_temp->get_next_elem(); //przejdz na kolejny element listy
                }
    
    
        temp->set_next_elem(*start_temp->get_next_elem()); //wez nastepny element(petla zakonczyla sie element wczesniej)
    
        start_temp->set_next_elem(*temp); //ustawia nowy node w poprawnie wybranym miejscu
    
            }
    }

    #include <iostream>
    #include <stdlib.h>
    #include <fstream>
    #include <string.h>
    #include "LinkedList.cpp"
    #include "SNode.h"
    
    /*
    template<typename TYPE>
    struct Mess_prio
    {
    int _key;
    TYPE _mess;
    };
    */
    
    
    int main()
        {
        
    int value,size,prio;
    LinkedList<int> list;
    
    std::cout << " Pass list size: " <<std::endl;
    std::cin >> size;
    std::cout << std::endl;
    for(int i=0; i<size; i++)
    {
    std::cout << "Enter the value: " << std::endl;
    std::cin >> value;
    std::cout << std::endl;
    std::cout << "Enter the priority: " << std::endl;
    std::cin >> prio;
    std::cout << std::endl;
    list.add_by_priority(value,prio);
    
    }
    list.print();
    
        }

Never include cpp files. Also, being a template class, all the `LinkedList` code needs to live in the header file. And please format your code better. Indentation is very inconsistent. You can use a tool like clang-format to auto-format for you. — sweenish, Mar 31 '21 at 20:59
@77jt777 You may want to read [Why can templates only be implemented in the header file?](https://stackoverflow.com/questions/495021/why-can-templates-only-be-implemented-in-the-header-file). Also, please try to minimize the amout of code into a [mre]. — Ted Lyngmo, Mar 31 '21 at 21:13

Chris Uzdavinis · Accepted Answer · 2021-04-01T13:33:42.243

You have several bugs in your code:

// OP CODE
template<typename TYPE>
    SNode<TYPE>::SNode(){}

Does not initialize _next_elem, leaves it in an invalid state. It is not necessarily null after this constructor runs.

// OP CODE
template<typename TYPE>
SNode<TYPE>::SNode(const TYPE & elem, const SNode<TYPE>* next_elem, const int prio)
{
    _elem=elem;
    next_elem= NULL;
    _prio = prio;
}

Here you do set it to null but you are setting the function argument, not the member, and you never read from the function argument. _next_elem is uninitialized after this constructor too.

// OP CODE
template<typename TYPE>
void SNode<TYPE>::set_next_elem( SNode<TYPE>& next_elem)
{
    _next_elem = &next_elem;
}

Here you're storing the address of an object you only know was alive when the function was called. There's no easy way to detect if the provided next_elem's lifetime has ended, and your pointer is dangling. But assume that's a possibility.

// OP CODE
template<typename TYPE>
bool SNode<TYPE>::operator<(SNode<TYPE> & Node) 
{
    if((*this).get_prio() > Node.get_prio())
        return true;
    return false;
}

A more "natural" way to write this is:

// suggestion
template<typename TYPE>
bool SNode<TYPE>::operator<(SNode<TYPE> & Node) 
{
    return this->get_prio() > Node.get_prio();
}

And another problem in LinkedList code

// OP CODE
template<typename TYPE>
LinkedList<TYPE>::LinkedList()
{
    head = nullptr; 
}

// OP CODE
template<typename TYPE>
void LinkedList<TYPE>::addFront(const TYPE& Node, const int &prio) 
{
...
    temp->set_next_elem(*head);
}

Here, if you create a LinkedList, head is nullptr, but if you try to addFront on this list, suddenly you dereference null.

I'm stopping here. Be careful with your addresses, pointers, lifetimes, and so on.

I see that. I'm of two minds when it comes to correcting their code. With the kind of critiques you were bringing up, I think it was worth correcting their code; they need the lesson. I will say, though, I didn't downvote over that. If I were to give a downvote, it would be because I consider this answer incomplete. I was thinking of contributing one of my own, but OP has chosen yours and is unlikely to revisit. Mine would have ignored the linked list and talked more to separating concerns better. — sweenish, Apr 01 '21 at 13:32
@sweenish I see your confusion. The formatting put my suggestion for operator< above another block of OP code, making it all look like it was what I suggested. I've added comments to identify it better and put a little text to introduce the "next problem" — Chris Uzdavinis, Apr 01 '21 at 13:35

Priority Queue based on Link List

1 Answers1