Структура данных для медиа-плейлиста?

Question

С первого взгляда двойной связанный список кажется разумным, но по мере того, как я начал внедрять, я столкнулся с проблемой отслеживания текущей позиции. Я использовал std :: list iterator, но работа с крайними случаями (см. Следующую часть) стала болью. Так вот требование к DS:

• сохранить порядок элементов
• Эффективного введения в середине
• Вставка/стирает не отменяют итераторы
• O (N) произвольный доступ не является проблема

Соединительный список подходит для этого.

Требование к текущей позиции курсора (итератор):

• Двунаправленного
• Изначально обозначает end положения
• При итераторе в end положения, после вставки элемента в конце концов, в следующем итераторе вперед будет двигаться это к этому элементу. Такое же поведение, если ранее список воспроизведения был пуст
• же в противоположном случае: итератор в начале, push_front, двигаясь в обратном направлении будет идти вновь добавленный элемент

Каковы лучшие практики по его реализации? Есть ли для него библиотеки (C++)?

Answer 1

std::list - это контейнер, который поддерживает постоянную установку времени и удаление элементов из любого места в контейнере. Быстрый случайный доступ не поддерживается (что не является проблемой в вашем случае). Он обычно реализуется как двусвязный список. По сравнению с std::forward_list этот контейнер обеспечивает возможность двунаправленной итерации при меньшем пространстве.

Добавление, удаление и перемещение элементов в списке или в нескольких списках не отменяет итераторов или ссылок. Итератор недействителен только при удалении соответствующего элемента.

С моей точки зрения std::list идеально подходит для описанной вами проблемы.