Wednesday

View Stack data structure source code from CodeBlocks and g++

View Stack data structure source code from CodeBlocks and g++

Open CodeBlocks

Create a CodeBlocks project
Menu > File > New > Project > Console application > Go button
Follow on-screen instructions

Replace all the main.cpp content with the below code.
{{{{{
#include <iostream>
#include <stack>
using namespace std;

int main(int argc, char* argv[])
{
    stack<int> mystack;

    mystack.push(1);
    mystack.push(2);
    mystack.push(3);

    cout << "stack size: " << mystack.size() << endl;

    cout << "stack content in LIFO context: ";
    while(!mystack.empty())
    {
        cout << mystack.top() << " ";
        mystack.pop();
    }
    cout << endl;

    return 0;
}
}}}}}

Right-click at the push() method of the mystack object on the line “mystack.push(1);”, select “Find implementation of: push”

The stack data structure source code from the g++.exe compiler is at:
“C:\program files (x86)\codeblocks\MinGW\lib\gcc\mingw32\4.7.1\include\c++\bits\stl_stack.h”
File name: stl_stack.h
Both the stack class declaration and implementation are coded in this header file.

You can view the push() method implementation of the stack class as shown below:
{{{{{
      /**
       *  @brief  Add data to the top of the %stack. //documentation comments
       *  @param  __x  Data to be added.
       *
       *  This is a typical %stack operation.  The function creates an
       *  element at the top of the %stack and assigns the given data
       *  to it.  The time complexity of the operation depends on the
       *  underlying sequence.
       */
      void                                         
      push(const value_type& __x)  //call by reference
      { c.push_back(__x); }
}}}}}

Right-click on the “deque” word on top of the “class stack” line as shown below and select “Find declaration of: deque”.
{{{{{
  template<typename _Tp, typename _Sequence = deque<_Tp> >
    class stack
    {
        . . .
}}}}}

The g++ stack class is implemented as a container adapter. It uses the standard deque data structure.
The stl_deque.h is at:
C:\program files (x86)\codeblocks\MinGW\lib\gcc\mingw32\4.7.1\include\c++\bits\stl_deque.h
Press Ctrl+F and search for the “push_back” method.
The push_back() method implementation for the deque data structure is shown below:
{{{{{
      void
      push_back(const value_type& __x)
      {
    if (this->_M_impl._M_finish._M_cur
        != this->_M_impl._M_finish._M_last - 1)       // deque capacity is not full
      {                                                                      // add data to the end of the deque
        this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __x);
        ++this->_M_impl._M_finish._M_cur;
      }
    else                                                                    // else add data to the end of the auxiliary deque
      _M_push_back_aux(__x);
      }
}}}}}

Due to the nature of the deque data structure, this push_back() operation can be done in constant time.

No comments:

Newton-Raphson Method in C++

The Newton Raphson Method is an open method used to find the roots of a function. It employs the technique of linear approximation and invol...