# Optimization suggestions for my Stack [closed]

stack.hpp

class Stack
{
public:
Stack(float incFactor = 1.5f);
~Stack();

template<typename T>
inline void push(T value)
{
validate(sizeof(T));
*(reinterpret_cast<T*>(top)) = value;
top += sizeof(T);
size += sizeof(T);
}

void push(char* value);
void push(char* value, int size);

template<typename T>
inline T pop()
{
validate(sizeof(T));
top -= sizeof(T);
size -= sizeof(T);
return *(reinterpret_cast<T*>(top));
}

char* pop_str();
char* pop(int size = 1);

void print(const char* end = "\n");
void print_int(const char* end = "\n");

int length();
void* get_data();
void revalidate(int size);

private:

float incFactor;
char* top;
char* data;
int size;
int capacity;
};


stack.cpp

Stack::Stack(float incFactori)
{
incFactor = incFactori;
capacity = STACK_SIZE;
size = 0;
data = (char*)malloc(capacity);
top = data;
}

Stack::~Stack()
{
if(data)
free(data);
}

void Stack::print(const char* end)
{
printf("[ ");
for(int i = 0; i < size; i++)
printf("%d ", (int)data[i]);
printf("]");
printf("%s", end);
}

void Stack::print_int(const char* end)
{
printf("[ ");
int count = size / sizeof(int);
for(int i = 0; i < count; i++)
printf("%d ", ((int*)data)[i]);
printf("]");
printf("%s", end);
}

void Stack::revalidate(int sizei)
{
if(sizei + size > capacity)
{
capacity = (int)(capacity * incFactor);
char* datat = (char*)malloc(capacity);
memcpy(datat, data, size);
free(data);
data = datat;
top = data + size;
}
}

void Stack::push(char* value)
{
validate(strlen(value) + 1);
*top = '\0';
memcpy(top + 1, value, strlen(value));
top += strlen(value) + 1;
size += strlen(value) + 1;
}

void Stack::push(char* value, int sizei)
{
validate(sizei);
memcpy(top, value, sizei);
top += sizei;
size += sizei;
}

char* Stack::pop_str()
{
char* value = top - 1;
int sizei = 0;

while(*value != '\0')
{
value--;
sizei++;
}
char* outStr = (char*)malloc((top - value) + 1);
memset(outStr, '\0', (top - value) + 1);
memcpy(outStr, value + 1, top - value);
outStr[top - value] = '\0';
top -= sizei + 1;
size -= sizei + 1;
return outStr;
}

char* Stack::pop(int sizei)
{
char* value = top - sizei;
char* outStr = (char*)malloc((top - value));
memset(outStr, '\0', (top - value));
memcpy(outStr, value, top - value);
top -= sizei;
size -= sizei;
return outStr;
}

int Stack::length()
{
return size;
}

void* Stack::get_data()
{
return data;
}

• validate has not been defined. Dec 10 '21 at 18:06
• We need working code to do a review. It may also help if you include some usage examples. Is this an exercise or are you trying to create something faster than achievable with std::stack/std::vector?
– jdt
Dec 10 '21 at 21:45
• @jdt neither i am making a stack based language and this is the stack for that. And std::stack doesnt fit my needs directly. Also i want something as bare metal as possible and fast Dec 11 '21 at 6:45
• @jdt sorry that just got ommitted while copy paste #define validate(x) revalidate(x)  Dec 11 '21 at 6:46
• Don't comment comments asking for missing information: Edit your post. Dec 11 '21 at 12:15

## 2 Answers

You're implementing a growable collection like vector and only using it for this Stack.

Don't use raw pointers, malloc, etc. If you are implementing your own low-level memory management (instead of just using vector), at least use unique_ptr for the data. You should not need to write a destructor for the class!

Writing inline for a member function defined inside the class doesn't do anything.

So Stack is not a template based on the element type, but push and pop are templates? This is weird and dangerous. How do you you know what the next element is supposed to be in order to pop it correctly?

You are not respecting the alignment of the objects you push. That can fail on some architectures.

You are not calling destructors of all the stacked stuff when you destroy the stack.

The Pop function copies the element into the return value, but never calls the destructor of the location on the stack. Try stacking std::string objects and watch the memory leaks!

The autogenerated copy constructor and assignment operator will not work properly, and will simply copy the data pointer and now the two instances can fight over it!

If you write any of the special member functions (e.g. the destructor, as you have), you probably need to write all of them.

You're using malloc, printf; you don't appreciate that objects have constructors/destructors even though your class needs it; is seems like this has a "C" mentality and just dresses it up in a class but it's not really.

What are your design requirements for this? How is it different from the std::stack?

What is your goal in writing it: is it something you need, or is it to learn how such data structures can be implemented?

Start with documentation. Let others help spot gaps and inconsistencies (like the copy constructor) in the design first. You should not be worrying about optimization at this point: first make it correct. Deeper than that, make it do something sensible in the first place.

• i am not deleting any individual elements form stack on being popped as its a big block of memory allocated and will be deallocated together when everything is done and pop is not meant to totally delete the data(a later push will overwrite it). then i am not very familiar with inline i got suggested by some people to use it so its there. Stack is not meant to be a template as it should be able to hold any type of data as it works with the bytes like the RAM. i am not at all using std::string all strings for my project are char[4096] and i have separate methods to handle that. Dec 11 '21 at 6:55
• This is not purely a exercise i am trying to make a stack based VM. std::stack can hold only one type but as i told it needs to hold everything. And one of the most important reason is as you geussed it C Mentality. Yeah i want it to be very similar to a C implementation(I do have a C transpiler which should have this same stack) Dec 11 '21 at 6:58
• "Forgetting" and then overwriting the same memory is what I was talking about; I know the larger chunk is not freed to the free store until later, and as one big chunk. You are not calling the destructor of the object your "forgot". Dec 13 '21 at 14:41
• A "stack-based VM" you mean for doing arithmetic? And you have different kinds of values you are working with, like real, complex, and strings and whatnot? Anyway, how do you know what the correct type is to pop? If this is meant for a real program, you are going down a scary road there. You ought to look into something like std::stack<std::variant>. Dec 13 '21 at 14:44
• re "not familiar with inline": It means that a function or variable can be defined outside of any class in a header file without causing a linker error. Nothing more. See en.cppreference.com/w/cpp/language/inline The interesting part is #2 under Explaination where it says "has the following additional properties". Subpoint #1 under that is the main point. The others are clarifications on the exact meaning and proper use. Dec 13 '21 at 15:00

# Stack::revalidate

In this function, you are using malloc but not checking if it was successful. Since you are already using malloc+free instead of new+delete you could have simply used realloc.

Also, note that the standard type for array indexes and size is std::size_t and not int. Using an int will limit them to 32-bit values.

I think that the floating-point incFactor is also somewhat unusual. Perhaps you could make incFactor 15 and then divide by 10.

Suggested:

bool Stack::revalidate(std::size_t sizei)
{
if (sizei <= size > capacity)
return true;
std::size_t newcap = capacity * incFactor / 10;
char* newdata = (char*)realloc(data, newcap);
if (!newdata)
return false;
capacity = newcap;
data = newdata;
top = data + size;
return true;
}


# Stack::pop

I'm not sure why you are first setting all the items to zero and then copying over them. Something does not look right and removing the unnecessary parentheses makes it clear:

memset(outStr, '\0',  top - value);
memcpy(outStr, value, top - value);


# Final thoughts

Without any usage samples it's hard to review the rest. Most likely you can save yourself a lot of problems by simply using the standard std::stack with a std::variant:

std::stack<std::variant<std::string, int, double>> mystack;


Or, a union:

union Data
{
char* str;
int num;
};

std::stack<Data> data;

• I want to have something thats easily rewritable in c so std::stack is not an option. Dec 11 '21 at 14:54
• @JaysmitoMukherjee then write it in C. What you are attempting is not C++, but C code packaged as member functions instead of having to pass this as the first parameter explicitly. Does it really need to be implemented in C also, or just callable from C? Dec 13 '21 at 14:51
• @JDługosz not callable but i have a c transpiler that needs to use a same stack Dec 15 '21 at 5:22