Mezera mezery - Gap buffer

Mezera vyrovnávací paměti v výpočetní techniky je dynamické pole , který umožňuje efektivní vkládání a mazání operace clusterů v blízkosti na stejném místě. Vyrovnávací paměti mezer jsou obzvláště běžné v textových editorech , kde většina změn textu nastává na aktuálním místě kurzoru nebo v jeho blízkosti . Text je uložen ve velké vyrovnávací paměti ve dvou sousedících segmentech, přičemž mezi nimi je mezera pro vložení nového textu. Pohyb kurzoru zahrnuje kopírování textu z jedné strany mezery na druhou (někdy se kopírování zpozdí až do další operace, která změní text). Vložení přidá nový text na konec prvního segmentu; vymazání to smaže.

Text ve vyrovnávací paměti mezery je reprezentován jako dva řetězce , které zabírají jen velmi málo místa navíc a které lze ve srovnání s propracovanějšími datovými strukturami, jako jsou propojené seznamy, prohledávat a zobrazovat velmi rychle . Operace na různých místech v textu a na těch, které vyplňují mezeru (vyžadující vytvoření nové mezery), však mohou vyžadovat kopírování většiny textu, což je zvláště neúčinné pro velké soubory. Použití mezerových vyrovnávacích pamětí je založeno na předpokladu, že k takovému překódování dochází zřídka natolik, že jeho náklady mohou být amortizovány během běžnějších levných operací. Díky tomu je vyrovnávací paměť mezery jednodušší alternativou k lanu pro použití v textových editorech, jako je Emacs .

Příklad

Níže uvádíme několik příkladů operací s mezerami ve vyrovnávací paměti. Mezeru představuje prázdné místo mezi hranatými závorkami. Tato reprezentace je trochu zavádějící: v typické implementaci jsou koncové body mezery sledovány pomocí ukazatelů nebo indexů pole a obsah mezery je ignorován; to umožňuje například odstranění, které lze provést úpravou ukazatele beze změny textu ve vyrovnávací paměti. Běžnou programovací praxí je použití polootevřeného intervalu pro ukazatele mezery, tj. Začátek mezery ukazuje na neplatný znak následující za posledním znakem v první vyrovnávací paměti a konec mezery ukazuje na první mezeru platný znak ve druhé vyrovnávací paměti (nebo ekvivalentně jsou ukazatele považovány za body „mezi“ znaky).

Počáteční stav: 

This is the way [                     ]out.

Uživatel vloží nový text: 

This is the way the world started [   ]out.

Uživatel pohybuje kurzorem před „spuštěním“; systém přesune "spuštěno" z prvního bufferu do druhého bufferu. 

This is the way the world [   ]started out.

Uživatel přidá text vyplňující mezeru; systém vytváří novou mezeru: 

This is the way the world as we know it [                   ]started out.

Viz také

Reference

externí odkazy