Структура данных для медиа-плейлиста?
На первый взгляд двойной связанный список кажется разумным, но когда я начал внедрять, я столкнулся с проблемой отслеживания текущей позиции. Я использовал итератор std :: list, но работа с крайними случаями (см. Следующую часть) стала проблемой.
Итак, вот требования к DS:
- Сохранить порядок элементов
- Эффективная вставка в середине
- Вставки / стирания не делают недействительными итераторы
- O (N) произвольный доступ не проблема
Связанный список подходит лучше всего для этого.
Требования к текущей позиции курсора (итератор):
- Двунаправленный
- Изначально обозначает
endпозиция - Когда итератор в
endпозиция, после вставки элемента в конце, следующий шаг итератора переместит его в этот элемент. Такое же поведение, если ранее плейлист был пуст - То же самое для противоположного случая: итератор в начале,
push_frontперемещение назад приведет к добавлению нового элемента
Каковы лучшие практики для его реализации? Есть ли библиотеки для этого (C ++)?
Решение
std::list это контейнер, который поддерживает постоянное время вставки и удаления элементов из любой точки контейнера. Быстрый произвольный доступ не поддерживается (что не является проблемой в вашем случае). Обычно он реализуется в виде двусвязного списка. По сравнению с std::forward_list этот контейнер обеспечивает возможность двунаправленной итерации, при этом занимая меньше места.
Добавление, удаление и перемещение элементов в списке или в нескольких списках не делает недействительными итераторы или ссылки. Итератор становится недействительным только при удалении соответствующего элемента.
С моей точки зрения std::list идеально подходит для описанной вами проблемы.
Другие решения
Других решений пока нет …