c++ solution fails on leetcode with misaligned address error but runs in visual studio

Question

i'm new to C++ so i'm trying some leetcode problems. i'm currently attempting the min stack problem. i think i've solved it correctly, except i get the following runtime error from leetcode:

Line 24: Char 37: runtime error: member access within misaligned address 0xbebebebebebebebe for type 'struct ListNode', which requires 8 byte alignment (solution.cpp)

here is my visual studio code, with tests - the error originates from the following line in push():

                topStackNode->stackPrev = newNode;

anyone know what would cause this to happen? i read a bit and some people with similar errors say its because ListNode is not initialized to NULL, but i clearly initialize all ListNodes to NULL in my struct. thanks!

#include <vector>
#include <iostream>
using namespace std;
// design a stack that supports push, pop, top, and retrieving the minimum element in constant time


class MinStack {

struct ListNode {
    ListNode* stackNext;
    ListNode* stackPrev;
    ListNode* minNext;
    ListNode* minPrev; 
    int val;
    ListNode(int v) : val(v), stackNext(NULL), stackPrev(NULL), minNext(NULL), minPrev(NULL) 
    {
    }
};

public:
    /** initialize your data structure here. */
    MinStack() {}

    void push(int x) {

        ListNode* newNode = new ListNode(x); 

        if (topStackNode == NULL)
            topStackNode = newNode;
        else {
            topStackNode->stackPrev = newNode;
            newNode->stackNext = topStackNode;
            topStackNode = newNode; 
        }

        insertNodeMinStack(newNode); 
    }

    void pop() {
        removeFromMinStack(topStackNode);
        popFromStack();
    }

    void popFromStack() {
        topStackNode = topStackNode->stackNext; 
    }

    void removeFromMinStack(ListNode* node) { // delete the currently popped node from the min stack
        if (node != NULL) {
            if (node == topMinNode) {
                topMinNode = node->minNext;
                min = topMinNode->val; 
                return; 
            }
            if (node->minPrev != NULL)
                node->minPrev->minNext = node->minNext; 
            if (node->minNext != NULL)
                node->minNext->minPrev = node->minPrev;  
        }

    }

    int top() {
        if (topStackNode != NULL)
            return topStackNode->val;
        else 
            return NULL; 
    }

    int getMin() {
        return min; 
    }

    void insertNodeMinStack(ListNode* node) {
        if (topMinNode == NULL) { // inserting node on an empty list
            topMinNode = node; 
        }
        else if (node->val < topMinNode->val) { // node has smallest value
            topMinNode->minPrev = node;
            node->minNext = topMinNode;
            topMinNode = node; // set new top min node and update min
            min = node->val; 
        }
        else {
            ListNode* currentNode = topMinNode;
            while (currentNode->minNext != NULL && currentNode->val < node->val) {
                currentNode = currentNode->minNext;
            }
            if (currentNode->minNext == NULL) { // reached end of list, 'node' has largest value in list
                currentNode->minNext = node;
                node->minPrev = currentNode; 
                //min remains unchanged
            }
            else { // we're somewhere in the middle of the list, ie there are nodes surronding 'node'
                node->minNext = currentNode->minNext; 
                node->minPrev = currentNode; 
                currentNode->minNext = node;
                node->minNext->minPrev = node; 
            }
        }
    }

private: 
    int min;
    ListNode* topStackNode;
    ListNode* topMinNode; 
};

int main() {//1,2,6,3,4,5,6
    MinStack* ms = new MinStack(); 

    ms->push(5); 
    ms->push(3);
    ms->pop(); 
    ms->push(10);
    ms->push(-3);
    ms->pop();
    ms->pop();
    ms->push(-11);

    cout << "minstack min = " << ms->getMin() << endl;

}

EDIT - new solution below using shared pointers:

class MinStack {
    struct ListNode {
        shared_ptr<ListNode> prev;
        shared_ptr<ListNode> next;
        shared_ptr<ListNode> minNext;
        shared_ptr<ListNode> minPrev; 
        int value;
        ListNode(int val) : prev(nullptr), next(nullptr), minNext(nullptr), minPrev(nullptr), value(val) {}
    };

public:

    shared_ptr<ListNode> topn;
    shared_ptr<ListNode> minTop; 
    shared_ptr<ListNode> node;

    MinStack() : topn(nullptr), minTop(nullptr), node(nullptr){}

     void push(int value) {

        // cout << "pushing value " << value << endl; 

        if (topn == nullptr) {
            topn = make_shared<ListNode>(value);
            insertToMinList();
        }
        else {
            node.reset(); 
            node = make_shared<ListNode>(value);
            node->next = topn;
            topn = node;
            insertToMinList(); 
        }
    }

     void removeFromMinList() { 
     //removing the node topn from min list
         if (topn->minNext != nullptr && topn->minPrev != nullptr) {
            // cout << "removing, neither null, " << topn->value << endl; 
             topn->minNext->minPrev = topn->minPrev;
             topn->minPrev->minNext = topn->minNext; 
         }
         else if (topn->minNext != nullptr) {
            // cout << "removing, next not null, " << topn->value << endl; 
             topn->minNext->minPrev = topn->minPrev;
         }
         else if (topn->minPrev != nullptr) {
            // cout << " removing, prev not null, " << topn->value << endl; 
             topn->minPrev->minNext = topn->minNext;
         }
         else {
            // cout << "no condition met in removign " << endl; 
         }
         if (topn == minTop) {
             minTop = topn->minNext;
         }

     }

     void insertToMinList() { 
         if (minTop == nullptr) {
             minTop = topn;
             //cout << "min list null, initializing with " << topn->value << endl; 
         }
         else if (topn->value <= minTop->value) {
             //cout << "new value is smallest " << topn->value << endl; 
             minTop->minPrev = topn; 
             topn->minNext = minTop; 
             minTop = topn; 
         }
         else {
             //cout << "searching list to place value " << topn->value << endl; 
             shared_ptr<ListNode> temp = make_shared<ListNode>(minTop->value); 
             temp->minNext = minTop->minNext; 

             while (temp != nullptr && temp->value < topn->value) { //go down the list
                 topn->minNext = temp->minNext; 
                 topn->minPrev = temp;
                 temp = temp->minNext; 
             }
             //while loop completes. now, temp is either nullptr or between two nodes
             if (temp == nullptr) {// new value is largest
                 //cout << "reached end of list, assigning value " << topn->value << endl; 
                 topn->minPrev->minNext = topn; 
                 topn->minNext = nullptr; 
             }
             else { // between two nodes, reassign prev and next
                 //cout << "in middle of list, assigning vale " << topn->value << endl; 
                 topn->minNext->minPrev = topn;
                 topn->minPrev->minNext = topn; 
             }
         }
     }

    void pop() {

        //cout << "popping value " << topn->value << endl; 
        removeFromMinList(); 
        topn = topn->next;


    }

    int top(){
        return topn->value;
    }

    int getMin() {
        return minTop->value; 
    }
};

Disapprove

Answer 1

You are not initializing all your class members.

MinStack has members:

int min;
ListNode* topStackNode;
ListNode* topMinNode; 

Your constructor for MinStack does not have any member initializer list and doesn't set any of the members:

MinStack() {}

You are using this constructor to construct an object here:

MinStack* ms = new MinStack();

Since the members of MinStack are not declared with any any default initializers specified and the constructor does not provide any initializers for them, they will be default-initialized. Since they are non-class types default-initialization means that no initialization will be performed. The members will keep their indeterminate values.

Then in the next line:

ms->push(5); 

you call push which executes:

if (topStackNode == NULL)

This has undefined behavior, because topStackNode has indeterminate value.

---

Initialize all your members in the constructor's initializer list or with default member initializers in the class definition:

int min = 0;
ListNode* topStackNode = nullptr;
ListNode* topMinNode = nullptr;

or equivalently:

int min{};
ListNode* topStackNode{};
ListNode* topMinNode{};  

---

Also enable warnings on your compiler.

It will warn you that the initalizer list of ListNode's constructor is not in the same order as the member declarations. It is important that they are in the same order, because the order of initialization is the order of the declarations, not the order of the member initializers. In order to avoid accidentally using an uninitialized member, you should always keep the initializer list order consistent with the member declaration order.

It will also tell you that you are misusing NULL. You are using it as return value for top() which returns int. It is not guaranteed that NULL can be cast to an integer. NULL should only be used to represent a pointer. And since C++11 NULL should not be used at all. Instead use nullptr, which would have given you a proper error that returning it from int top() doesn't make sense.

---

Also avoid using new. It is not exception-safe, will cause you memory leaks, requires special care to be taken that copy operations of classes are implemented correctly (look up "rule of 0/3/5") and will cause you many headaches.

The new use in main is completely pointless. You can just declare the object directly as variable:

int main() {//1,2,6,3,4,5,6
    MinStack ms; 

    ms.push(5); 
    ms.push(3);
    ms.pop(); 
    ms.push(10);
    ms.push(-3);
    ms.pop();
    ms.pop();
    ms.push(-11);

    cout << "minstack min = " << ms.getMin() << endl;

}

The new use and use of raw owning pointers in the class can probably also be replaced with std::unique_ptr and std::make_unique. Your class is currently leaking its memory allocations and will likely cause undefined behavior if an instance of it is ever copied (explicitly or implicitly). That would not be a concern when using std::unique_ptr.

Anetteaneurin

thanks. it is running now on leetcode...except it appears that my solution is wrong, heh. – Disapprove

I wouldn't worry about that much. Leetcode's opinion on what makes a good solution is dodgy at best. – Quizmaster

i assume by "raw owning pointers" you're referring to my ListNode* variables? and to replace with std::unique_ptr, i'll do something like std::unique_ptr<ListNode> node, instead of ListNode* node ? thx – Disapprove

@RussellButler Yes, but only the owning ones, so probably the *Next and top* ones. It will also require some modification of the code, in particular some std::move or std::swaps will be required. You need to first learn about these things, it is not trivial. I suggest you work through a good C++ introductory book. As mentioned in a comment above, leetcode will probably not care about that, but using new is, except in rare situations, terrible style for any production code. – Anetteaneurin

@RussellButler Leetcode, from my understanding (haven't used it myself), is about algorithms and data structures, not the programming language or style. These are two different things, that you will need to both learn (to varying degrees). – Anetteaneurin

@Anetteaneurin hello, i re-did my solution using shared pointers (not sure how it could be possible with unique pointers, because nodes need to be pointed at by multiple other nodes, because i'm using two lists (one for the regular stack, one for the minimum value). can you let me know if you spot any problems with the shared pointer implementation? thanks! – Disapprove

@RussellButler You need to learn about ownership semantics. Only one of the pointers pointing to any given node should be a unique_ptr (owning) and the rest should be raw pointers (non-owning). If the two lists point to the same objects, only one of them should be owning and the other shouldn't be at all. Then also only next and top of the one list should be owning and unique_ptr. temp may be unique_ptr as well, depending on how you set it up. The rest shouldn't be. Then, because unique_ptr is not copyable, as you noticed, you need to use std::move to transfer ownership. – Anetteaneurin

This is a bit too much to explain in a comment. Try looking up a detailed ressource, such as one of the introductory books I mentioned above. Your current solution probably works and doesn't cause any problems like memory leaks and so on anymore, that you would have had with new, but it now models shared ownership when really each object only needs to be owned by one pointer. It won't be well-performing and there is always a risk with shared_ptr, because shared_ptrs can create cyclic ownership, which may again result in memory leaks. – Anetteaneurin

Also in practice you wouldn't write your own list implementation in the first place. There is already a generic list implementation in the standard library (std::list or maybe just std::vector) that would be much easier and safer to use. But using those might defeat the purpose of learning how to implement these data structures. (As I said, I don't really know what the intend of leetcode is.) – Anetteaneurin

great, thanks alot for the response! i'll take a look at some of those resources you mentioned. – Disapprove