c++ - C++解决方案在带有未对齐地址错误的leetcode上失败，但在Visual Studio中运行

我是C++的新手，所以我正在尝试一些leetcode问题。我目前正在尝试最小堆栈问题。我认为我已经正确解决了，除了我从leetcode中得到了以下运行时错误:

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

这是我的带有测试的Visual Studio代码-错误源自push()中的以下行:

                topStackNode->stackPrev = newNode;

有人知道会导致这种情况发生吗？我读了一些，有类似错误的人说这是因为ListNode没有初始化为NULL，但我在我的结构中显然将所有ListNodes初始化为NULL。谢谢!

#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;

}

编辑-下面使用共享指针的新解决方案:

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;
    }
};

最佳答案

您没有初始化所有类(class)成员。
MinStack具有成员:

int min;
ListNode* topStackNode;
ListNode* topMinNode;

您的MinStack构造函数没有任何成员初始化程序列表，并且未设置任何成员:

MinStack() {}

您正在使用此构造函数在此处构造对象:

MinStack* ms = new MinStack();

由于MinStack的成员未使用任何指定的默认初始值设定项声明，并且构造函数未为其提供任何初始值设定项，因此将对其进行默认初始化。由于它们是非类类型，因此默认初始化意味着不会执行任何初始化。成员将保持其不确定的值(value)观。

然后在下一行:

ms->push(5);

您调用执行的push:

if (topStackNode == NULL)

这具有不确定的行为，因为topStackNode的值不确定。

在构造函数的初始化程序列表中初始化您的所有成员，或者在类定义中使用默认的成员初始化程序进行初始化:

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

或等效地:

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

同时在编译器上启用警告。

它会警告您ListNode构造函数的初始化列表与成员声明的顺序不同。它们具有相同的顺序很重要，因为初始化的顺序是声明的顺序，而不是成员初始化程序的顺序。为了避免意外使用未初始化的成员，应始终使初始化程序列表顺序与成员声明顺序保持一致。

它还会告诉您您正在滥用NULL。您将其用作top()的返回值，该返回值返回int。不保证NULL可以转换为整数。 NULL仅应用于表示指针。而且由于C++ 11 NULL根本不应该使用。而是使用nullptr，它会给您一个适当的错误，即从int top()返回它没有任何意义。

还要避免使用new。它不是异常安全的，会导致您的内存泄漏，需要特别注意正确执行类的复制操作(查找“0/3/5规则”)，并且会引起很多麻烦。
new中使用的main完全没有意义。您可以直接将对象声明为变量:

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;

}

可以使用new和std::unique_ptr替换std::make_unique的使用和在类中使用原始拥有的指针。您的类当前正在泄漏其内存分配，并且如果曾经复制过其实例(显式或隐式)，则可能会导致未定义的行为。使用std::unique_ptr时不必担心。

关于c++ - C++解决方案在带有未对齐地址错误的leetcode上失败，但在Visual Studio中运行，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/59586063/