Как часовое устройство node предлагает преимущества по сравнению с NULL?

Ответ 1

Нет никаких преимуществ с часовыми, если вы просто выполняете простую итерацию и не смотрите на данные в элементах.

Однако существует некоторый реальный выигрыш при использовании его для алгоритмов типа "найти". Например, представьте список связанных списков std::list, где вы хотите найти определенное значение x.

То, что вы сделали бы без часовых, будет:

for (iterator i=list.begin(); i!=list.end(); ++i) // first branch here
{
  if (*i == x) // second branch here
    return i;
}
return list.end();

Но с часовыми (конечно, конец действительно должен быть настоящим node для этого...):

iterator i=list.begin();
*list.end() = x;

while (*i != x) // just this branch!
  ++i;

return i;

Вы видите, что нет необходимости в проверке дополнительной ветки для конца списка - всегда гарантируется, что вы всегда будете возвращать значение end(), если x не может быть найдено в вашем "действительном" элементы.

Для другого прохладного и действительно полезного применения часовых см. "intro-sort", который является алгоритмом сортировки, который использовался в большинстве реализаций std::sort. Он имеет классный вариант алгоритма разбиения, который использует часовые для удаления нескольких ветвей.

Ответ 2

Я думаю, что пример небольшого кода будет лучшим объяснением, чем теоретическое обсуждение.

Ниже приведен код для удаления node в двусвязном списке узлов, где NULL используется для отметки конца списка и где два указателя first и last используются для хранения адрес первого и последнего node:

// Using NULL and pointers for first and last
if (n->prev) n->prev->next = n->next;
        else first = n->next;
if (n->next) n->next->prev = n->prev;
        else last = n->prev;

и это тот же код, где вместо этого есть специальный макет node, чтобы пометить конец списка и где адрес первого node в списке сохраняется в поле next специального node и где последний node в списке сохраняется в поле prev специального макета node:

// Using the dummy node
n->prev->next = n->next;
n->next->prev = n->prev;

Такое же упрощение также присутствует для вставки node; например, чтобы вставить node n до node x (имея x == NULL или x == &dummy значение вставки в последней позиции), код будет:

// Using NULL and pointers for first and last
n->next = x;
n->prev = x ? x->prev : last;
if (n->prev) n->prev->next = n;
        else first = n;
if (n->next) n->next->prev = n;
        else last = n;

и

// Using the dummy node
n->next = x;
n->prev = x->prev;
n->next->prev = n;
n->prev->next = n;

Как вы можете видеть, что метод dummy node удален для дважды связанного списка, все специальные случаи и все условные обозначения.

Следующее изображение представляет два подхода для одного и того же списка в памяти...

Ответ 3

Ответ на ваш вопрос (1) содержится в последнем предложении связанной записи Википедии: "Как узлы, которые обычно связываются с NULL, теперь ссылаются на" nil "(в том числе на nil), это устраняет необходимость в дорогостоящем чтобы проверить значение NULL.

Обычно вам нужно протестировать node для NULL, прежде чем обращаться к нему. Если вместо этого у вас есть действительный nil node, вам не нужно делать этот первый тест, сохраняя сравнение и условную ветвь, что в противном случае может быть дорогостоящим для современных суперскалярных процессоров, когда ветвь неверно предсказана.

Ответ 4

Я попытаюсь ответить в контексте стандартной библиотеки шаблонов:

1) При вызове "next()" NULL необязательно указывает конец списка. Что делать, если произошла ошибка памяти? Возвращение стражника node является окончательным способом указать, что произошел конец списка, а не какой-то другой результат. Другими словами, NULL может указывать на множество вещей, а не только на конец списка.

2) Это всего лишь один из возможных способов: при создании списка создайте закрытый node, который не используется вне класса (например, "lastNode" )). После обнаружения того, что вы выполнили итерацию до конца списка, "next()" возвращает ссылку на "lastNode" . Также используйте метод "end()", возвращающий ссылку на "lastNode" . Наконец, в зависимости от того, как вы реализуете свой класс, вам может потребоваться переопределить оператор сравнения для правильной работы.

Пример:

class MyNode{

};

class MyList{

public:
    MyList () : lastNode();

    MyNode * next(){

       if (isLastNode) return &lastNode;
       else return //whatever comes next
    }

    MyNode * end() {

       return &lastNode;
    }

    //comparison operator
    friend bool operator == (MyNode &n1, MyNode &n2){

        return (&n1 == &n2); //check that both operands point to same memory
    }


private:
    MyNode lastNode;
};


int main(){

  MyList list;
  MyNode * node = list.next();

  while ( node != list.end() ){ 

     //do stuff!

     node = list.next();
  }

  return 0; 
}