Выбор между векторами и связными списками

Имея в распоряжении все средства для работы со связным списком, можем переделать рассмотренную в начале лекции программу об удалении элемента в заданной позиции, заменив вектора списками:

#include "integer_list.hpp"

// Функция сообщения о некорректной позиции

voidreportPositionError ()

{

std::cout << "Error: invalid position specified." << std::endl;

}

// Функция распечатки результата программы

voidprintResult ( const IntegerList & _l )

{

std::cout << "Result: ";

IntegerListPrint( _l, std::cout );

std::cout << std::endl;

}

intmain ()

{

// Создаем и инициализируем список

IntegerList l;

IntegerListInit( l );

// Вводим числа до ввода 0

std::cout << "Input integers, stop with zero: ";

IntegerListReadTillZero( l, std::cin );

// Вводим позицию, которую требуется удалить

std::cout << "Input position to delete: ";

intposition2Delete;

std::cin >> position2Delete;

// Проверяем позицию на некорректность (нижняя граница)

if( position2Delete < 0 || IntegerListIsEmpty( l ) )

reportPositionError();

// Специальный случай - удаление первого элемента

else if( position2Delete == 0 )

{

IntegerListPopFront( l );

printResult( l );

}

Else

{

// Общий случай. Находим узел-предшественник интересующей позиции

intcurrentIndex = 0;

IntegerList::Node * pCurrentNode = l.m_pFirst;

while( pCurrentNode && ( currentIndex + 1 ) < position2Delete )

{

pCurrentNode = pCurrentNode->m_pNext;

++currentIndex;

}

// Проверяем корректность введенной позиции (верхняя граница)

if( ! pCurrentNode || l.m_pLast == pCurrentNode )

reportPositionError();

Else

{

// Удаляем элемент списка

IntegerListDeleteAfter( l, pCurrentNode );

// Печатаем результирующую последовательность

printResult( l );

}

}

// Освобождаем память списка

IntegerListDestroy( l );

}

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

Еще один существенный минус связных список по сравнению с векторами состоит в нерациональном использовании памяти. Каждый узел выделяется в куче отдельной аллокацией. Узлы являются маленькими структурами, и при большом количестве узлов только лишь за счет “невидимой” служебной доли каждой динамической аллокации будет наблюдаться существенный расход памяти. Кроме того, поскольку время выделения памяти в куче мало зависит от выделяемого объема в байтах, N небольших выделений динамической памяти однозначно работает существенно медленней одного большого выделения памяти.

Утверждение, что вставка/удаление элементов в произвольной позиции в векторах работает медленнее, чем в списках, также может быть опровергнуто при определенных обстоятельствах. Строго говоря, это утверждение может не выполняться для небольших последовательностей (5-7 элементов) на большинстве современных компьютеров. Такая аномалия может быть связана с нюансами работы кэш-памяти. Как известно, элементы векторов соседствуют в физической памяти и с высокой долей вероятности будут считываться в кэш-память при обращении одновременно. Элементы же списков, напротив, скорее всего попадут в совершенно разные области физической памяти и чаще всего не будут находиться в кэш-памяти одновременно при последовательном проходе. В зависимости от свойств аппаратного обеспечения конкретного компьютера, время выполнения сдвига нескольких ячеек, находящихся рядом в более быстрой кэш-памяти может быть меньшим, чем время нескольких обращений к более медленным чипам оперативной памяти.

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

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