STL.js

Standard Template Library for {Type,Java}Script projects

Why?

Have you ever been in a situation where you need to use a deque but you don't have such a thing in JavaScript? "Why don't you use an array?", they might ask. I'd like to give an answer: time complexity

Let's take a look at the deque example. It has O(1) for {push,pop}_{front,back} (C++ API) operations, in a word, it's a doubly linked list and you can push and pop items to boths ends fast. You can't take an arbitrary element by index as you can do with arrays, and that's the price you pay. That's fine since you don't need to, doubly linked lists serve the different purpose.

What's about unshift complexity of Array in V8? Benchmarks show it's significantly slower than push. It moves the elements to relayout memory, as you might expect, it's O(n) in worst case.

Deque

Compliant with JavaScript Array API.

Benchmarks 🚀

Array#unshift works in O(n) time and Deque#unshift works in O(1) time, check out the benchmarks:

Array#shift is optimized though, works faster than Deque#shift on ~20%:

Array#push and Array#pop works faster as expected:

Note: tests run ~4s on 10.000 items

API

push

import { Deque } from 'stljs';
const deque = new Deque<number>()
deque.push(1);
// 1
deque.back();

pop

import { Deque } from 'stljs';
const deque = new Deque<number>()
deque.push(1);
// 1
deque.pop();

unshift

import { Deque } from 'stljs';
const deque = new Deque<number>()
deque.push(2);
deque.push(3);
deque.unshift(1);
// 1
deque.front();

shift

import { Deque } from 'stljs';
const deque = new Deque<number>()
deque.push(1);
deque.push(2);
deque.push(3);
// 1
deque.shift();

length

import { Deque } from 'stljs';
const deque = new Deque<number>()
deque.push(1);
deque.push(2);
deque.push(3);

while (deque.length > 0) {
  // 3, 2, 1
  deque.pop();
}