C++ implementation of basic_string

Question

This is a basic_string implementation that has SSO. It's not done, but the fundamental operations are all there (append, erase, resize, reserve, push_back/pop_back). Proper iterators and my own char_traits impl will be added eventually.

#include <string>

template<typename CharType, typename Traits = std::char_traits<CharType>, typename Allocator = std::allocator<CharType>>
class kbasic_string
{
public:
  static const size_t npos = -1;
  using iterator = CharType*;
  using const_iterator = const CharType*;

  friend kbasic_string operator+(const kbasic_string& lhs, const kbasic_string& rhs)
  {
    return kbasic_string{lhs}.append(rhs);
  }

  friend kbasic_string operator+(const kbasic_string& lhs, const CharType* rhs)
  {
    return kbasic_string{lhs}.append(rhs);
  }

  friend kbasic_string operator+(const kbasic_string& lhs, CharType rhs)
  {
    return kbasic_string{lhs}.append(rhs);
  }

  friend std::ostream& operator<<(std::ostream& lhs, const kbasic_string& rhs)
  {
    lhs.write(rhs.data(), rhs.size());
    return lhs;
  }

  friend std::wostream& operator<<(std::wostream& lhs, const kbasic_string& rhs)
  {
    lhs.write(rhs.data(), rhs.size());
    return lhs;
  }

  kbasic_string() = default;

  kbasic_string(const kbasic_string& other)
  {
    reserve(other.capacity_);
    if (other.size_)
      std::copy(other.begin(), other.end() + 1, begin());
    size_ = other.size_;
  }

  kbasic_string(kbasic_string&& other)
  {
    if (other.on_heap())
    {
      std::memcpy(&data_, &other.data_, sizeof(CharType*));
      std::memset(&other.data_, 0, sizeof(CharType*));
    }
    else
    {
      std::copy(other.begin(), other.end() + 1, begin());
    }
    size_ = other.size_;
    capacity_ = other.capacity_;
    on_heap_ = other.on_heap_;
    other.on_heap_ = false;
  }

  kbasic_string& operator=(const kbasic_string& other)
  {
    reserve(other.capacity_);
    if (other.size_)
      std::copy(other.begin(), other.end() + 1, begin());
    size_ = other.size_;
    return *this;
  }

  kbasic_string& operator=(kbasic_string&& other)
  {
    if (other.on_heap())
    {
      std::memcpy(&data_, &other.data_, sizeof(CharType*));
      std::memset(&other.data_, 0, sizeof(CharType*));
      on_heap_ = true;
    }
    else
    { 
      std::copy(other.begin(), other.end() + 1, begin());
    }
    size_ = other.size_;
    capacity_ = other.capacity_;
    other.on_heap_ = false;
    return *this;
  }

  kbasic_string(const CharType* str)
  {
    size_t size = Traits::length(str);
    if (size > capacity_)
      reserve(size);
    std::copy(str, str + size + 1, data());
    size_ = size;
  }

  kbasic_string& operator=(const CharType* str)
  {
    size_t size = Traits::length(str);
    if (size > capacity_)
      reserve(size);
    std::copy(str, str + size + 1, data());
    size_ = size;
  }

  void reserve(size_t capacity)
  {
    if (capacity <= capacity_ || capacity <= 22)
      return;
    Allocator alloc;
    CharType* mem = alloc.allocate(capacity + 1);
    if (size_)
      std::copy(begin(), end() + 1, mem);
    if (on_heap())
      alloc.deallocate(data(), capacity_ + 1);
    else
      on_heap_ = true;
    std::memcpy(data_, &mem, sizeof(CharType*));
    capacity_ = capacity;
  }

  void resize(size_t size, CharType app)
  {
    if (size > size_)
    {
      reserve(size);
      std::fill(end(), end() + (size - size_), app);
      *(end() + (size - size_) + 1) = 0;
    }
    else if (size < size_)
    {
      erase(end() - (size_ - size), end());
    } 
    else
    {
      return;
    }
    size_ = size;
  }

  void resize(size_t size)
  {
    resize(size, 0);
  }

  template<typename Iter, typename = std::enable_if_t<std::_Is_iterator_v<Iter>>>
  kbasic_string& erase(Iter first, Iter last)
  {
    return erase(first - begin(), last - first);
  }

  kbasic_string& erase(size_t pos, size_t count)
  {
    if (pos > size_)
      throw std::out_of_range("pos is out of range");
    std::copy(begin() + pos + count, end() + 1, begin() + pos);
    size_ -= count;
    return *this;
  }

  template<typename Iter, typename = std::enable_if_t<std::_Is_iterator_v<Iter>>>
  kbasic_string& erase(Iter it)
  {
    return erase(it - begin(), 1);
  }

  void pop_back()
  {
    erase(end() - 1);
  }

  void clear()
  {
    erase(begin(), end());
  }

  kbasic_string& append(const CharType* str, size_t len)
  {
    if (size_ + len > capacity_)
      reserve(size_ + len);
    std::copy(str, str + len + 1, begin() + size_);
    size_ += len;
    return *this;
  }

  kbasic_string& append(const CharType* str)
  {
    return append(str, Traits::length(str));
  }

  kbasic_string& append(const kbasic_string& str)
  {
    return append(str.data());
  }

  kbasic_string& append(CharType ch)
  {
    if (size_ + 1 > capacity_)
      reserve(size_ + 1);
    iterator prev_end = begin() + size_;
    *prev_end = ch;
    *(prev_end + 1) = 0;
    ++size_;
    return *this;
  }

  template<typename Iter, typename = std::enable_if_t<std::_Is_iterator_v<Iter>>>
  kbasic_string& append(Iter first, Iter last)
  {
    if (last - first > capacity_)
      reserve(last - first);
    std::copy(first, last, begin() + size_);
    return *this;
  }

  void push_back(CharType ch)
  {
    append(ch);
  }

  CharType* data() noexcept
  {
    return on_heap() ? heap_ptr() : data_;
  }

  const CharType* data() const noexcept
  {
    return on_heap() ? heap_ptr() : data_;
  }

  size_t size() const noexcept
  {
    return size_;
  }

  size_t length() const noexcept
  {
    return size_;
  }

  size_t capacity() const noexcept
  {
    return capacity_;
  }

  iterator begin() noexcept
  {
    return data();
  }

  const_iterator begin() const noexcept
  {
    return data();
  }

  iterator end() noexcept
  {
    return data() + size_;
  }

  const_iterator end() const noexcept
  {
    return data() + size_;
  }

  bool empty() const noexcept
  {
    return !size_;
  }

  CharType& at(size_t n)
  {
    return data()[n];
  }

  const CharType& at(size_t n) const
  {
    return data()[n];
  }

  CharType& operator[](size_t n)
  {
    return at(n);
  }

  const CharType& operator[](size_t n) const
  {
    return at(n);
  }

  kbasic_string& operator+=(const kbasic_string& other)
  {
    return append(other);
  }

  kbasic_string& operator+=(const CharType* str)
  {
    return append(str);
  }
  kbasic_string& operator+=(CharType ch)
  {
    return append(ch);
  }

  bool operator==(const kbasic_string& other)
  {
    return std::equal(begin(), end(), other.begin(), other.end());
  }

  bool operator==(const CharType* str)
  {
    return std::equal(begin(), end(), str, str + Traits::length(str));
  }

  bool operator==(CharType ch)
  {
    return size_ == 1 && *begin() == ch;
  }

  bool operator!=(const kbasic_string& other)
  {
    return !(*this == other);
  }

  bool operator!=(const CharType* str)
  {
    return !(*this == str);
  }

  bool operator!=(CharType ch)
  {
    return !(*this == ch);
  }

  ~kbasic_string()
  {
    if (on_heap())
      Allocator{}.deallocate(data(), capacity_ + 1);
  }

private:
  bool on_heap() const
  {
    return on_heap_;
  }

  const CharType* heap_ptr() const
  {
    CharType* ptr = nullptr;
    std::memcpy(&ptr, data_, sizeof(CharType*));
    return ptr;
  }

  CharType* heap_ptr()
  {
    CharType* ptr = nullptr;
    std::memcpy(&ptr, data_, sizeof(CharType*));
    return ptr;
  }

  size_t size_ = 0;
  size_t capacity_ = 22;
  bool on_heap_ = false;
  CharType data_[23] = {0};
};

a small thing: since is c++ it should be std::size_t not size_t — Sandro4912
– Sandro4912, Commented Jan 15, 2019 at 20:45

Quuxplusone · Accepted Answer · 2019-01-15 07:03:40Z

It's tricky to review something like this where you're imitating an overcomplicated design, so you know certain things are unimplemented (such as iterators), but then other things might also be unimplemented by accident. For example:

You take a parameter Traits = std::char_traits<CharType> but then you don't use it! The real basic_string would use the traits class for things like where you use std::copy.
You take an allocator parameter Allocator = std::allocator<CharType> and do use it, kind of, but you don't go through std::allocator_traits<Allocator>. Since all you use is a.allocate() and a.deallocate(), this is probably fine in all real-world situations; but really you should be using allocator_traits. It can't hurt.
You don't store an Allocator data member of kbasic_string; instead, you default-construct one ex nihilo every time you want to use the allocator. This (plus the previous bullet point, technically) means that your container is not allocator-aware: it won't work with user-defined allocators or allocators such as std::pmr::polymorphic_allocator<char>. You get away with it in your tests right now only because std::allocator<char> is (A) empty and (B) default-constructible.
You do have tests, right?

  std::memcpy(&data_, &other.data_, sizeof(CharType*));
  std::memset(&other.data_, 0, sizeof(CharType*));

This is a very strange way of writing

  data_ = other.data_;
  other.data_ = nullptr;

...oh, I see, your data_ is a char[23], not a char *. Well, okay. I would strongly recommend making it a union of char[23] and char * so that you can copy the pointer member without weird type-punning tricks.

Pedantic nit: Setting all-bits-zero is not technically the same thing as setting to nullptr — the in-memory representation of nullptr need not be all-bits-zero (even though, in practice, it will be).

Also, notice that to be allocator-aware you will have to store a pointer of type std::allocator_traits<Allocator>::pointer, which you definitely cannot assume is all-bits-zero when it's null! For example, boost::interprocess::offset_ptr<char> is not all-bits-zero when it's null.

bool operator==(const kbasic_string& other)

Here and throughout, you forgot the trailing const. These days I recommend making every operator an "ADL friend" non-member:

friend bool operator==(const kbasic_string& other, const kbasic_string& other) {
    return std::equal(begin(), end(), other.begin(), other.end());
}

Then it's really obvious if you forget one of the two consts.

  template<typename Iter, typename = std::enable_if_t<std::_Is_iterator_v<Iter>>>
  kbasic_string& append(Iter first, Iter last)
  {
    if (last - first > capacity_)
      reserve(last - first);
    std::copy(first, last, begin() + size_);
    return *this;
  }

Write a test case for this function! For example, string("123456789").append(a, a+3). There's a bug in the if condition that leads quickly to undefined behavior.

kbasic_string& append(const kbasic_string& str)
{
    return append(str.data());
}

Also write tests for this function! Since str knows its own size(), does it make sense to throw away that information here? What happens if str contains an embedded '\0' character — what is string("abc").append(string("d\0e", 3))?

Your use of std::_Is_iterator_v<Iter> is sketchy. I would recommend writing your own portable type-trait, something like this:

template<class, class = void> struct is_iterator : std::false_type {};
template<class T> struct is_iterator<T, decltype(void(std::iterator_traits<T>::iterator_category{}))> : std::true_type {};

Orthogonally, you seem to be using _Is_iterator_v almost like pseudocode that magically does whatever you want done. Here you use it to mean "is an input iterator or better":

template<typename Iter, typename = std::enable_if_t<std::_Is_iterator_v<Iter>>>
kbasic_string& append(Iter first, Iter last)

Here you use it to mean "is either kbasic_string::iterator or kbasic_string::const_iterator":

template<typename Iter, typename = std::enable_if_t<std::_Is_iterator_v<Iter>>>
kbasic_string& erase(Iter it)

erase should certainly be rewritten as a non-template:

kbasic_string& erase(const_iterator it)

Finally, consider whether you could save space by replacing every instance of on_heap_ with the condition (capacity_ > 22). And consider moving the magic number 22 into a variable!

static constexpr size_t SBO_CAPACITY = 22;
size_t size_ = 0;
size_t capacity_ = SBO_CAPACITY;
CharType data_[SBO_CAPACITY + 1] = {0};

JVApen · Accepted Answer · 2019-01-15 07:19:12Z

3

I was looking at a method which I considered to be really easy: c_str, however, it doesn't look that easy based on how you implemented it.

Currently, you have a bool indicating whether you should store it on the heap or not. If you replace that by a pointer to the first character. You could implement the onHeap by comparing 2 pointers. Every access to the characters can simply use the pointer, unless for the appending.

answered Jan 15, 2019 at 7:19

JVApen

1,1916 silver badges17 bronze badges

Add a comment |

Stack Exchange Network

C++ implementation of basic_string

2 Answers 2

You must log in to answer this question.

Hot Network Questions

C++ implementation of basic_string

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions