Czytaj książkę: «Компоновщик. Паттерн GoF на Python, C++23, Rust и Java»
Введение
Эта книга посвящена одному паттерну проектирования — Компоновщик (Composite). Он относится к каталогу «Банды четырёх» (Gang of Four, GoF). Здесь паттерн разобран сразу в четырёх реализациях: на Python, C++23, Rust и Java. Каждая реализация — отдельная часть книги: сначала задача и общая схема, затем код, модификации, гибридные варианты и самостоятельные работы.
Как читать
Основы каждого языка здесь не повторяются: они собраны в книгах серий по соответствующему языку. Разделы каждой части нумеруются заново, поэтому ссылка «раздел 1.2» указывает на раздел той же части, где она сделана.
Глава 8. Реализация на Python
8.1. Зачем нужен компоновщик
Файловая система состоит из файлов и папок, а папки содержат файлы и другие папки. Меню состоит из пунктов и подменю. Заказ — из товаров и наборов товаров. Во всех случаях мы имеем дерево, и хочется обращаться с одиночным элементом и с группой одинаково: «посчитай размер», «покажи», «найди».
Компоновщик объединяет объекты в древовидные структуры и даёт листьям и контейнерам общий интерфейс. Клиент вызывает size() у корня и не думает, сколько там уровней вложенности: контейнер сам передаст вызов детям и сложит результаты.
В Python компоновщик естественно сочетается с рекурсией, генераторами (yield from) и протоколами контейнеров (__iter__, __len__).
8.2. Участники и схема

Component — общий интерфейс листьев и контейнеров.
Leaf — элемент без детей, делает реальную работу.
Composite — хранит детей и делегирует им операции.
8.3. Классический пример: файловая система
Файл 01_filesystem.py :

Листинг 8.1 — Классический пример: файловая система

Листинг 8.1 (продолжение) — Классический пример: файловая система
Разбор. Folder.size складывает размеры детей, не зная, файлы это или папки: каждый ребёнок сам умеет отвечать. Пустая папка корректно даёт 0 — sum от пустого генератора равен нулю. show — генератор, и yield from передаёт наверх строки из поддеревьев любой глубины. add возвращает self, поэтому вызовы можно сцеплять.
8.4. Обход дерева и поиск
Файл 02_traversal.py :

Листинг 8.2 — Обход дерева и поиск

Листинг 8.2 (продолжение) — Обход дерева и поиск
Разбор. Здесь лист и контейнер — один класс: лист — это узел без детей. Такой «прозрачный» компоновщик проще, а у набора может быть и собственная цена (упаковка за 1500). __iter__ делает дерево итерируемым, и вся мощь Python — генераторные выражения, sum, any, max — работает над деревом без отдельных функций обхода. walk дополнительно отдаёт путь к узлу.
8.5. Модификации паттерна
Компоновщик выражений
Арифметическое выражение — дерево: числа — листья, операции — контейнеры.
Файл 03_expressions.py :

Листинг 8.3 — Модификации паттерна

Листинг 8.3 (продолжение) — Модификации паттерна
Разбор. У операции может быть сколько угодно аргументов, и любой аргумент — лист или поддерево. str и eval рекурсивны и одинаково работают на любом уровне. FUNCS объявлен в теле класса без аннотации, поэтому dataclass не считает его полем.
Параллельное вычисление поддеревьев
Если листья дорогие (сетевой запрос, тяжёлое вычисление), контейнер может обрабатывать детей параллельно.
Файл 04_parallel_composite.py :

Листинг 8.4 — Модификации паттерна

Листинг 8.4 (продолжение) — Модификации паттерна
Разбор. Group.check запускает проверки детей одновременно через asyncio.gather. Вложенные группы делают то же, так что всё дерево проверяется примерно за время самого медленного сервиса (0,2 с), а не за сумму. gather сохраняет порядок результатов, поэтому вывод детерминирован.
8.6. Самостоятельные работы
Работа 1. Меню ресторана
Задание. Постройте меню из разделов и блюд. Выведите его с отступами, посчитайте число блюд и найдите все вегетарианские.
Полное решение — файл 05_menu.py :

Листинг 8.5 — Самостоятельные работы

Листинг 8.5 (продолжение) — Самостоятельные работы
Разбор. Метод dishes превращает дерево в плоский поток листьев. Над этим потоком дальше работают обычные функции Python. Блюдо может лежать прямо в корне, рядом с разделами.
Работа 2. Оргструктура и бюджет
Задание. Отделы содержат сотрудников и подотделы. Посчитайте фонд оплаты труда каждого отдела и найдите самый дорогой подотдел верхнего уровня.
Полное решение — файл 06_org.py :

Листинг 8.6 — Самостоятельные работы

Листинг 8.6 (продолжение) — Самостоятельные работы
Разбор. Две операции компоновщика — payroll и headcount — устроены одинаково: лист отвечает за себя, контейнер суммирует детей. max(…, key=Department.payroll) передаёт несвязанный метод как функцию ключа.
8.7. Типичные ошибки
Циклы в дереве. Если папку добавить в саму себя, рекурсия станет бесконечной. Проверяйте при add, что узел не является предком.
Слишком глубокие деревья. Рекурсия в Python ограничена (по умолчанию около 1000 уровней). Для очень глубоких структур нужен итеративный обход со стеком.
Повторный пересчёт. Folder.show вызывает size() на каждом уровне — для больших деревьев это квадратичная сложность. Кешируйте результат или считайте за один проход.
Методы контейнера у листа. В «прозрачном» варианте у листа есть add, который не имеет смысла. Решите заранее: безопасность (методы только у контейнера) или единообразие.
8.8. Вопросы для самопроверки
Какую структуру данных описывает компоновщик?
Чем лист отличается от контейнера?
Зачем в обходе нужен yield from?
Что даёт реализация __iter__ у узла дерева?
Как компоновщик сочетается с asyncio.gather?
Чем опасна вложенность папки в саму себя?
В чём разница между «прозрачным» и «безопасным» компоновщиком?
Почему sum по пустому контейнеру — корректное поведение?
8.9. Ответы
Дерево «часть — целое».
Лист выполняет работу сам, контейнер делегирует её детям и объединяет результаты.
Он передаёт наверх все значения генератора поддерева.
Возможность обходить дерево циклом for и использовать встроенные функции Python.
Контейнер запускает операции детей параллельно и объединяет результаты.
Бесконечной рекурсией при любой операции.
В прозрачном методы работы с детьми есть у всех узлов; в безопасном — только у контейнеров.
Сумма пустой последовательности равна нулю — это верный размер пустой папки.
Глава 8. Реализация на C++23
8.1. Структуры «часть — целое»
В интернет-магазине отдельный товар можно положить в коробку, а несколько коробок — в большую коробку. При расчёте общей стоимости клиенту нужно обработать и отдельные товары, и составные упаковки. Похожая задача возникает в файловых системах, графических сценах, организационных структурах и синтаксических деревьях.
Composite представляет отдельные и составные объекты через общий интерфейс. Лист выполняет операцию непосредственно; составной узел делегирует её детям и объединяет результаты. Паттерн входит в группу структурных паттернов GoF.
Однообразный интерфейс упрощает клиента, но не отменяет различий между листом и контейнером. В частности, не у каждого узла логически есть операция добавления потомков. Выбор места таких методов создаёт компромисс между прозрачностью и проверкой допустимых операций типами.
8.2. Участники и устройство
Component задаёт общий интерфейс операций.
Leaf представляет отдельный объект без детей.
Composite хранит дочерние компоненты и объединяет их поведение.
Client вызывает общую операцию, не разбирая структуру вручную.

В дереве владения C++ удобно хранить детей через std::vector<std::unique_ptr<Component>>. Это выражает одного владельца каждого узла. Если листья действительно разделяются между ветками, может подойти shared_ptr<const T>, но тогда структура уже может быть DAG, а правила обратных ссылок и обхода меняются.
8.3. Применимость и последствия
Паттерн полезен, когда клиент должен одинаково применять операции к отдельным и составным объектам. Рекурсивная структура естественно выражает вложенность. Недостатки включают дополнительную иерархию, необходимость контролировать допустимые виды детей, возможную глубокую рекурсию и цену полного обхода.
Владелец должен определить, допускаются ли циклы, кто уничтожает дочерние объекты и что происходит с невладеющими ссылками при удалении узла. Кэширование требует правил инвалидирования; совместное изменение дерева требует синхронизации. Утверждения о производительности нужно проверять на реальных данных.
8.4. Классический пример: товары, упаковка и доставка
Product возвращает цену товара, а Box добавляет стоимость своей упаковки и стоимость детей. Снаружи к сумме добавляется фиксированная стоимость доставки. Все суммы в примере — небольшие целые значения в условных минимальных денежных единицах; производственный расчёт должен проверять валюту, отрицательные значения и переполнение.

Листинг 8.1 — Классический пример: товары, упаковка и доставка

Листинг 8.1 (продолжение) — Классический пример: товары, упаковка и доставка
Разбор. Component задаёт общую операцию стоимости. Product возвращает цену товара, а Box хранит детей с единоличным владением и суммирует их стоимость вместе со своей упаковкой. Вложенная коробка обрабатывается тем же вызовом, что и товар.
При выходе из main корневая коробка уничтожает дочерние компоненты через виртуальные деструкторы. Отдельно прибавляется фиксированная стоимость доставки. Пример не синхронизирует изменение дерева и не проверяет переполнение или отрицательные суммы.
Пример вывода:

8.5. Восемь разновидностей и связанных подходов
1. Composite for Transparency — прозрачный интерфейс
Операции управления детьми объявляются в общем интерфейсе. Клиент может вызвать их через Component, но лист должен сообщить, что добавление или удаление недопустимо. Работа 1 возвращает такую ошибку через std::expected.
2. Composite for Type Safety — типобезопасный интерфейс
Методы добавления и удаления находятся только у контейнера. Попытка вызвать их непосредственно у листа не проходит проверку типов. Цена — через общий интерфейс Component эти операции недоступны. Работа 2 проверяет разницу с помощью концепта и static_assert.
3. Parent-Pointer / Bidirectional Composite
Дочерний узел хранит невладеющую ссылку на родителя, что позволяет подниматься по дереву, например распространять событие фокуса. Владелец должен гарантировать, что родитель жив дольше ребёнка, и обновлять ссылку при перемещении узла. Работа 3 не предоставляет отсоединение и запрещает копирование узлов.
4. Caching Composite
Контейнер кэширует итог обхода, а изменение листа инвалидирует кэши предков. Это уменьшает повторные вычисления, но усложняет все операции изменения. Работа 4 рассчитывает размеры для моделей с общим началом координат; перемещения и повороты не учитываются.
5. Ordered / Indexed Composite
Потомки хранятся в определённом порядке, например по Z-индексу. При одинаковых индексах важно определить порядок. Работа 5 применяет стабильную сортировку и сохраняет порядок добавления элементов с равным Z.
6. Flyweight-Shared Composite / DAG
Неизменяемый лист может использоваться несколькими ветвями через shared_ptr<const T>. Одна и та же структура хранится один раз, но логический обход по двум рёбрам может обработать её дважды. Работа 6 разделяет числовой лист выражения. Одного shared_ptr недостаточно, чтобы запретить циклы или изменение через другие псевдонимы.
7. Visitor-Enabled / Algebraic Composite
Типы узлов можно представить через std::variant, а операцию вынести в std::visit. Рекурсивные варианты нуждаются в косвенном хранении, например unique_ptr. Работа 7 вычисляет небольшое дерево сложения.
8. Flattened / Data-Oriented Composite
Узлы располагаются в одном векторе, а связи задаются индексами первого ребёнка и следующего соседа. Это меняет организацию памяти и может улучшить локальность, но эффект зависит от задачи и требует измерения. Работа 8 предполагает корректные ациклические индексы и не является обобщённым валидатором графов.
8.6. Связанные решения
Fork / Join & Work Stealing — Composite + Command + Iterator
Большую задачу можно разделить на независимые части и распределить между рабочими потоками. В работе 10 каждый поток имеет собственную очередь диапазонов QuickSort: он забирает свои задачи с одного конца, а при отсутствии может украсть задачу из очереди другого работника. Счётчик незавершённых задач позволяет определить окончание работы.
Пример демонстрирует механизм, а не промышленный планировщик. Разбиение массивов выполняется по непересекающимся диапазонам; вектор нельзя параллельно менять по размеру. При неудачном выборе опорного элемента QuickSort может работать квадратично. Повторные запуски проверяют результат, но не доказывают отсутствие всех ошибок параллелизма.
Darmowy fragment się skończył.