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
#include
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 prev;
shared_ptr next;
shared_ptr minNext;
shared_ptr minPrev;
int value;
ListNode(int val) : prev(nullptr), next(nullptr), minNext(nullptr), minPrev(nullptr), value(val) {}
};
public:
shared_ptr topn;
shared_ptr minTop;
shared_ptr node;
MinStack() : topn(nullptr), minTop(nullptr), node(nullptr){}
void push(int value) {
// cout << "pushing value " << value << endl;
if (topn == nullptr) {
topn = make_shared(value);
insertToMinList();
}
else {
node.reset();
node = make_shared(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 temp = make_shared(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
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.
No comments:
Post a Comment