Monday, September 8, 2014

Translator – Hold Stack As Standard Stack

Continuing with the transition to STL classes and for the preparation of changing token pointers to a shared smart pointer, the hold stack, which holds token pointers, was changed from a QStack to a std::stack.  This stack contains Hold Item structures, each with a pointer to a token and a pointer to the token of the first operand if the token is an operator.  The Hold Stack class was created to add two functions to the QStack used as its base class.

The added push function contained arguments for the pointer to a token and an optional pointer first operand token.  The stack was resized up by one element and the new top element was set to the token pointers provided.  This was an attempt to optimize the push operation.  The default constructor would be called to the stack item added by the resize, but since the Hold Item structure only contained plain old data members (pointers), there was no constructor.

The added drop function resized the stack down one element.  The destructor for the element dropped would be called, but again, since the element was a simple structure, there was no destructor.

The functions of std::stack work differently.  With C++11, the std::stack gains the emplace function, which as previously described, does an in-place construction of the item being pushed.  This is exactly what the added push function was implemented to achieve, so all push calls were changed to emplace although this required that the Hold Item have a constructor with arguments for the token pointer and optional first token pointer (like the added push function).

The pop function of the std::stack class does not return a reference like with QStack and it only pops the top item off of the stack (there is no return value).  Therefore, all pop calls had to be changed to top calls (to get the value) followed by a pop call.  However, the pop function is identical to the added drop function, so these were changed to pop calls.  Finally, the isEmpty() calls were changed to the standard equivalent empty() and the Hold Stack class was removed.

An attempt was made to modify the Hold Stack class to combine the top and pop functions, but the resulting code was slightly larger and slower than using std::stack directly (determined by using a small test program with many iterations).  This is probably why these functions were implemented the way they were.  Therefore, these functions will be used as is.

The std::stack class is an adapter for the underlying class, which by default is the std::deque ("deck") class that works like both a vector (array) and double linked list (sounds expensive).  The std::stack class can work with any class that supports empty, size, back, push back and pop back.  The class is specified as the second template parameter after the stack element type.  Using a test program, a std::vector and std::list were also tried, but the default std::deque class was the fastest (though not the smallest).  The std::forward_list class, a simple single linked list, was also tried as a stack, though it can't be used with the std::stack class.  And while std::forward_list is the simplest, it was also the slowest (by over four times).  Therefore, the default std::stack will be used.


[branch cpp11 commit e4d568e43f]

No comments:

Post a Comment

All comments and feedback welcomed, whether positive or negative.
(Anonymous comments are allowed, but comments with URL links or unrelated comments will be removed.)