Я довго вдивлявся в цю картинку і намагався зрозуміти, що ж таке мультіспісок, але до сих пір не розумію, як це реалізувати.
Ось мої спроби реалізувати мультіспісок.
Будь ласка наведіть приклад мультіспіска + приклад в вставки елементів.
Найпростіший спосіб реалізувати таке в C ++ - використовувати shared_ptr для зберігання даних A, B, C, D (shared_ptr - це покажчик з підрахунком посилань), і пов'язувати їх звичайним списком:
При цьому всі ресурси будуть коректно звільнятися, коли списки будуть видалятися, а списків може бути будь-яка кількість (в загальному випадку, можна побудувати граф).
Але при цьому пам'ять під самі дані виділяється динамічно, і при цьому динамічно виділяється пам'ять під кожен вузол. Лічильник посилань також може бути створений в динамічної пам'яті, якщо не використовувати make_shared.
Можна спробувати спростити підрахунок посилань (по суті, досить булева прапора - чи є вузол елементом відразу двох списків, або тільки одного), але виникає питання, як видаляти вузли, щоб не видалити два рази один і той же, і як додати один вузол в обидва списки.
У мене вийшов такий список (c ++ 14):
Вузли додаються в початок списку, тому що він односпрямований, не реалізована вставка в довільне місце і видалення довільного вузла (для видалення потрібно викликати next1.release () і next2.release (). що обнуляє покажчик, але не видаляє об'єкт, але спочатку потрібно знайти попередні елементи в обох списках)
EDIT: Видалення списку спочатку зроблено неправильно, судячи з усього. Тепер має нормально працювати.