7
\$\begingroup\$

I am working on a basic linked list implementation of a stack of ItemType (currently set to double but can be changed) values. The stack code will then be used in a function that reverses a sound data file by reading in all the data samples, pushing them onto a stack, and then creating a new sound data file while popping values off the stack. My code seems to be working fine, but it does take a rather long time to finish processing.

Though this is likely due in part to the length of the files, I would appreciate any tips to help optimize my code and potentially speed it up.

Below is my header file:

#ifndef DBLSTACK_H
#define DBLSTACK_H


typedef double ItemType; // stack currently holds doubles


class DblStack
{
private:
    //Node class
    class Node
    {
    public:
        double data;
        Node *next;

        // Node constructor
        Node(double value, Node * link = 0)
        {
            data = value;
            next = link;
        }
    };

    typedef Node * NodePtr;

    // Data members
    NodePtr myTop;  //points to top of stack

  public:
    // Class Constructor
    DblStack();

    // Copy Constructor
    DblStack(const DblStack& rhs);

    // Class Deconstructor
    ~DblStack();

    // Assignment operator
    // Assigns a stack to another
    const DblStack& operator= (const DblStack& rhs);

    // isEmpty
    // Checks if the stack is empty
    bool isEmpty() const;

    // push
    // Pushes an item on top of the stack.
    void push(const ItemType& item);

    // pop
    // Pops the top item off the stack.
    void pop();

    // top
    // Returns the top item of the stack without popping it.
    ItemType top() const;

    // size
    // Returns the number of items on the stack.
    size_t size() const;

};

#endif

And here is my source file:

#include <cstddef>
#include <stdexcept>
#include "DblStack.h"
using namespace std;

// Class Constructor
// post: stack is created & initialized to be empty
DblStack::DblStack()
: myTop(0), mySize(0)
{
}


// Copy Constructor
// pre: parameter object, rhs, exists
// post: stack is created to be a copy of the parameter stack
DblStack::DblStack(const DblStack& rhs)
{
    myTop = 0;
    if (!rhs.isEmpty())
    {
        // Copy first node
        myTop = new DblStack::Node(rhs.top());

        // Set pointers to run through stack
        DblStack::NodePtr lastPtr = myTop;
        DblStack::NodePtr origPtr = rhs.myTop->next;
        while (origPtr != 0)
        {
            lastPtr->next = new DblStack::Node(origPtr->data);
            lastPtr = lastPtr->next;
            origPtr = origPtr->next;
        }
    }
}



// Class Deconstructor
// pre: the stack exists
// post: the stack is destroyed and any dynamic memory is returned to the system
DblStack::~DblStack()
{
    // Set pointers to run through stack
    DblStack::NodePtr curr = myTop, next;
    while (!isEmpty())
    {
        next = curr->next;
        delete curr;
        curr = next;
    }
}


// Assignment operator
// Assigns a stack to another
// pre: both class objects exist
// post: this class object gets assigned a copy of the parameter class object
const DblStack& DblStack::operator= (const DblStack& rhs)
{
    if (this != &rhs)
    {
        if (rhs.isEmpty())
        {
            myTop = 0;
        }
        else
        {
            DblStack tmp(rhs);  // Call copy constructor
            std::swap(myTop, tmp.myTop);
        }
    }
    return *this;
}


// isEmpty
// Checks if the stack is empty
// pre:  A stack exists.
// post: Returns true if it IS empty, false if NOT empty.
bool DblStack::isEmpty() const
{
    return (myTop == 0);
}


// push
// Pushes an item on top of the stack.
// pre:  Stack exists and item is passed.
// post: the item is placed on top of the stack, and size is incremented.
void DblStack::push(const ItemType& item)
{
    myTop = new DblStack::Node(item, myTop);
    mySize++;
}


// pop
// Pops the top item off the stack.
// pre:  Stack exists.
// post: Removes item on top of stack.  If the stack
//       was already empty, throws a std::underflow_error exception.
void DblStack::pop()
{
    if (!isEmpty())
    {
        DblStack::NodePtr ptr = myTop;
        myTop = myTop->next;
        mySize--;
        delete ptr;
    }
    else
    {
        throw std::underflow_error("Stack is empty");
    }
}


// top
// Returns the top item of the stack without popping it.
// pre:  Stack exists.
// post: Returns item on top of stack.  If the stack
//       was already empty, throws a std::underflow_error exception.
ItemType DblStack::top() const
{
    if (!isEmpty())
    {
        return myTop->data;
    }
    else
    {
        throw std::underflow_error("Stack is empty");
    }
}


// size
// Returns the number of items on the stack.
// post: Returns size from the private section of class.
size_t DblStack::size() const
{
    return mySize;
}

Additionally, here is the source code for "reverse" which will implement the stack:

#include <iostream>
#include <fstream>
#include <string>
#include <cstdlib>
#include "DblStack.h"
using namespace std;


// open input and output files
// pre: user is prepared to enter file names at the keyboard
// post: files have been opened
void openFiles (ifstream &infile, ofstream &outfile);



int main ()
{

   ifstream infile;
   ofstream outfile;
   openFiles(infile, outfile);

   cout << "Reading the input file..." << endl;

   string firstLine, secondLine;

   getline(infile,firstLine);
   getline(infile,secondLine);   

   DblStack timeStep, soundData;
   double val;
   while (infile >> val)
   {
       timeStep.push(val);
       infile >> val;
       soundData.push(val);
   }


   cout << "There were " << timeStep.size() << " samples in the file." << endl;
   cout << "Creating output file... wait for Done message." << endl;


   outfile << firstLine << endl;
   outfile << secondLine << endl;

   while (!(timeStep.isEmpty() || soundData.isEmpty()))
   {
       outfile << "  " << timeStep.top() << "\t" << soundData.top() << "\n";
       timeStep.pop();
       soundData.pop();
   }

   infile.close();
   outfile.close();

   cout << "Done." << endl;

   char junk;
   cout << "press enter to exit";
   junk = cin.get();
   junk = cin.get();

}


// open input and output files
// pre: user is prepared to enter file names at the keyboard
// post: files have been opened
void openFiles (ifstream &infile, ofstream &outfile)
{

   // open input data file
   string inFileName;
   cout << "Enter the name of the input file: ";
   cin >> inFileName;
   infile.open(inFileName.c_str());
   if (infile.fail()) {
      cout << "Error opening input data file" << endl;
      exit(1);
   }

   // open output data file
   string outFileName;
   cout << "Enter the name of the output file: ";
   cin >> outFileName;
   outfile.open(outFileName.c_str());
   if (outfile.fail()) {
      cout << "Error opening output data file" << endl;
      exit(1);
   }

}
\$\endgroup\$
3
  • \$\begingroup\$ What is a long time processing? for how big data files? what OS and compiler? There are several things that could eat your time but first try watching this speak by Bjarne Stroustrup, especially note the graph. \$\endgroup\$
    – Surt
    Oct 22, 2014 at 21:55
  • 3
    \$\begingroup\$ Curious why you are not using std::stack \$\endgroup\$ Oct 22, 2014 at 23:14
  • \$\begingroup\$ @LokiAstari if I could be, I certainly would. However, the code is part of a class project and the professor has specified that we may not use any classes from the C++ standard template library. \$\endgroup\$
    – Nea
    Oct 23, 2014 at 10:19

2 Answers 2

11
\$\begingroup\$

Bug here:

If rhs.isEmpty() is true then you don't initialize mySize thus you have a random size.

DblStack::DblStack(const DblStack& rhs)
{
    myTop = 0;
    if (!rhs.isEmpty())

Copy and Swap Idiom

Rather than write your own assignment operator. Prefer to use the standard idiom of the language. Since this is mostly a copy of the copy constructor may as well use it rather than re-write the code.

DblStack& operator=(DblStack copy)
{
    copy.swap(*this);
    return *this;
}
void swap(DblStack& other) nothrow
{
    std::swap(myTop,  other.myTop);
    std::swap(mySize, other.mySize);
}

Efficiency

To make sure things are working perfectly you way want to implement the move constructor and the move assignment operator. These will make sure the compiler does the most efficient thing when you use the standard libraries.

nullptr

Use nullptr to represent the empty pointer.

return (myTop == 0);  // 0 should be nullptr

Should always check operations succeed

while (infile >> val)
{
   timeStep.push(val);
   infile >> val;         // You should make sure that works
                          // before you push into `soundData`
   soundData.push(val);
}

// Personally I would write like this:

while(infile >> timeVal >> soundVal)
{
   // Read worked.
   timeStep.push_back(timeVal);
   soundVal.push_back(soundVal);
}
\$\endgroup\$
3
  • \$\begingroup\$ Thanks for your answer, it was extremely helpful and clear. Your suggestion for the copy constructor and move constructor/assignment operator were not things I had though of and are, indeed, much more efficient. Also, I was already slightly concerned about its performance should there not exist a value in one of the stack, but the code you recommended seems to fix that problem. Thank you again for your help. \$\endgroup\$
    – Nea
    Oct 23, 2014 at 10:31
  • \$\begingroup\$ My apologies for the second comment, but I also wanted to verify that the bug you discovered in my copy constructor would be fixed if I assign mySize = 0 above my initialization of Top. On that same note, do I need to then assign mySize to be equal to rhs.mySize should rhs.isEmpty() be false? Further, after becoming aware of this bug, I realized there may be a similar issue in my assignment operator method (assuming I left it as is, rather than changing it as I likely will)...is this the case or will mySize be given when I call the copy constructor? \$\endgroup\$
    – Nea
    Oct 23, 2014 at 10:49
  • \$\begingroup\$ You need to make sure that by the time the copy constructor is complete the member mySize has the correct value (in both situations). You can can get this by copying it from the other object. \$\endgroup\$ Oct 23, 2014 at 13:56
5
\$\begingroup\$

Your main performance issue with this implementation is going to be with data locality.

For each new item pushed onto the stack, there is a small memory allocation involved. A dynamic memory allocation is by itself a fairly expensive operation, but the worst thing is going to be the fact that you will wind up with all these small Node objects scattered through the memory. That will have a terrible CPU cache efficiency.

To optimize your stack, you should implement it as an array and resize it eventually when it reaches full capacity. That would be basically what std::vector does.

A second option would be to implement the stack as an array-of-arrays, that is, a linked list of memory blocks that group several Nodes together. With this approach, you just allocate a new block when the stack is full and append it to the blocks list. This option might be better performant than the previous since it avoids a memory copy, as would be with a vector-like stack. This architecture, AFAIK, is the way std::stack is implemented. It uses an std::deque as the default back end, which should be an array-of-arrays on most library implementations.

But the end question is this: Do you really need to implement a custom stack? If not, use std::stack. I bet you it is going to perform much better than your linked implementation. I don't see any reason from the code you've shown that indicates the stack has to be a linked-list.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.