c++ 解决方案在 leetcode 上因地址未对齐错误而失败，但在 visual studio 中运行

Question

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

Answer 1

您没有初始化所有 class 成员。

MinStack 有成员：

int min;
ListNode* topStackNode;
ListNode* topMinNode;

MinStack 的构造函数没有任何成员初始值设定项列表，也没有设置任何成员：

MinStack() {}

您正在使用此构造函数在此处构造一个对象：

MinStack* ms = new MinStack();

由于 MinStack 的成员没有声明任何指定的默认初始化器并且构造函数不为它们提供任何初始化器，因此它们将被 默认初始化 .由于它们是非 class 类型，默认初始化意味着不会执行任何初始化。成员将保留其不确定的值。

然后在下一行：

ms->push(5);

你调用 push 执行：

if (topStackNode == NULL)

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

在构造函数的初始化器列表中或使用 默认成员初始化器 在 class 定义中初始化所有成员：

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

或等同于：

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

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

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

它还会告诉你你滥用了NULL。您将其用作 top() 的 return 值，其中 returns int。不保证 NULL 可以转换为整数。 NULL 应该只用来表示一个指针。而且由于 C++11 NULL 根本不应该使用。而是使用 nullptr，这会给你一个正确的错误，即从 int top() 中 return 没有意义。

同时避免使用 new。它不是异常安全的，会导致内存泄漏，需要特别注意正确实现 classes 的复制操作（查找 "rule of 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的使用和class中原始拥有指针的使用大概也可以用std::unique_ptr和std::make_unique代替。您的 class 当前正在泄漏其内存分配，如果它的一个实例被复制（显式或隐式），可能会导致未定义的行为。使用 std::unique_ptr.

时，这不是问题

c++ 解决方案在 leetcode 上因地址未对齐错误而失败，但在 visual studio 中运行

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

c++

pointers

alignment

memory-alignment