C and C++ Programming Resources

Custom Search

Generic containers

Stack

The stack, along with the queue and priority_queue, are classified as adapters, which means they adapt one of the basic sequence containers to store their data. This is an unfortunate case of confusing what something does with the details of its underlying implementation?the fact that these are called ?adapters? is of primary value only to the creator of the library. When you use them, you generally don?t care that they?re adapters, but instead that they solve your problem. Admittedly at times it?s useful to know that you can choose an alternate implementation or build an adapter from an existing container object, but that?s generally one level removed from the adapter?s behavior. So, while you may see it emphasized elsewhere that a particular container is an adapter, we?ll only point out that fact when it?s useful. Note that each type of adapter has a default container that it?s built upon, and this default is the most sensible implementation. In most cases you won?t need to concern yourself with the underlying implementation.

The following example shows stack implemented in the three ways: the default (which uses deque), with a vector, and with a list:

// Demonstrates the STL stack
#include <FSTREAM>
#include <IOSTREAM>
#include <LIST>
#include <STACK>
#include <STRING>
#include <VECTOR>
using namespace std;

// Default: deque<STRING>:
typedef stack<STRING> Stack1;
// Use a vector<STRING>:
typedef stack<STRING, vector<string> > Stack2;
// Use a list<STRING>:
typedef stack<STRING, list<string> > Stack3;

int main() {
ifstream in("Stack1.cpp");
Stack1 textlines; // Try the different versions
// Read file and store lines in the stack:
string line;
while(getline(in, line))
textlines.push(line + "\n");
// Print lines from the stack and pop them:
while(!textlines.empty()) {
cout << textlines.top();
textlines.pop();
}
} ///:~

The top( ) and pop( ) operations will probably seem nonintuitive if you?ve used other stack classes. When you call pop( ), it returns void rather than the top element that you might have expected. If you want the top element, you get a reference to it with top( ). It turns out this is more efficient, since a traditional pop( ) would have to return a value rather than a reference and thus invoke the copy-constructor. More important, it is exception safe. If pop( ) both changed the state of the stack and attempted to return the top element, an exception in the element?s copy-constructor could cause the element to be lost. When you?re using a stack (or a priority_queue, described later), you can efficiently refer to top( ) as many times as you want and then discard the top element explicitly using pop( ). (Perhaps if some term other than the familiar ?pop? had been used, this would have been a bit clearer.)

The stack template has a simple interface?essentially the member functions you saw earlier. Since it only makes sense to access a stack at its top, no iterators are available for traversing it. Nor are there sophisticated forms of initialization, but if you need that, you can use the underlying container upon which the stack is implemented. For example, suppose you have a function that expects a stack interface, but in the rest of your program you need the objects stored in a list. The following program stores each line of a file along with the leading number of spaces in that line. (You might imagine it as a starting point for performing some kind of source-code reformatting.)

// Converting a list to a stack
#include <IOSTREAM>
#include <FSTREAM>
#include <STACK>
#include <LIST>
#include <STRING>
using namespace std;

// Expects a stack:
template<CLASS Stk>
void stackOut(Stk& s, ostream& os = cout) {
while(!s.empty()) {
os << s.top() << "\n";
s.pop();
}
}

class Line {
string line; // Without leading spaces
int lspaces; // Number of leading spaces
public:
Line(string s) : line(s) {
lspaces = line.find_first_not_of(' ');
if(lspaces == string::npos)
lspaces = 0;
line = line.substr(lspaces);
}
friend ostream&
operator<<(ostream& os, const Line& l) {
for(int i = 0; i < l.lspaces; i++)
os << ' ';
return os << l.line;
}
// Other functions here...
};

int main() {
ifstream in("Stack2.cpp");
list<LINE> lines;
// Read file and store lines in the list:
string s;
while(getline(in, s))
lines.push_front(s);
// Turn the list into a stack for printing:
stack<LINE, list<Line> > stk(lines);
stackOut(stk);
} ///:~

The function that requires the stack interface just sends each top( ) object to an ostream and then removes it by calling pop( ). The Line class determines the number of leading spaces and then stores the contents of the line without the leading spaces. The ostream operator<< re-inserts the leading spaces so the line prints properly, but you can easily change the number of spaces by changing the value of lspaces. (The member functions to do this are not shown here.)

In main( ), the input file is read into a list <LINE>, and then each line in the list is copied into a stack that is sent to stackOut( ).

You cannot iterate through a stack; this emphasizes that you only want to perform stack operations when you create a stack. You can get equivalent ?stack? functionality using a vector and its back( ), push_back( ), and pop_back( ) member functions, and then you have all the additional functionality of the vector. Stack1.cpp can be rewritten to show this:

// Using a vector as a stack; modified Stack1.cpp
#include
#include
#include
#include
using namespace std;

int main() {
ifstream in("Stack3.cpp");
vector textlines;
string line;
while(getline(in, line))
textlines.push_back(line + "\n");
while(!textlines.empty()) {
cout << textlines.back();
textlines.pop_back();
}
} ///:~

This produces the same output as Stack1.cpp, but you can now perform vector operations as well. Of course, list can also push things at the front, but it?s generally less efficient than using push_back( ) with vector. (In addition, deque is usually more efficient than list for pushing things at the front.)

Pages: [Page - 1] [Page - 2] [Page - 3] [Page - 4] [Page - 5] [Page - 6] [Page - 7] [Page - 8] [Page - 9] [Page - 10] [Page - 11] [Page - 12] [Page - 13]

Tags: , ,

There are 1 Comment to this post. You can follow any responses to this entry through the RSS 2.0 feed. You can skip to the end and leave a response or TrackBack from your own site.

  • Jimson says:

    Sorry to disappoint you, but this is actually bull. STL containers are not meant to be used as base classes. There are no virtual functions to overwrite, so you can’t alter the functionality. Data members are private, so no luck there either – these two points are make container inheritance questionable, but the fact that no virtual destructor is offered makes it just plain wrong. Deleting a derived class via a pointer to the container base class will result in undefined behaviour.

    If you want to add data members, just use composition. If you want to add functionality, write a new algorithm, but don’t inherit from STL containers.

    You might want to look this issue up, the internet is actually full of advice on this, as many novice STL users make this mistake…


Leave a Reply

You must be logged in to post a comment.