# 텍스트 편집기의 데이터 구조 > Clean Markdown view of GeekNews topic #9393. Use the original source for factual precision when an external source URL is present. ## Metadata - GeekNews HTML: [https://news.hada.io/topic?id=9393](https://news.hada.io/topic?id=9393) - GeekNews Markdown: [https://news.hada.io/topic/9393.md](https://news.hada.io/topic/9393.md) - Type: news - Author: [kuroneko](https://news.hada.io/@kuroneko) - Published: 2023-06-14T16:10:46+09:00 - Updated: 2023-06-14T16:10:46+09:00 - Original source: [cdacamar.github.io](https://cdacamar.github.io/data%20structures/algorithms/benchmarking/text%20editors/c++/editor-data-structures/) - Points: 69 - Comments: 2 ## Topic Body - 나만의 텍스트 편집기를 만들기 위해, 직접 텍스트 데이터 구조를 만들어 보는 과정. - 텍스트 편집기는 거대한 파일을 편집하거나, 다중 커서, 실행/취소 등 다양한 기능에 의해 그 구조를 만들기가 매우 어려움. - 이에 데이터 구조에 요구되는 기능은 다음과 같음. - 효율적인 삽입/삭제 - 효율적인 실행 취소/다시 실행 - UTF-8 인코딩을 사용 가능 - 효율적인 다중 커서 편집 - Gap Buffer는 구현이 간단하지만, 실행 취소와 다중 커서 기능을 구현하기 매우 어려움. - Rope는 큰 파일을 작은 크기로 분할하여 수정이 가능해 효율적이지만, 실행 취소 기능을 위해선 오버헤드가 커지고 메모리 사용량이 예상보다 많이 늘어날 수 있음. - Piece Table은 Microsoft Word에서 사용했을 정도로 효율적인 구조지만, 편집을 많이 할 경우 성능이 저하되고 실행 취소를 위해 메모리 사용량이 늘어날 수 있음. - Piece Tree는 위의 모든 단점을 해결하기 위해 VSCode 팀에서 구현한 텍스트 편집기를 위한 가장 좋은 데이터 구조임. - Rope와 Piece Table의 장점만을 골라 구현함. - 조각 간의 연결을 위해 RB Tree를 쓰기 때문에 많은 편집이 있더라도 여전히 효율적임. - 다만 VSCode 팀에서 구현한 버전은 불변 데이터 구조가 아니기 때문에 실행 취소 기능에서 약간의 비효율성을 가짐. - 데이터 구조에 불변성을 추가해 모든 문제를 해결한 새로운 Piece Tree를 구현하기로 함. - 전통적인 RB 트리는 불변성을 줄 수 없어 Bartosz Milewski가 구현한 불변 RB 트리를 참조하여 구현 시작. - VSCode 팀에서 구현한 구조와 차이점은 다음과 같음. - 에디터가 Carriage Return 문자를 고려해야 하는 경우가 적기 때문에 CRLF를 별도로 기록하지 않음. - 디버깅을 위해 전체 버퍼를 반복자와 같은 형태로 확인할 수 있는 API를 추가함. - 데이터 구조가 불변이기 때문에 실행 취소/다시 실행이 아주 간단함. - 삭제 기능을 구현하는 것이 가장 어려웠지만, 결국 구현에 성공함. - 새로 작성한 데이터 구조를 [fredbuf](https://github.com/cdacamar/fredbuf)라는 이름으로 공개함. ## Comments ### Comment 16529 - Author: junghan0611 - Created: 2023-06-15T05:42:40+09:00 - Points: 1 오! 감사합니다. 이런 귀한 정보가! 이맥스를 제대로 사용하기 시작하면서 텍스트 편집기 그 자체에 관심이 많이 생기네요. 원문도 찬찬히 봐야겠어요! :-) ### Comment 16525 - Author: cosine20 - Created: 2023-06-14T17:50:42+09:00 - Points: 1 상세히 요약해주셔서 감사합니다. 텍스트 편집기의 데이터 구조는 어떻게 구현하는걸까 한 번쯤 고민해본 적이 있는데 이런 자료구조가 쓰이는군요.