Процедуру удаления элемента из двухуровневого массива
я здесь приводить не буду. Ее код можно найти в файле, приложенном к статье.
Больший интерес представляет функция поиска индекса в двухуровневом массиве.
Существуют ситуации, когда нужно найти значение, ассоциированное с ключом, и если его нет, то вставить некоторое значение, ассоциированное с этим ключом. Если для решения этой задачи воспользоваться
отдельными процедурами поиска и вставки, то общее время удвоится, так как
процедура вставки (перед непосредственной вставкой значения) производит поиск
места вставки, т.е. имеет место повторное (непродуктивное) выполнение по сути
одной и той же операции (поиска). В принципе, если при поиске запоминать
найденную позицию, то процедура вставки могла бы воспользоваться результатами
функции поиска (при условии, что между поиском и вставкой не было никаких
действий). Однако это привело бы к тому, что пользователя класса пришлось
допустить в дебри реализации данной коллекции, и надежность работы алгоритмов, построенных по такому принципу, была бы крайне низка. С целью оптимизации я
решил создать метод, который пытался бы найти ключ и, если не нашел, вставлял
бы некоторое значение «по умолчанию» и позиционировался на него (а если нашел, то просто позиционировался). Это позволяет избавиться от лишней операции поиска
в описанных выше случаях, так как после этой операции пользователь получает
возможность работать с текущим значением (значением, на которое произошло
позиционирование). При этом для чтения или модификации значения не требуется
производить повторный поиск. Функцию, производящую позиционирование (или
вставку и позиционирование), я решил назвать NavigateOrInsertDefault. Вот ее
код:
public bool NavigateOrInsertDefault(K Key)
{
bool result =
this.NavigateKey(Key);
if (!result)
{
// Нет такого элемента. Вставляем в
текущую позицию.
Insert(Key);
// Помещаем в текущую позицию значение по
умолчанию.