Реферат: Создание эффективной реализации сортированного списка с использованием generics

// Если массив верхнего уровня полностью заполнен просто увеличиваем

// его емкость в 2 раза (в Б+деревьях в этом случае выстраивается

// новыйуровень).

if (_pageCount == NodeArray.Length)

{

NodeItem[] NewNodeArray = new NodeItem[2 * _pageCount];

Array.Copy(NodeArray, 0, NewNodeArray, 0, _pageCount);

NodeArray = NewNodeArray;

}

}

}

}

Процедуру удаления элемента из двухуровневого массива я здесь приводить не буду. Ее код можно найти в файле, приложенном к статье. Больший интерес представляет функция поиска индекса в двухуровневом массиве.

Существуют ситуации, когда нужно найти значение, ассоциированное с ключом, и если его нет, то вставить некоторое значение, ассоциированное с этим ключом. Если для решения этой задачи воспользоваться отдельными процедурами поиска и вставки, то общее время удвоится, так как процедура вставки (перед непосредственной вставкой значения) производит поиск места вставки, т.е. имеет место повторное (непродуктивное) выполнение по сути одной и той же операции (поиска). В принципе, если при поиске запоминать найденную позицию, то процедура вставки могла бы воспользоваться результатами функции поиска (при условии, что между поиском и вставкой не было никаких действий). Однако это привело бы к тому, что пользователя класса пришлось допустить в дебри реализации данной коллекции, и надежность работы алгоритмов, построенных по такому принципу, была бы крайне низка. С целью оптимизации я решил создать метод, который пытался бы найти ключ и, если не нашел, вставлял бы некоторое значение «по умолчанию» и позиционировался на него (а если нашел, то просто позиционировался). Это позволяет избавиться от лишней операции поиска в описанных выше случаях, так как после этой операции пользователь получает возможность работать с текущим значением (значением, на которое произошло позиционирование). При этом для чтения или модификации значения не требуется производить повторный поиск. Функцию, производящую позиционирование (или вставку и позиционирование), я решил назвать NavigateOrInsertDefault. Вот ее код:

public bool NavigateOrInsertDefault(K Key) { bool result = this.NavigateKey(Key); if (!result) { // Нет такого элемента. Вставляем в текущую позицию. Insert(Key); // Помещаем в текущую позицию значение по умолчанию. CurrentLeafPage.PageItems[_currentElementIndex].Value = V.default; _count++; } // Стоим на нужной позиции. _selected = true; return result; }