История изменений
Исправление alysnix, (текущая версия) :
В моём бенчмарке обрабатывалось как раз самое сложное для массива - реаллокация при росте.
в своем «бенчмарке» ты сравнивал время аллокирования N байт на хипменеджере, с временем сдвига M байт в памяти. Такое сравнивать конечно можно…но смысла большого в этом нет.
список это упорядоченное множество произвольных элементов, а массив это N элементов ОДНОГО типа, лежащих друг за другом… которые тоже выражают собой казалось бы «упорядоченное множество», НО это вовсе не так.
при рандомной вставке/удалении(а мы расматриваем только такую вставку) в список, все указатели на другие элементы остаются валидными. при рандомной вставке/удалении в массив индексы последующих элементов становятся невалидными(из за сдвига). то есть не все алгоритмы, работающие на списках, могут быть отображены на массивы.
также список хорош тем, что не имеет ограничений по длине. массив имеет.
на самом то деле большинство нормального софта сделано с использованием списков. пример - оконный менеджер - окна провязаны в списки, например по Z порядку. менеджер памяти - имеются списки свободных блоков. компиляторы - списки локальных обьектов или бинарные деревья из них, геймдев - всякие там физ обьекты, частицы…да и вообще все. я не могу придумать такого реально сложного кода, где можно обойтись без списков. списки разумеется свои, где линки встроены в обьект,но можно юзать и обобщенные, если это не влияет на производительность.
Исходная версия alysnix, :
В моём бенчмарке обрабатывалось как раз самое сложное для массива - реаллокация при росте.
в своем «бенчмарке» ты сравнивал время аллокирования N байт на хипменеджере, с временем сдвига M байт в памяти. Такое сравнивать конечно можно…но смысла большого в этом нет.
список это упорядоченное множество произвольных элементов, а массив это N элементов лежащих друг за другом… которые тоже выражают собой казалось бы «упорядоченное множество», НО это вовсе не так.
при рандомной вставке/удалении(а мы расматриваем только такую вставку) в список, все указатели на другие элементы остаются валидными. при рандомной вставке/удалении в массив индексы последующих элементов становятся невалидными(из за сдвига). то есть не все алгоритмы, работающие на списках, могут быть отображены на массивы.
также список хорош тем, что не имеет ограничений по длине. массив имеет.
на самом то деле большинство нормального софта сделано с использованием списков. пример - оконный менеджер - окна провязаны в списки, например по Z порядку. менеджер памяти - имеются списки свободных блоков. компиляторы - списки локальных обьектов или бинарные деревья из них, геймдев - всякие там физ обьекты, частицы…да и вообще все. я не могу придумать такого реально сложного кода, где можно обойтись без списков. списки разумеется свои, где линки встроены в обьект,но можно юзать и обобщенные, если это не влияет на производительность.