Создается класс, реализующий map<double,X> и unordered_map<X,X>, который состоит из фиксированной части и массива «записей». Массив может менять свой размер, фиксированная часть - нет. Этот класс реализует объект javascript если быть совсем точным. Зачем - ну допустим потом объясню.
map реализовано через skip-list, это по сути double-linked list, но со ссылками для быстрого проскока значений с шагом 2,4,8,...
unordered_map делаю через хэши и фиксированный набор корзин. такой способ может порождать много коллизий, и рехешировать это дело или увеличивать колво корзин не хочется. поэтому возникла первая идея:
пусть N=hash%Nbuckets, K=hash/Nbuckets. Тогда для каждой корзины можно создать свой скип-лист, где ключем будет K. это позволит иметь логарифмическую сложность даже если одна корзина перегружена.
вторая идея: а пусть «неупорядоченный список» вообще весь будет реализован отдельным скиплистом, как и упорядоченный. Но в него будет не один вход как в упорядоченный, а Nbuckets входов. Ключом в обоих списках является double, но для unordered - это будет double((2^51-1)&((hash<<51-5)^hash)) и Nbuckets=32.
Поскольку движок использует inline cache для запоминания индексов, то околологарифмический поиск будет не сильно долбать т.к. будет происходить с большинстве случаев лишь на первом поиске. Обычный unordered_map в конце концов это тоже массив списков, у меня получается немного оптимизированный с одной стороны массив и немного деоптимизированный с другой.
Хороша ли идея на первый взгляд?
Заранее говорю, что задачи сделать збс как в v8 не стоит. Это очень специфический компилятор JS, задача которого быстро прототипировать код, на лету потыкать палкой что отвалилось. Если будет не очень но не совсем ужас-ужас, то вроде как и не ужас.
