std :: list를 사용해야합니까, 아니면 더 좋은 방법이 있습니까?

Question

저는 현재 C++의 2D 지오메트리 편집기로 코딩하고 있습니다. 사용자 장소 노드가 있습니다. 두 개의 노드를 선택하여 선과 호를 그릴 수 있습니다.

지금 당장 노드의 주소를 각 행/호에 저장하고 싶기 때문에 노드를 std :: deque 컨테이너 (선과 호가 동일한 항목)에 저장하고 있습니다. 이것은 노드 이동을위한 기능을 구현할 때 매우 편리하게 코딩 할 수있게 해줍니다. 각 행/호 안에 실제 노드를 저장하려면 노드를 이동하려는 경우 전체 행과 호 구조를 반복하여 노드를 찾은 다음 매개 변수를 방금 업데이트해야합니다. 이 옵션은 테이블의 옵션이 아닙니다. 따라서, 각 라인/아크 내부에 노드의 어드레스를 저장할 필요가있다.

그러나 노드를 삭제해야하는 문제가 있습니다. 레퍼런스 매뉴얼을 보면 모든 포인터에 대해 deque에서 엘리먼트를 지울 때 (모든 엘리먼트가 처음이나 끝에 있지 않다면) 무효화 된 것으로 보인다. (논의를 위해서 나는이 경우를 고려하지 않을 것이다) . 이로 인해 지우기와 관련된 문제가 발생합니다. 이제는 모든 라인/아크가 다른 노드에 다시 연결되거나 노드가 지워지고 프로그램이 결국 중단 될 수 있기 때문입니다.

온라인으로 계속해서 보니, 요소 중 하나가 지워졌을 때 어떤 포인터 나 참조를 무효화하지 않는 std :: list를 보았습니다. 이것은 내 문제에 대한 아주 좋은 해결책 인 것 같다.

그러나 스택 오버 플로우를 살펴본 결과 목록과 대기열을 사용할 때의 이점과 단점을 확인했습니다. 그리고 deque와 list를 사용하는 것이 더 선호되는 것처럼 보입니다. 리스트가 deque에 접근하는 것이 더 느린 것 같습니다. 사용자가 그리려는 노드의 수를 모르기 때문에 좋지 않습니다. 내가 아는 한, 기하학에 10,000 개 이상의 노드가있을 수 있으며 사용자가 노드를 이동하려는 경우 사용자가 노드를 찾기 위해 모든 요소를 ​​반복하는 데 30 초를 기다리지 않아도됩니다. (들)을 지울 수 있습니다.

한편으로는 deque가 훨씬 빠르지 만 요소가 제거 되 자마자 모든 포인터와 참조가 무효화됩니다. 반면 std :: list를 사용하면 포인터와 참조 중 하나를 무효화하지 않고 원하는 모든 요소를 ​​지울 수 있지만 deque와 비교할 때 속도가 느립니다.

목록이 더 느리더라도 포인터와 참조를 무효화하지 않고 요소를 지울 수 없으면 프로그램이 작동하지 않으면 속도가 현저하게 떨어 지므로 목록으로 전환 할 것을 고려 중입니다. 일하지 마라.

그러나 내 상황에서는 목록을 사용하는 것이 가장 좋습니다. deque를 사용할 방법이 있습니까? 아니면 제가 고려하지 않은 세 번째 옵션이 있습니까?

편집 :

나는 깜빡합니다. 내가 목록을 좋아하지 않는 한 가지는 요소의 데이터를 직접 가져올 수 없다는 것입니다 (std :: deque 및 vector에서는 at 함수를 사용하여 요소에 액세스 할 수 있습니다). 이것은 내 코드를 다루는 큰 문제가 아닙니다. 그러나 그것은 편리하게 만듭니다. 예를 들어, 사용자가 선/호를 만들 때 노드를 선택하면 코드는 전체 노드 목록을 반복하여 선택한 노드를 찾은 다음 첫 번째 선택을 위해 인덱스를 변수에 저장합니다. firstNodeIndex). 두 번째 노드의 경우 동일한 작업을 수행하지만 두 변수 (firstNodeIndex 및 secondNodeIndex)가 실행 가능한 숫자이면 행/호를 작성하는 함수가 호출되고 함수는 저장된 두 개의 인덱스를 사용하여 노드 목록에 다시 액세스합니다. 노드에 주소를 부여하십시오.목록을 사용하려면 두 노드의 주소를 변수에 저장 한 다음 두 노드에 대한 주소를 포함하는 두 변수가 실행 가능한 옵션인지 확인하기 위해 몇 가지 추가 논리를 작성해야합니다.

또 다른 해결책은 전체 노드 목록을 다시 반복하여 선택한 노드를 잡아내는 것입니다 (선택한 노드를 나타 내기 위해 각 노드 내부에 변수가 있습니다). 그러나 이것이 std :: list 제한을 고려할 때 좋은 생각이 아닐 수도 있습니다.

내 첫 번째 방법에 찬성 가지 생각하지만 필요하다면 변경을 열어주는 말들 또는 더 나은 방법

Answer 1

따라서 요소를 삽입하거나 지울 때 반복기가 무효화되는 것을 원하지 않지만 데이터 구조가 빠르다는 것이 문제입니다.

링크 된 목록은 모든 요소를 ​​자주 반복해야하는 경우에만 느립니다. In은 vector 나 deque와 같은 연속적인 데이터 접근을 이용하지 않습니다. 또한 목록에서 선형 검색이 느립니다.

비슷한 상황이 있습니다. 다음은 몇 가지 옵션입니다.

1. 목록을 사용하여 선형 검색을 피하십시오. 연결된 목록의 메모리 액세스 속도가 성능에 큰 영향을 미치는지, 그렇지 않은 경우 사용하는지 확인하십시오.

2. 지도 또는 세트를 사용하십시오. 검색 (O (logn))을 제외하고리스트와 같은 단점. 또는 정렬 요소에 신경 쓰지 않으면 정렬되지 않은 버전을 사용할 수 있습니다.

3. plf::colony과 같은 비표준 데이터 구조를 사용하십시오. 삽입 순서에 신경 쓰지 않는다면 아마도 이것이 최선의 선택 일 것입니다.

4. 이터레이터를 무효화하지 않는 (skipfields를 사용하거나 어딘가에 자유 요소를 저장하는) 자체 deque-like 데이터 구조를 만듭니다. 어쨌든 plf::colony과 같은 것을 작성하게 될 것이므로 추천하지 않습니다.

Answer 2

엄지 손가락의 규칙이있는 경우 :

내가 추가하고 삭제할 것 무작위로 항목?

set, list, map, multimap and unordered versions of same 

개별 항목의 이름을 지정하고 빠르게 찾을 수 있기를 원하십니까?

map, set, multimap and unordered versions of same 

내가 저장하고있는 것은 변경 가능한 데이터가 있습니까, 아니면 이름 (키)보다 더 자세히 설명되어 있습니까?

map, multimap, unordered versions thereof 

순서대로 말할 항목이 필요합니까?

yes: map, no: unordered_map