Мертвы ли списки? C

#c #память #структуры_данных #data_structures

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

struct Node{
    void *data;
    struct Node *next;
}


Появились следующие вопросы:


Как затратней, realloc или моя реализация?
Почему создатель связного списка его не использует?
Как работает класс vector в C++?
Почему в C++ есть аналог malloc, calloc и free (new, new [], delete), но нет аналога
realloc?


Пожалуйста приведите как реализовываете вы, как лучше, почему.

UPD


Что затратней выделять память или копировать один участок в другой (уже выделенный),
на сколько затратней?

    

Ответы

Ответ 1

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

Кеш

Все дело в кеше. В одной линии кеша располагается сразу несколько элементов массива.
Следовательно, при доступе к ним процессор не тратит много времени. А элементы связного
списка с высокой долей вероятности не попадут в одну линию кеша. Следовательно, при
обращении к очередному элементу будет промах и процессору придётся обращаться к основной
памяти.

Память

Английское название - RAM (random access memory) - память со случайным доступом -
давным-давно стало неправильным обозначением этого типа памяти. На самом деле она давно
является блочной. Кстати, русское ОЗУ (оперативное запоминающее устройство), не несёт
в своём определении такого недостатка.

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


Ответ 2

Как затратней, realloc или моя реализация?


Для чего? С точки зрения памяти, локальности, поиска, сортировки...? Как будете выделять
память - каждый раз по одному элементу или сразу раза в 2 больший буфер и поддерживать
его емкость/заполненность? Вопрос поставлен некорректно...


Почему создатель связного списка его не использует?


А "создатель" - это кто? без этого непонятно, использует ли он его или нет...

Update С тем же успехом, что считать Блоха создателем связанного списка, можно считать
собравшего из разного железа в гараже велосипед слесаря дядю Васю - создателем велосипеда.
Но дяде Васе просто некуда и незачем на нем ездить. Как и у Блоха, вероятно, нет задач,
для которых связанный список более подходящ, чем массив...


Как работает класс vector в C++?


Поддерживая буфер, увеличиваемый по заполнении в некоторое количество раз - например,
в два, так что обычно в нем есть достаточно пустого места для новых элементов. Когда
заполняется - выделяется новый буфер удвоенного размера, куда перекопируется содержимое
старого. Так что в результате амортизированное количество копирований - O(1), а все
данные хранятся в одном блоке памяти.


Почему в C++ есть аналог malloc, calloc и free (new, new[], delete), но нет аналога
realloc?


Ну, я бы не говорил, что это аналоги, уж тем более что new[] - аналог calloc. Эти
"аналоги" вызывают конструкторы и деструкторы, а при realloc это, скажем так, задача,
которую непросто решить для нетривиальных типов. Это совсем не так просто, как в С
-  перебросить память с одного места в другое...


Ответ 3

Как затратней, realloc или моя реализация?


Выделение памяти- это дорогостоящий процесс.
Именно по этому память любят выделять с запасом.

Более того, происходит копирования всего старого блока памяти на новый участок памяти
нового размера(если размер увеличивается).

Поэтому реализация без постоянного дерганья realloc более производительна.


  Как работает класс vector в C++?
  
  Типичная реализация вектора — это указатель на динамический массив.
  Размер вектора — это фактическое число элементов, а объём — количество
  используемой им памяти.
  
  Если при вставке в вектор новых элементов, его размер становится
  больше его объёма, происходит перераспределение памяти. Как правило,
  это приводит к тому, что вектор выделяет новую область хранения,
  перемещая элементы и свободные старые области в новый участок памяти.


Wiki