Get last value inserted into a Set

Question

The MDN documentation for Set says that JavaScript Set objects retain insertion order of elements:

Set objects are collections of values, you can iterate its elements in insertion order.

Is there a way to get the last item inserted into a Set object?

var s = new Set();
s.add("Alpha");
s.add("Zeta");
s.add("Beta");

console.log(getLastItem(s)); // prints "Beta"

Edit

It is possible to implement a Linked Set datastructure container class that has the same interface as Set and has the desired capability. See my answer below.

Frazil

In insertion order? Does javascript have O(n) set operations? – Foliated

@FilipHaglund Insert, lookup and remove are O(1). The standard requires one more thing: iterate the items in insertion order. But you don't have to iterate over to do a lookup. – Frazil

I'm very sure it's not O(1). Is it keeping a separate list of the keys for iteration, and a tree for lookup, making iteration O(n log n)? – Foliated

@FilipHaglund Those operations can be implemented by a combination of a hashtable and a linked list. Imagine a 'next item' reference (an index in the hashtables underlying array) besides every entry, and update that on every operation. Insertion and deletion is O(1) on linked lists. For lookup, the hashtable is used. – Frazil

The spec only requires access times to be sublinear on average. The specific structure and cost are implementation-dependent. – Disobedience

Ah, okey. The next-pointer is good. But the actual hash table updates are O(log n), right? So then it's still O(log n) – Foliated

Hash table updates are O(1) in average bigocheatsheet.com – Frazil

The best way I found it to have a wrapper over Set(), say MySet(), add keys to MySet object, while adding, maintain prev value in MySet, and last() will return prev in constant time. – Noelnoelani

@ManoharReddyPoreddy I also settled for a wrapper, see my answer below – Frazil

@TamasHegedus Nice, that makes sense. However, I was hinting a more lean wrapper. – Noelnoelani

Answer 1

I was not able to find any method to get last value inserted in set from ECMA 2015 Specification, may be they never intended such a method, but you can do something like:

const a = new Set([1, 2, 3]);
a.add(10);
const lastValue = Array.from(a).pop();

Edit:

on second thought, a space efficient solution might be:

function getLastValue(set){
  let value;
  for(value of set);
  return value;
}

const a = new Set([1, 2, 3]);
a.add(10);
console.log('last value: ', getLastValue(a));

Cortney

Is there no builtin constant time solution? – Frazil

@hege_hegedus unfortunately no, at least I cannot find any in the specifications :( – Cortney

I start to suspect the overhead of converting set back to an array. For the case of large collection it may or may not exhibit some overhead. However, it makes sense the .last is not included in the spec because in theory, set doesn't need the order. – Culmiferous

Answer 2

Some ideas:

• Consider using an array instead of a set. Extracting the last element of an array is easy, e.g.

  array[array.length-1];
  array.slice(-1)[0];
  array.pop(); // <-- This alters the array
  

  If you really need a set, you can convert it to an array when you want to extract the last item, but that will cost time and space.

• Iterate the set manually. This will cost time but not as much space as copying into an array. For example (there are probably more elegant ways to do this)

  var set = new Set([1, 2, 3]);
  var iter = set.values(), prev, curr;
  do {
    prev = curr;
    curr = iter.next();
  } while(!curr.done)
  var last = prev.value; // 3
  

• Consider inserting the items in reverse order. Then you only need to get the first item in the set, and that's easier:

  set.values().next().value;
  

• Subclass Set to add this new functionality:

  class MySet extends Set {
    add(value) {
      super.add(value);
      this.last = value;
    }
  }
  var set = new MySet();
  set.add(1); set.add(2); set.add(3);
  set.last; // 3
  

  Note this will only detect values added with add. To be more complete, it should also detect the latest value when the set is constructed, and update the value when the last item is removed.

Disobedience

Answer 3

Yes, there is a way to do that, you can simply convert the set to an array and pop of the last item

function getLastItem(_set) {
    return [..._set].pop();
}

to get keys/values etc, you can do

return [..._set.entries()].pop(); // the entire entry
return [..._set.keys()].pop();    // the key only
return [..._set.values()].pop();  // the value only

If you don't want to create an array, you'd probably have to iterate and get the last value, like this

var last; s.forEach(k => { last = k }); // last === "Beta"

FIDDLE

Trelu

@hege_hegedus - I didn't notice mido's answer and posted the same one at first, so I figured I'd have to come up with something at least a little different, the spread operator and how to get the entire entries, keys etc, seemed like enough to not just post the exact same thing. – Trelu

I'm just curious: is there a short syntax to exhaust the iterator and get the last element without building a list? (I mean shorter than writing a separate function for that task too) – Frazil

I don't think there is, but I still don't know all the ins and outs of ES2015. Sets are somewhat limited to a few prototyped methods, it would have to be something else that's clever from ES2015, something with iterators etc. – Trelu

This is a terrible solution. Why do Javascript developers never care about performance or efficiency? – Knoll

@Knoll - Why is it terrible, spreading the Set in an array is most likely faster than the other solutions, except for the empty for...of loop that iterates. A Set has no real way of getting the last item, there's no index or built-ins, so either one iterates to the last item, or converts the Set to something that has built-ins, like an array. Unless the Set is huge, the performance differences won't be noticeable. – Trelu

@adeneo: That's exactly why. Converting to an array is twice as slow even in your example that only adds three things to the set! And it probably uses your memory. Good test, but can you update it to add 1000 random values to the set instead of 3? I think that's a bit more realistic. – Knoll

@Knoll - I could add a thousand random strings to the Set, but I'm not sure the result is what you think it would be -> jsperf.com/test-set-last-value ... What you really should be taking away from this, is that the browser can run this 400 000 times in a second, with a million entries, so it's not going to be a bottle neck in any really application, except maybe in very special cases, so it's basically micro-optimization. – Trelu

That kind of attitude is why people hate Electron apps. If you sprinkle your code with stuff that's slow because it's "not going to be a bottle neck" you end up with a slow app. There's no compelling reason to use the slow version so why would you? In any case, thanks for the updated benchmark - very useful! – Knoll

That kind of attitude is what get stuff built, spending lots of time figuring out that for ...of is 000000000000000000.4 milliseconds faster is micro-optimization, and all though fun, not very important. At the end of the day, if one needs to get the last item from a collection, a Set is probably the wrong choice to begin with. – Trelu

Answer 4

Just another approach.

Set.prototype.last = function(){
  return new Set().add( [...this].pop() );
}

Set.prototype.lastKey = function(){
  return [...this.keys()].pop();
}

Set.prototype.lastValue = function(){
  return [...this.values()].pop();
}

var lastSet = s.last(); // "Beta"
var lastKey = s.lastKey(); // "Beta"
var lastValue = s.lastValue(); //  "Beta"

Cockatrice

Note that s.last(), defined as new Set().add( [...this].pop() ); in this answer, returns Set {"Beta"}, not "Beta" – Passenger

expensive surely to do it this way – Silicious

@AlexanderMills Mhm, I think spread is slower than Array.from too. – Cockatrice

Array.from and spread are both too slow, both are creating a complete array just to remove an item? – Silicious

Yes. To get the last value in the set, or you can always iterate through it in the order of insertion order. I believe other answers provide ways to do it. – Cockatrice

yeah either way, it's O(N) to remove an item here – Silicious

Another issue with the above code is that you are modifying Set. Modifying objects that you don't own makes your code less maintainable. – Pennyroyal

@Pennyroyal The approach above can be used as a reference if you want to encapsulate for any new object model. But, you can also use it as it shows and wouldn't recommend if you don't know what you're doing. – Cockatrice

Answer 5

I have created a replacement for Set, which re-implements the linked functionality of the set, using an underlying Map.

class LinkedSetLink {
  constructor(value) {
    this.value = value;
    this.prev = this;
    this.next = this;
  }
  
  insertBefore(item) {
    const prev = item.prev = this.prev;
    const next = item.next = this;
    next.prev = item;
    prev.next = item;
  }
  
  remove() {
    const prev = this.prev;
    const next = this.next;
    next.prev = prev;
    prev.next = next;
  }
}


class LinkedSet {
  constructor(iterable) {
    this._map = new Map();
    this._pivot = new LinkedSetLink(/* undefined */);
    if (iterable) {
      this._addAll(iterable);
    }
  }

  _addAll(iterable) {
    for (const item of iterable) {
      this.add(item);
    }
  }

  has(item) {
    return this._map.has(item);
  }

  add(item) {
    if (!this._map.has(item)) {
      const link = new LinkedSetLink(item);
      this._pivot.insertBefore(link);
      this._map.set(item, link);
    }
  }

  delete(item) {
    const link = this._map.get(item);
    if (link) {
      this._map.delete(item);
      link.remove();
    }
  }

  clear() {
    this._map.clear();
    this._pivot.next = this._pivot.prev = this._pivot;
  }

  get size() {
    return this._map.size;
  }

  values() {
    return this._map.keys();
  }

  keys() {
    return this.values();
  }

  [Symbol.iterator]() {
    return this.values();
  }

  *entries() {
    for (const key of this.values()) {
      yield [key, key];
    }
  }

  first() {
    return this._pivot.next.value;
  }

  last() {
    return this._pivot.prev.value;
  }
}

function test1() {
  console.log(Array.from(new LinkedSet(["a", "b", "c"]).entries()));
}
function test2() {
  console.log(new LinkedSet(["a", "b", "c"]).last());
}

<button onclick="test1()">test entries</button>
<button onclick="test2()">test last</button>

Frazil

Answer 6

There is no method for accessing the last item, but you can do it as follows

let setOfNumbers = new Set([10]);
setOfNumbers.add(20).add(2);
let lastValue = [...setOfNumbers].pop()

Camise

Answer 7

A simple solution, but O(N):

const getLastValueFromSet = (set) => {
    for (var value of set);
    return value;
}

Uneasy