Discuss
  • Map/Set.prototype.size is O(n)

Map/Set.prototype.size is O(n)

# Daniel Herman (7 years ago)

In reading the relevant section for the size accessors (http://www.ecma- international.org/ecma-262/7.0/index.html#sec-get-map.prototype.size), I'm confused and wondering why this was defined as an O(n) operation in the get accessor rather than as an additional step in the set, delete, and clear methods to track an internal [[Size]] variable or something, making the public size accessor capable of being O(1).

It seems surprising to me that in order to be spec compliant, Map and Set implementations must implement accessors that have surprising perf implications.

# Michał Wadas (7 years ago)

Implementations aren't required to follow exactly these steps, just to have the same result.

# Oriol _ (7 years ago)

Not only size. All get, set, has, etc. algorithms in the spec are O(n).

But as explained in www.ecma-international.org/ecma-262/7.0/index.html#sec-map-objects,

# Isiah Meadows (7 years ago)

The only part that matters is that it's observably equivalent functionally. In theory, indexOf could be done in constant steps provided there are no indexed getters or setters, and there's no overriding proxy hook. It'd be impractical to ensure that, but it's still theoretically possible to both do that and remaining conformant.

Isiah Meadows me at isiahmeadows.com