| home / programming / javascript / gr / column13 / 1 |   [previous] |
|
|
|
A reference in C++ is a kind of pointer variable; it points to (or references) a value in the computer’s memory. A C++ reference can be designed to reference any kind of value, which makes it a powerful tool for passing values inside a program without the burden of copying the value each time. A referenced value may also be modified through the reference, which allows functions to modify the values of arguments passed to them.
JavaScript variables can be thought of as references to objects. Even the simple types like Numbers, Strings and Booleans are modeled as objects with methods such as toString() and valueOf(). These simple types are immutable since there is no way to modify the value once it has been created; the illusion of changing variable values is maintained by creating a new ‘instance’ for each new value (in practice, JavaScript would be actually implemented this way but it's still useful to think in terms of the model).
To support the flexibility of references in the JavaScript STL, I considered two options; introduce a Reference class that would contain each value the calling code produces or provide mutator functions at every level to allow values to be changed. I decided to use the Reference class as it would give programmers the choice on whether to use them or not.
The most popular part of STL and indeed the first thing most people think of in STL is collections. The STL provides a rich assortment of collections with varying properties able to suit most situations. With consistency and standards in mind, STL collections have similar interfaces where methods of different collections do the same thing, in fact, they are identical. For example: the push_back(value) method, which appends a value to the end of the collection is supported on the three unsorted collections vector, deque and list. Any code that uses this function would work equally well with each type of collection, freeing the programmer to choose the container to fit the situation and even interchanging them at runtime.
The STL list is a linked list of values, which has been optimized for fast inserts and deletes both at the ends and anywhere in between, but it's not indexed so searching for items stored within the list will potentially require iterating over all elements in the list. On the other hand, the STL vector is organized as an array and optimized for random access to all its elements. It still offers fast inserts and deletes at the end of the vector but inserting and deleting anywhere else will suffer (since many as N items may need to be moved to make room for the new ones).
All STL collections provide iterators that (as the name suggests) allows for iterating through a range in the collection in some order. Ranges are written using the notation [first,last) which means starting with the element 'first' and include all elements up to but not including 'last.' This convention mirrors the standard for() loop in C++ and JavaScript where the starting value and one more than the last value are specified.
// a for() loop from zero, up to but not
including ten: [0,10)
for ( i = 0; i < 10; i++ )The STL containers implement the begin() method for the first element in the collection and end() for the upper bound. A for() loop can now be written that iterates through all elements in an STL collection:
// iterate through all elements in myList
from begin(), up to but
// not including end()
for ( i = myList.begin();
!i.equal_to(myList.end()); i.increment() )At the head of the code is a class
called "STD" that provides access to the JavaScript STL features.
// simulate the std namespace
function STD()
{
}
STD.prototype.list = function()
{
return new STDList();
}
STD.prototype.vector = function()
{
return new STDVector();
}
An instance of this class is created and named "std", which offers a runtime equivalent of the C++ namespace "std".
var std = new STD();
The features and functionality of the JavaScript STL code can be accessed as members attached to this instance. For example:
// create a new list
var myList = std.list();
// create a new vector
var myVector = std.vector();Passing functions as arguments is a fundamental aspect of the STL. It makes sorting possible where the ordering is not obvious or could be arbitrary. The STL has gone one step further and built a specialized object often called a function object or “functor” for short. A functor is quite simply an object that has a function. I have included the following generic functors in the STD definition:
STD.prototype.equal_to =
{
fn:function(a,b)
{
return a == b;
}
};
STD.prototype.greater =
{
fn:function(a,b)
{
return a > b;
}
};
STD.prototype.greater_equal =
{
fn:function(a,b)
{
return a >= b;
}
};
STD.prototype.less =
{
fn:function(a,b)
{
return a < b;
}
};
STD.prototype.less_equal =
{
fn:function(a,b)
{
return a <= b;
}
};The functors defined above are commonly used throughout the STL. To keep these functors as simple as possible, they all operate on two inputs and return a boolean value. This helps simplify other parts of the STL framework and can also improve performance. Many of the methods and algorithms in STL (e.g. sort) depend on using functors like these ones.
One big advantage of passing an object in place of a function pointer is that other information that may be relevant to the function can be bundled along with it. For example, say it was necessary to order a list of numbers according to how close they are to a given target and the target is not known until the program is run.
// ProximityFunctor: ranks values according
to how close
// they are to some arbitrary target
function ProximityFunctor(target)
{
this.target = target;
}
ProximityFunctor.prototype.fn =
function(a,b)
{
return Math.abs(a-this.target) <
Math.abs(b-this.target);
}The STDReference class allows values inside a collection to be modified without requiring internal knowledge of the collection:
STD.prototype.ref = function(value)
{
return new STDReference(value);
}
//===========================================================
// STDReference
// - A reference to some value
// when it is necessary to modify the values
contained inside
// a collection use this object
function STDReference(value)
{
this.value = value;
}Next week we'll look at The List Collection, The Vector Collection and The Deque Collection. Part two will also feature a download of the code. After part two, future installments will introduce more collections from the STL repertoire and delve deeper into how iterators can do more than just iterate.
Guyon Roche is a freelance web developer in
| home / programming / javascript / gr / column13 / 1 | [previous] |
Legal Notices, Licensing, Reprints, Permissions, Privacy Policy.
Advertise | Newsletters | Shopping | E-mail Offers | Freelance Jobs 
Created: March 27, 2003
Revised: August 22, 2005
URL: http://webreference.com/programming/javascript/gr/column13/1
