이것은 존재할 수도 있고 존재하지 않을 수도 있지만 메모리에 연속적으로 정렬 된 합리적인 정렬 목록을 저장하는 방법을 찾고 있습니다. 합리적으로 작고 O (로그 n) 상한 삽입 및 삭제가 허용됩니다. 다양한 셀프 - 밸런싱 바이너리 검색 트리는 내가 원하는 삽입 및 삭제 속성을 갖고있는 것처럼 보이지만, 모든 곳에서 포인터로 구현됩니다. 이는 사용 사례에 잘 맞지 않습니다. 어떤 아이디어?연속 가변 순서 목록
(이 중요한 경우에 당신이 제안하는 무엇이든 기존의 구현, 모든 더 나은이있는 경우 구현 언어는 거의 확실히., C 될 것입니다,하지만 난 내 자신을 쓰기에 괜찮아요.)
binary search tree 수 array을 사용하여 구현할 수 있습니다.
이것은 사실이지만 O (log n) 인 배열 -BST에 대한 BST 균형 작업을 구현하는 방법을 보지 못했습니다. 즉, 균형이 맞지 않는 상태에서 살아야한다는 의미입니다. compact 또는 performant), 또는 O (log n) 삽입 및 삭제를 희생합니다. –
"읽음보다 많은 쓰기가 발생합니다"라는 사실에 따라 dynamicaly-resized array + binary search을 그 위에 사용할 수 있습니다. 따라서 O(log n) 시간 (원소)에 액세스 할 수 있지만 삽입/삭제 (O(log n) - 배열- 오른쪽 또는 왼쪽으로 이동하는 elemets의 적절한 위치 검색)에 O(n)을 지불해야합니다. 그것은 천천히 일종의이지만, 이것은 그것을 해결하는 방법입니다. 그것에 대해 생각해보십시오.
배열의 문제점은 요소에 대한 새로운 포인터를 'malloc'할 때 새로운 요소를 추가하기 위해 전체 배열의 크기를 조정해야한다는 것입니다. 또한 필요 이상으로 많은 메모리를 할당하므로 불필요하게 크기를 조정하지 않아도됩니다. (예 : 크기가 두 배가 될 때마다 크기가 두 배가 됨) 그래서 당신이 필요로하는 이유는 무엇입니까? 초기화 할 때 필요한 정확한 크기를 이미 알고 있습니까? – GRAYgoose124
죄송합니다, 지금까지 귀하의 의견을 보지 못했습니다. 정기적으로 압축되어 디스크로 플러시되고 나중에 앱의 다른 부분에서 읽히는 목록입니다. 읽기는 쓰기보다 많은 일이 발생하며 읽는 작업은 실제로는 deserialize 할 수 있어야하므로 파일의 내용을 가져 와서 램으로 압축을 풀고 그대로 사용하는 것이 이상적입니다. 별도의 태스크 세트가 목록을 변경시키고 변경시에는 추가 또는 삭제할 int 수를 처음부터 알고 있으므로 현재 목록과 새 int에 모두 맞도록 충분히 큰 버퍼를 할당 할 수 있습니다. –