12
\$\begingroup\$

The following is my attempt at a string class that behaves like std::string. Any feedback would be appreciated.

my_string.h

#pragma once

#include <stdexcept>

//class that attempts to emulate the behavior of std::string
//uses allocator in order to be able to store uninitialized data
class my_string
{
private:
    size_t m_size;
    size_t m_space;
    char* m_contents;
    std::allocator<char> alloc;

    //destroys and deallocates memory owned by m_contents
    void cleanup();

    //helper functions for my_string::insert
    my_string& reserve_and_add(const size_t n, char c);
    my_string& reserve_and_add(const size_t n, const char* s);
    void shift_and_insert(size_t pos, size_t n, char c);
    void shift_and_insert(size_t pos, const char* s, size_t s_size, size_t new_end);
    void allocate_and_insert(size_t pos, size_t n, char c);
    void allocate_and_insert(size_t pos, const char* s, size_t s_size, size_t new_end);

public:
    using value_type = char;
    using iterator = char*;
    using const_iterator = const char*;

    my_string();
    //contents must be null-terminated. otherwise, behavior is undefined.
    my_string(const char* contents);
    //stores n elements with value c in m_contents
    my_string(size_t n, char c);

    //copy functions perform a deep copy on rhs. space of copy arg is not copied.
    my_string(const my_string& rhs);
    my_string& operator=(const my_string& rhs);

    //like the copy functions, the move functions do not copy space of args.
    my_string(my_string&& rhs) noexcept;
    my_string& operator=(my_string&& rhs) noexcept;

    size_t size() const noexcept
    {
        return m_size;
    }

    //size including terminating zero
    size_t tot_size() const noexcept
    {
        return m_size == 0 ? 0 : m_size + 1;
    }

    size_t capacity() const noexcept
    {
        return m_space;
    }

    char& operator[](size_t n)
    {
        return m_contents[n];
    }

    const char& operator[](size_t n) const
    {
        return m_contents[n];
    }

    char& at(size_t n);
    const char& at(size_t n) const;

    iterator begin()
    {
        return &m_contents[0];
    }

    const_iterator begin() const noexcept
    {
        return &m_contents[0];
    }

    const_iterator cbegin() const noexcept
    {
        return &m_contents[0];
    }

    iterator end()
    {
        return &m_contents[m_size];
    }

    const_iterator end() const noexcept
    {
        return &m_contents[m_size];
    }

    const_iterator cend() const noexcept
    {
        return &m_contents[m_size];
    }

    //reserves space for n chars and copies old elements to new space.
    void reserve(size_t n);

    void resize(size_t n, char c);
    void resize(size_t n) { resize(n, ' '); }

    const char* c_str() const noexcept
    { 
        return m_contents; 
    }

    //inserts n elements with value c starting at index pos
    my_string& insert(size_t pos, size_t n, char c);
    //inserts C-style string s at index pos
    my_string& insert(size_t pos, const char* s);

    //erases count elemenets starting at index
    my_string& erase(size_t index, size_t count);
    //erases pos if it is found in m_contents
    iterator erase(const_iterator pos);

    void pop_back();

    void push_back(char c);

    my_string& operator+=(const my_string& rhs);
    ~my_string();
};

my_string.cpp

my_string::my_string()
:m_contents{ nullptr }, m_size{ 0 }, m_space{ 0 }{}

my_string::my_string(const char* contents)
    : m_size{ my_strlen(contents) }, m_space{ tot_size()},
    m_contents{ alloc.allocate(m_space) }
{
    for (int i = 0; i < m_size; ++i)
    {
        alloc.construct(&m_contents[i], contents[i]);
    }
    alloc.construct(&m_contents[m_size], '\0');
}

my_string::my_string(size_t size, char c)
    :m_size{ size }, m_space{ size + 1 },
    m_contents{ alloc.allocate(m_space) }
{
    for (int i = 0; i < m_size; ++i)
    {
        alloc.construct(&m_contents[i], c);
    }
    alloc.construct(&m_contents[m_size], '\0');
}

my_string::my_string(const my_string& rhs)
    :m_size{ rhs.m_size }, m_space{ rhs.tot_size() },
    m_contents{ alloc.allocate(m_space) }
{
    for (int i = 0; i < m_size; ++i)
    {
        alloc.construct(&m_contents[i], rhs.m_contents[i]);
    }
    alloc.construct(&m_contents[m_size], '\0');
}

my_string& my_string::operator=(const my_string& rhs)
{
    char* temp = alloc.allocate(rhs.tot_size());
    for (int i = 0; i < rhs.m_size; ++i)
    {
        alloc.construct(&temp[i], rhs.m_contents[i]);
    }
    alloc.construct(&temp[rhs.m_size], '\0');
    cleanup();
    m_contents = temp;
    m_size = rhs.m_size;
    m_space = tot_size();
    return *this;
}

my_string::my_string(my_string&& rhs) noexcept
    :m_size{ rhs.m_size }, m_space{ rhs.tot_size() },
    m_contents{ rhs.m_contents }
{
    rhs.m_contents = nullptr;
    rhs.m_size = rhs.m_space = 0;
}

my_string& my_string::operator=(my_string&& rhs) noexcept
{
    cleanup();
    m_contents = rhs.m_contents;
    m_size = rhs.m_size;
    m_space = tot_size();
    rhs.m_contents = nullptr;
    rhs.m_size = rhs.m_space = 0;
    return *this;
}

char & my_string::at(size_t n)
{
    if (n >= m_size) throw std::out_of_range{ "invalid index passed to my_string::at" };
    return m_contents[n];
}

const char & my_string::at(size_t n) const
{
    if (n >= m_size) throw std::out_of_range{ "invalid index passed to my_string::at" };
    return m_contents[n];
}


//reserves new uninitialized space by reallocating. can only reserve 
// more than the current space
void my_string::reserve(size_t n)
{
    if (n <= m_space) return;
    char* temp = alloc.allocate(n);
    if (m_size)
    {
        for (int i = 0; i < tot_size(); ++i)
        {
            alloc.construct(&temp[i], m_contents[i]);
        }
        for (int i = 0; i < tot_size(); ++i)
        {
            alloc.destroy(&m_contents[i]);
        }
    }
    alloc.deallocate(m_contents, m_space);
    m_contents = temp;
    m_space = n;
}

void my_string::resize(size_t n, char c)
{
    if (n > m_space) reserve(n + 1);
    for (int i = n; i < tot_size(); ++i) alloc.destroy(&m_contents[i]);
    for (int i = m_size; i < n; ++i) alloc.construct(&m_contents[i], c);
    alloc.construct(&m_contents[n], '\0');
    m_size = n;
}


my_string & my_string::reserve_and_add(const size_t n, char c)
{
    reserve(n + 1);
    for (int i = 0; i < n; ++i) alloc.construct(&m_contents[i], c);
    alloc.construct(&m_contents[n], '\0');
    m_size += n;
    return *this;
}

my_string & my_string::reserve_and_add(const size_t n, const char * s)
{
    reserve(n + 1);
    for (int i = 0; i < n + 1; ++i) alloc.construct(&m_contents[i], s[i]);
    m_size += n;
    return *this;
}

//the elements in the range [new_end, new_end - elems_moving)
//are the ones that will be shifted n spaces to the right for 
//both shift_and_insert functions
void my_string::shift_and_insert(size_t pos, size_t n, char c)
{
    const auto elements_moving = (tot_size()) - pos;
    const auto new_end = m_size + n;
    for (auto i = new_end; i > new_end - elements_moving; --i)
    {
        m_contents[i] = m_contents[i - n];
    }
    for (int i = 0; i < n; ++i)
    {
        m_contents[pos + i] = c;
    }
}

void my_string::shift_and_insert(size_t pos, const char * s, size_t s_size, size_t new_end)
{
    const int elements_moving = tot_size() - pos;
    for (auto i = new_end; i > new_end - elements_moving; --i)
    {
        m_contents[i] = m_contents[i - s_size];
    }
    for (auto i = 0; i < s_size; ++i)
    {
        m_contents[pos + i] = s[i];
    }
}

void my_string::allocate_and_insert(size_t pos, size_t n, char c)
{
    //allocate more memory than needed to save for future insertion operations
    char* temp = alloc.allocate(m_space * 2 + n);
    //initialize elements before insertion, the insertion itself, then elements after
    for (auto i = 0; i < pos; ++i) alloc.construct(&temp[i], m_contents[i]);
    for (auto i = 0; i < n; ++i) alloc.construct(&temp[pos + i], c);
    for (auto i = pos; i < m_size; ++i)
    {
        alloc.construct(&temp[i + n], m_contents[i]);
    }
    alloc.construct(&temp[size() + n], '\0');
    cleanup();
    m_contents = temp;
}

void my_string::allocate_and_insert(size_t pos, const char * s, size_t s_size, size_t new_end)
{
    char* temp = alloc.allocate(tot_size() + s_size);
    for (int i = 0; i < pos; ++i)
    {
        alloc.construct(&temp[i], m_contents[i]);
    }
    for (int i = 0; i < s_size; ++i)
    {
        alloc.construct(&temp[pos + i], s[i]);
    }
    for (auto i = pos; i < m_size; ++i)
    {
        alloc.construct(&temp[i + s_size], m_contents[i]);
    }
    alloc.construct(&temp[new_end], '\0');
    m_contents = temp;
    m_space = m_size + s_size + 1;
}

//inserts n elements starting at index pos with the value of c
//checks to see if there is already enough in the reserve; 
//otherwise, allocates new memory
my_string & my_string::insert(size_t pos, size_t n, char c)
{
    if (pos > size()) throw std::out_of_range{ "Invalid index arg to my_string::insert" };

    if (size() == 0) return reserve_and_add(n, c);

    if (n + m_size <= m_space) shift_and_insert(pos, n, c);

    else allocate_and_insert(pos, n, c);

    m_size += n;
    return *this;
}

my_string& my_string::insert(size_t pos, const char* s)
{
    if (pos > size()) throw std::out_of_range{ "Invalid index arg to my_string::insert" };

    const int s_size = my_strlen(s);

    if (size() == 0) return reserve_and_add(s_size, s);

    const int new_end = size() + s_size;

    if (s_size + tot_size() <= m_space) shift_and_insert(pos, s, s_size, new_end);

    else allocate_and_insert(pos, s, s_size, new_end);

    m_size += s_size;
    return *this;
}

my_string & my_string::erase(size_t index, size_t count)
{
    if (index >= m_size) throw std::out_of_range{ "out of range index to my_string::erase" };
    if (m_size == 0 || count == 0) return *this;
    //don't want to remove more elems than there are in the string
    const auto num_elems_removing = min(m_size - index, count);
    const auto num_elems_shifting = m_size - (index + num_elems_removing);
    const auto new_size = m_size - num_elems_removing;
    for (int i = 0; i < num_elems_shifting; ++i)
    {
        m_contents[i + index] = m_contents[i + index + num_elems_removing];
    }
    for (int i = new_size; i < tot_size(); ++i)
    {
        alloc.destroy(&m_contents[i]);
    }
    m_size = new_size;
    alloc.construct(&m_contents[m_size], '\0');
    return *this;
}

my_string::iterator my_string::erase(const_iterator pos)
{
    auto elem = std::find(begin(), end(), *pos);
    if (elem == end()) return elem;

    //this loop also copies back the terminating zero
    for (auto iter = elem; iter != end(); ++iter)
    {
        *iter = *(iter + 1);
    }
    --m_size;
    return elem;
}

void my_string::pop_back()
{
    if (m_size == 0) return;
    m_contents[m_size - 1] = '\0';
    alloc.destroy(&m_contents + m_size);
    //destroy old terminating zero
    alloc.destroy(&m_contents + m_size + 1);
    --m_size;
}

void my_string::push_back(char c)
{
    if (m_space == 0) reserve(8);
    else if (tot_size() == m_space) reserve(2 * m_space);
    alloc.construct(&m_contents[size()], c);
    alloc.construct(&m_contents[size() + 1], '\0');
    ++m_size;
}

my_string & my_string::operator+=(const my_string & rhs)
{
    return insert(m_size, rhs.c_str());
}

my_string::~my_string()
{
    cleanup();
}

std::ostream & operator<<(std::ostream & os, const my_string & rhs)
{
    return os << rhs.c_str();
}

void my_string::cleanup()
{
    for (int i = 0; i < tot_size(); ++i) alloc.destroy(&m_contents[i]);
    alloc.deallocate(m_contents, m_space);
}

size_t my_strlen(const char* str)
{
    size_t size = 0;
    while (*str)
    {
        ++size;
        ++str;
    }
    return size;
}
\$\endgroup\$
  • 2
    \$\begingroup\$ One thing you should have noticed is ,that std::basic_string abstracts out the character types to use as a template parameter. Your code probably won't work well with unicode characters. \$\endgroup\$ – πάντα ῥεῖ Apr 15 '18 at 14:55
  • \$\begingroup\$ Why do you force potential users of your class to read through the private section, which they can't access, first? \$\endgroup\$ – yuri Apr 15 '18 at 17:15
  • \$\begingroup\$ my_string.cpp won't compile if it doesn't include my_string.h. I would suggest to move some more functions to the header. Especially that default constructor. Even better IMO is to stick it all in the header. Also add a namespace. Those things are really useful. \$\endgroup\$ – Cris Luengo Apr 15 '18 at 18:57
11
\$\begingroup\$
  1. Where are your includes? I only see #include <stdexcept>. However, there should be a lot more: #include <memory> for std::allocator, #include <cstddef> for std::size_t, #include <ostream> for std:ostream, #include <algorithm> for std::find, etc. Add them, or a conforming compiler may refuse to accept your code.
  2. Why do you even include stdexcept here? You don't use anything from it!
  3. You don't forward declare my_strlen, thus it shouldn't be visible further up in my_string.cpp. A conforming compiler actually has to reject your program because of this.
  4. Maybe you wondered about me mentioning std::size_t instead of size_t without the prefix in point 1? C++ only guarantees that the legacy C types exist in the std namespace (provided that the right headers are included) whereas their existence in the global namespace is not mandatory. You should thus prefer the std:: versions of those functions at all times.
  5. What is the point of using std::allocator over normal new/delete here? Normally, standard containers support allocators through template parameters in order to facilitate the use of different allocation managers and schemes. However, your code doesn't take an allocator template parameter, so there is nothing useful you can do with allocators here.
  6. Building on point 5: If you remove that useless std::allocator, you can actually simplify a lot of your code to use std::memset/std::memcpy/std::strncpy/etc. to move and copy data around.
  7. Let's take a look at for (int i = 0; i < m_size; ++i). There is an issue here that you don't seem to have thought through thoroughly: m_size is of type std::size_t, which is not only unsigned but also larger than int on many common platforms (most importantly, x86-64). That means that I can easily exploit your code to have undefined behavior if I make a string bigger than std::numeric_limits<int>::max() characters, in which case your code will have undefined behavior due to signed integer overflow. It is good practice in general to ensure that loop iteration variables are always the same size (or larger) than the loop bound type.
  8. Utilize the copy-and-swap idiom for move assignment operators. Instead of calling cleanup() manually and then tediously reassigning values from one object to another, just swap the contents of each member variable with its equivalent on the move-from side and have the destructor of the move-from side handle the cleanup eventually.
  9. If you are striving for noexcept correctness, the move constructor should be noexcept, as well as both operator[]s, and begin and end, too.
  10. void resize(size_t n) { resize(n, ' '); } seems dubious. If you are following the std::string specification, that code should probably be void resize(size_t n) { resize(n, 0); }, since the default value for type char is 0 (as for all other integral types).
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks for the response. Do you think it would be better to use std::move in functions like reserve ( alloc.construct(&temp[i], std::move(m_contents[i])); ), or would it not make a difference for chars? \$\endgroup\$ – Equilibrium Apr 16 '18 at 0:30
  • \$\begingroup\$ @Equilibrium std::move makes only sense which are not trivially to move from (e.g. types with a dynamically allocated data member), so using it on chars will gain you nothing. \$\endgroup\$ – Ben Steffan Apr 16 '18 at 5:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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