'delete' throwing an error in g++ while compiling perfectly in clang

Question

So I implemented a standard linked list and it compiled and ran perfectly in clang. However, g++ threw a lot of errors and after removing common memory leaks, there's one error that no book/documentation/tutorial is helping with-

struct token{
    string data;
    string id = "n";
    void print(){
        cerr<<"| "<<data<<" | ";
    }
};

struct node{
    token data;
    node *next = nullptr;
    void print(){
        cerr<<" ||| "<<this<<" | "<<data.data<<" | "<<next<<" ||| ";
    }
};

class list{
    friend class queue;
    friend class stack;
public:
    node *head = nullptr;
    node *tail = nullptr;

void insert(token incoming_data){
    if (head == nullptr){
        node *new_node = new node;
        new_node->data = incoming_data;
        new_node->next = nullptr;
        head = new_node;
        tail = new_node;
        new_node = nullptr;
    }
    else{
        node *new_node = new node;
        new_node->data = incoming_data;
        tail->next = new_node;
        new_node->next = nullptr;
        tail = new_node;
        new_node = nullptr;
    }
}

void del(){
            cerr<<"List before deletion is ";
            print();
            cerr<<"\n";
            cerr<<"Head is at "<<head;
            cerr<<"\n";
    if (head == nullptr){
                cerr<<"List is empty\n";
        return;
    }
    else if (head->next == nullptr){
        tail = nullptr;
                    cerr<<endl<<"Deleting object at "<<head<<endl;
                    delete head;
        head = nullptr; //keep an eye on this

    }
    else{
        node *temp = head;
        head = temp->next;
                cerr<<endl<<"Deleting object at "<<temp<<endl;
        delete temp;
        temp = nullptr;
    }
            cerr<<"List after deletion is ";
            print();
    cerr<<"\n";
}

~list(){
    cerr<<"Destructor calling delete"<<endl;
    while (not(head == nullptr)){
        del();
    }
}
void insert_front(token incoming_data){
    if (head == nullptr){
        node *new_node = new node;
        new_node->data = incoming_data;
        new_node->next = nullptr;
        head = new_node;
        tail = new_node;
        new_node = nullptr;
    }
    else{
        node *new_node = new node;
        new_node->data = incoming_data;
        new_node->next = head;
        head = new_node;
        new_node = nullptr;
    }
}

};

Now, it works perfectly on its own. The stacks and queues implemented using it works perfectly. However, at some point down the line when the destructor tries to call it, this is what happens-

Destructor calling delete

List before deletion is 
 ||| 0x100409bc0 | 55 | 0x100431890 |||  -->  ||| 0x100431890 | 5 | 0x100504830 |||  -->  ||| 0x100504830 | + | 0x0 |||  --> NULL

Head is at 0x100409bc0
Deleting object at 0x100409bc0
test shunting yard (76600,0x10039e380) malloc: *** error for object 0x100409bc0: pointer being freed was not allocated

Node is printed in the format ||| Address of this node | Data | Address of next node ||

And yes, every node was created dynamically using 'new'. Also, the same destructor and del functions work multiple times within the same program perfectly, yet for one particular instance, fail.

In other stack overflow question with the same error, the pointer wasn't referring to anything, however here clearly there's an object that can be deleted at the pointer in question.

---

Edit: It was an implementation of RPN parse using Shunting-Yard, and here's the complete code-

    #include <iostream>
    #include <string.h>
    #include<cmath>
    using namespace std;
    struct token{
        string data;
        string id = "n";
        void print(){
            cerr<<"| "<<data<<" | ";
        }
    };

    struct node{
        token data;
        node *next = nullptr;
        void print(){
            cerr<<" ||| "<<this<<" | "<<data.data<<" | "<<next<<" ||| ";
        }
    };

    class list{
        friend class queue;
        friend class stack;
    public:
        node *head = nullptr;
        node *tail = nullptr;

    void insert(token incoming_data){
        if (head == nullptr){
            node *new_node = new node;
            new_node->data = incoming_data;
            new_node->next = nullptr;
            head = new_node;
            tail = new_node;
            new_node = nullptr;
        }
        else{
            node *new_node = new node;
            new_node->data = incoming_data;
            tail->next = new_node;
            new_node->next = nullptr;
            tail = new_node;
            new_node = nullptr;
        }
    }
    void print(){
        cerr<<endl;
        if (head == nullptr){
            cerr<<"List is empty";
        }
        else{
            node *active_ptr = head;
            while(active_ptr!=nullptr){
                active_ptr->print();
                cerr<<" --> ";
                active_ptr = (*active_ptr).next;
            }
            cerr<<"NULL\n";
        }
    }
    void del(){
                cerr<<"List before deletion is ";
                print();
                cerr<<"\n";
                cerr<<"Head is at "<<head;
                cerr<<"\n";
        if (head == nullptr){
                    cerr<<"List is empty\n";
            return;
        }
        else if (head->next == nullptr){
            tail = nullptr;
                        cerr<<endl<<"Deleting object at "<<head<<endl;
                        delete head;
            head = nullptr; //keep an eye on this

        }
        else{
            node *temp = head;
            head = temp->next;
                    cerr<<endl<<"Deleting object at "<<temp<<endl;
            delete temp;
            temp = nullptr;
        }
                cerr<<"List after deletion is ";
                print();
        cerr<<"\n";
    }
    bool is_empty(){
        if (head == nullptr){
            return true;
        }
        else return false;
    }

    token first_elem(){
        return head->data;
    }

    ~list(){
        cerr<<"Destructor calling delete"<<endl;
        while (not(head == nullptr)){
            del();
        }
    }
    void insert_front(token incoming_data){
        if (head == nullptr){
            node *new_node = new node;
            new_node->data = incoming_data;
            new_node->next = nullptr;
            head = new_node;
            tail = new_node;
            new_node = nullptr;
        }
        else{
            node *new_node = new node;
            new_node->data = incoming_data;
            new_node->next = head;
            head = new_node;
            new_node = nullptr;
        }
    }

};

class queue{
public:
    list l_queue_list;

    void push(token incoming_data){
        l_queue_list.insert(incoming_data);
    }
    void pop(){
        if(is_empty()){
            return;
        }
        l_queue_list.del();
    }
    token peek(){
        return (l_queue_list.first_elem());
    }
    void print(){
        l_queue_list.print();
    }
    bool is_empty(){
        if(l_queue_list.is_empty())
            return true;
        else return false;
    }
};
class stack{
public:
    list l_stack_list;
    void push(token incoming_data){
        l_stack_list.insert_front(incoming_data);
    }
    void pop(){
        if(is_empty()){
            return;
        }
        l_stack_list.del();
    }
    token peek(){
        return l_stack_list.first_elem();
    }
    void print(){
        l_stack_list.print();
    }
    bool is_empty(){
        if(l_stack_list.is_empty())
            return true;
        else return false;
    }
};

class Thermostat{
public:
    bool heating, cooling, user_setting, valid_command = true; //command is valid until an exception is thrown
    int current_temp, desired_temp;
    Thermostat(string cmd){
        try{
            lexer(&cmd);
            logic();
        }
        catch(...){
            raise_error(7);
        }
    }
private:
    void lexer(string *cmd) {
        string command = *cmd;
        int pos = 0, len = (int)command.length();
        char *start = NULL, *end = NULL;
        if (!(command.find_first_not_of("TtCcHh0123456789+-") == string::npos)){
            raise_error(0);
            return;
        }
        if (command[pos] != 'T' and command[pos] !='t' and !(isdigit(command[pos+1]))){
            raise_error(1);
            return;
        }
        else{
            pos++;
            if(!isdigit(command[pos])){
                raise_error(2);
                return;
            }
            start = &command[pos];
            while(isdigit(command[pos]) and pos<len)
                pos++;
            end = &command[--pos];
            current_temp = parse_digits(start, end);
            pos++;
            if (pos == len){
                user_setting = false;
                return;
            }
            else if(command[pos]!='H' and command[pos]!='h' and command[pos]!='C' and command[pos]!='c'){
                raise_error(3);
                return;
            }
            else{
                user_setting = true;
                if(command[pos] == 'H' or command[pos] == 'h')
                    heating = true;
                if(command[pos] == 'C' or command[pos] == 'c')
                    cooling = true;
                pos++;
                if(!isdigit(command[pos])){
                    raise_error(4);
                    return;
                }
                desired_temp = parse_expression(pos, cmd);
            }
        }
    }
    int parse_digits(char *start, char *end){
        int temperature = 0, place_value = 0;
        for(; end>=start; end--){
            temperature = temperature + (*end-'0') * pow(10,place_value);
            place_value++;
        }
        return temperature;
    }
    queue generate_expression_queue(int pos, string *cmd){ //Generates the expression queue for Shunting-Yard to work on
        string command = *cmd, literal ="";
        queue exp_queue;
        int flag = pos;
        for(; pos<=command.length(); pos++){
            if(command[pos] == '+' or command[pos]=='-'){
                literal = command.substr(flag, (pos-flag)); //Literals are numbers precceded by operators
                token tok1, tok2;
                tok1.data = literal;
                tok2.data =(string(1, command[pos])); //Converting the operator to string-type inline
                tok2.id = "o";
                exp_queue.push(tok1);
                exp_queue.push(tok2);
                flag = pos+1;
            }
        }
        token tok3;
        tok3.data = (command.substr(flag, (command.length()-flag))); //token 3 carries the last digits which aren't succeeded by an operator
        exp_queue.push(tok3);
        return exp_queue;
    }
    queue shunting_yard(queue exp_queue) {  //Simplified execution of shunting-yard because expressions don't have parantheses or operator precedence
        queue output;
        stack ops;
        token temp;
        while(!exp_queue.is_empty()){
            if(exp_queue.peek().id=="n"){
                temp = exp_queue.peek();
                output.push(temp);
                exp_queue.pop();
            }
            else if(exp_queue.peek().id=="o"){
                if(ops.is_empty()){
                    temp = exp_queue.peek();
                    ops.push(temp);
                    exp_queue.pop();
                }
                else {
                    temp = ops.peek();
                    output.push(temp);
                    ops.pop();
                    temp = exp_queue.peek();
                    ops.push(temp);
                    exp_queue.pop();
                }
            }
        }
        while(!ops.is_empty()){
            temp = ops.peek();
            output.push(temp);
            ops.pop();
        }
        return output;
    }
    token eval(token op1, token op2, token operation){// Evaluate binary operation of + or -
        int num1, num2, result;
        token output;
        try {
            num1 = stoi(op1.data);
            num2 = stoi(op2.data);
            if(num1 == 0 or num2 == 0){     // Increment or Decrement by 0 not allowed
                raise_error(6);
                return output;
            }
            if(operation.data == "+"){
                result = num1 + num2;
                output.data = to_string(result);
                return output;
            }
            else if (operation.data == "-"){
                result = num1 - num2;
                output.data = to_string(result);
                return output;
            }
            else{
                raise_error(5);
                return output;
            }
        }
        catch(...){
            raise_error(5);
            return output;
        }
    }

    int reverse_polish_parse(queue exp_queue){ //RPN parsing algorithm
        stack ops_stack;
        token op1, op2, operation, temp;
        while(!exp_queue.is_empty()){
            if(exp_queue.peek().id == "n"){
                temp = exp_queue.peek();
                ops_stack.push(temp);
                exp_queue.pop();
            }
            else if(exp_queue.peek().id == "o"){
                op1 = ops_stack.peek();
                ops_stack.pop();
                op2 = ops_stack.peek();
                ops_stack.pop();
                operation = exp_queue.peek();
                exp_queue.pop();
                token x = eval(op2, op1, operation);
                ops_stack.push(eval(op2,op1,operation));
            }
        }
        try{
            return (stoi(ops_stack.peek().data));
        }
        catch(...){
            raise_error(5);
            return -1000;
        }
    }
    int parse_expression(int pos, string*cmd){//
        queue exp_queue = generate_expression_queue(pos, cmd);
        exp_queue = shunting_yard(exp_queue);
        return reverse_polish_parse(exp_queue);
    }
    void raise_error(int id){
        valid_command = false;

        switch (id) {
            case 0:
                cerr<<"Ilegal characters\n";
                break;
            case 1:
                cerr<<"First letter of command must be T or t\n";
                break;
            case 2:
                cerr<<"T must be followed by current temperature\n";
                break;
            case 3:
                cerr<<"Current temperature must be followed by setting\n";
                break;
            case 4:
                cerr<<"Setting must be followed by a vaid expression\n";
                break;
            case 5:
                cerr<<"Error parsing expression token. Please check\n";
                break;
            case 6:
                cerr<<"Increment or Decrement should be more than 0\n";
                break;
            case 7:
                cerr<<"Please don't walk into a bar and try to order -5 beers. Thanks :) \n";
                break;
            default:
                break;
        }

    }
    void logic(){
        if (heating and current_temp >= desired_temp){
            heating = false;
        }
        if (cooling and current_temp <= desired_temp){
            cooling = false;
        }
    }
};

bool isWellFormedThermostatString(string commands){
    Thermostat thermos(commands);
    return thermos.valid_command;
}

int temperature(string commands){
    Thermostat thermos(commands);
    if (thermos.valid_command){
        return thermos.current_temp;
    }
    else return -1;
}

int setting(string commands){
    Thermostat thermos(commands);
    if (thermos.valid_command and thermos.user_setting){
        return thermos.desired_temp;
    }
    else if(thermos.valid_command){
        return 0;
    }
    else return -1;
}

bool isHeating(string commands){
    Thermostat thermos(commands);
    if (thermos.valid_command)       //Extra security doesn't hurt :)
        return thermos.heating;
    else return false;
}

bool isCooling(string commands){
    Thermostat thermos(commands);
    if (thermos.valid_command)
        return thermos.cooling;
    else return false;
}
int main(){

    string str = "T205h55+5";
    cerr<<"\nThe command is valid: "<<boolalpha<<isWellFormedThermostatString(str)<<endl<<endl;;
    cerr<<"Current temperature is "<<temperature(str)<<endl<<endl;
    cerr<<"User's desired temperature "<<setting(str)<<endl<<endl;
    cerr<<"Heating: "<<boolalpha<<isHeating(str)<<endl<<endl;
    cerr<<"Cooling: "<<boolalpha<<isCooling(str)<<endl<<endl;
}

Answer 1

Your list is used as an immediate member of queue and stack classes. Class queue is passed around by value in your code. Since Rule of Three is violated by your list class, it expectedly and unavoidably leads to typical problems, like double deletion, access to deallocated memory and so on.

The current compiler-provided copy constructor and copy assignment operator of list perform shallow-copying of your list objects, i.e. all copies of the same list will refer to the same linked lists of nodes. When one such instance gets destructed, it deallocates the list. After that other copies are left pointing to deallocated memory.

If you really want to pass these classes around by value you have to follow the Rule of Three (or Rule of Five). You have to properly implement copy constructor and copy assignment operator for your list class.

Another solution would be to avoid passing these objects by value. If you decide to go that way, define the copy constructor and copy assignment operator as "deleted". This will make sure you never inadvertently make a shallow copy of these objects.