나는 얼마 동안 텍스트 편집기에서 작업 해왔다. 처음부터 사용자 정의 편집 컨트롤을 만들었으므로 지금은 기본 사항을 가지고 있습니다. 내가 직면하고있는 문제는 회선 관리에 관한 것입니다. 내 프로그램은 입력 텍스트를 줄 단위로 나누기 때문에 (줄 단위로 텍스트가 인쇄됩니다.) 줄 관리가 매우 중요합니다. std :: vector를 사용하여 줄 위치를 저장했습니다. 내 텍스트 처리를 위해 Piece Table을 사용하고 있지만, 단순화를 위해 문자 배열을 사용한다고 가정 해 보겠습니다. 사용자가 엔터를 누를 때마다 요소를 선 벡터에 추가/삽입합니다. 문제는 사용자가 문자를 삽입 할 때마다 전체 구조가 방해 받는다는 것입니다. 예를 들면 다음과 같습니다 때문에 삽입의텍스트 편집기에서 줄 관리
0 1 2 3 4 5 6 7 8 9 10 11
text = ['h','e','l','x','l','o','\n','W','o','r','l','d']
state of line vector :
line[0] = 0
line[1] = 6
, 나는 각각의 값을 업데이트해야합니다 :
0 1 2 3 4 5 6 7 8 9 10
text = ['h','e','l','l','o','\n','W','o','r','l','d']
state of line vector :
line[0] = 0
line[1] = 6
는 이제 사용자가 텍스트 [2] 이후 ('X') 문자를 삽입한다고 가정 해 봅시다 현재 행 뒤의 행 벡터에있는 요소. 삭제시에도 마찬가지입니다. 프로그램에 1000 줄이 있고 사용자가 첫 번째 줄을 편집하면 999 개의 요소 (첫 번째 요소 제외)를 모두 업데이트하는 것은 상당히 비효율적입니다.
내가 생각했던 것은 각 줄을 서로 독립적으로 유지하는 것이 었습니다. 그러나 기존 라인이 두 라인으로 나뉘어지면 합병증이 생길 수 있습니다. 그래서 나는 문제에 대해 좋은 방법이 무엇인지 알고 싶습니다.
편집 : 분명히하기 위해 피스 테이블이라는 데이터 구조를 사용하고 있습니다. 나는 일련의 문자들을 사용하지 않고있다. 다음은 조각 테이블 데이터 구조입니다. http://www.cs.unm.edu/~crowley/papers/sds.pdf
저렴한 삽입물을 지원하려면 벡터 <>가 잘못된 데이터 구조입니다. O (n) 복잡성. <> 목록을 고려 했습니까? –
@HansPassant 목록에 요소 당 줄을 저장한다는 것은 한 줄에서 다른 줄로 이동하는 데 비용이 많이 든다는 뜻입니다. (한 줄을 다른 줄로 옮기는 것보다 일반적으로 줄을 삽입하는 것이 일반적 일 수 있음) –
당신이 풀려고하는 문제를 설명했습니다. 예를 들어, N 번째 라인에 O (1) 액세스가 필요합니까, 아니면 O (N)이 수행합니까? (그렇다면 벡터에 줄의 길이를 유지하고 필요할 경우 추가 할 수 있습니다.) – Neil