Список внутри словаря

[metaclass]

А вот как правильно сделать такую иммутабельную функциональную структуру данных:

есть словарь(map) из строк в качестве ключей и некоей структуры в качестве значений. Причем эта структура содержит внутри себя список. Для простоты можно считать что структура и есть просто список.
И задача - заполнить оный словарь имея список пар "строка-ключ, значение для списка". Ключи в списке пар повторяются. Короче, что-то вроде "select key,list(value) from KeyValuePairs group by key".

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

Comments

[gds.livejournal.com]

правильно -- в зависимости от того, что делают с ключами потом, для доступа по ним. В среднем случае -- какое-нибудь avl tree (есть доказанно-корректная реализация, если чо), значения которого хранят эти самые list(value) (либо список, либо finger trees).
А вот как такое строить -- есть разные идеи. Если очень хочется эффективности, можно сделать слияние деревьев, где для слияния значений будет использоваться какая-нибудь из эффективных форм склеивания содержимого (для списков -- зависит от списков и семантики языка, для finger trees -- всё однозначно).