История изменений

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

Делать список массивами тебе понадобится только если нужно список читать линейно, т.е. в нем нужно что-то искать. Если в нем нужно что-то искать по одному критерию, то можно сделать binary tree, это ведь тоже список. И это будет куда быстрее, чем линейный поиск для достаточно больших деревьев (100+ элементов). Например, если у наших потоков есть приоритеты, то нужна heap (очередь с приоритетами).

Нет никаких проблем иметь несколько heap/search tree в случае интрузивных структур, это не требует каких-то дополнительных аллокаций (память под ссылки требует, да).

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

Делать список массивами тебе понадобится только если нужно список читать линейно, т.е. в нем нужно что-то искать. Если в нем нужно что-то искать по одному критерию, то можно сделать binary tree, это ведь тоже список. И это будет куда быстрее, чем линейный поиск для достаточно больших деревьев (100+ элементов). Например, если у наших потоков есть приоритеты, то нужна heap (очередь с приоритетами).