Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Design a STRING class. Provide support for:

  • Assigning one object for another
  • Two string can be concatenated using + operator
  • Two strings can be compared using the relational operators

Modify the String class so that assigning/initializing a string by another will not copy it physically but will keep a reference count, which will be incremented. Reference value 0 means the space can be released.

I have a pointer to the reference count within each class and keep incrementing it when the string is assigned or copied. The program seems to work. Can this implementation be made simpler, especially the += operator for String?

#include <iostream>
#include <algorithm>
#include <iterator>
#include <cstddef>
#include <cstring>

class String {
    friend void swap(String &first, String &second);

    friend String operator+(String lhs, String const &rhs);

    friend bool operator<(String const &lhs, String const &rhs);
    friend bool operator>(String const &lhs, String const &rhs);

    friend bool operator==(String const &lhs, String const &rhs);
    friend bool operator!=(String const &lhs, String const &rhs);

    friend std::ostream &operator<<(std::ostream &os, const String &s);
public:
    typedef char *iterator;
    typedef const char *const_iterator;
    typedef std::size_t size_type;
    typedef char value_type;

    static const size_t npos = -1;

    String();
    String(size_type count, char c);
    String(const char *cp);
    template<class In> String(In first, In last);
    String(const String &s);

    String &operator=(const String &rhs);

    size_type size() const;

    iterator begin();
    const_iterator begin() const;

    iterator end();
    const_iterator end() const;

    String &operator+=(const String &s);

    int compare(const String &str) const;

    ~String();
private:
    size_type data_size;
    iterator data; // points to the first char
    int *ref_cnt;
};

void swap(String &first, String &second);

String operator+(String lhs, String const &rhs);

std::ostream &operator<<(std::ostream &os, const String &s);

bool operator<(String const &lhs, String const &rhs);
bool operator>(String const &lhs, String const &rhs);

bool operator==(String const &lhs, String const &rhs);
bool operator!=(String const &lhs, String const &rhs);

// implementation of friend functions

void swap(String &first, String &second)
{
    using std::swap;
    swap(first.data_size, second.data_size);
    swap(first.data, second.data);
    swap(first.ref_cnt, second.ref_cnt);
}

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

std::ostream &operator<<(std::ostream &os, const String &s)
{
    for (auto c : s)
        os << c;
    return os;
}

bool operator<(String const &lhs, String const &rhs)
{
    return rhs.compare(lhs) < 0;
}

bool operator>(String const &lhs, String const &rhs)
{
    return rhs < lhs;
}

bool operator==(String const &lhs, String const &rhs)
{
    return !(lhs < rhs) && !(lhs > rhs);
}

bool operator!=(String const &lhs, String const &rhs)
{
    return !(lhs == rhs);
}

// public member functions

// Allocated memory is always data_size + 1,
// since the last char is required to store the null character

String::String():
    data_size(0), data(new char[data_size + 1]()), ref_cnt(new int())
{
    *ref_cnt = 1;
}

String::String(size_type count, char c):
    data_size(count), data(new char[data_size + 1]()), ref_cnt(new int())
{
    std::fill(data, data + data_size, c);
    *ref_cnt = 1;
}

String::String(const char *cp):
    data_size(strlen(cp)), data(new char[data_size + 1]()), ref_cnt(new int())
{
    std::copy(cp, cp + strlen(cp), data);
    *ref_cnt = 1;
}

template<class In> String::String(In first, In last):
    data_size(std::distance(first, last)), data(new char[data_size + 1]),
    ref_cnt(new int())
{
    std::copy(first, last, data);
    *ref_cnt = 1;
}

String::String(const String &s):
    data_size(s.data_size), data(s.data), ref_cnt(s.ref_cnt)
{
    (*ref_cnt)++;
}

String &String::operator=(const String &rhs)
{
    *ref_cnt = *ref_cnt - 1;
    if (*ref_cnt == 0) {
        delete ref_cnt;
        delete[] data; 
    }

    data = rhs.data;
    data_size = rhs.data_size;
    ref_cnt = rhs.ref_cnt;
    *ref_cnt += 1;
    return *this;
}

String::size_type String::size() const
{
    return data_size;
}

String::iterator String::begin()
{
    return data;
}

String::const_iterator String::begin() const
{
    return data;
}


String::iterator String::end()
{
    return data + data_size;
}

String::const_iterator String::end() const
{
    return data + data_size;
}

String &String::operator+=(const String &s)
{

    iterator new_data = new char[s.data_size + data_size + 1]();
    std::copy(data, data + data_size, new_data);
    std::copy(s.data, s.data + s.data_size, new_data + data_size);

    *ref_cnt = *ref_cnt - 1;
    if (*ref_cnt == 0) {
        delete ref_cnt;
        delete[] data; 
    }

    data = new_data;
    data_size += s.data_size;
    ref_cnt = new int();
    *ref_cnt = 1;

    return *this;
}

int String::compare(const String &str) const
{
    const_iterator it1 = begin();
    const_iterator it2 = str.begin();
    while (it1 != end() || it2 != end()) {
        if (it1 == end()) {
            return 1;
        } else if (it2 == str.end()) {
            return -1;
        } else if (*it1 > *it2) {
            return -1;
        } else if (*it1 < *it2) {
            return 1;
        }
        ++it1;
        ++it2;
    }
    return 0;
}

String::~String()
{
    *ref_cnt -= 1;
    if (*ref_cnt == 0) {
        delete ref_cnt;
        delete[] data;
    }
}

int main(void)
{
    using namespace std;

    String str(10, 'c');
    cout << str << '\n';
    char arr[11]="C++CodesII";
    String str2(arr,arr + 10);
    cout << str2 << '\n';
    bool equals=str==str2;
    cout<<equals<<endl;
    String str3(str2);
    cout << str3 << '\n';
    str=str3;
    cout << str << '\n';
    String str4=str+str3;
    cout << str4 << '\n';
    equals= str2==str3;
    cout<<equals<<endl;
    return 0;
}
share|improve this question
1  
Note: this is generally known as the Copy On Write optimization and was used by libstdc++ (coming with gcc) until gcc 5.0 (which switched to Short String Optimization instead to be compliant with C++11). – Matthieu M. Feb 21 at 17:20
up vote 12 down vote accepted

Overall that's very good.

I did not find any issues with the code. All the comments are very minor.

Design

At a design level there is one change I would make. Note yours works.

But you can put all three members (size/ptr/ref) into a shared object. The advantage to this is that the (size/ptr) are in the sample place. This reduces the chance for them to accidentally go out of sync because of a small error.

There is also the advantage that your String object is reduced in size. From sizeof(ptr) + sizeof(std::size_t) + sizeof(ptr) to simply sizeof(ptr).

Free standing Vs member functions

    friend String operator+(String lhs, String const &rhs);

    friend bool operator<(String const &lhs, String const &rhs);
    friend bool operator>(String const &lhs, String const &rhs);

    friend bool operator==(String const &lhs, String const &rhs);
    friend bool operator!=(String const &lhs, String const &rhs);

The reason to use a free standing function over a member is to allow either sides of the expression to be auto converted into the class (rather than just the right hand side being potentially auto converted into the class).

Make sure this the expected behavior.

Stealing things from std::string

    static const size_t npos = -1;

Not actually used anywhere.

Rule of Three

When I see classes that manage resources; like strings. I want to check that they are obeying the rule of three. I don't immediately see the destructor and I have to scroll down to the bottom of the classes.

    String();
    String(size_type count, char c);
    String(const char *cp);
    template<class In> String(In first, In last);
    String(const String &s);

    String &operator=(const String &rhs);


    // Lots of other functions.

    ~String();

Internal Data

    iterator data; // points to the first char

Sure the iterator does share the same data type. But it does not have the same meaning. I would have used char* to indicate that meaning of the data.

Redeclaring functions.

You don't actually need to re-declare the friend functions. The friend declaration in the class should be enough.

void swap(String &first, String &second);

String operator+(String lhs, String const &rhs);

std::ostream &operator<<(std::ostream &os, const String &s);

bool operator<(String const &lhs, String const &rhs);
bool operator>(String const &lhs, String const &rhs);

bool operator==(String const &lhs, String const &rhs);
bool operator!=(String const &lhs, String const &rhs);

noexcept

You should mark the swap() function as no except (it is noexcept) but it makes using it from other noexcept functions useful (like move constructor and move assignment).

void swap(String &first, String &second)
{
    using std::swap;
    swap(first.data_size, second.data_size);
    swap(first.data, second.data);
    swap(first.ref_cnt, second.ref_cnt);
}

Print more efficiently.

This is probably the most inefficient way to print the string. You are calling the output operator for each character in the string. Also the stream operator is already overloaded for char* so you can do this with a single line.

std::ostream &operator<<(std::ostream &os, const String &s)
{
    for (auto c : s)
        os << c;
    return os;
}

Comparison

I see you are trying to define everything in terms of operator<

bool operator<(String const &lhs, String const &rhs)
{
    return rhs.compare(lhs) < 0;
}

bool operator>(String const &lhs, String const &rhs)
{
    return rhs < lhs;
}

bool operator==(String const &lhs, String const &rhs)
{
    return !(lhs < rhs) && !(lhs > rhs);
}

bool operator!=(String const &lhs, String const &rhs)
{
    return !(lhs == rhs);
}

But as a result I think you have made these less efficient than they could be. I would define all these operators in terms of compare().

Assumptions.

// Allocated memory is always data_size + 1,
// since the last char is required to store the null character

Do you need to store the null character. Are there any functions that you use require that functionality?

The constructors allocate the extra byte. But they don't set that last byte to '\0'. So currently they have indeterminate value.

One line per variable.

Just like declaring one variable per line. It also a good idea to use one line per variable n the initializer list.

String::String():
    data_size(0), data(new char[data_size + 1]()), ref_cnt(new int())

// I would do:

String::String()
    : data_size(0)
    , data(new char[data_size + 1]())
    , ref_cnt(new int())

DRY Code

Seems like I have seen this clip of code more than once.

    *ref_cnt = *ref_cnt - 1;
    if (*ref_cnt == 0) {
        delete ref_cnt;
        delete[] data; 
    }

May want to wrap this in a function.

share|improve this answer
    
Won't new char[size]() set all bytes to '\0'? – In78 Feb 21 at 14:17
    
@In78: Yes it will. Missed that. – Loki Astari Feb 21 at 14:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.