Velocity Reviews > Iterating sparse arrays

# Iterating sparse arrays

Christopher Benson-Manica
Guest
Posts: n/a

 01-18-2005
If an array is sparse, say something like

var foo=[];
foo[3]=4;
foo['bar']='baz';
foo['quux']='moo';

is there a way to iterate through the entire array?

--
Christopher Benson-Manica | I *should* know what I'm talking about - if I
ataru(at)cyberspace.org | don't, I need to know. Flames welcome.

Richard Cornford
Guest
Posts: n/a

 01-18-2005
Christopher Benson-Manica wrote:
> If an array is sparse, say something like
>
> var foo=[];
> foo[3]=4;
> foo['bar']='baz';
> foo['quux']='moo';
>
> is there a way to iterate through the entire array?

<snip>

for (var c = foo.length; c--; ){
... // using foo[c]
}

The values at indexes 0 to 2 will return Undefined values. The named
properties are not related to the Arrayness of the Array object but
rather to its Objectness. As such they should not be considered relevant
to a desire to iterate through the "entire array".

Richard.

Douglas Crockford
Guest
Posts: n/a

 01-18-2005
> If an array is sparse, say something like
>
> var foo=[];
> foo[3]=4;
> foo['bar']='baz';
> foo['quux']='moo';
>
> is there a way to iterate through the entire array?

It is incorrect to use an array when the keys are non-integers. If you
have keys like 'bar' and 'quux', you should be using an object. You can
then use the for..in statement to iterate through them.

var foo = {};
foo[3] = 4;
foo.bar = 'baz';
foo['quux'] = 'moo';

for (key in foo) {
...
}

See http://www.crockford.com/javascript/survey.html

Robert
Guest
Posts: n/a

 01-19-2005
In article <csjvpb\$6of\$(E-Mail Removed)>,
Christopher Benson-Manica <(E-Mail Removed)> wrote:

> If an array is sparse, say something like
>
> var foo=[];
> foo[3]=4;
> foo['bar']='baz';
> foo['quux']='moo';
>
> is there a way to iterate through the entire array?

Yes.

Note: The length property includes the numeric indexes. Since three is
the highest index, the length property has a value of four.

Robert

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
"http://www.w3.org/TR/html4/loose.dtd">
<html>
<title>Sparse array</title>

<script type="text/javascript">

var foo=[];
foo[3]=4;
foo['bar']='baz';
foo['quux']='moo';

var accumulate = "";

for (var i in foo)
{
accumulate += "foo["+ i + "] = " + foo[i] + "; ";
}

alert("number of elements in foo = " + foo.length);
</script>
<body>
<p>Demonstrate retrieving all set array values.</p>
</body>

Robert
Guest
Posts: n/a

 01-19-2005
In article <d9b27\$41ed9bce\$436562c0\$(E-Mail Removed) s.com>,
Douglas Crockford <(E-Mail Removed)> wrote:

> > If an array is sparse, say something like
> >
> > var foo=[];
> > foo[3]=4;
> > foo['bar']='baz';
> > foo['quux']='moo';
> >
> > is there a way to iterate through the entire array?

>
> It is incorrect to use an array when the keys are non-integers.

I think this is too strong of a statement since the array declaration
supports string values as references. See my post to this thread for
the example code.

When you declare an object an array your javascript supports methods
like pop and the length property with the array object. When you
declare a variable an object you get fewer methods and properties. The
author of the javascript code should decide what is more appropriate.

I do not think we can tell from the segment of code shown what is more
appropriate.

The object declaration does allow for a more compact declaration:

var foo= { 3: 4, bar: "baz", "quux": "moo" };

Robert

Douglas Crockford
Guest
Posts: n/a

 01-19-2005
>>It is incorrect to use an array when the keys are non-integers.

> I think this is too strong of a statement since the array declaration
> supports string values as references.

Wrong is wrong even if you do not understand the difference.

Robert
Guest
Posts: n/a

 01-19-2005
In article <MsxHd.673\$(E-Mail Removed)>,
David Given <(E-Mail Removed)> wrote:

> With better designed programming languages, associative arrays distinguish
> between methods and data, so you can have a key "push" which doesn't
> conflict with the method push(). Alas, Javascript doesn't seem to have this
> concept, which is a shame.

This is unfortunate. Seems like 'informal' languages win out in market
share over 'formal' one.

> It's usually considered good practice (in other languages with similar
> semantics to Javascript) that associative arrays are used for storing

People freak out over the term 'associative arrays' in this forum.
'cause it's not in the standard they stay.

> stupid data and objects are used for storing smart data; that is, it's
> intended that the data gets modified by calling methods on the object.

Robert

Christopher Benson-Manica
Guest
Posts: n/a

 01-19-2005
Douglas Crockford <(E-Mail Removed)> spoke thus:

> It is incorrect to use an array when the keys are non-integers. If you
> have keys like 'bar' and 'quux', you should be using an object. You can
> then use the for..in statement to iterate through them.

> var foo = {};
> foo[3] = 4;
> foo.bar = 'baz';
> foo['quux'] = 'moo';

> for (key in foo) {
> ...
> }

That is a beautiful thing - thank you for showing me the light!

--
Christopher Benson-Manica | I *should* know what I'm talking about - if I
ataru(at)cyberspace.org | don't, I need to know. Flames welcome.

Michael Winter
Guest
Posts: n/a

 01-20-2005
On Thu, 20 Jan 2005 15:06:45 GMT, David Given <(E-Mail Removed)> wrote:

> In fact...
>
> for (i in a) alert(i.value)
>
> ...produces 'undefined',

It should in every case. The value assigned to i on each iteration is the
property name as a string, and strings don't have a value property. If you
want the value of the enumerated property, use

a[i]

> Using an object instead of an array for 'a' does the same thing.

Again, it should. This whole business has nothing to do with arrays. See
my other post (and the link therein).

> I'm going to need a real associative array;

There are several in the archives. Mine is at
<URL:http://www.mlwinter.pwp.blueyonder.co.uk/clj/hash.js> (14.4KB). This
particular implementation allows objects to be true keys (rather than only
their toString value). However, it's also more readable than efficient (or
small). If you do end up using it, at the very least I'd advise you to
make a copy, remove methods that you aren't using (including the Iterator,
if appropriate) and run it through JSMin
(<URL:http://www.crockford.com/javascript/jsmin.html>). That'll take out
you could also shorten the variable names - that'll shave off another
kilobyte or so.

I'm terrible at formal testing procedures, so the script hasn't undergone
any, but playing with it hasn't uncovered any errors (unlike the last time

Mike

[1] My apologies for asking for a check of a blatently non-functioning
script.

--
Michael Winter
Replace ".invalid" with ".uk" to reply by e-mail.

Michael Winter
Guest
Posts: n/a

 01-20-2005
On Thu, 20 Jan 2005 16:48:20 GMT, David Given <(E-Mail Removed)> wrote:

> [...] looking at the code, you seem to be using toString() as your hash
> function.

could force client code to implement a hashCode method like Java, but that
would add (*way*) too much of a burden.

> [...] I'm going to end up with a vast linear list [...]

True, iff all of the objects have the same toString result[1], but I seem
to remember good performance (see the end of

[snip]

> a = {}
> b = {}
> ASSERT(a != b)

Object equality is based on references to the object itself, not its
content. References are only equal if they refer to the same object or a
joined object (algorithm: 11.9.3; joined objects 13.1.2).

> ASSERT(!(a < b))
> ASSERT(!(a > b))

In relational comparisons (11.8.5), the internal ToPrimitive operator
(9.1) is called on both objects with the hint, Number. If a valueOf method
is defined, the return value is used when comparing, otherwise toString is
used (8.6.2.6).

Mike

And here I was thinking I'd take a break from Usenet...

[1] If they're your own objects, you could implement a toString method
that generates a return based on the content of that object.
Alternatively, you could just generate random numbers:

function MyObject() {
var id = String((Math.random() % 1) * 100000);

this.toString = function() {return id;};
}

Although there would be some clashes, it would prevent a single list and

--
Michael Winter
Replace ".invalid" with ".uk" to reply by e-mail.