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

 

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

 

#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 элементов) на большинстве современных компьютеров. Такая аномалия может быть связана с нюансами работы кэш-памяти. Как известно, элементы векторов соседствуют в физической памяти и с высокой долей вероятности будут считываться в кэш-память при обращении одновременно. Элементы же списков, напротив, скорее всего попадут в совершенно разные области физической памяти и чаще всего не будут находиться в кэш-памяти одновременно при последовательном проходе. В зависимости от свойств аппаратного обеспечения конкретного компьютера, время выполнения сдвига нескольких ячеек, находящихся рядом в более быстрой кэш-памяти может быть меньшим, чем время нескольких обращений к более медленным чипам оперативной памяти.

 

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

 

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








Дата добавления: 2016-01-29; просмотров: 1008;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.005 сек.