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代码，带有测试--错误起源于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

您没有初始化所有的类成员。

MinStack有以下成员：

int min;
ListNode* topStackNode;
ListNode* topMinNode; 

MinStack的构造函数没有任何成员初始化程序列表，也没有设置任何成员：

MinStack() {}

您在这里使用此构造函数构造一个对象：

MinStack* ms = new MinStack();

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

然后在下一行：

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时，这不会引起关注。