Michael (mstone) wrote,
Michael
mstone

Разворачиваем список правильно

Задачка на разворачивание односвязного списока задом наперёд и некоторые её вариации очень популярны на программистских интервью. Несмотря на её бесполезность при оценке пригодности кандидата к практической работе, из задачки можно неожиданно много выжать в качестве упражнения по кодированию на С++.

Шаг 0. Традиционное решение

Как выглядит традиционное решение? Сначала определяем стуктуру node для представления узла списка. Полагаем, что в каждом узле хранится какой-то payload, который нас в рамках данной задачи не волнует, и указатель на следующий узел (в последнем узле он будет нулевым):
struct node
{
    ...
    node *pnext;
};
Искомая функция получает указатель на голову списка, переворачивает список и возвращает указатель на голову перевёрнутого списка:
node *reverse(node *phead)
{
    node *prhead = nullptr; // Здесь в итоге окажется указатель на голову перевёрнутого списка.

    while (phead != nullptr)
    {
        node *p = phead->pnext;
        phead->pnext = prhead;
        prhead = phead;
        phead = p;
    }

    return prhead;
}
Решение простое, работающее, и, если речь идёт о техническом интервью, обычно достаточное. Тем не менее, этот простой код можно неоднократно улучшить, а в процессе улучшения открыть для себя много нового и интересного. Этим мы и займёмся.

DISCLAIMER: Важно помнить о разнице между "уметь водить машину" и "уметь сдавать на права". Средний уровень владения C++ в индустрии находится на уровне "Си с классами", поэтому на техническом интервью в большинстве компаний описываемые ниже улучшения кода могут не только не встретить понимания, но, хуже того, понизить ваши шансы.

Шаг 1. Повышаем уровень абстракции

Для начала обратим внимание, что функция жёстко завязана на тип структуры node, но при этом из всего содержимого структуры обращается только к члену pnext. Нет никаких причин, почему бы нашей функции не работать с любой структурой, в которой есть указатель pnext на структуру того же типа. Решение очевидно: параметризуем функцию типом узла списка, превратив её в шаблон:
template <typename Node> Node *reverse(Node *phead)
{
    Node *prhead = nullptr; // Здесь в итоге окажется указатель на голову перевёрнутого списка.

    while (phead != nullptr)
    {
        Node *p = phead->pnext;
        phead->pnext = prhead;
        prhead = phead;
        phead = p;
    }

    return prhead;
}
Если бы стандарт C++ поддерживал концепты, мы бы ещё явным образом указали требование наличия поля pnext нужного типа у шаблонного параметра Node, и потом любовались бы простым и понятным сообщением об ошибке при попытке инстанцировать класс с неподходящим типом. Но концептов в C++ пока что нету, поэтому просто порадуемся тому, что ошибка выловится и вывалится на этапе компиляции, а не в рантайме [Сноска: если очень хочется, вопрос можно решить, хотя и несколько громоздко, через темлейтную метамагию. Идея хорошо описана здесь]. Кроме того, как мы увидим ниже, неуказание явного типа для Node->pnext добавляет шаблону гибкости.

Шаг 2. Прекращаем врать

Теперь смотрим на сигнатуру функции:
template <typename Node> Node *reverse(Node *phead)
Функция принимает указатель на голову исходного списка и возвращает указатель на голову перевёрнутого списка. Глядя на такую сигнатуру, можно подумать, что возвращаемый указатель указывает на голову нового списка, представляющего собой перевёрнутую копию исходного. На самом же деле функция переворачивает список in-place, то есть модифицирует исходный список, а не создаёт новый. Поскольку весь смысл функции состоит в том, чтобы произвести побочный эффект, прекращаем вводить читателя-пользователя функции в заблуждение и заменяем возвращаемый тип на void:
template <typename Node> void reverse(Node *phead)
{
    Node *prhead = nullptr; // Здесь в итоге окажется указатель на голову перевёрнутого списка.

    while (phead != nullptr)
    {
        Node *p = phead->pnext;
        phead->pnext = prhead;
        prhead = phead;
        phead = p;
    }

    return prhead; // Ошибка компиляции.
}

Шаг 3. Совсем прекращаем врать

Теперь наша функция не компилируется, как бы намекая, что полуправда иногда хуже лжи. Проблема в том, что, заменив возвращаемый тип функции на void, мы потеряли возможность вернуть указатель на новую голову списка. Что же делать? Кто сказал "добавить output параметр"? А вы в курсе, что каждый раз, когда вы добавляете в функцию output параметр, где-то умирает котёнок? Ладно, ладно, не хватайтесь за сердце. На этот раз котёнку ничего не угрожает: превращать функцию в void и одновременно вводить output параметр было бы шагом в неверном направлении: от лжи к изощрённой лжи, а не к правде.

Поскольку наша функция модифицирует исходный список, будет вполне естественно, если параметр phead, который на входе в функцию содержит указатель на голову списка, по окончании работы функции будет указывать на голову модифицированного списка. Чтобы модифицировать указатель, нужно получить его не по значению, а по ссылке, превратив input параметр в input-output параметр:
template <typename Node> void reverse(Node*& phead)
{
    Node *prhead = nullptr; // Здесь в итоге окажется указатель на голову перевёрнутого списка.

    while (phead != nullptr)
    {
        Node *p = phead->pnext;
        phead->pnext = prhead;
        prhead = phead;
        phead = p;
    }

    phead = prhead;
}
Input-output параметр, конечно, тоже сомнительной красоты конструкция, но тут уж грех на зеркало пенять, коли рожа крива. Выбор реализации, в которой список модифицируется in-place неизбежно приносит функциональную чистоту кода в жертву производительности, и input-output параметр -- всего лишь следствие этого выбора. Зато теперь у нас всё действительно по-честному и in-place-ность реализации гордо и недвусмысленно анонсирована в сигнатуре функции, а не заметена стыдливо под ковёр.

Шаг 4. Делаем тайное явным

А теперь самое интересное. Задумаемся о том, что хотя и в условии задачи, и в обсуждении реализации центральным объектом является список, в коде никаких списков не наблюдается, только узлы. Попробуем определить тип списка явно, исходя из определения понятия списка.

Для начала вспомним бытовое определение списка: упорядоченная последовательность объектов типа T, возможно пустая. В С++ есть несколько готовых реализаций для представления упорядоченной последовательности, но они нам не годятся, поскольку наша задача как раз реализовать своё представление списка, а не использовать готовое. Мы должны объяснить компилятору как реализуется наш список, а не что он собой представляет.

По счастью, у списка есть и другое определение, рекурсивное, приоткрывающее завесу над внутренним устройством: список либо пуст, либо состоит из элемента типа T (голова) и списка (хвост) [Сноска: это самое распространённое, но не единственно возможное рекурсивное определение списка. Главное, оно лучше всего нам подходит]. На первый взгляд, под это определение хорошо ложится структура Node: в ней хранится что-то полезное плюс указатель на следующий узел [Сноска: в коде полезная нагрузка не упоминается, но мы предполагаем, что она есть: из узла, в котором нет ничего, кроме указателя на следующий узел, пользу извлечь, конечно, можно, но это отдельное теоретическое упражнение сродни определению нумералов Чёрча в лямбда-исчислении]. Указатель на следующий узел при этом автоматически указывает и на хвост списка, для которого следующий узел является, в свою очередь, головой. Что же получается, структура Node и есть список? Не совсем, но близко. Помимо того, что это звучит противоестественно -- узел списка и сам список, очевидно, разные вещи -- с помощью структуры Node невозможно представить пустой список, поскольку там всегда будет как минимум один элемент.

В выбранной нами реализации пустой список представляется нулевым указателем. А непустой? (Ненулевым) указателем на Node. То есть список всегда представлен указателем. А раз так, может быть указатель и есть список? Рефлекторной реакцией на такое допущение будет "Как может указатель быть списком? Список содержит кучу элементов, а указатель вообще ничего не содержит, только адрес. Можно, пожалуй, сказать, что указатель на Node содержит адрес списка, но сказать, что указатель сам является списком -- явный перебор". Требуется, однако, совсем небольшое усилие, чтобы идея перестала казаться такой уж бредовой. Достаточно вспомнить, как устроены языки с сборкой мусора, такие как Java или C#. Про эти языки иногда можно услышать, что они "не поддерживают указатели", хотя на самом деле они, за небольшими исключениями [Сноска: встроенные примитивные типы, а в C# ещё и определяемые пользователем типы-значения], вообще не оперируют объектами, а только указателями. Если в программе на C++ определён класс Foo и функция void f(Foo foo), то при вызове функции в параметр foo будет записан объект класса Foo -- копия того объекта, который передала вызывающая функция. А в C#/Java при вызове функции никакого копирования не произойдёт, а в параметр foo будет записан указатель на объект, переданный вызывающей функцией. Переменная или параметр функции типа Foo в C#/Java реализованы внутри как указатели на объект класса Foo. И это никого не смущает: если из языка убрать возможность оперировать объектами напрямую, оставив только указатели, то несложно сделать вид, что указатели и есть сами объекты. В С++ такой терминологический трюк на уровне языка провернуть не получится (да и не надо), поскольку с любыми объектами можно оперировать как напрямую (сохраняя семантику значений), так и через указатели, но никто не мешает нам это сделать для отдельного типа. Более того, это довольно логично, поскольку у списка в том виде, в котором мы его определяем, нет семантики значений: не просто так же мы сразу сказали, что в функцию, оперирующую со списком, передаётся не список, а указатель на голову списка. А раз со списком нельзя оперировать иначе как через указатель на головной узел списка, то вполне естественно, в духе C#/Java, заявить, что указатель на узел и есть список. Поскольку тип узла передаётся в функцию как шаблонный параметр-тип, мы просто заменяем один шаблонный параметр на другой:
template <typename List> void reverse(List& phead)
{
    List prhead = nullptr; // Здесь в итоге окажется указатель на голову перевёрнутого списка.

    while (phead != nullptr)
    {
        List p = phead->pnext;
        phead->pnext = prhead;
        prhead = phead;
        phead = p;
    }

    phead = prhead;
}
Что интересно, к тому же определению можно прийти и обратным путём: начать с написания идеологически правильной сигнатуры функции и из неё вывести тип списка. Обратный путь будет даже проще.

Функция совершает операцию над списком, значит входным параметром должен быть объект-список. Функция модифицирует объект in-place, значит, объект должен быть передан по неконстантной ссылке (если бы менять объект in-place не требовалось, мы бы передали его по значению или по константной ссылке). Новых объектов функция не создаёт и не возвращает, значит тип возврата -- void. Получаем сигнатуру
void reverse(List& list)
Сопоставив её с сигнатурой реализации
template <typename Node> void reverse(Node*& phead)
получаем
List ≡ Node*

Шаг 5. Совсем-совсем прекращаем врать

Теперь внимательно посмотрим на тело функции и перечислим операции, которые совершаются с объектами типа List:

1. Присваивание объекту значения nullptr.
2. Проверка объекта на равенство значению nullptr.
3. Использование оператора -> для обращения к члену pnext.

Заметим, что все эти операции применимы не только к обычным указателям, но и к "умным указателям" (smart pointers) -- типам, переопределяющим оператор -> и реализующим семантику указателей с дополнительной логикой. Таким образом, избавившись от явного упоминания указателей путём замены Node* на List, мы получили неожиданный бонус: теперь pnext в узлах списка может быть произвольным умным указателем! Ну, почти получили. Для окончательного счастья понадобится ещё одна модификация.

Шаблон функции reverse в его текущем виде не будет работать для умных указателей с семантикой владения, таких как unique_ptr<T>. Семантика владения предполагает, что указатель-владелец в своём деструкторе удаляет объект, на который он указывает, поэтому, если мы не хотим поиметь двойное удаление объекта, на любой "владеемый" объект в каждый момент времени может ссылаться один и только один умный указатель. Появившаяся в C++11 поддержка move-семантики позволяет выразить это ограничение напрямую: для умных указателей с семантикой владения определяют только move-конструктор и move-оператор присваивания, и подавляют традиционные копирующий конструктор и копирующий оператор присваивания. В результате попытка создать копию такого указателя приводит к ошибке компиляции. Компилятор откажется инстанцировать шаблон функции reverse с типом указателя unique_ptr<T>, поскольку на каждой итерации цикла функция копирует указатели аж четыре раза, и ещё один раз в самом конце.

Однако легко заметить, что нас просто снова наказывают за враньё: целью производимых в теле цикла манипуляций является циклическое перемещение трёх указателей. Создание копий для этого совершенно не требуется. И если мы честно напишем в коде, что указатели перемещаются (move), а не копируются, всё сразу встанет на свои места. Как это сделать? Принудительно привести (cast) копируемые указатели к категории rvalue. Функция принудительного приведения к rvalue (неслучайно) называется std::move():
#include <utility>

template <typename List> void reverse(List& phead)
{
    List prhead = nullptr;  // Здесь в итоге окажется указатель на голову перевёрнутого списка.

    while (phead != nullptr)
    {
        List p       = std::move(phead->pnext);
        phead->pnext = std::move(prhead);
        prhead       = std::move(phead);
        phead        = std::move(p);
    }

    phead = std::move(prhead);
}
Вот такую функцию уже не стыдно и людям показать, и в репозиторий зачекинить. Не забыв при этом, конечно, юнит-тестов добавить.

Выводы

Большинство улучшений кода, которые мы осуществили, заключались просто в использовании наиболее подходящих средств языка для выражения действий алгоритма. Для этого требуется не только хорошо владеть языком, на котором кодируется алгоритм, но и понимать, что мы на самом деле хотим сделать. Как видим, это оказывается не столь очевидно даже для такой простой и известной задачи, как переворачивание списка.
Tags: c++, c++11, excercise, programming
  • Post a new comment

    Error

    default userpic
  • 0 comments