My implementation of String in C++

Question

I wrote my string class. The code works, but could anyone tell if I am doing anything wrong?

It is an exercise from the "Accelerated c++" book:

Implement the Str class, but choose an implementation strategy that requires that the class manage the storage itself. For example, you might store an array of char and a length. Consider what implications this change in design has for copy control. Also consider the cost of using Vec, (e.g., in storage overhead). Implement the c_str, data, and copy functions.

#ifndef STRINGCLASS_STR_H
#define STRINGCLASS_STR_H

#include <memory>
#include <cstring>
#include <iostream>

using std::strlen;
using std::allocator;


class Str {
    friend std::ostream &operator<<(std::ostream &, const Str &);
    friend std::istream &operator>>(std::istream &, Str &);
    friend Str operator+(const Str &, const Str &);




public:
    typedef char* iterator;
    typedef size_t size_type;

    Str() { }

    Str(size_type n, char c) { create(n, c); }

    Str(const char *s) { create(s); }

    template<class In>
    Str(In b, In e) {create(b,e); }

    ~Str() {
        if (data) alloc.deallocate(data, length);
        data = 0;
        length = 0;
    }

    Str &operator+=(const Str &s) {
        size_type new_length = s.length + length - 1; //remove 1 because of 2 nulls
        char *new_data = alloc.allocate(new_length);
        strcpy(new_data, data);
        strcpy(new_data + length - 1, s.data); //overwrite null from s
        data = new_data;
        length = new_length;
        return *this;
    }

    Str &operator=(const Str &rhs) {
        if (&rhs != this) {
            if (data) alloc.deallocate(data, length);
            create(rhs.data);
        }

        return *this;
    }

    char &operator[](size_type i) { return data[i]; };

    const char &operator[](size_type i) const { return data[i]; };

    size_type size() { return length; }

    const size_type size() const { return length; }

    const char* c_str(){
        char* result = alloc.allocate(length);
        std::uninitialized_copy(data, data+length, result);
        return result;
    }

    const char* rawdata(){
        char* result = alloc.allocate(length-1);
        std::uninitialized_copy(data, data+length-1, result);
        return result;
    }

    void copy(char *p, size_type n){
        if(n>length)
            throw std::out_of_range("Out of range");
        std::copy(data, data+n, p);
    }

    char* begin(){return data;};
    char* end(){ return data+length;};

private:
    char *data;
    allocator<char> alloc;
    size_type length;

    void create(size_type n, char c) {
        length = n + 1;
        data = alloc.allocate(length);
        std::uninitialized_fill(data, data + length - 1, c);
        alloc.construct(data + length - 1, '\0');
    }

    void create(const char *s) {
        length = strlen(s) + 1;
        data = alloc.allocate(length);
        strcpy(data, s);
        alloc.construct(data + length - 1, '\0');
    }

    template<class In>
    void create(In b, In e){
        length = e - b + 1;
        data = alloc.allocate(length);
        size_type i = 0;
        while (b != e) {
            data[i++] = *(b++);
        }
        alloc.construct(data + length - 1, '\0');
    }
};

std::istream &operator>>(std::istream &is, Str &s) {
    std::vector<char> buf;
    char c;
    while (is.get(c) && isspace(c)) { ;
    }
    if (is) {
        do buf.push_back(c);
        while (is.get(c) && !isspace(c));
        if (is)
            is.unget();
    }
    s.create(buf.begin(), buf.end());
    return is;
}

std::ostream &operator<<(std::ostream &os, const Str &s) {
    os << s.data;
    return os;
}

Str operator+(const Str &s, const Str &t) {
    Str res;
    res.length = s.length + t.length - 1;
    res.data = res.alloc.allocate(res.length);
    strcpy(res.data, s.data);
    strcpy(res.data + s.length - 1, t.data);
    return res;
}

#endif //STRINGCLASS_STR_H

This is example main.cpp

#include <iostream>
#include <vector>
#include "Str.h"

using std::cout;
using std::endl;

int main() {
    Str s("Siema");
    cout<<s.c_str()<<endl;

    s = "Hello";
    cout<<s<<endl;

    Str t = "World";
    cout<<s+t<<endl;

    s+=t;
    cout<<s<<endl;

    cout<<s[3]<<s[5]<<s[11]<<endl;

    cout<<s.size()<<endl;
    cout<<Str(s.begin()+3, s.end()-2)<<endl;
    for(Str::iterator i = s.begin(); i<s.end() ; i+=2){
        cout<<i<<endl;
    }

    char copied[3];
    u.copy(copied, 4);
    cout<<copied<<endl;

    return 0;
}

Answer 1

A few things to look into

• This is a very bad idea in a header file:

  using std::strlen;
  using std::allocator;
  

  Don't tamper with the global namespace. This exposes those names to every other file including the Str header, which in the long run is a recipe for name collisions. Better to just std:: qualify your names as needed. If you must using or using namespace, then do it only in the implementation file (.cpp).

  As a side note, consider always namespacing your stuff. Str is a very common name used by many codebases. If you leave it as a global name, it can become a conflict if you end up merging your code with some other third-party codebase. Namespaces are a great underused feature of C++.

• I would prefer if your operators where non-members and non-friends of the class. They are already non-members, but making then friends is just as good, they can mess around with the internal data. Prefer defining a minimal public interface that the operators can build on. For instance, operator + could be defined in terms of +=:

  Str operator + (Str lhs, const Str& rhs) {
      lhs += rhs;
      return lhs;
  }
  

• Consider adding move support. Since your class is just a pointer wrapper, it can easily be moved. This could turn out to be a big performance boost with very little implementation cost.

• Speaking of move and looking at the assignment operator, I would like to see the use of copy-and-swap style in there. It is a well stablished way of handling copy in these kinds of resource containers. I strongly suggest you take a look.

• The copy constructor is missing entirely though, which is a major design flaw. If you did Str a(b);, where b is another Str, you will just get a shallow pointer copy, but the destructors won't know that and both will attempt to free the same pointer. You must fix this before your code is anywhere near usable.

• Default constructor is broken. It doesn't initialize the member data to safe defaults, so you effectively get garbage data in the pointer and size. Fix it by explicitly setting the pointer to nullptr and the size to zero.

• It's a bit pointless resetting the data in the destructor. The object is gone after that.

  ~Str() {
       if (data) alloc.deallocate(data, length);
       data = 0; // <-- use nullptr!
       length = 0;
   }
  

  Another little issue there: use nullptr for pointers. 0 is implicitly convertible to pointer, yes, but zero evokes numbers. Not quite the same thing!

• begin/end need const overloads, also retuning a const char* (but wait, shouldn't they return iterators instead?).

• c_str() allocates memory... Wait whaaaa??? Very unexpected behavior there for a method that mimics std::string::c_str(). It should just be a lightweight accessor that returns a read-only pointer to the underlaying null-terminated string. I can't tell 100% by reading the code if data is always '\0' terminated, but if it is not, then it should be. It only costs you an extra byte to ensure the underlaying buffer is always a valid C-string, so do that and avoid a large series of problems.

• Same would apply to rawdata(), even though I really don't see much of a reason for its existence in the first place.

---

A couple departing notes on optimization

SSO:

The first obvious optimization here would be to add Small String Optimization (SSO). The idea behind it is that a lot of times the strings are small. So we might benefit from having a local inline char buffer within the string object itself to prevent an expensive dynamic allocation for the short string case. In terms of code, it might look a bit like this:

class Str
{
    char* data;
    char smallstr[N];
};

Where N is a carefully chosen constant to balance between memory usage and average size of strings. Then data will either point to the local inline buffer if the string fits in it, or to heap-allocated memory if it doesn't.

EBO:

Empty Baseclass Optimization (EBO) could be applied to your use of std::allocator. The default Standard allocator is a stateless class. It just forwards every call to operator new and delete. Problem is, if you declare an instance of allocator, it still takes some space. This happens because of a few requirements of the C++ Standard that I will not go in detail here (check the link above for full info). Suffice to say, you are paying for some extra storage space that is not needed by the allocator itself.

So to prevent std::allocator from taking any space in our class, rather than declaring an instance of it, you could take advance of private inheritance and leverage EBO. If you inherit from an empty class, then it is guaranteed to take no extra space in the resulting child type:

class Str : private std::allocator<char>
{
    // as before
};

Private inheritance won't expose any of the allocator's interface publicly in Str, which precisely what we want here.

Answer 2

Let's start from the top:

Better Naming

The function naming as well as some of your variable names is a little too terse. Consider using longer, more descriptive names.

Where is push_back()?!

Having that would make the implementation of many of your functions much easier! Note that you'll have to introduce another member variable std::size_t capacity to make this work. Example:

static const size_t DEFAULT_CAPACITY = 20;
class Str {
public:
    void push_back(char c)
    {
         if (size == capacity) {
             reallocate(capacity == 0 ? DEFAULT_CAPACITY : 2 * capacity);
         }
         data[size++] = c;
    }
private:
    void reallocate(size_t new_capacity)
    {
        char *new_data = alloc.allocate(new_capacity);
        std::copy(data, data + size, new_data);
        alloc.deallocate(data, size);
        data = new_data;
        capacity = new_capacity;
    }
    char *data;
    std::size_t size, capacity;
};

Now you can make the implementation of many of your functions much easier:

Str(size_type n, char c)
{
    for (size_type i = 0; i < n; ++i) { push_back(c); }
}

Str(const char *s)
{
    while (*s) { push_back(*s++); }
}

template <class ForwardIterator>
Str(ForwardIterator begin, ForwardIterator end)
{
    while (begin != end) { push_back(*begin); ++begin; }
}

Str& operator+=(const Str &s)
{
    for (size_type i = 0; i < s.size; ++i) { push_back(s.data[i]); }
}

Also note that we've gotten rid of the need for the 3 different versions of create() by providing this single function.

Properly Initialize Members

In your default constructor, it's best for you to initialize your private member variables in an initializer list:

Str() : data(nullptr), size(0), capacity(0) {}

You can then use constructor delegation to initialize the same way for all your other constructors:

Str(size_type n, char c) : Str() { /* ... */ }
Str(const char *s) : Str() { /* ... */ }

template <class In>
Str(In b, In e) : Str() { /* ... */ }

DRY

Notice how the code for your += and + operators is almost identical? That's because you can implement one in terms of the other:

friend Str operator+(Str lhs, const Str& rhs)
{
    lhs += rhs;
    return lhs;
}

Consider adding iterators

std::string has iterators and if you're trying to match std::string, then yours should too. But seriously, iterators prove to be highly useful as you can then plug in your data structure into many of the standard library's algorithm algorithms as well as provide a nice interface to use a range-based for-loop.