ch28.htm

linux-unix130.linux.and.unix.ebooks130 linux and unix ebookslinuxLearning Linux - Collection of 12 E

</P>

</CENTER>

<P>Plexes are a very useful class on which many of the other classes in the GNU C++

class library are based. Some of the Stack, Queue, and Linked list types are built

on top of the Plex class.

<CENTER>

<H4><A NAME="Heading22<FONT COLOR="#000077">Stacks</FONT></H4>

</CENTER>

<P>The Stack class implements the standard version of a last-in-first-out (LIFO)

stack. Three different implementations of stacks are offered by the GNU C++ class

library: the <TT>VStack</TT>, the <TT>XPStack</TT>, and the <TT>SLStack</TT>. The

<TT>VStack</TT> is a fixed-size stack, meaning that you must specify an upper bound

on the size of the stack when you first create it. The <TT>XPStack</TT> and the <TT>SLStack</TT>

are both dynamically sized stacks that are implemented in a slightly different way.</P>

<P>Table 28.8 lists the operations that can be performed on the Stack classes. </P>

<CENTER>

<P><FONT SIZE="4"><B>Table 28.8.</B> Stack class operators. </FONT>

<TABLE BORDER="0">

	<TR ALIGN="LEFT" rowspan="1">

		<TD WIDTH="88" ALIGN="LEFT"><I>Operator</I></TD>

		<TD ALIGN="LEFT"><I>Description</I></TD>

	</TR>

	<TR ALIGN="LEFT" rowspan="1">

		<TD WIDTH="88" ALIGN="LEFT"><TT>Stack st</TT></TD>

		<TD ALIGN="LEFT">Declares <TT>st</TT> to be a stack</TD>

	</TR>

	<TR ALIGN="LEFT" rowspan="1">

		<TD WIDTH="88" ALIGN="LEFT"><TT>Stack st(sz)</TT></TD>

		<TD ALIGN="LEFT">Declares <TT>st</TT> to be a stack of size <TT>sz</TT></TD>

	</TR>

	<TR ALIGN="LEFT" rowspan="1">

		<TD WIDTH="88" ALIGN="LEFT"><TT>st.empty()</TT></TD>

		<TD ALIGN="LEFT">Returns <TT>TRUE</TT> if <TT>stack</TT> is empty</TD>

	</TR>

	<TR ALIGN="LEFT" rowspan="1">

		<TD WIDTH="88" ALIGN="LEFT"><TT>st.full()</TT></TD>

		<TD ALIGN="LEFT">Returns <TT>TRUE</TT> if <TT>stack</TT> is full</TD>

	</TR>

	<TR ALIGN="LEFT" rowspan="1">

		<TD WIDTH="88" ALIGN="LEFT"><TT>st.length()</TT></TD>

		<TD ALIGN="LEFT">Returns the number of elements in <TT>stack</TT></TD>

	</TR>

	<TR ALIGN="LEFT" rowspan="1">

		<TD WIDTH="88" ALIGN="LEFT"><TT>st.push(</TT>x<TT>)</TT></TD>

		<TD ALIGN="LEFT">Puts element x onto the top of the stack</TD>

	</TR>

	<TR ALIGN="LEFT" rowspan="1">

		<TD WIDTH="88" ALIGN="LEFT">x<TT> = st.pop()</TT></TD>

		<TD ALIGN="LEFT">Removes and returns the top element from the stack</TD>

	</TR>

	<TR ALIGN="LEFT" rowspan="1">

		<TD WIDTH="88" ALIGN="LEFT"><TT>st.top()</TT></TD>

		<TD ALIGN="LEFT">Returns a pointer to the top element in the stack</TD>

	</TR>

	<TR ALIGN="LEFT" rowspan="1">

		<TD WIDTH="88" ALIGN="LEFT"><TT>st.del_top()</TT></TD>

		<TD ALIGN="LEFT">Deletes the top element from the stack without returning it</TD>

	</TR>

	<TR ALIGN="LEFT" rowspan="1">

		<TD WIDTH="88" ALIGN="LEFT"><TT>st.clear()</TT></TD>

		<TD ALIGN="LEFT">Deletes all elements from <TT>stack</TT></TD>

	</TR>

</TABLE>



</CENTER>

<CENTER>

<H4><A NAME="Heading23<FONT COLOR="#000077">Queues</FONT></H4>

</CENTER>

<P>The Queue class implements a standard version of a first-in-first-out (FIFO) queue.

Three different kinds of queue are provided by the GNU C++ class library: the <TT>VQueue</TT>,

the <TT>XPQueue</TT>, and the <TT>SLQueue</TT>. The <TT>VQueue</TT> is a fixed-size

queue, so you must specify an upper bound on the size of this kind of queue when

you first create it. The <TT>XPQueue</TT> and the <TT>SLQueue</TT> are both dynamically

sized queues, so no upper bound is required. The operations supported by the Queue

classes are listed in Table 28.9. </P>

<CENTER>

<P><FONT SIZE="4"><B>Table 28.9.</B> Queue class operators. </FONT>

<TABLE BORDER="0">

	<TR ALIGN="LEFT" rowspan="1">

		<TD ALIGN="LEFT"><I>Operator</I></TD>

		<TD ALIGN="LEFT"><I>Description</I></TD>

	</TR>

	<TR ALIGN="LEFT" rowspan="1">

		<TD ALIGN="LEFT"><TT>Queue q</TT></TD>

		<TD ALIGN="LEFT">Declares <TT>q</TT> to be a queue</TD>

	</TR>

	<TR ALIGN="LEFT" rowspan="1">

		<TD ALIGN="LEFT"><TT>Queue q(</TT>sz<TT>)</TT></TD>

		<TD ALIGN="LEFT">Declares <TT>q</TT> to be a queue of size sz</TD>

	</TR>

	<TR ALIGN="LEFT" rowspan="1">

		<TD ALIGN="LEFT"><TT>q.empty()</TT></TD>

		<TD ALIGN="LEFT">Returns <TT>TRUE</TT> if <TT>q</TT> is empty</TD>

	</TR>

	<TR ALIGN="LEFT" rowspan="1">

		<TD ALIGN="LEFT"><TT>q.full()</TT></TD>

		<TD ALIGN="LEFT">Returns <TT>TRUE</TT> if <TT>q</TT> is full</TD>

	</TR>

	<TR ALIGN="LEFT" rowspan="1">

		<TD ALIGN="LEFT"><TT>q.length()</TT></TD>

		<TD ALIGN="LEFT">Returns the number of elements in <TT>q</TT></TD>

	</TR>

	<TR ALIGN="LEFT" rowspan="1">

		<TD ALIGN="LEFT"><TT>q.enq(</TT>x<TT>)</TT></TD>

		<TD ALIGN="LEFT">Adds the x element to <TT>q</TT></TD>

	</TR>

	<TR ALIGN="LEFT" rowspan="1">

		<TD ALIGN="LEFT">x<TT> = q.deq()</TT></TD>

		<TD ALIGN="LEFT">Removes and returns an element from <TT>q</TT></TD>

	</TR>

	<TR ALIGN="LEFT" rowspan="1">

		<TD ALIGN="LEFT"><TT>q.front()</TT></TD>

		<TD ALIGN="LEFT">Returns a pointer to the front of <TT>q</TT></TD>

	</TR>

	<TR ALIGN="LEFT" rowspan="1">

		<TD ALIGN="LEFT"><TT>q.del_front()</TT></TD>

		<TD ALIGN="LEFT">Removes an element from <TT>q</TT> and does not return the result</TD>

	</TR>

	<TR ALIGN="LEFT" rowspan="1">

		<TD ALIGN="LEFT"><TT>q.clear</TT></TD>

		<TD ALIGN="LEFT">Removes all elements from the queue</TD>

	</TR>

</TABLE>

</P>

</CENTER>

<P>In addition to the normal kind of queue that is discussed in this section, the

GNU C++ class library also supports double-ended queues and priority queues. Both

of these types of queues have similar behavior to the regular queue. The double-ended

queue adds operators for returning a pointer to the rear of the queue and deleting

elements from the rear of the queue. The priority queues are arranged so that a user

has fast access to the least element in the queue. They support additional operators

that allow for searching for elements in the queue.

<CENTER>

<H4><A NAME="Heading24<FONT COLOR="#000077">Sets</FONT></H4>

</CENTER>

<P>The Set class is used to store groups of information. The only restriction on

this information is that no duplicate elements are allowed. The class library supports

several different implementations of sets. All of the implementations support the

same operators. These operators are shown in Table 28.10. </P>

<CENTER>

<P><FONT SIZE="4"><B>Table 28.10.</B> Set operators. </FONT>

<TABLE BORDER="0">

	<TR ALIGN="LEFT" rowspan="1">

		<TD ALIGN="LEFT"><I>Operator</I></TD>

		<TD ALIGN="LEFT"><I>Description</I></TD>

	</TR>

	<TR ALIGN="LEFT" rowspan="1">

		<TD ALIGN="LEFT"><TT>Set s</TT></TD>

		<TD ALIGN="LEFT">Declares a set named <TT>s</TT> that is initially empty</TD>

	</TR>

	<TR ALIGN="LEFT" rowspan="1">

		<TD ALIGN="LEFT"><TT>Set s(sz)</TT></TD>

		<TD ALIGN="LEFT">Declares a set named <TT>s</TT> that is initially empty and has a set maximum size

			of <TT>sz</TT></TD>

	</TR>

	<TR ALIGN="LEFT" rowspan="1">

		<TD ALIGN="LEFT"><TT>s.empty()</TT></TD>

		<TD ALIGN="LEFT">Returns <TT>TRUE</TT> if <TT>s</TT> is empty</TD>

	</TR>

	<TR ALIGN="LEFT" rowspan="1">

		<TD ALIGN="LEFT"><TT>s.length()</TT></TD>

		<TD ALIGN="LEFT">Returns the number of elements in <TT>s</TT></TD>

	</TR>

	<TR ALIGN="LEFT" rowspan="1">

		<TD ALIGN="LEFT"><TT>i = s.add(z)</TT></TD>

		<TD ALIGN="LEFT">Adds <TT>z</TT> to <TT>s</TT>, returning its index value</TD>

	</TR>

	<TR ALIGN="LEFT" rowspan="1">

		<TD ALIGN="LEFT"><TT>s.del(z)</TT></TD>

		<TD ALIGN="LEFT">Deletes <TT>z</TT> from <TT>s</TT></TD>

	</TR>

	<TR ALIGN="LEFT" rowspan="1">

		<TD ALIGN="LEFT"><TT>s.clear()</TT></TD>

		<TD ALIGN="LEFT">Removes all elements from <TT>s</TT></TD>

	</TR>

	<TR ALIGN="LEFT" rowspan="1">

		<TD ALIGN="LEFT"><TT>s.contains(z)</TT></TD>

		<TD ALIGN="LEFT">Returns <TT>TRUE</TT> if <TT>z</TT> is in <TT>s</TT></TD>

	</TR>

	<TR ALIGN="LEFT" rowspan="1">

		<TD ALIGN="LEFT"><TT>s.(i)</TT></TD>

		<TD ALIGN="LEFT">Returns a pointer to the element indexed by <TT>i</TT></TD>

	</TR>

	<TR ALIGN="LEFT" rowspan="1">

		<TD ALIGN="LEFT"><TT>i = a.first()</TT></TD>

		<TD ALIGN="LEFT">Returns the index of the first item in the set</TD>

	</TR>

	<TR ALIGN="LEFT" rowspan="1">

		<TD ALIGN="LEFT"><TT>s.next(i)</TT></TD>

		<TD ALIGN="LEFT">Makes <TT>i</TT> equal to the index of the next element in <TT>s</TT></TD>

	</TR>

	<TR ALIGN="LEFT" rowspan="1">

		<TD ALIGN="LEFT"><TT>i = s.seek(z)</TT></TD>

		<TD ALIGN="LEFT">Sets <TT>i</TT> to the index of <TT>z</TT> if <TT>z</TT> is in <TT>s</TT>, and 0

			otherwise</TD>

	</TR>

	<TR ALIGN="LEFT" rowspan="1">

		<TD ALIGN="LEFT"><TT>set1 == set2</TT></TD>

		<TD ALIGN="LEFT">Returns <TT>TRUE</TT> if <TT>set1</TT> contains all the same elements as <TT>set2</TT></TD>

	</TR>

	<TR ALIGN="LEFT" rowspan="1">

		<TD ALIGN="LEFT"><TT>set1 != set2</TT></TD>

		<TD ALIGN="LEFT">Returns <TT>TRUE</TT> if <TT>set1</TT> does not contain all the same elements as

			<TT>set2</TT></TD>

	</TR>

	<TR ALIGN="LEFT" rowspan="1">

		<TD ALIGN="LEFT"><TT>set1 &lt;= set2</TT></TD>

		<TD ALIGN="LEFT">Returns <TT>TRUE</TT> if <TT>set1</TT> is a subset of <TT>set2</TT></TD>

	</TR>

	<TR ALIGN="LEFT" rowspan="1">

		<TD ALIGN="LEFT"><TT>set1 |= set2</TT></TD>

		<TD ALIGN="LEFT">Adds all elements of <TT>set2</TT> to <TT>set1</TT></TD>

	</TR>

	<TR ALIGN="LEFT" rowspan="1">

		<TD ALIGN="LEFT"><TT>set1 -= set2</TT></TD>

		<TD ALIGN="LEFT">Deletes all the elements that are contained in <TT>set2</TT> from <TT>set1</TT></TD>

	</TR>

	<TR ALIGN="LEFT" rowspan="1">

		<TD ALIGN="LEFT"><TT>set1 &amp;= set2</TT></TD>

		<TD ALIGN="LEFT">Deletes all elements from <TT>set1</TT> that occur in <TT>set1</TT> and not in <TT>set2</TT></TD>

	</TR>

</TABLE>

</P>

</CENTER>

<P>The class library contains another class that is similar to sets. This class is

known as the bag. A bag is a group of elements that can be in any order (just as

is the case with sets) but in which there can also be duplicates. Bags use all the

operators that sets use except for the <TT>==</TT>, <TT>!=</TT>, <TT>|=</TT>, <TT>&lt;=</TT>,

<TT>|=</TT>, <TT>-=</TT>, and <TT>&amp;=</TT> operators. In addition, bags add two

new operators for dealing with elements that are in the bag more than once. These

new operators are shown in Table 28.11. </P>

<CENTER>

<P><FONT SIZE="4"><B>Table 28.11.</B> Additional operators for bags. </FONT>

<TABLE BORDER="0">

	<TR ALIGN="LEFT" rowspan="1">

		<TD ALIGN="LEFT"><I>Operator</I></TD>

		<TD ALIGN="LEFT"><I>Description</I></TD>

	</TR>

	<TR ALIGN="LEFT" rowspan="1">

		<TD ALIGN="LEFT"><TT>b.remove(z)</TT></TD>

		<TD ALIGN="LEFT">Deletes all occurrences of <TT>z</TT> from <TT>b</TT></TD>

	</TR>

	<TR ALIGN="LEFT" rowspan="1">

		<TD ALIGN="LEFT"><TT>b.nof(z)</TT></TD>

		<TD ALIGN="LEFT">Returns the number of occurrences of <TT>z</TT> that are in <TT>b</TT></TD>

	</TR>

</TABLE>

</P>

</CENTER>

<P>Many other classes available in the GNU C++ class library provide functions other

than those listed here. In addition to what comes with the compiler, many other freely

available class libraries can be useful as well.

<CENTER>

<H3><A NAME="Heading25<FONT COLOR="#000077">Summary</FONT></H3>

</CENTER>

<P>C++ offers many advantages over C. Some of these advantages come from the concepts

of object-oriented programming, and others come from the highly flexible class libraries

that are available to C++ programmers. This chapter gave a brief introduction to

object-oriented programming and also talked about the C++ features that exist in

the GNU C compiler and the GNU debugger.</P>



<P>One problem that has existed with C++ for quite some time is the lack of freely

available C++ development tools. You may notice that the number of free tools available

for C++ programming is much smaller than the number available for C, but the tide

is turning. As more and more people choose C++ over C, the number of tools and class

libraries available keeps increasing. The tool support has reached the stage where

learning C++ in the Linux environment is something that you can enjoy rather than

avoid.









</td>
</tr>
</table>
<!-- begin footer information -->


</body></html>