Implementation of the Gap Buffer algorithm as C++ container and iterator

Question

Please my review my implementation of the gap buffer algorithm for efficient text editing. I am particularly interested in the following areas:

1. Have I properly implemented a C++14 container and random-access iterator? I found the spec to be a little hard to understand but I think I have everything required I hope. But in particular, have I implemented const iterators correctly?

2. There are a couple of places where I need advice on whether I've coded correctly/efficiently. They are marked by comments.

3. Any other C++ stylistic advice.

---

This is buffer.h:

// Buffer -- manages text in a text editor (Interface)
//
// By Jaldhar H. Vyas <jaldhar@braincells.com>
// Copyright (C) 2017, Consolidated Braincells Inc. All rights reserved.
// "Do what thou wilt" shall be the whole of the license.

#ifndef _BUFFER_H_
#define _BUFFER_H_

#include <vector>

using BUFFER = std::vector<char>;

template<typename T>
class Buffer {
public:
    using value_type = T;
    using reference = T&;
    using const_reference = const T&;
    using iterator = BufferIterator<T>;
    using const_iterator = BufferIterator<const T>;
    using difference_type = ptrdiff_t;
    using size_type = size_t;

    Buffer();
    Buffer(const Buffer<T>& that);

    Buffer<T>& operator=(const Buffer<T>& that);
    bool       operator==(const Buffer<T>& that) const;
    bool       operator!=(const Buffer<T>& that) const;
    reference  operator[](difference_type n);

    iterator begin();
    iterator end();

    const_iterator cbegin();
    const_iterator cend();

    size_type capacity();
    bool      empty();
    size_type max_size();
    size_type size();

    bool            deletePrevious();
    bool            deleteNext();
    bool            insert(value_type c);
    difference_type point() const;
    bool            pointMove(int count);
    bool            pointSet(BUFFER::iterator loc);

private:
    friend iterator;

    static constexpr size_t BUFFERSIZE = 80;

    BUFFER           _text;
    difference_type  _point;
    BUFFER::iterator _gapStart;
    BUFFER::iterator _gapEnd;

    void             moveGap();
    BUFFER::iterator userToGap(difference_type p);
    difference_type  gapToUser(BUFFER::iterator i);
};

template<typename T>
void std::swap(Buffer<T>& lhs, Buffer<T>& rhs);

template<typename T>
class BufferIterator {
public:
    // Iterator traits, previously from std::iterator.
    using value_type = T;
    using difference_type = typename BUFFER::difference_type;
    using pointer = typename BUFFER::iterator;
    using reference = typename Buffer<T>::reference;
    using iterator_category = std::random_access_iterator_tag;

    BufferIterator();
    BufferIterator(Buffer<T>& b);
    BufferIterator(const BufferIterator<T>& that);

    BufferIterator<T>&       operator=(const BufferIterator<T>& that);
    bool                     operator==(const BufferIterator<T>& that);
    bool                     operator!=(const BufferIterator<T>& that);
    BufferIterator<T>&       operator+=(const difference_type& n);
    BufferIterator<T>        operator+(const difference_type& n);
    BufferIterator<T>&       operator++();
    BufferIterator<T>        operator++(int);
    BufferIterator<T>&       operator-=(const difference_type& n);
    BufferIterator<T>        operator-(const difference_type& n);
    BufferIterator<T>&       operator--();
    const BufferIterator<T>& operator--(int);
    reference                operator*() const;
    pointer                  operator->() const;
    reference                operator[](const difference_type& n) const;

private:
    Buffer<T>& _b;
    pointer    _i;

};

template<typename T>
bool std::operator<(const BufferIterator<T>& lhs, const BufferIterator<T>& rhs);
template<typename T>
bool std::operator>(const BufferIterator<T>& lhs, const BufferIterator<T>& rhs);
template<typename T>
bool std::operator<=(const BufferIterator<T>& lhs,
const BufferIterator<T>& rhs);
template<typename T>
bool std::operator>=(const BufferIterator<T>& lhs,
const BufferIterator<T>& rhs);
template<typename T>
typename BufferIterator<T>::difference_type std::operator+(
const BufferIterator<T>& lhs, const BufferIterator<T>& rhs);
template<typename T>
typename BufferIterator<T>::difference_type std::operator-(
const BufferIterator<T>& lhs, const BufferIterator<T>& rhs);

template<typename T>
void std::swap(BufferIterator<T>& lhs, BufferIterator<T>& rhs);

#include "buffer.inl"

#endif

---

And this is buffer.inl:

// Buffer -- manages text in a text editor (Implementation)
//
// By Jaldhar H. Vyas <jaldhar@braincells.com>
// Copyright (C) 2017, Consolidated Braincells Inc. All rights reserved.
// "Do what thou wilt" shall be the whole of the license.

#include <algorithm>
#include <cstdlib>
#include <iterator>

template<typename T>
Buffer<T>::Buffer() : _text(BUFFERSIZE, 0), _point{0}, _gapStart{_text.begin()},
_gapEnd{_text.end()} {
}

template<typename T>
Buffer<T>::Buffer(const Buffer<T>& that) : _text(that._text),
_point{that._point}, _gapStart{that._gapStart}, _gapEnd{that._gapEnd} {
}

template<typename T>
Buffer<T>& Buffer<T>::operator=(const Buffer<T>& that) {
    if (this != &that) {
        this->_text = that._text;
        this->_point = that._point;
        this->_gapStart = that._gapStart;
        this->_gapEnd = that._gapEnd;
    }
    return *this;
}

template<typename T>
bool Buffer<T>::operator==(const Buffer<T>& that) const {
    return this->_text == that._text &&
        this->_point == that._point &&
        this->_gapStart == that._gapStart &&
        this->_gapEnd == that._gapEnd;
}

template<typename T>
bool Buffer<T>::operator!=(const Buffer<T>& that) const {
    return !operator==(that);
}

template<typename T>
typename Buffer<T>::reference Buffer<T>::operator[](difference_type n) {
    return Buffer<T>::iterator(*this)[n];
}

template<typename T>
typename Buffer<T>::iterator Buffer<T>::begin() {
    return Buffer<T>::iterator(*this);
}

template<typename T>
typename Buffer<T>::iterator Buffer<T>::end() {
    return Buffer<T>::iterator(*this) +  size();
}

template<typename T>
typename Buffer<T>::const_iterator Buffer<T>::cbegin() {
    return const_cast<const Buffer<T>&>(*this).begin();
}

template<typename T>
typename Buffer<T>::const_iterator Buffer<T>::cend() {
    return const_cast<const Buffer<T>&>(*this).end();
}

template<typename T>
typename Buffer<T>::size_type Buffer<T>::capacity() {
    return _text.capacity();
}

template<typename T>
bool Buffer<T>::empty() {
    return size() ? false : true;
}

template<typename T>
typename Buffer<T>::size_type Buffer<T>::max_size() {
    return _text.max_size();
}

template<typename T>
typename Buffer<T>::size_type Buffer<T>::size() {
    return _text.capacity() - (_gapEnd - _gapStart);
}

template<typename T>
bool Buffer<T>::deletePrevious() {
    if (_point <= 0 || _point > static_cast<difference_type>(size())) {
        return false;
    }

    moveGap();
    _gapStart--;
    return pointMove(-1);
}

template<typename T>
bool Buffer<T>::deleteNext() {
    if (_point < 0 || _point >= static_cast<difference_type>(size())) {
        return false;
    }

    moveGap();
    _gapEnd++;
    return true;
}

template<typename T>
bool Buffer<T>::insert(value_type c) {
    if (_point < 0 || _point > static_cast<difference_type>(size())) {
        return false;
    }

    moveGap();
    *_gapStart = c;
    _gapStart++;
    return pointMove(1);
}

template<typename T>
typename Buffer<T>::difference_type Buffer<T>::point() const {
    return _point;
}

template<typename T>
bool Buffer<T>::pointMove(int count) {
    Buffer<T>::difference_type loc = _point + count;
    if (loc < 0 || loc > static_cast<Buffer<T>::difference_type>(size())) {
        return false;
    }

    return pointSet(userToGap(loc));
}

template<typename T>
bool Buffer<T>::pointSet(BUFFER::iterator loc) {
    if (loc < _text.begin() || loc > _text.end()) {
        return false;
    }

    _point = gapToUser(loc);

    return true;
}

template<typename T>
void Buffer<T>::moveGap() {

    // I used shrink_to_fit because I found that resize() was sometimes
    // giving me more space than I asked for.  Is that normal?  If so, is
    // this how I should deal with it?  Should I bother trying to reclaim
    // space if the gap gets too big?

    if (_gapStart == _gapEnd) {
        _text.resize(_text.capacity() + BUFFERSIZE, 0);
        _text.shrink_to_fit();
        _gapStart = _text.end() - BUFFERSIZE;
        _gapEnd = _text.end();
    }

    BUFFER::iterator p = userToGap(_point);
    if (p == _gapStart) {
        return;
    }

    Buffer<T>::difference_type n;
    if (_gapStart < p) { // point is after gapStart
        n = p - _gapEnd;
        copy(p - n , p, _gapStart);
        _gapStart += n;
        _gapEnd += n;
        _point = gapToUser(_gapStart);
    } else { // point is before _gapStart
        n = _gapStart - p;
        _gapStart -= n;
        _gapEnd -= n;
        copy(p, p + n, _gapEnd);
    }
}

template<typename T>
BUFFER::iterator Buffer<T>::userToGap(difference_type p) {
    BUFFER::iterator i = _text.begin() + p;

    if (i > _gapStart) {
        i += (_gapEnd - _gapStart);
    }

    return i;
}

template<typename T>
typename Buffer<T>::difference_type Buffer<T>::gapToUser(BUFFER::iterator i) {
    Buffer<T>::difference_type p = distance(_text.begin(), i);

    if (i > _gapEnd) {
        p -= (_gapEnd - _gapStart);
    }

    return p;
}

template<typename T>
void std::swap(Buffer<T>& lhs, Buffer<T>& rhs) {
    if (lhs != rhs) {
        lhs._text.swap(rhs._text);
        std::swap(lhs._point, rhs._point);
        std::swap(lhs._gapStart, rhs._gapStart);
        std::swap(lhs._gapEnd, rhs._gapEnd);
    }
}

template<typename T>
BufferIterator<T>::BufferIterator() : _b{nullptr}, _i{nullptr} {
}

template<typename T>
BufferIterator<T>::BufferIterator(Buffer<T>& b) : _b{b} {
    if (b._gapStart == b._text.begin() && !_b.empty()) {
        _i = b._gapEnd;
    } else {
        _i = b._text.begin();
    }
}

template<typename T>
BufferIterator<T>::BufferIterator(const BufferIterator<T>& that) : _b(that._b),
_i{that._i} {
}

template<typename T>
BufferIterator<T>& BufferIterator<T>::operator=(const BufferIterator<T>& that) {
    if (this != &that) {
        this->_b = that._b;
        this->_i = that._i;
    }
    return *this;
}

template<typename T>
bool BufferIterator<T>::operator==(const BufferIterator<T>& that) {
    return _i == that._i;
}

template<typename T>
bool BufferIterator<T>::operator!=(const BufferIterator<T>& that) {
    return !this->operator==(that);
}

template<typename T>
BufferIterator<T>& BufferIterator<T>::operator+=(const difference_type& n) {
    auto count = n;

    // I don't like my code here.  The idea is a BufferIterator should
    // "skip over" the gap when incrementing or decrementing.  I feel like
    // I should be able to express it in terms of Buffer::userToGap or 
    // Buffer::gapToUser but I was unable to get that working correctly.

    if (count >= 0) {
        while (count--) {
            ++_i;
            if (_i == _b._gapStart) {
                _i += (_b._gapEnd - _b._gapStart);
            }
        }
    } else {
        while (count++) {
            --_i;
            if (_i == _b._gapEnd) {
                _i -= (_b._gapEnd - _b._gapStart);
            }
        }
    }

    return *this;
}

template<typename T>
BufferIterator<T> BufferIterator<T>::operator+(const difference_type& n) {
    return BufferIterator<T>(*this += n);
}

template<typename T>
BufferIterator<T>& BufferIterator<T>::operator++() {
    this->operator+(1);
    return *this;
}

template<typename T>
BufferIterator<T> BufferIterator<T>::operator++(int) {
    BufferIterator<T> tmp(*this);
    operator++();
    return tmp;
}

template<typename T>
BufferIterator<T>& BufferIterator<T>::operator-=(const difference_type& n) {
    return *this += -n;
}

template<typename T>
    BufferIterator<T> BufferIterator<T>::operator-(const difference_type& n) {
        return BufferIterator<T>(*this - n);
    }

template<typename T>
BufferIterator<T>& BufferIterator<T>::operator--() {
    this->operator-(1);
    return *this;
}

template<typename T>
const BufferIterator<T>& BufferIterator<T>::operator--(int) {
    BufferIterator<T> tmp(*this);
    operator--();
    return tmp;
}

template<typename T>
typename BufferIterator<T>::reference BufferIterator<T>::operator*() const {
    return *_i;
}

template<typename T>
typename BufferIterator<T>::pointer BufferIterator<T>::operator->() const {
    return _i;
}

template<typename T>
typename BufferIterator<T>::reference BufferIterator<T>::operator[](
const difference_type& n) const {
    return *(_i + n);
}

template<typename T>
bool std::operator<(const BufferIterator<T>& lhs,
const BufferIterator<T>& rhs) {
    return lhs._i < rhs._i;
}

template<typename T>
bool std::operator>(const BufferIterator<T>& lhs,
const BufferIterator<T>& rhs){
    return lhs._i > rhs._i;
}

template<typename T>
bool std::operator<=(const BufferIterator<T>& lhs,
const BufferIterator<T>& rhs) {
    return !operator>(lhs, rhs);
}

template<typename T>
bool std::operator>=(const BufferIterator<T>& lhs,
const BufferIterator<T>& rhs) {
    return !operator<(lhs, rhs);
}

template<typename T>
typename BufferIterator<T>::difference_type std::operator+(
const BufferIterator<T>& lhs, const BufferIterator<T>& rhs) {
    return lhs._i + rhs._i;
}

template<typename T>
typename BufferIterator<T>::difference_type std::operator-(
const BufferIterator<T>& lhs, const BufferIterator<T>& rhs) {
    return lhs._i - rhs._i;
}

template<typename T>
void std::swap(BufferIterator<T>& lhs, BufferIterator<T>& rhs) {
    if (lhs != rhs) {
        lhs._b.swap(rhs._b);
        std::swap(lhs._i, rhs._i);
    }
}

Answer 1

Implementation

• BUFFER could be a defaulted template parameter. This allows for specifying different containers for storage.
• Any specific reason why Buffer<T>::operator[](difference_type) takes a difference_type instead of a size_type parameter?
• Buffer<T>::pointSet(BUFFER::iterator) takes an iterator of a private member - but Buffer<T> provides no publicly accessible member function which would return one.
• Buffer<T>::cbegin() and Buffer<T>::cend() are declared to return a BufferIterator<const T>, but would return a BufferIterator<T> instead.
• The const_cast<const Buffer<T>&> in Buffer<T>::cbegin() and Buffer<T>::cend() is weird. The called Buffer<T>::begin() and Buffer<T>::end() aren't marked const, so calling them from a const Buffer<T>& isn't possible anyways.
• The BufferIterator<T> constructor should probably accept a const Buffer<T>& instead of a non-const reference.
• Buffer<T>::gapToUser() reports incorrectly if p > _gapStart && p <= _gapEnd.
• BufferIterator<T>::operator=(const BufferIterator<T>&): References (this->b_) cannot be reseated.
• The comparison operators of BufferIterator<T> don't check whether the underlying Buffer<T> object is the same.
• std::swap(BufferIterator<T>&, BufferIterator<T>&) doesn't check correctly for referential equality (lhs != rhs instead of &lhs != &rhs).
• std::swap(BufferIterator<T>&, BufferIterator<T>&): I don't think it's intended to swap the contents of rhs.b_ and lhs.b_. Did you want to exchange the references instead?
• Rule of 5 violation: You provide custom copy constructors and copy assignment operators for Buffer<T> and BufferIterator<T>, so you should also provide custom move constructors, move assignment operators and possibly destructors.
• Many member functions should be marked const.

Naming

Many variable have very non-descriptive names. These could be improved for better readability (what tells you more: b_ or buffer_?).

---

EDIT: To respond to some of the comments.

• cbegin() and cend(): The easiest and most correct way is to use overloads with const member functions. This requires BufferIterator<T>s constructor to take a const Buffer<T>& instead (shouldn't be a problem, as it doesn't change that buffer through the reference).

  template<typename T>
  class Buffer<T> {
      /* skipping stuff */
  
      // keep non-const begin and end
      iterator begin() { return iterator{*this}; }
      iterator end() { return iterator{*this}; }
  
      // add const overloads
      const_iterator begin() const { return const_iterator{*this}; }
      const_iterator end() const { return const_iterator{*this}; }
  
      // make cbegin and cend const, forward to const version of begin and end
      // This forwards to the right overloads, since this is const
      const_iterator cbegin() const { return begin(); }
      const_iterator cend() const { return end(); }
  };
  

• "Reseating a reference" is another way to say "change the object a reference is referring to". This isn't allowed! References are seated (= set) once when they are initialized, and cannot legally be changed afterwards. If there is a need to change the pointed to object, pointers must be used instead.

• I have been thinking about operator+(const BufferIterator<T>&, const BufferIterator<T>&) and operator-(const BufferIterator<T>&, const BufferIterator<T>&) a bit more, and found that there is a use case (basically: determining std::distance(it1, it2) more easily), so keep them (I don't know how I overlooked that one when I wrote the original answer, sorry).

• Regarding move constructor and move assignment operator: Since you have a user defined copy constructor, the compiler won't generate a move constructor by default. Even if it were to generate the default move constructor by using Buffer(Buffer<T>&&) = default;, it wouldn't move any members that don't have a trivial move constructor themselves (e.g. Buffer<T>::_text).

  template<typename T>
  Buffer<T>::Buffer(Buffer<T>&& that) noexcept : _text(std::move(that._text)),
  _point{that._point}, _gapStart{std::move(that._gapStart)}, _gapEnd{std::move(that._gapEnd)} {
  }
  
  template<typename T>
  Buffer<T>& Buffer<T>::operator=(Buffer<T>&& that) noexcept {
      if (this != &that) {
          this->_text = std::move(that._text);
          this->_point = that._point;
          this->_gapStart = std::move(that._gapStart);
          this->_gapEnd = std::move(that._gapEnd);
      }
      return *this;
  }