?? page389.html
字號:
<HTML>
<HEAD>
<TITLE>Implementing Sets</TITLE>
</HEAD>
<BODY bgcolor="#FFFFFF">
<img src="cover75.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cover75.gif" alt="Logo" align=right>
<b>Data Structures and Algorithms
with Object-Oriented Design Patterns in C++</b><br>
<A NAME="tex2html6735" HREF="page390.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page390.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html6733" HREF="page388.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page388.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html6729" HREF="page388.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page388.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html6737" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html6738" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <BR><HR>
<H2><A NAME="SECTION0013110000000000000000">Implementing Sets</A></H2>
<A NAME="secsetssets"> </A>
<P>
<P><A NAME="28187"> </A><A NAME="figclasses8"> </A> <IMG WIDTH=575 HEIGHT=183 ALIGN=BOTTOM ALT="figure28183" SRC="img1602.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1602.gif" ><BR>
<STRONG>Figure:</STRONG> Object Class Hierarchy<BR>
<P>
<P>
As discussed above,
this chapter addresses the implementation of sets of integers.
A set is a collection of elements.
Naturally, we want to insert and withdraw objects from the collection
and to test whether a given object is a member of the collection.
Therefore, we consider sets as being derived
from the <tt>SearchableContainer</tt> class defined in Chapter <A HREF="page107.html#chapadts" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page107.html#chapadts"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>.
<P>
In general, a searchable container can hold arbitrary objects.
However, in this chapter we will assume that the elements
of a set are integers.
Furthermore, all the searchable container implementations
which we have seen so far have been based on two assumptions.
These are that the container <em>owns</em> the objects it contains
and that indirect storage is used,
i.e., a pointer to the contained object is actually held by the container.
Since we deal with integers and not with arbitrary objects,
the set implementations in this chapter invalidate both these assumptions.
<P>
Program <A HREF="page389.html#progset1h" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page389.html#progset1h"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> defines the abstract class <tt>Set</tt>.
The <tt>Set</tt> class is derived from <tt>SearchableContainer</tt>
which is defined in Section <A HREF="page117.html#secadtscontainers" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page117.html#secadtscontainers"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>.
The definition does not declare any new member functions--the interface inherited from the base class is sufficient.
In addition,
a new type called <tt>Set::Element</tt> is defined.
<P>
<P><A NAME="28720"> </A><A NAME="progset1h"> </A> <IMG WIDTH=575 HEIGHT=200 ALIGN=BOTTOM ALT="program28199" SRC="img1603.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1603.gif" ><BR>
<STRONG>Program:</STRONG> <tt>Set</tt> Class Definition<BR>
<P>
<P>
The items <em>contained</em> in a set are unsigned integers.
However, the member functions of the base class interface such
as <tt>Insert</tt>, <tt>IsMember</tt>, and <tt>Withdraw</tt>,
expect their arguments to be derived from the class <tt>Object</tt>.
Therefore, the <tt>Wrapper</tt> template (defined in Section <A HREF="page115.html#secadtswrappers" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page115.html#secadtswrappers"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>)
is used to define the type <tt>Set::Element</tt> as the encapsulation of
an <tt>unsigned int</tt>.
We assume that the only <tt>Object</tt> instances
which are passed to a set are instances of the class <tt>Set::Element</tt>.
<P>
The default constructor for the <tt>Set</tt> class
is also given in Program <A HREF="page389.html#progset1h" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page389.html#progset1h"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>.
It takes a single argument, <IMG WIDTH=136 HEIGHT=11 ALIGN=BOTTOM ALT="tex2html_wrap_inline67266" SRC="img1604.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1604.gif" >,
which specifies that the universal set shall be <IMG WIDTH=115 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67264" SRC="img1601.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1601.gif" >.
<P>
<HR><A NAME="tex2html6735" HREF="page390.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page390.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html6733" HREF="page388.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page388.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html6729" HREF="page388.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page388.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html6737" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html6738" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <P><ADDRESS>
<img src="bruno.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/bruno.gif" alt="Bruno" align=right>
<a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html">Copyright © 1997</a> by <a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.
</ADDRESS>
</BODY>
</HTML>
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -