Словари в AS3 (не Dictionary)
 

Возник вопрос - что, в ActionScript3 API нет нормальной реализации словаря?

Из стандартных решений (ActionScript3 Common Collections не в счёт, это сторонняя разработка) я нашёл возможность задания словаря только через Object и Dictionary (смотрел в документации, собственно, и немного по форумам). Использовать их как-то не особо охота - у них, мягко говоря, не очень дружественный интерфейс. Чего только удаление элементов через delete стоит и тот факт, что если попытаться в качестве ключа использовать что-нибудь кроме строки, он вообще некорректно работает.

Dictionary

Нормальной реализации как в других языках нет, увы.
Ниразу не неблюдал ничего подобного. Dictionary нормально работает и со сложными объектами в качестве ключа

gagaga, читайте тему внимательнее, перед тем как отвечать.

Попробуйте выполнить вот такой код:
Он у меня возвращает:
second movie
second movie

Я сам виноват. Тему назвал реально криво, а где переиминовать - не знаю.

изменить - расширеный режим и там должен быть заголовок
Ну само собой. Object не умеет использовать сложные объекты как ключи.
А так:
Работать будет.

Спасибо! Действительно работает. Но всё-таки API не очень приятное.

Хочу как-нибудь попробовать то, что вот тут

Только надо помнить что это AS3 и простое использование функции getX(i) уже снизит производительность раз в 5 по сравнению с простым доступом к элементу массива.
Так что сторонние либы есть смысл использовать только если коллекции действительно не могут сделать того что нужно, тут чем нативнее тем лучше.

Нужен Set - заменяем Dictionary, как бы маразматически не выглядело set[x] = x или set[x] = true вместо set.Add(x).
Но если нам нужно поддержание порядка в Set - тот тут ничего не попишешь - придется сочинять свои, нетривиальные вещи, чтобы это эффективно работало (ну или вот, по библиотекам шариться).

Не могу утверждать, так как не смотрел, но что-то мне подсказывает, что эта либа так же построена поверх Dictionary и Object

Да построена поверх.
Но есть 2 интересных штуки: SortedList и SortedMap, которые Dictionary не заменишь никак (хотя сами его используют)
плюс там где-то реализована сортировка слиянием - единственная широко известная _стабильная_ сортировка с временим O(n * lon n) (во флеш встроена какая-то нестабильная, возможно qsort)
Т.е. полезная либа, не смотря на то что Set и StringSet там ничего толкового не делают - только работу замедляют.

LinkedList в наивной (как там) реализации - тоже злое зло - начинает обгонять массив на произвольных удалениях и вставках только при очень больших значениях - а всё потому, что память без дела выделяется под Node.

Тут нужно сам объект использовать как узел(добавить ему prev/next) - мы же всё равно память под него выделяем - тогда добавление в список не жрёт столько времени.

Можно ещё с пулом нодов экспериментировать, тогда список начнёт обгонять массив пораньше.

Можно ещё раскладывать линкованный список в массиве (ну как кучу раскладывают в массив - можно разложить и список, тогда при удалении объекта просто перебиваются значения-индексы в паре мест этого массива, запоминается пустое место (запоминается в конце того же массива для последующего добавления элемента в дырку) а не двигается всё что было после этого элемента)
Но начинает обгонять простой массив на случайных вставках на числах > 100, на 10000 элементов было только в 8 раз быстрее. Вдобавок написание такого списка немного выносит мозг.

Код по ссылке - ну не совсем бесполезный, конечно, но оставляет желать много лучшего по следующим причинам:
1. писатели пытались скопировать устройство из Явы, и поэтому написали много дурацкого и / или бесполезного кода.
2. писатели не знали, как на самом деле должны работать те или иные вещи (например, списки у них добавляют в конец, а не в начало).
3. в библиотеке нет даже необходимого минимума для работы с коллекциями, типа сортировки, поиска, удаления, конкатенации и т.п. Поскольку п. 1. то людям не пришло в голову использовать функции высшего порядка для реализации таких идей. В общем случае код плохо расширяемый / бессистемный.

Но так чтобы сказать "не используйте это, потому, что есть лучше" - увы, я не в курсе про "лучше", мне не попадалось. Из практических соображений (т.е. скорость работы / тривиальность подавляющего большинства задач, которые приходится решать), отсутствие менее тривиальных коллекций очень редко когда сильно мешало.

Кроме всего прочего, стоит заметить очень наивные реализации всего, что там заявлено и плохое понимание основ AS3. Например:

комментарии мои.

Опять же, комментарий мой. Наивность реализации заключается в том, что для сортированной хеш-таблицы было бы куда выгоднее использовать массив, или два массива, вместо использования двух (а в реальности трех) хеш таблиц.

Proxy

Они там по-ходу хеши используют для связки значения с узлом, а из самих узлов строят AVL-дерево, которым всё это сортируют.

С теоретической точки всё правильно:
Добавление:

O(1) на один хеш + O(1) на другой + O(log n) для добавления в дерево.
И того O(log n)

А с массивами надо было бы искать место вставки O(log n) + пододвигать элементы справа O(n).
И того O(n) - оценка хуже

Но это в теории.
А на практике вряд ли это будет работать быстрее (может быть только на очень больших числах), потому что создание объекта-узла в динамической памяти дорого, плюс куча операций и вызовов функций.

Может я и напрасно назвал эти сортированные коллекции интересными.
SortedList только в динамической памяти не мусорит и должен показать приемлемую скорость.

А мне ascommons нравятся. Правда юзаю только log, reflect и async.

Ну так это опять же, наивная реализация. Можно же сделать B+tree из массивов, например. Ну и не добавлением единым, есть еще много других операций. Наверняка тот, кто будет использовать такую коллекцию создает ее для того, чтобы сортировать.

Или, еще вариант: можно оставлять "окна" для последующих вставок.
Тут еще опять же варианты, что важнее, память, скорость и скорость каких именно операций. Возможно, список был бы лучше, потому что расход памяти минимальный. Нужно эксперементировать, и почти наверняка в коллекции претендующей на универсальность должно быть несколько стратегий, и несколько специально заготовленных функций, которые умеют их использовать по максимуму. Пример такой функции: одновременное добавление нескольких элементов.

Можно попробовать разложить дерево в массив и сохранять список индексов, из которых удалялись элементы (один элемент - значение, 2 следующих - индекс правого и левого поддерева)
Хотя AVL-дерево так эффективно как куча на массив не ляжет. Плюс там линкованный список разложить на массив - уже весело, а реализовывать вращение поддеревьев, которые лежат в массиве - там сплошное жонглирование индексами будет (и не продебажить - у тебя линейная структура с индексами заплетёнными в клубок)

Вот в AS3 всегда так: нельзя просто взять и реализовать эффективный алгоритм с Википедии - накладные расходы на поддержание структуры данных весь прирост съедят. Да и в Java, наверно, с этим не легче.