미디어 재생 목록의 데이터 구조는 무엇입니까?

Question

첫눈에 이중 연결 목록은 합리적인 것처럼 보이지만 구현하기 시작하면서 현재 위치를 추적하는 문제에 직면했습니다. std :: list iterator를 사용했지만 극단적 인 경우 (다음 부분 참조)를 처리하는 것은 고통이되었습니다. 그래서 여기 DS에 대한 요구 사항 :

• 의 요소의 순서
• 효과적인 삽입 유지 중간
• 삽입/반복기
• O (N), 랜덤 액세스가 아닌 무효화하지 지워 문제

연결된 목록이 가장 적합합니다. 현재 위치에 커서 (반복자) 용

요건 :

• 양방향
• 처음에 end 위치를 나타낸다
• end 위치 반복자 결국 소자를 삽입 한 후, 다음 반복기 어드밴스 이동 이 요소에. 같은 재생 목록이 반대의 경우에 대한
• 동일 비어 이전하는 경우의 행동 : 처음에 반복자는, push_front는 뒤쪽으로 이동하면 새로 추가 된 요소

를 구현하는 가장 좋은 방법은 무엇을 갈 것인가? 그것을위한 라이브러리가 있습니까 (C++)?

Answer 1

std::list은 컨테이너의 어느 곳에서나 요소의 일정 시간 삽입 및 제거를 지원하는 컨테이너입니다. 빠른 임의 액세스는 지원되지 않습니다 (어떤 경우에는 문제가되지 않습니다). 일반적으로 이중 연결 목록으로 구현됩니다. std::forward_list과 비교하여이 컨테이너는 양방향 반복 기능을 제공하지만 공간 효율성은 떨어집니다.

목록에서 요소를 제거하거나 여러 목록에 걸쳐 요소를 제거하고 이동해도 반복기 또는 참조가 무효화되지 않습니다. 이터레이터는 해당 요소가 삭제 될 때만 무효화됩니다.

올린 사람 내 관점 std::list은 당신이 설명한 문제에 딱 맞습니다.