GapBuffer: Header-Only C++17 Text Editor Data Structure

Overview

GapBuffer is a header-only, fully-templated C++17 implementation of the gap buffer data structure — the foundational text-editor buffer used historically by Emacs. The core innovation is maintaining a contiguous internal gap at the cursor position, making insertions and deletions at the cursor O(1) amortized while preserving O(1) random access via transparent index translation. The implementation features a random-access iterator (GapBufferIterator<T>) that satisfies std::sort requirements, complete Rule-of-Five compliance with timing-validated move semantics (<10 microseconds for 10,000-element moves), the Scott Meyers const-cast idiom for DRY const/non-const overloads, STL-compatible type aliases and comparison operators, and a 2x doubling reallocation strategy with two-phase element transfer. The 41-test Qt Test harness covers edge cases including pathological self-assignment chains ((buf = buf = buf) = buf), nested GapBuffer<GapBuffer<int>> containers, and std::sort compatibility verification.

Gap Buffer: Physical Memory Layout

[ element_0 ... element_{cursor-1} | GAP_SLOTS | element_{cursor} ... element_{n-1} ]
  ^─── pre-cursor content ─────^    ^── gap ──^   ^─── post-cursor content ─────^

Five member variables track the buffer state:

Fundamental invariant: _buffer_size == _logical_size + _gap_size must always hold.

Core Operations

O(1) Amortized Insertion at Cursor

void insert_at_cursor(const_reference element) {
    if (_gap_size == 0) reserve(2 * _buffer_size);  // 2x doubling
    _elems[_cursor_index++] = element;
    ++_logical_size;
    --_gap_size;
}

The element is placed directly into the gap slot at _cursor_index. When the gap is exhausted, the buffer doubles in size. An rvalue overload uses std::move(element) to avoid copying expensive types (e.g., GapBuffer<std::vector<int>>).

O(1) Deletion at Cursor (Backspace Semantics)

void delete_at_cursor() {
    if (_cursor_index > 0) {
        --_cursor_index;
        --_logical_size;
        ++_gap_size;
    }
}

No data is physically moved — the cursor retreats one position, growing the gap to “absorb” the element. Deletion at position 0 is a safe no-op.

O(|delta|) Cursor Movement

void move_cursor(int delta) {
    if (delta > 0) {
        // Moving right: shift elements from after gap to before gap
        std::move(begin_after_gap, begin_after_gap + delta, cursor_position);
    } else {
        // Moving left: shift elements from before gap to after gap
        std::move(cursor_position + delta, cursor_position, destination_after_gap);
    }
    _cursor_index += delta;
}

Transparent Index Translation

The gap is invisible to external users. Two private helpers translate between logical (external) and physical (array) indices:

size_type to_array_index(size_type external_index) const {
    if (external_index < _cursor_index) return external_index;        // Before gap: identity
    else return external_index + _gap_size;                           // After gap: skip gap
}

size_type to_external_index(size_type array_index) const {
    if (array_index < _cursor_index) return array_index;              // Before gap: identity
    else if (array_index >= _cursor_index + _gap_size)
        return array_index - _gap_size;                               // After gap: subtract gap
    else throw std::string("Inside gap: invalid");
}

Memory Management: 2x Doubling Reallocation

void reserve(size_type new_size) {
    if (_logical_size >= new_size) return;              // No shrinking
    auto new_elems = new T[new_size];
    std::move(_elems, _elems + _cursor_index, new_elems);           // Phase 1: pre-gap
    size_t new_gap_size = new_size - _logical_size;
    std::move(_elems + _cursor_index + _gap_size,
              _elems + _buffer_size,
              new_elems + _cursor_index + new_gap_size);             // Phase 2: post-gap
    delete[] _elems;
    _elems = new_elems;
    _buffer_size = new_size;
    _gap_size = new_gap_size;
}

Two-phase element transfer: Pre-cursor elements are moved first, then post-cursor elements are repositioned after the enlarged gap. The old array is delete[]‘d only after the new one is fully populated — if new throws, _elems still points to valid data. Uses std::move for element transfer, avoiding unnecessary copies of complex types.

Rule-of-Five: Complete Value Semantics

Scott Meyers Const-Cast Idiom

Non-const access methods delegate to their const counterparts to avoid code duplication:

reference get_at_cursor() {
    return const_cast<reference>(
        static_cast<const GapBuffer*>(this)->get_at_cursor()
    );
}

This pattern appears in get_at_cursor(), at(), and operator[].

Random-Access Iterator

GapBufferIterator<T> stores a pointer to the owning GapBuffer and a logical index (not array index). Dereferencing calls _pointee->at(_index), which handles gap translation transparently.

The constructor is private — only GapBuffer<T> (declared friend) can create iterators. Users obtain them via begin(), end(), or cursor() (a gap-buffer-specific method returning an iterator at the cursor position).

STL Compatibility

The iterator satisfies random-access iterator requirements, verified by std::sort compatibility in the test suite (TEST5F).

STL-Compatible Operator Overloads

Performance Characteristics

Why Gap Buffers Excel for Text Editing

The gap buffer is optimal when edits are strongly localized (typing, backspacing, small cursor movements) — exactly the dominant pattern in text editors.

Test Suite (41 Qt Test Cases)

Edge cases tested: empty buffer ops, single-element buffers, deletion at position 0 (no-op), reserve smaller than logical size (no-op), self-assignment (buf = buf), chained self-assignment ((buf = buf = buf) = buf), self-move-assignment, nested containers (GapBuffer<std::vector<int>>, GapBuffer<GapBuffer<int>>).

Tech Stack

C++17, Qt (qmake build system), Qt Test (QTest framework), STL (std::move, std::equal, std::lexicographical_compare, std::fill, std::initializer_list)