~/talk

Word's one data structure

on YouTube 06m
Talkat CppCon 2016 · 2016-09-18..09-23· [c-and-cpp]

speaker

name:Ravi Pinjala
links:none on file

resources

video:https://youtu.be/8OjSDaaySDA
slides:none on file

summary

Flat arrays map character offsets to attached objects using C-style positions[] and data[] arrays; instead of touching every entry on insert the structure records an adjustment point (index and delta) so updates cost O(distance from last edit) and lookups remain O(log n). While typing the last binary-search result is cached as a search hint, making common-case edits effectively constant time. This exact scheme underlies many Word features and is proven practical in production.

AI-written summary · about

chapters (5)

  1. 0:00Introduction
  2. 0:55Data Structure
  3. 2:45Recording Changes
  4. 3:27Making Changes
  5. 4:10Conclusion

related talks

~/search
type to search 6,249 conferences, 138,987 speakers and 185,172 talks
~/help
cmdctrl k
search every conference, speaker and series
/
focus the filter search
h
home
c
conferences
s
speakers
e
series
t
light / dark — the status bar button does the same
?
this help
esc
close this, then clear every filter — or just the search, while you are typing in it

Ignored while you are typing. Pages without a filter rail have no search to focus.