📄 4limit.html
字号:
<HTML>
<HEAD>
<TITLE>Removing Limitations</TITLE>
<meta name="description" content="Removing built-in limits from a program">
<meta name="keywords" content="dynamic, array, overload, operator, string, template">
<link rel="stylesheet" href="../rs.css">
</HEAD>
<BODY background="../images/margin.gif" bgcolor="#ffffe0">
<!---- Main Table ---->
<table cellpadding="6">
<tr>
<td width="78"> </td>
<td>
<h3>Code Review 4: Removing Limitations</h3>
<p class=topics>Dynamic arrays, overloading of the array access operator, separating string table
</td></tr>
<tr>
<td class=margin valign=top>
<a href="source/calc3.zip">
<img src="../images/brace.gif" width=16 height=16 border=1 alt="Download!"><br>source</a>
</td>
<td>
<P>Don't you just hate it when you're trying to save a few hours' worth of editing and suddenly you get a message box saying "Cannot save: Too many windows open." or some such nonsense? What is it? Unfortunately, it's a common occurrence--somebody who considers himself or herself a programmer hardcoded a fixed size array to store some important program resources. Then somebody found a problem during testing. The limitation probably caused a fault when the bounds were first overwritten. A bug appeared in the database, "The program GP-faulted when user tried to save a big document." Then another genius fixed it by adding a boundary test and putting up the message box. At least that's how I imagine it happening. As you can see, I don't think highly of code that has unreasonable limitations built-in. And with templates it's so easy to remove the unnecessary limits!
<P>Let's first look around to see where in our program we managed to impose unreasonable limitations due to our ignorance of templates. There's one we have just created in <var>MultiNode</var> by arbitrarily limiting the number of children to 8. The whole symbol table is infested with limitations: the buffer for string is limited, the array of offsets is finite. Finally, the storage of variable values has an arbitrary limit imposed on it.
<P>You might ask, "What's the likelihood of user hitting one of the limitations? Is it worth going into all this trouble in order to deal with such unlikely cases?" The answer is:
<!---- Definition ---->
<p>
<table border=4 cellpadding=10><tr>
<td bgcolor="#ffffff" class=defTable>
It is less trouble to use dynamic arrays than it is to deal with limitations. </td></tr>
</table>
<!---- End Definition ---->
<P>Just think of all the error messages you'll have to display, the propagation of these errors (by the way, we'll deal with this topic separately later), the localization of message strings. Believe me, you don't want to do it.
<h3>Dynamic Array</h3>
<P>Almost all cases of artificial limits can be solved by just one template--the dynamic array. Let's go together through its design and implementation. In the process you'll not only learn more about templates and operator overloading, but you'll also prepare yourself for the general-purpose dynamic <var>vector</var> from the Standard Library.
<p>Let's first try to come up with a set of requirements for this data structure. As much as possible we would like the dynamic array to look just like an array. That means we would like to access its elements by indexing, both to read and to write. Adding new elements is a bit more tricky. For performance reasons, we don't want the array to check for bounds on every access (except in the debugging version) to see if it's necessary to extend the array. Second, we never actually need to add new elements at an arbitrary offset. In all our applications we keep adding elements to the end of the array. It would be tempting to just keep track of the last added element and have method <var>Push</var> to add and extend the array. Instead I decided to be a little more general and have a method <var>Add</var> that can add a new element at an arbitrary offset. That's because I want to be able to use pairs of synchronized arrays that share the same insertion index--we'll see an example in a moment.
<P>One more thing: in many cases it makes sense to pre-fill the array with some default values. For instance, an array of pointers could be pre-filled with null pointers, integers could be preset to zero or minus one, enumerated types to some default value, etc. We'll store this default value in the dynamic array, so that we could use it to pre-fill the new pieces of the array when we grow it.
<!---- Code ---->
<table width="100%" cellspacing=10><tr>
<td class=codeTable>
<pre>template <class T>
class DynArray
{
enum { initDynArray = 8 };
public:
explicit DynArray (T const valDefault);
~DynArray ();
void Add (int i, T const val);
T operator [] (int i) const;
T & operator [] (int i);
int InRange (int i) const { return i < _capacity; }
private:
void Grow (int i);
T * _arr;
int _capacity; // size of the array
T const _valDefault;
};</pre>
</td></tr>
</table>
<!---- End Code ---->
<P>The line
<!-- Code -->
<table width="100%" cellspacing=10><tr>
<td class=codeTable>
<pre>T operator [] (int i) const;</pre>
</td></tr>
</table>
<!-- End Code -->
<P>is another example of operator overloading. Here we are overloading the array access operator [] (square brackets) in order to be able to access dynamic arrays just like regular arrays.
<p>Here's how we can define a dynamic array of integers, add a value to it using <var>Add</var>, and retrieve it using array access.
<!-- Code -->
<table width="100%" cellspacing=10><tr>
<td class=codeTable>
<pre>DynArray<int> a (0); // dynamic array with 0 default value
a.Add (3, 10); // add entry with value 10 at offset 3
int i = a [3]; // access it like a regular array</pre>
</td></tr>
</table>
<!-- End Code -->
<P>The compiler will translate the last line into the call to operator [], just like this:
<!-- Code -->
<table width="100%" cellspacing=10><tr>
<td class=codeTable>
<pre>int i = a.operator [] (3);</pre>
</td></tr>
</table>
<!-- End Code -->
<P>which, by the way, is also correct alternative syntax.
<P>Notice that we have another overloading of the same operator in the same class:
<!-- Code -->
<table width="100%" cellspacing=10><tr>
<td class=codeTable>
<pre>T & operator [] (int i);</pre>
</td></tr>
</table>
<!-- End Code -->
<P>How can this be done? It's the same operator, takes the same arguments, but it returns <var>T</var> by reference, not by value. Is it enough for the compiler to decide between these two when is sees, for instance, <var>a[3]</var>? The answer is, no--two overloads that only differ by return type are not allowed. What really makes a difference here is the word <var>const</var>. One method is constant and the other is not. When acting on a <var>const</var> object, the compiler will pick the <var>const</var> method, otherwise it will use the non-const one.
<P>The non-const, reference-returning version of the operator allows us to use the result of array indexing as an lvalue. The following statement "does the right thing"
<!-- Code -->
<table width="100%" cellspacing=10><tr>
<td class=codeTable>
<pre>a [3] = 11;</pre>
</td></tr>
</table>
<!-- End Code -->
<P>Compare it with the more verbose version:
<!-- Code -->
<table width="100%" cellspacing=10><tr>
<td class=codeTable>
<pre>int & r = a.operator [] (3); // reference to the third element of 'a'
r = 11; // change value through a reference</pre>
</td></tr>
</table>
<!-- End Code -->
<P>In the above example, if <var>a</var> were defined to be <var>const</var>, the compiler would flag it as an error. And rightly so! You are not supposed to change the value of a <var>const</var> object. That, by the way, shows you why I had to define two versions of this method.
<P>If I only had the non-const version, I wouldn't be able to use it on const objects or in const methods of <var>DynArray</var>. In fact our program wouldn't compile for exactly that reason.
<P>If I only had the const version, I wouldn't be able to modify the elements of the array using indexing--I couldn't use them as lvalues.
<P>There is a third possibility: I could say that by returning a reference I am not really changing the state of the object. Let's try this
<!-- Code -->
<table width="100%" cellspacing=10><tr>
<td class=codeTable>
<pre>T & operator [] (int i) const // <-- const method?!
{
return _arr[i]; // <-- ERROR!
}</pre>
</td></tr>
</table>
<!-- End Code -->
<P>Oops! It didn't work! It's really getting harder and harder to shoot yourself in the foot, doesn't it?
<P>Let me try to explain why the compiler wouldn't let us compile the above code. It's because of the <var>this</var> pointer. The <var>this</var> pointer is the pointer to the object upon which a given method was invoked. You can use <var>this</var> explicitly; or implicitly, by accessing the members of the object. The above code, for instance, is equivalent to
<!-- Code -->
<table width="100%" cellspacing=10><tr>
<td class=codeTable>
<pre>T & operator [] (int i) const
{
return this->_arr[i]; // <- ERROR!
}</pre>
</td></tr>
</table>
<!-- End Code -->
<P>The type of the <var>this</var> pointer depends on the class of the object. It also depends on whether the method is <var>const</var> or not. Inside a non-const method of, say, class <var>Foo</var> , <var>this</var> acts as if it were declared as
<!-- Code -->
<table width="100%" cellspacing=10><tr>
<td class=codeTable>
<pre>Foo * const this;</pre>
</td></tr>
</table>
<!-- End Code -->
whereas, in a const method, <var>this</var> becomes
<!-- Code -->
<table width="100%" cellspacing=10><tr>
<td class=codeTable>
<pre>Foo const * const this;</pre>
</td></tr>
</table>
<!-- End Code -->
<P>Therefore, inside a const method, the expression <var>this-->_arr[i]</var> produces a const integer, because it dereferences a pointer to const. The compiler catches us red-handed trying to create a "reference to non-const" (the return type) from a const integer. It's as bad as
<!-- Code -->
<table width="100%" cellspacing=10><tr>
<td class=codeTable>
<pre>const double speedOfLight = 300000.0; // km/s
double & mySpeed = speedOfLight; // <-- ERROR! Won't compile!
// now let me slow down
mySpeed = 0.0; // Oops! Changed the speed of light!</pre>
</td></tr>
</table>
<!-- End Code -->
<P>The bottom line is: If you want to have a method that can be used as an lvalue, because it returns a reference to the object's data, such method cannot be const. If you also want to overload the same method (that is have another method with the same name and argument types) to provide read-only access, you can do it by making the second method const. Its return type must be different, though. It could be a reference-to-const; or just the type of the value itself, if we want to return the data by value.
<P>Although this technique is mostly used in the context of operator overloading, it can be used with any other kind of overloading. In principle, one could have
<!-- Code -->
<table width="100%" cellspacing=10><tr>
<td class=codeTable>
<pre>class Foo
{
public:
Foo (double x) :_x(x) {}
double & Get () { return _x; }
double Get () const { return _x; }
// Another possibility:
// double const & Get () const { return _x; }
private:
double _x;
};</pre>
</td></tr>
</table>
<!-- End Code -->
and use <var>Get</var> both as an lvalue and an rvalue (right-hand-side value), as in
<!-- Code -->
<table width="100%" cellspacing=10><tr>
<td class=codeTable>
<pre>Foo varFoo (1.1);
const Foo constFoo (3.14);
varFoo.Get () = varFoo.Get () + 2.0 * constFoo.Get ();</pre>
</td></tr>
</table>
<!-- End Code -->
<P>I'm not saying that I recommend this kind of programming. A much better solution would be to provide a separate method <var>Set</var> and avoid overloading whatsoever.
<p>In any case, it should be obvious that it is very important to be consistent--the two overloads should give access to the same piece of data.
<P>The implementation of the dynamic array is pretty straightforward. Here's the constructor and the destructor.
<!-- Code -->
<table width="100%" cellspacing=10><tr>
<td class=codeTable>
<pre>template <class T>
DynArray <T>::DynArray (T const valDefault)
: _capacity (initDynArray), _valDefault (valDefault)
{
_arr = new T [initDynArray]; // allocate memory
for (int i = 0; i < initDynArray; ++i)
_arr[i] = _valDefault;
}
template <class T>
DynArray <T>::~DynArray ()
{
delete []_arr;
}</pre>
</td></tr>
</table>
<!-- End Code -->
<P>Method <var>Add</var> has the potential of extending the array.
<!---- Code ---->
<table width="100%" cellspacing=10><tr>
<td class=codeTable>
<pre>template <class T>
void DynArray <T>::Add (int i, T const val)
{
if ( i >= _capacity )
Grow(i);
_arr [i] = val;
}</pre>
</td></tr>
</table>
<!---- End Code ---->
<P>Here are the two versions of the array access operator. Notice that none of them can be used to extend the array--the assertions are there to make sure that nobody even tries.
<!-- Code -->
<table width="100%" cellspacing=10><tr>
<td class=codeTable>
<pre>template <class T>
inline T DynArray<T>::operator [] (int i) const
{
assert (i < _capacity);
return _arr[i];
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -