Rus*_*ler 2 c++ pointers alignment memory-alignment
我是 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，但我清楚地在我的结构中将所有 ListNode 初始化为 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;
}
};
您没有初始化所有班级成员。
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应该只用于表示一个指针。而且由于NULL根本不应该使用C++11 。而是使用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_ptrand std::make_unique。您的类当前正在泄漏其内存分配，并且如果它的实例被复制（显式或隐式），则可能会导致未定义的行为。使用std::unique_ptr.