search

tc39 / proposal-built-in-modules

BSD 2-Clause "Simplified" License
891 stars 25 forks source link

Please give us the remaining basic containers #26

Closed StoneCypher closed 5 years ago

StoneCypher commented 5 years ago

We are container-poor. This is problematic. Please give us the remaining basic containers.

They should be easily pulled from the host implementation's c++ stl

We need queue, deque, pqueue, and some or another tree.

Arguably you can skip lists on homebrew implementations but standardization is useful. Anyone arguing for homebrew implementations of trees as nested containers is missing the point.

It would be nice to have linked and doubly linked list. These actually can be reasonably implemented as homebrew, but native ones would be ridic faster, and having a shared api would be nice

It would be really nice to have bimap. Greenspun's rule is about lisp. It should be about bimap. Most people don't know bimap (where values are also keys) exists, and yet have buggily implemented it a thousand times.

Consequentially we'll also want multibimap, which is what everyone needs and doesn't realize and doesn't end up implementing

It would be nice to have multiset and multimap. It is reasonable to fake these with a set-of-arrays and so on, so, this isn't critical. It would be a performace benefit at large, though, and probably a defect reduction.

It would be interesting to have trie, but this is probably overboard. This is properly userland-implementable. The only reason or interest here would be to have a shared/unified API, but for trie it's not entirely clear that's actually needed or warranted.

bakkot commented 5 years ago

It's not obvious to me that it would be a good thing to add all of these. For example, most people can use arrays instead of linked lists and have that be quite performant, since engines have put a huge amount of work into optimizing arrays. And then they don't have to think all the time about which to use. Can you say more about why it makes sense for each of these to be built in?

Mouvedia commented 5 years ago

Can you say more about why it makes sense for each of these to be built in?

negative indexes faster arrays

tabatkins commented 5 years ago

I'm 100% on board with this. Every hobby project I write I end up implementing several extra container classes; Counter and DefaultMap (defaultdict in Python) in particular are common ones for me.

Stacks can be done trivially and efficiently with arrays, but queues, dequeues, and pqueues are all relatively bad with plain arrays; good implementations exist but are non-trivial to write. (If you're doing a significant amount of .insert() or .splice() to insert/delete from the front of an array, you're gonna be paying for it...).

The DOM is reinventing multimaps in several places (URLSearchParams, CSSStylePropertyMap, etc), and having a canonical version in JS would be great. At minimum, the usage of them in core platform APIs suggests that they'd be useful to expose for author usage as well.

Mouvedia commented 5 years ago

Maybe add a constructor for iterable array-like instances? Maybe called List?

ljharb commented 5 years ago

@Mouvedia see https://github.com/keithamus/proposal-array-last for "negative arrays"

Mouvedia commented 5 years ago

Actually I am interested in negative indexes; a method wouldn't fit the bill.

ljharb commented 5 years ago

@Mouvedia let's discuss that on that proposal's repo then :-)

Mouvedia commented 5 years ago

@ljharb sadly, I know already that it's impossible using unproxied Array, that's why I am asking here :) cf keithamus/proposal-array-last#1

StoneCypher commented 5 years ago

I like negative array index calls, but they're a pretty separate issue than this. I'd like them to not bury this in the discussion please 😄

littledan commented 5 years ago

Let's follow up on feature idea brainstorming in #16.

StoneCypher commented 5 years ago

I really wish you'd stop closing my tickets, dan