📄 page82.html
字号:
<HTML>
<HEAD>
<TITLE>Array Constructor</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="tex2html2917" HREF="page83.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page83.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="tex2html2915" HREF="page80.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page80.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="tex2html2909" HREF="page81.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page81.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="tex2html2919" 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="tex2html2920" 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="SECTION005120000000000000000">Array Constructor</A></H2>
<A NAME="secfdsarraycons"> </A>
In this section we consider the <tt>Array<T></tt> class constructor
which takes two numeric arguments of type <tt>unsigned int</tt>.
The definition of this constructor is given in Program <A HREF="page82.html#progarray2c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page82.html#progarray2c"><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>.
Given argument values <I>m</I> and <I>n</I>, the constructor first allocates
an array of <I>n</I> elements of type <tt>T</tt> using <tt>operator new</tt>,
and then sets the <tt>length</tt> field to <I>n</I>
and the <tt>base</tt> field to <I>m</I>.
The running time is a constant plus the time do the array allocation.
<P>
<P><A NAME="2869"> </A><A NAME="progarray2c"> </A> <IMG WIDTH=575 HEIGHT=123 ALIGN=BOTTOM ALT="program2682" SRC="img592.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img592.gif" ><BR>
<STRONG>Program:</STRONG> <tt>Array<T></tt> Class Constructor Definition<BR>
<P>
<P>
In C++, when an array is allocated, two things happen.
First, memory is allocated for the array from the free store<A NAME=2690> </A>,
known as the <em>heap</em><A NAME=2692> </A>.
Second, each element of the array is initialized
by calling its default constructor.
<P>
For now, we shall assume that the first step in the dynamic allocation--the allocation of space in the heap--takes a constant amount of time.
In fact, when we look at how the heap is implemented
we will see that this assumption is does not always hold
(see Chapter <A HREF="page416.html#chapheap" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page416.html#chapheap"><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>).
Suppose that the running time of the default constructor for
objects of type <tt>T</tt> is given by <IMG WIDTH=60 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline60949" SRC="img593.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img593.gif" >.
Then, the time to initialize an array
of size <I>n</I> is <IMG WIDTH=176 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline60953" SRC="img594.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img594.gif" >.
<P>
There is a special case to consider:
The behavior of the default constructor
for the C++ built-in types
(<tt>int</tt>, <tt>char</tt>, ..., and pointers thereto)
is to do nothing!
So, if <tt>T</tt> is a built-in type, <IMG WIDTH=89 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline60955" SRC="img595.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img595.gif" >.
In this case, the running time for the <tt>Array<T></tt> constructor
is simply <I>T</I>(<I>n</I>)=<I>O</I>(1),
regardless of the value <I>n</I>.
<P>
<HR><A NAME="tex2html2917" HREF="page83.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page83.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="tex2html2915" HREF="page80.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page80.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="tex2html2909" HREF="page81.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page81.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="tex2html2919" 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="tex2html2920" 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 + -