Chapter 7. Arrays and Collections
Topics in This Chapter
7.2 The length Property and Index Properties
Whenever you learn a new programming language, you want to know how to store your data. The traditional data structure of choice for sequential data is the humble array. In this chapter, you will learn the various array methods that the JavaScript API provides. We then turn to typed arrays and array buffers—advanced constructs for efficient handling of binary data blocks. Unlike Java or C++, JavaScript does not provide a rich set of data structures, but there are simple map and set classes that we discuss at the end of the chapter.
7.1 Constructing Arrays
You already know how to construct an array with a given sequence of elements—simply write a literal:
const names = ['Peter', 'Paul', 'Mary']
Here is how to construct an empty array with ten thousand elements, all initially undefined:
const bigEmptyArray = [] bigEmptyArray.length = 10000
In an array literal, you can place spreads of any iterable. Arrays and strings, the sets and maps that you will see later in this chapter, as well as NodeList and HTMLCollection from the DOM API, are iterable. For example, here is how to form an array containing the elements of two iterables a and b:
const elements = [...a, ...b]
As you will see in Chapter 9, an iterable object has a somewhat complex structure. The Array.from method collects elements from a simpler array-like object. An array-like object is an object with an integer-valued property with name 'length' and properties with names '0', '1', '2', and so on. Of course, arrays are array-like, but some methods of the DOM API yield array-like objects that aren’t arrays or iterables. Then you can call Array.from(arrayLike) to place the elements into an array.
const arrayLike = { length: 3 , '0': 'Peter', '1': 'Paul', '2': 'Mary'}
const elements = Array.from(arrayLike)
// elements is the array ['Peter', 'Paul', 'Mary']
// Array.isArray(arrayLike) is false, Array.isArray(elements) is true
The Array.from method accepts an optional second argument, a function that is called for all index values from 0 up to length − 1, passing the element (or undefined for missing elements) and the index. The results of the function are collected into an array. For example,
const squares = Array.from({ length: 5 }, (element, index) => index * index)
// [0, 1, 4, 9, 16]
Caution
There is a constructor for constructing an array with given elements that you can invoke with or without new:
names = new Array('Peter', 'Paul', 'Mary')
names = Array('Peter', 'Paul', 'Mary')
But it has a pitfall. Calling new Array or Array with a single numeric argument has an entirely different effect. The single argument denotes the length of the array:
numbers = new Array(10000)
The result is an array of length 10000 and no elements!
I suggest to stay away from the Array constructor and use array literals:
names = ['Peter', 'Paul', 'Mary'] numbers = [10000]
Note
The factory function Array.of doesn’t suffer from the problem of the Array constructor:
names = Array.of('Peter', 'Paul', 'Mary')
littleArray = Array.of(10000) // An array of length 1, same as [10000]
But it offers no advantage over array literals either. (Exercise 2 shows a subtle and uncommon use case for the of method.)
7.2 The length Property and Index Properties
Every array has a 'length' property whose value is an integer between 0 and 232 − 1. The properties whose numeric values are non-negative integers are called index properties. For example, the array
const names = ['Peter', 'Paul', 'Mary']
is an object with a 'length' property (whose value is 3) and index properties '0', '1', '2'. Recall that property keys are always strings.
The length is always one more than the highest index:
const someNames = [ , 'Smith', , 'Jones'] // someNumbers.length is 4
The length is adjusted when a value is assigned to an index property:
someNames[5] = 'Miller' // Now someNames has length 6
You can adjust the length manually:
someNames.length = 100
If you decrease the length, any element whose index is at least the new length gets deleted.
someNames.length = 4 // someNames[4] and beyond are deleted
There is no requirement that an array has an index property for every index between 0 and length − 1. The ECMAScript standard uses the term missing elements for gaps in the index sequence.
To find out whether an element is missing, you can use the in operator:
'2' in someNames //false—no property'2'3 in someNames //true; there is a property'3'// Note that the left operand is converted to a string
Note
An array can have properties that are not index properties. This is occasionally used to attach other information to an array. For example, the exec method of the RegExp class yields an array of matches, with additional properties index and input.
/([1-9]|1[0-2]):([0-5][0-9])([ap]m)/.exec('12:15pm')
// ['12:15pm', '12', '15', 'pm', index: 0, input: '12:15pm']
Caution
A string containing a negative number, such as '-1', is a valid property, but it is not an index property.
const squares = [0, 1, 4, 9] squares[-1] = 1 // [ 0, 1, 4, 9, '-1': 1 ]
7.3 Deleting and Adding Elements
The calls
let arr = [0, 1, 4, 9, 16, 25] const deletedElement = arr.pop() //arris now[0, 1, 4, 9, 16]const newLength = arr.push(x) //arris now[0, 1, 4, 9, 16, x]
delete or add an element at the end of an array, adjusting the length.
Note
Instead of calling pop and push, you could write
arr.length-- arr[arr.length] = x
I prefer pop and push since they indicate the intent better.
To delete or add the initial element, call
arr = [0, 1, 4, 9, 16, 25] const deletedElement = arr.shift() //arris now[1, 4, 9, 16, 25]const newLength = arr.unshift(x) //arris now[x, 1, 4, 9, 16, 25]
The push and unshift methods can add any number of elements at once:
arr = [9] arr.push(16, 25) //16,25are appended;arris now[9, 16, 25]arr.unshift(0, 1, 4) //0,1,4are prepended;arris now[0, 1, 4, 9, 16, 25]
Use the splice method to delete or add elements in the middle:
const deletedElements = arr.splice(start, deleteCount, x1, x2, . . .)
First, deleteCount elements are removed, starting at offset start. Then the provided elements are inserted at start.
arr = [0, 1, 12, 24, 36] const start = 2 // Replacearr[start]andarr[start + 1]arr.splice(start, 2, 16, 25) //arris now[0, 1, 16, 25, 36]// Add elements at indexstartarr.splice(start, 0, 4, 9) //arris now[0, 1, 4, 9, 16, 25, 36]// Delete the elements at indexstartandstart + 1arr.splice(start, 2) //arris now[0, 1, 16, 25, 36]// Delete all elements at indexstartand beyond arr.splice(start) //arris now[0, 1]
If start is negative, it is counted from the end of the array (that is, it is adjusted by adding arr.length).
arr = [0, 1, 4, 16]
arr.splice(-1, 1, 9) // arr is now [0, 1, 4, 9]
The splice method returns an array of the removed elements.
arr = [1, 4, 9, 16]
const spliced = arr.splice(1, 2) // spliced is [4, 9], arr is [1, 16]
7.4 Other Array Mutators
In this section, you will see the mutator methods of the Array class other than those for deleting and adding elements.
The fill method overwrites existing elements with a new value:
arr.fill(value, start, end)
The copyWithin method overwrites existing elements with other elements from the same array:
arr.copyWithin(targetIndex, start, end)
With both methods, start defaults to 0 and end to arr.length.
If start, end, or targetIndex are negative, they count from the end of the array.
Here are some examples:
let arr = [0, 1, 4, 9, 16, 25] arr.copyWithin(0, 1) //arris now[1, 4, 9, 16, 25, 25]arr.copyWithin(1) //arris now[1, 1, 4, 9, 16, 25]arr.fill(7, 3, -1) //arris now[1, 1, 4, 7, 7, 25]
arr.reverse() reverses arr in place:
arr = [0, 1, 4, 9, 16, 25]
arr.reverse() // arr is now [25, 16, 9, 4, 1, 0]
The call
arr.sort(comparisonFunction)
sorts arr in place. The comparison function compares two elements x, y and returns
A negative number if
xshould come beforeyA positive number if
xshould come aftery0if they are indistinguishable
For example, here is how you can sort an array of numbers:
arr = [0, 1, 16, 25, 4, 9]
arr.sort((x, y) => x - y) // arr is now [0, 1, 4, 9, 16, 25]
Caution
If the comparison function is not provided, the sort method turns elements to strings and compares them—see Exercise 5. For numbers, this might be the world’s worst comparison function:
arr = [0, 1, 4, 9, 16, 25]
arr.sort() // arr is now [0, 1, 16, 25, 4, 9]
The most useful methods of the Array class are summarized in Table 7-1.
Table 7-1 Useful Functions and Methods of the Array Class
Name |
Description |
|---|---|
Functions |
|
|
Produces an array from any object with properties named |
Mutating Methods |
|
|
Removes and returns the last element |
|
Appends or prepends |
|
Overwrites the given range with |
|
Copies the given range to the target index |
|
Reverses the elements of this array |
|
Sorts this array |
|
Removes and returns |
Nonmutating Methods |
|
|
Returns the elements in the given range |
|
If the array includes |
|
Returns the elements of this array, replacing any arrays of dimension ≤ |
|
Calls the given function on each element and returns an array of the results, or the flattened results, or |
|
Returns all elements for which |
|
Return the index or value of the first element for which |
|
Return |
|
Returns a string consisting of all elements turned to strings and separated by the given separator (which defaults to |
For sorting strings in a human language, the localeCompare method can be a good choice:
const titles = . . . titles.sort((s, t) => s.localeCompare(t))
Chapter 8 has more information about locale-based comparisons.
Note
Since 2019, the sort method is guaranteed to be stable. That is, the order of indistinguishable elements is not disturbed. For example, suppose you have a sequence of messages that was previously sorted by date. If you now sort it by the sender, then messages with the same sender will continue to be sorted by date.
7.5 Producing Elements
All methods that are introduced from this point on do not mutate the array on which they operate.
The following methods produce arrays containing elements from an existing array.
The call
arr.slice(start, end)
yields an array containing the elements in the given range. The start index defaults to 0, end to arr.length.
arr.slice() is the same as [...arr].
The flat method flattens multidimensional arrays. The default is to flatten one level.
[[1, 2], [3, 4]].flat()
is the array
[1, 2, 3, 4]
In the unlikely case that you have an array of more than two dimensions, you can specify how many levels you want to flatten. Here is a flattening from three dimensions to one:
[[[1, 2], [3, 4]], [[5, 6], [7, 8]]].flat(2) // [1, 2, 3, 4, 5, 6, 7, 8]
The call
arr.concat(arg1, arg2, . . .)
yields an array starting with arr, to which the arguments are appended. However, there is a twist: Array arguments are flattened.
const arr = [1, 2]
const arr2 = [5, 6]
const result = arr.concat(3, 4, arr2) // result is [1, 2, 3, 4, 5, 6]
Since you can nowadays use spreads in array literals, the concat method is no longer very useful. A simpler way of achieving the same result is:
const result = [...arr, 3, 4, ...arr2]
There is one remaining use case for the concat method: to concatenate a sequence of items of unknown type and flatten just those that are arrays.
Note
You can control the flattening with the isConcatSpreadable symbol. (Symbols are covered in Chapter 8.)
If the symbol is false, arrays are not flattened:
arr = [17, 29]
arr[Symbol.isConcatSpreadable] = false
[].concat(arr) // An array with a single element [17, 29]
If the symbol is true, then array-like objects are flattened:
[].concat({ length: 2, [Symbol.isConcatSpreadable]: true,
'0': 17, '1': 29 }) // An array with two elements 17, 29
7.6 Finding Elements
The following calls check whether a specific value is contained in an array.
const found = arr.includes(target, start) //trueorfalseconst firstIndex = arr.indexOf(target, start) // first index or-1const lastIndex = arr.lastIndexOf(target, start) // last index or-1
The target must match the element strictly, using the === comparison.
The search starts at start. If start is less than 0, it counts from the end of the array. If start is omitted, it defaults to 0.
If you want to find a value that fulfills a condition, then call one of the following:
const firstIndex = arr.findIndex(conditionFunction) const firstElement = arr.find(conditionFunction)
For example, here is how you can find the first negative number in an array:
const firstNegative = arr.find(x => x < 0)
For this and the subsequent methods of this section, the condition function receives three arguments:
The array element
The index
The entire array
The calls
arr.every(conditionFunction) arr.some(conditionFunction)
yield true if conditionFunction(element, index, arr) is true for every element or at least one element.
For example,
const atLeastOneNegative = arr.some(x => x < 0)
The filter method yields all values that fulfill a condition:
const negatives = [-1, 7, 2, -9].filter(x => x < 0) // [-1, -9]
7.7 Visiting All Elements
To visit all elements of an array, you can use a for of loop to visit all elements in order, or the for in loop to visit all index values.
for (const e of arr) {
// Do something with the element e
}
for (const i in arr) {
// Do something with the index i and the element arr[i]
}
Note
The for of loop looks up elements for all index values between 0 and length − 1, yielding undefined for missing elements. In contrast, the for in loop only visits keys that are present.
In other words, the for in loop views an array as an object, whereas the for of loop views an array as an iterable. (As you will see in Chapter 12, iterables are sequences of values without gaps.)
If you want to visit both the index values and elements, use the iterator that the entries method returns. It produces arrays of length 2 holding each index and element. This loop uses the entries method, a for of loop, and destructuring:
for (const [index, element] of arr.entries()) console.log(index, element)
Note
The entries method is defined for all JavaScript data structures, including arrays. There are corresponding methods keys and values that yield iterators over the keys and values of the collection. These are useful for working with generic collections. If you know that you are working with an array, you won’t need them.
The call arr.forEach(f) invokes f(element, index, arr) for each element, skipping missing elements. The call
arr.forEach((element, index) => console.log(index, element))
is equivalent to
for (const index in arr) console.log(index, arr[index])
Instead of specifying an action for each element, it is often better to transform the elements and collect the results. The call arr.map(f) yields an array of all values returned from f(arr[index], index, arr):
[1, 7, 2, 9].map(x => x * x) // [1, 49, 4, 81] [1, 7, 2, 9].map((x, i) => x * 10 ** i) // [1, 70, 200, 9000]
Consider a function that returns an array of values:
function roots(x) {
if (x < 0) {
return [] // No roots
} else if (x === 0) {
return [0] // Single root
} else {
return [Math.sqrt(x), -Math.sqrt(x)] // Two roots
}
}
When you map this function to an array of inputs, you get an array of the array-valued answers:
[-1, 0, 1, 4].map(roots) // [[], [0], [1, -1], [2, -2]]
If you want to flatten out the results, you can call map followed by flat, or you can call flatMap which is slightly more efficient:
[-1, 0, 1, 4].flatMap(roots) // [0, 1, -1, 2, -2]
Finally, the call arr.join(separator) converts all elements to strings and joins them with the given separator. The default separator is ','.
[1,2,3,[4,5]].join(' and ') // '1 and 2 and 3 and 4,5'
Note
The forEach, map, filter, find, findIndex, some, and every methods (but not sort or reduce), as well as the from function, take an optional argument after the function argument:
arr.forEach(f, thisArg)
The thisArg argument becomes the this parameter of f. That is,
thisArg.f(arr[index], index, arr)
is called for each index.
You only need the thisArg argument if you pass a method instead of a function. Exercise 4 shows how you can avoid this situation.
7.8 Sparse Arrays
An array with one or more missing elements is called sparse. Sparse arrays can arise in four situations:
Missing elements in an array literal:
const someNumbers = [ , 2, , 9] // No index properties0,2Adding an element beyond the length:
someNumbers[100] = 0 // No index properties4to99Increasing the length:
const bigEmptyArray = [] bigEmptyArray.length = 10000 // No index propertiesDeleting an element:
delete someNumbers[1] // No longer an index property1
Most methods in the array API skip over the missing elements in sparse arrays. For example, [ , 2, , 9].forEach(f) only invokes f twice. No call is made for the missing elements at indices 0 and 2.
As you have seen in Section 7.1, “Constructing Arrays” (page 141), Array.from(arrayLike, f) is an exception, invoking f for every index.
You can use Array.from to replace missing elements with undefined:
Array.from([ , 2, , 9]) // [undefined, 2, undefined, 9]
The join method turns missing and undefined elements into empty strings:
[ , 2, undefined, 9].join(' and ') // ' and 2 and and 9'
Most methods that produce arrays from given arrays keep the missing elements in place. For example, [ , 2, , 9].map(x => x * x) yields [ , 4, , 81].
However, the sort method places missing elements at the end:
let someNumbers = [ , 2, , 9]
someNumbers.sort((x, y) => y - x) // someNumbers is now [9, 2, , , ]
(Eagle-eyed readers may have noted that there are four commas. The last comma is a trailing comma. If it had not been present, then the preceding comma would have been a trailing comma and the array would only have had one undefined element.)
The filter, flat, and flatMap skip missing elements entirely.
A simple way of eliminating missing elements from an array is to filter with a function that accepts all elements:
[ , 2, , 9].filter(x => true) // [2, 9]
7.9 Reduction
This section discusses a general mechanism for computing a value from the elements of an array. The mechanism is elegant, but frankly, it is never necessary—you can achieve the same effect with a simple loop. Feel free to skip this section if you don’t find it interesting.
The map method applies a unary function to all elements of a collection. The reduce and reduceRight methods that we discuss in this section combine elements with a binary operation. The call arr.reduce(op) applies op to successive elements like this:
.
.
.
op
/
op arr[3]
/
op arr[2]
/
arr[0] arr[1]
For example, here is how to compute the sum of array elements:
const arr = [1, 7, 2, 9] const result = arr.reduce((x, y) => x + y) // ((1 + 7) + 2) + 9
Here is a more interesting reduction that computes the value of a decimal number from an array of digits:
[1, 7, 2, 9].reduce((x, y) => 10 * x + y) // 1729
This tree diagram shows the intermediate results:
1729
/
172 9
/
17 2
/
1 7
In most cases, it is useful to start the computation with an initial value other than the initial array element. The call arr.reduce(op, init) computes
.
.
.
op
/
op arr[2]
/
op arr[1]
/
init arr[0]
Compared with the tree diagram of reduce without an initial value, this diagram is more regular. All array elements are on the right of the tree. Each operation combines an accumulated value (starting with the initial value) and an array element.
For example,
[1, 7, 2, 9].reduce((accum, current) => accum - current, 0)
is
0 − 1 − 7 − 2 − 9 = −19
Without the initial value, the result would have been 1 − 7 − 2 − 9, which is not the difference of all elements.
The initial value is returned when the array is empty. For example, if you define
const sum = arr => arr.reduce((accum, current) => accum + current, 0)
then the sum of the empty array is 0. Reducing an empty array without an initial value throws an exception.
The callback function actually takes four arguments:
The accumulated value
The current array element
The index of the current element
The entire array
In this example, we collect the positions of all elements fulfilling a condition:
function findAll(arr, condition) {
return arr.reduce((accum, current, currentIndex) =>
condition(current) ? [...accum, currentIndex] : accum, [])
}
const odds = findAll([1, 7, 2, 9], x => x % 2 !== 0)
// [0, 1, 3], the positions of all odd elements
The reduceRight method starts at the end of the array, visiting the elements in reverse order.
op
/
. arr[0]
.
.
/
op
/
op arr[n-2]
/
init arr[n-1]
For example,
[1, 2, 3, 4].reduceRight((x, y) => [x, y], [])
is
[[[[[], 4], 3], 2], 1]
Note
Right reduction in JavaScript is similar to a right fold in Lisp-like languages, but the order of the operands is reversed.
Reducing can be used instead of a loop. Suppose, for example, that we want to count the frequencies of the letters in a string. One way is to visit each letter and update an object.
const freq = {}
for (const c of 'Mississippi') {
if (c in freq) {
freq[c]++
} else {
freq[c] = 1
}
}
Here is another way of thinking about this. At each step, combine the frequency map and the newly encountered letter, yielding a new frequency map. That’s a reduction:
.
.
.
op
/
op 's'
/
op 'i'
/
empty map 'M'
What is op? The left operand is the partially filled frequency map, and the right operand is the new letter. The result is the augmented map. It becomes the input to the next call to op, and at the end, the result is a map with all counts. The code is
[...'Mississippi'].reduce(
(freq, c) => ({ ...freq, [c]: (c in freq ? freq[c] + 1 : 1) }),
{})
In the reduction function, a new object is created, starting with a copy of the freq object. Then the value associated with the c key is set either to an increment of the preceding value if there was one, or to 1.
Note that in this approach, no state is mutated. In each step, a new object is computed.
It is possible to replace any loop with a call to reduce. Put all variables updated in the loop into an object, and define an operation that implements one step through the loop, producing a new object with the updated variables. I am not saying this is always a good idea, but you may find it interesting that loops can be eliminated in this way.
7.10 Maps
The JavaScript API provides a Map class that implements the classic map data structure: a collection of key/value pairs.
Of course, every JavaScript object is a map, but there are advantages of using the Map class instead:
Object keys must be strings or symbols, but
Mapkeys can be of any type.A
Mapinstance remembers the order in which elements were inserted.Unlike objects, maps do not have a prototype chain.
You can find out the number of entries with the
sizeproperty.
To construct a map, you can provide an iterable with [key, value] pairs:
const weekdays = new Map( [["Mon", 0], ["Tue", 1], ["Wed", 2], ["Thu", 3], ["Fri", 4], ["Sat", 5], ["Sun", 6], ])
Or you can construct an empty map and add entries later:
const emptyMap = new Map()
You must use new with the constructor.
The API is very straightforward. The call
map.set(key, value)
adds an entry and returns the map for chaining:
map.set(key1, value1).set(key2, value2)
To remove an entry, call:
map.delete(key) // Returns true if the key was present, false otherwise
The clear method removes all entries.
To test whether a key is present, call
if (map.has(key)) . . .
Retrieve a key’s value with
const value = map.get(key) // Returns undefined if the key is not present
A map is an iterable yielding [key, value] pairs. Therefore, you can easily visit all entries with a for of loop:
for (const [key, value] of map) {
console.log(key, value)
}
Alternatively, use the forEach method:
map.forEach((key, value) => {
console.log(key, value)
})
Maps are traversed in insertion order. Consider this map:
const weekdays = new Map([['Mon', 0], ['Tue', 1], . . ., ['Sun', 6]])
Both the for of loop and the forEach method will respect the order in which you inserted the elements.
Note
In Java, you would use a LinkedHashMap to visit elements in insertion order. In JavaScript, tracking insertion order is automatic.
Note
Maps, like all JavaScript collections, have methods keys, values, and entries that yield iterators over the keys, values, and key/value pairs. If you just want to iterate over the keys, you can use a loop:
for (const key of map.keys()) . . .
In programming languages such as Java and C++, you get the choice between hash maps and tree maps, and you have to come up with a hash or comparison function. In JavaScript, you always get a hash map, and you have no choice of the hash function.
The hash function for a JavaScript Map is compatible with key equality: === except that all NaN are equal. Hash values are derived from primitive type values or object references.
This is fine if your keys are strings or numbers, or if you are happy to compare keys by identity. For example, you can use a map to associate values with DOM nodes. That is better than adding properties directly into the node objects.
But you have to be careful when you use other objects as keys. Distinct objects are separate keys, even if their values are the same:
const map = new Map()
const key1 = new Date('1970-01-01T00:00:00.000Z')
const key2 = new Date('1970-01-01T00:00:00.000Z')
map.set(key1, 'Hello')
map.set(key2, 'Epoch') // Now map has two entries
If that’s not what you want, consider choosing different keys, such as the date strings in this example.
7.11 Sets
A Set is a data structure that collects elements without duplicates.
Construct a set as
const emptySet = new Set() const setWithElements = new Set(iterable)
where iterable produces the elements.
As with maps, the size property yields the number of elements.
The API for sets is even simpler than that for maps:
set.add(x) // Addsxif not present and returnssetfor chaining set.delete(x) // Ifxis present, deletesxand returnstrue, otherwise returnsfalseset.has(x) // Returnstrueifxis present set.clear() // Deletes all elements
To visit all elements of a set, you can use a for of loop:
for (const value of set) {
console.log(value)
}
Alternatively, you can use the forEach method:
set.forEach(value => {
console.log(value)
})
Just like maps, sets remember their insertion order. For example, suppose you add weekday names in order:
const weekdays = new Set(['Mon', 'Tue', 'Wed', 'Thu', 'Fri', 'Sat', 'Sun'])
Then the for of loop and forEach method iterate over the elements in this order.
Note
A set is considered as a map of [value, value] pairs. Both the keys and values methods yield an iterator over the values, and the entries method yield an iterator over [value, value] pairs. None of these methods are useful when you work with a known set. They are intended for code that deals with generic collections.
As with maps, sets are implemented as hash tables with a predefined hash function. Set elements are considered to be the same if they are the same primitive type values or the same object references. In addition, NaN values equal each other.
7.12 Weak Maps and Sets
An important use case for JavaScript maps and sets is to attach properties to DOM nodes. Suppose we want to categorize certain nodes to indicate success, work in progress, or an error. We could attach the properties directly to the nodes:
node.outcome = 'success'
That generally works fine, but it is a bit fragile. DOM nodes have lots of properties, and trouble lies ahead if someone else, or a future version of the DOM API, uses the same property.
It is more robust to use a map:
const outcome = new Map() . . . outcome.set(node, 'success')
DOM nodes come and go. If a particular node is no longer needed, it should be garbage-collected. However, if a node reference resides in the outcome map, that reference will keep the node object alive.
That is where weak maps come in. If a key in a weak map is the only reference to an object, that object is not kept alive by the garbage collector.
Simply use a weak map to collect properties:
const outcome = new WeakMap()
Weak maps have no traversal methods, and the map objects are not iterable. The only methods are set, delete, has, and get. That is enough to set properties and to check the properties of a given object.
If the property that you want to monitor is binary, you can use a WeakSet instead of a WeakMap. Then the only methods are set, delete, and has.
The keys of weak maps and the elements of weak sets can only be objects, not primitive type values.
7.13 Typed Arrays
JavaScript arrays store sequences of elements of any kind, possibly with missing elements. If all you want to store is a sequence of numbers, or the raw bytes of an image, a generic array is quite inefficient.
If you need to store sequences of numbers of the same type efficiently, you can use a typed array. The following array types are available:
Int8Array Uint8Array Uint8ClampedArray Int16Array Uint16Array Int32Array Uint32Array Float32Array Float64Array
All elements are of the given type. For example, an Int16Array stores 16-bit integers between −32768 and 32767. The Uint prefix denotes unsigned integers. An UInt16Array holds integers from 0 to 65535.
When constructing an array, specify the length. You cannot change it later.
const iarr = new Int32Array(1024)
Upon construction, all array elements are zero.
There are no typed array literals, but each typed array class has a function named of for constructing an instance with given values:
const farr = Float32Array.of(1, 0.5, 0.25, 0.125, 0.0625, 0.03215, 0.015625)
As with arrays, there is a from function that takes elements from any iterable, with an optional mapping function:
const uarr = Uint32Array.from(farr, x => 1 / x)
// An Uint32Array with elements [1, 2, 4, 8, 16, 32, 64]
Assigning to a numerical array index that is not an integer between 0 and length − 1 has no effect. However, as with regular arrays, you can set other properties:
farr[-1] = 2 // No effect
farr[0.5] = 1.414214 // No effect
farr.lucky = true // Sets the lucky property
When you assign a number to an integer array element, any fractional part is discarded. Then the number is truncated to fit into the integer range. Consider this example:
iarr[0] = 40000.25 // Sets iarr[0] to -25536
Only the integer part is used. Since 40000 is too large to fit in the range of 32-bit integers, the last 32 bits are taken, which happen to represent −25536.
An exception to this truncation process is the Uint8ClampedArray which sets an out-of-range value to 0 or 255 and rounds non-integer values to the nearest integer.
The Uint8ClampedArray type is intended for use with HTML canvas images. The getImageData method of a canvas context yields an object whose data property is an Uint8ClampedArray containing the RGBA values of a rectangle on a canvas:
const canvas = document.getElementById('canvas')
const ctx = canvas.getContext('2d')
ctx.drawImage(img, 0, 0)
let imgdata = ctx.getImageData(0, 0, canvas.width, canvas.height)
let rgba = imgdata.data // an Uint8ClampedArray
The companion code for this book has a sample program that turns the canvas contents into negative when you click on it—see Figure 7-1.
canvas.addEventListener('click', event => {
for (let i = 0; i < rgba.length; i++) {
if (i % 4 != 3) rgba[i] = 255 - rgba[i]
}
ctx.putImageData(imgdata, 0, 0)
})
Figure 7-1 The canvas content turns into negative when clicked
Typed arrays have all methods of regular arrays, except for:
push,pop,shift,unshift—you can’t change the size of a typed arrayflat,flatMap—a typed array can’t hold arraysconcat—usesetinstead
There are two methods that regular arrays don’t have. The set method copies values from an array or typed array at an offset:
targetTypedArray.set(source, offset)
By default, the offset is zero. The source must fit entirely into the target. If the offset and source length exceed the target length, a RangeError is thrown. (This means you cannot use this method to shift elements of a typed array.)
The subarray method yields a view into a subrange of the elements:
const sub = iarr.subarray(16, 32)
If omitted, the end index is the length of the array, and the start index is zero.
This seems to be just the same as the slice method, but there is an important difference. The array and subarray share the same elements. Modifying either is visible in the other.
sub[0] = 1024 // Now iarr[16] is also 1024
7.14 Array Buffers
An array buffer is a contiguous byte sequence that can hold data from a file, a data stream, an image, and so on. The data from typed arrays are also stored in array buffers.
A number of web APIs (including the File API, XMLHttpRequest, and WebSockets) yield array buffers. You can also construct an array buffer with a given number of bytes:
const buf = new ArrayBuffer(1024 * 2)
Usually, the binary data in an array buffer has a complex structure, such as an image or sound file. Then use a DataView to look at the data inside:
const view = new DataView(buf)
Read values at a given offset with the DataView methods getInt8, getInt16, getInt32, getUInt8, getUInt16, getUInt32, getFloat32, getFloat64:
const littleEndian = true // false or omitted for big-endian byte order
const value = view.getUint32(offset, littleEndian)
Write data with the set method:
view.setUint32(offset, newValue, littleEndian)
Note
There are two ways of storing binary data as a sequence of bytes, called “big-endian” and “little-endian.” Consider the 16-bit value 0x2122. In the big-endian way, the more significant byte comes first: 0x21 followed by 0x22. Little-endian is the other way around: 0x22 0x21.
Most modern processors are little-endian, but a number of common file formats (such as PNG and JPEG) use big-endian numbers.
The “big-endian” and “little-endian” terms, while eminently sensible on their own, are actually borrowed from a satirical passage in Gulliver’s Travels.
The buffer of a typed array always uses the endianness of the host platform. If the entire buffer data is an array, and you know that the endianness matches that of the host platform, you can construct a typed array from the buffer contents:
const arr = new Uint16Array(buf) // An array of 1024 Uint16, backed by buf
Exercises
Implement a function that works exactly like the
fromfunction of theArrayclass. Pay careful attention to missing elements. What happens with objects that have keys whose numeric values are ≥ thelengthproperty? With properties that are not index properties?The
Array.ofmethod was designed for a very specific use case: to be passed as a “collector” to a function that produces a sequence of values and sends them to some destination—perhaps printing them, summing them, or collecting them in an array. Implement such a function:mapCollect(values, f, collector)
The function should apply
fto all values and then send the result to the collector, a function with a variable number of arguments. Return the result of the collector.Explain the advantage of using
Array.ofoverArray(i.e.,(...elements) => new Array(...elements)) in this context.An array can have properties whose numeric values are negative integers, such as
'-1'. Do they affect the length? How can you iterate over them in order?Google for “JavaScript forEach thisArg” to find blog articles explaining the
thisArgparameter of theforEachmethod. Rewrite the examples without using thethisArgparameter. If you find a call such asarr.forEach(function() { . . . this.something() . . . }, thisArg)where
thisArgisthis, replace the function with an arrow function. Otherwise, replace the innerthiswith whateverthisArgis. If the call has the formarr.forEach(method, thisArg)
use an arrow function invoking
thisArg.method(. . .). Can you come up with any situation wherethisArgis required?If you do not supply a comparison function in the
sortmethod of theArrayclass, then elements are converted to strings and lexicographically compared by UTF-16 code units. Why is this a terrible idea? Come up with arrays of integers or objects where the sort results are useless. What about characters aboveu{FFFF}?Suppose an object representing a message has properties for dates and for senders. Sort an array of messages first by date, then by sender. Verify that the
sortmethod is stable: Messages with the same sender continue to be sorted by date after the second sort.Suppose an object representing a person has properties for first and last names. Provide a comparison function that compares last names and then breaks the ties using first names.
Implement a comparison function that compares two strings by their Unicode code points, not their UTF-16 code units.
Write a function that yields all positions of a target value in an array. For example,
indexOf(arr, 0)yields all array index valuesiwherearr[i]is zero. Usemapandfilter.Write a function that yields all positions at which a given function is
true. For example,indexOf(arr, x => x > 0)yields all array index valuesiwherearr[i]is positive.Compute the spread (that is, the difference between maximum and minimum) of an array using
reduce.Given an array of functions
[f1, f2, . . . , fn], obtain the composition functionx => f1(f2( . . . (fn(x)) . . . ))usingreduceRight.Implement functions
map,filter,forEach,some,everyfor sets.Implement functions
union(set1, set2),intersection(set1, set2),difference(set1, set2)that yield the union, intersection, or difference of the sets, without mutating the arguments.Write a function that constructs a
Mapfrom an object, so that you can easily construct a map astoMap({ Monday: 1, Tuesday: 2, . . . }).Suppose you use a
Mapwhose keys are point objects of the form{ x:. . ., y:. . . }. What can go wrong when you make queries such asmap.get({ x: 0, y: 0 })? What can you do to overcome that?Show that weak sets really work as promised. Start Node.js with the flag
--expose-gc. Callprocess.memoryUsage()to find out how much of the heap is used. Allocate an object:let fred = { name: 'Fred', image: new Int8Array(1024*1024) }Verify that the heap usage has gone up by about a megabyte. Set
fredtonull, run the garbage collector by callingglobal.gc(), and check that the object was collected. Now repeat, inserting the object into a weak set. Verify that the weak set allows the object to be collected. Repeat with a regular set and show that the object won’t be collected.Write a function to find the endianness of host platform. Use an array buffer and view it both as a data view and a typed array.