String class implementation of C++STL Library

Foreword: Simply write a myString according to the design method of String class in source code. Standard String API in C++ Official Web Complete nearly all the String class methods, as much as possible similar to the source implementation style, some of the functions that are not implemented have a high degree of similarity, repeat work is not meaningful, or can not be written.

I have written the data structure lesson in person in Haffman tree use, there are no special problems, their own test is not a problem, if there are any errors I hope you can point out.

(1) About capacity expansion

When I started writing, I looked up the relevant data and source code first. For the extension to String, I found that in the implementation of String in source code, it would have a 16-byte buffer in the stack beforehand. If your String object is less than 16 bytes, you will not request the stack memory to use this part of the stack memory. In case of small memory consumption, direct use of the stack memory will be enhanced.Run efficiently to improve CPU cage hit ratio, but when you use string classes that occupy too much memory, check my system (Deepin 15.10.1) for only 8192 KB of default stack memory.

If the String class object occupies too much memory, it is likely that the program will directly explode the stack, so if the string memory is higher than 16 bytes, it will open up the heap memory. In the source code, to save space, a consortium is used here, which is the consortium structure below.

My own simulated structure

enum
    {
        BUF_LEN = 16
    };
    union _Bxty {
        char _Buf[BUF_LEN];
        char *_ptr;
    } _Bx;

When expanding, I use a method of double expansion. I judge that the string is full to the requested space. I will use the realloc function of the c-language library function to request a space twice as large as the previous one. Since realloc is implemented when you have enough memory behind the string at that time, it will expand directly. If it is not, it will expand where the memory is large enough.Please have enough memory, then copy the data to the new memory, and then free away the old memory. This is a more efficient way to process. Neither new memory will be allocated frequently, nor will it be consumed too much because of the memory allocation. At that time, the master said that he could write a memory pool to process it by himself, so I was too busy writing lesson settings.
This is a function implementation

inline void myString::rrsize(size_t x)
{
    if (ssize < x)
        _Bx._ptr = (char *)realloc(_Bx._ptr, x * 2);
}

(2) About input overload

I didn't think of a good solution here, so I was foolish enough to request a large block of memory for him to write in. After writing, I processed the block of memory, which was less than 16 bytes, then copied to the cache, called the rrize() function to reallocate the space, and then freed up the large block of space previously requested.
Here is the code implementation

std::istream &operator>>(std::istream &in, myString &str)
{
    char *tp = new char[1024];
    in >> tp;
    if (strlen(tp) <= 15)
    {
        strcpy(str._Bx._Buf, tp);
        str.ssize = strlen(tp);
    }
    else
    {
        str.rrsize(strlen(tp));
        strcpy(str._Bx._ptr, tp);
    }
    delete[] tp;
    return in;
}

About the Implementation of Find() Function

Here I have written two implementations of the find function, one of which is to call the C library function strstr() directly, the other is to fast find() of the handwritten KMP algorithm, and the other is to hear that the find function of the c++ source code is the BF algorithm that is used...I personally think it may feel like the KMP algorithm still needs to request some extra space for the next() array, so it's not used, but I'm not really sure why.
The code is implemented as follows

//fastfind
const char *myString::getnext(const char *w)
{
    int wlen = strlen(w);

    char *next1 = new char[wlen + 1];
    int j = 0, k = -1;
    next1[0] = -1;

    while (j < wlen)
    {
        if (k == -1 || w[k] == w[j])
        {
            ++k;
            ++j;
            next1[j] = k;
        }
        else
        {
            k = next1[k];
        }
    }
    return next1;
}

const char *myString::fastfind(const myString &w)
{

    int tlen = w.ssize;
    const char *next1 = getnext(w.c_str());

    int i = 0, j = 0;
    while (j < tlen)
    {
        if (i == -1 || w[i] == at(j))
        {
            i++;
            j++;
        }
        else
        {
            i = next1[i];
        }
    }
    if (next1 != NULL)
    {
        delete[] next1;
    }

    if (j == tlen)
    {
        return (char *)&at(i - j);
    }
    else
    {
        return NULL;
    }
}

find

const char *myString::find(const myString &w) const
{
    return strstr(c_str(), w.c_str());
}

Not to mention, it's better to look directly at the source code

myString.h

#ifndef MYSTRING_H_
#define MYSTRING_H_
#include <iostream>
#include <cstring>
#include <cstdlib>

class myString
{
    friend std::ostream &operator<<(std::ostream &out, myString &str);
    friend std::istream &operator>>(std::istream &in, myString &str);

public:
    myString();
    myString(const myString &str);
    myString(const myString &str, size_t pos, size_t len);
    myString(const char *s);
    myString(const char *s, size_t n);
    myString(size_t n, char c);
    ~myString();
    void clear() noexcept;
    char front() const;
    char back() const;
    //const char *end() const;
    //const char *begin() const;

    const char *c_str() const;
    size_t length() const noexcept;
    size_t size() const noexcept;
    const char *find(const myString &w) const;
    const char *fastfind(const myString &w);

    char &operator[](size_t pos);
    const char &operator[](size_t pos) const;
    myString &operator=(const myString &str);
    myString &operator=(const char *s);
    myString &operator=(char c);
    myString &operator+=(const myString &str);
    myString &operator+=(const char *s);
    myString &operator+=(char c);

    myString &append(const myString &str);
    myString &append(const char *s);

    myString &assign(const myString &str);
    myString &assign(const char *s);

    char &at(size_t pos);
    const char &at(size_t pos) const;
    
    int compare(const myString &str) const;
    int compare(const char *s) const;
    void swap(myString &str);
    const char *data() const;
    bool empty() const;

private:
    enum
    {
        BUF_LEN = 16
    };

    size_t ssize;
    union _Bxty {
        char _Buf[BUF_LEN];
        char *_ptr;
    } _Bx;

    void rrsize(size_t x);              //Expansion
    const char *getnext(const char *w); //kmp
};

bool operator==(const myString &lhs, const myString &rhs);
bool operator==(const char *lhs, const myString &rhs);
bool operator==(const myString &lhs, const char *rhs);
bool operator!=(const myString &lhs, const myString &rhs);
bool operator!=(const char *lhs, const myString &rhs);
bool operator!=(const myString &lhs, const char *rhs);
bool operator<(const myString &lhs, const myString &rhs);
bool operator<(const char *lhs, const myString &rhs);
bool operator<(const myString &lhs, const char *rhs);
bool operator<=(const myString &lhs, const myString &rhs);
bool operator<=(const char *lhs, const myString &rhs);
bool operator<=(const myString &lhs, const char *rhs);
bool operator>(const myString &lhs, const myString &rhs);
bool operator>(const char *lhs, const myString &rhs);
bool operator>(const myString &lhs, const char *rhs);
bool operator>=(const myString &lhs, const myString &rhs);
bool operator>=(const char *lhs, const myString &rhs);
bool operator>=(const myString &lhs, const char *rhs);
myString operator+(const myString &lhs, const myString &rhs);
myString operator+(const myString &lhs, const char *rhs);
myString operator+(const char *lhs, const myString &rhs);
myString operator+(const myString &lhs, char rhs);
myString operator+(char lhs, const myString &rhs);

#endif

myString.cpp

#include "myString.h"
inline void myString::rrsize(size_t x)
{
    if (ssize < x)
        _Bx._ptr = (char *)realloc(_Bx._ptr, x * 2);
}

std::ostream &operator<<(std::ostream &out, myString &str)
{
    if (str.length() <= 15)
    {
        out << str._Bx._Buf;
    }
    else
    {
        out << str._Bx._ptr;
    }
    return out;
}

std::istream &operator>>(std::istream &in, myString &str)
{
    char *tp = new char[1024];
    in >> tp;
    if (strlen(tp) <= 15)
    {
        strcpy(str._Bx._Buf, tp);
        str.ssize = strlen(tp);
    }
    else
    {
        str.rrsize(strlen(tp));
        strcpy(str._Bx._ptr, tp);
    }
    delete[] tp;
    return in;
}

inline char &myString::operator[](size_t pos)
{
    if (ssize <= 15)
        return _Bx._Buf[pos];
    else
        return _Bx._ptr[pos];
}

inline const char &myString::operator[](size_t pos) const
{
    if (pos >= ssize)
        return '\0';
    else if (ssize <= 15)
        return _Bx._Buf[pos];
    else
        return _Bx._ptr[pos];
}

inline const char *myString::c_str() const
{
    if (ssize <= 15)
    {
        return _Bx._Buf;
    }
    else
    {
        return _Bx._ptr;
    }
}

int myString::compare(const myString &str) const
{
    return strcmp(c_str(), str.c_str());
}
int myString::compare(const char *s) const
{
    return strcmp(c_str(), s);
}

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

bool operator==(const char *lhs, const myString &rhs)
{
    return (rhs.compare(lhs) == 0);
}

bool operator==(const myString &lhs, const char *rhs)
{
    return (lhs.compare(rhs) == 0);
}

bool operator!=(const myString &lhs, const myString &rhs)
{
    return (lhs.compare(rhs) != 0);
}

bool operator!=(const char *lhs, const myString &rhs)
{
    return (rhs.compare(lhs) != 0);
}

bool operator!=(const myString &lhs, const char *rhs)
{
    return (lhs.compare(rhs) != 0);
}

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

bool operator<(const char *lhs, const myString &rhs)
{
    return (rhs.compare(lhs) >= 0);
}

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

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

bool operator<=(const char *lhs, const myString &rhs)
{
    return (rhs.compare(lhs) > 0);
}

bool operator<=(const myString &lhs, const char *rhs)
{
    return (lhs.compare(rhs) <= 0);
}

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

bool operator>(const char *lhs, const myString &rhs)
{
    return (rhs.compare(lhs) <= 0);
}

bool operator>(const myString &lhs, const char *rhs)
{
    return (lhs.compare(rhs) > 0);
}

bool operator>=(const myString &lhs, const myString &rhs)
{
    return (lhs.compare(rhs) >= 0);
}

bool operator>=(const char *lhs, const myString &rhs)
{
    return (rhs.compare(lhs) < 0);
}

bool operator>=(const myString &lhs, const char *rhs)
{
    return (lhs.compare(rhs) >= 0);
}

myString &myString::operator=(char c)
{
    if (ssize <= 15)
    {
        memset(_Bx._Buf, 0, sizeof(_Bx._Buf));
        strcpy(_Bx._Buf, (char *)&c);
    }
    else
    {
        memset(_Bx._ptr, 0, ssize);
        strcpy(_Bx._ptr, (char *)&c);
    }
    ssize = 1;
    return *this;
}

myString &myString::operator=(const char *s)
{
    if (strlen(s) <= 15)
    {
        memset(_Bx._Buf, 0, sizeof(_Bx._Buf));
        strcpy(_Bx._Buf, s);
    }
    else
    {
        rrsize(strlen(s));
        memset(_Bx._ptr, 0, 2 * strlen(s));
        strcpy(_Bx._ptr, s);
    }
    ssize = strlen(s);
    return *this;
}

myString &myString::operator=(const myString &str)
{
    if (ssize <= 15)
    {
        if (str.ssize <= 15)
        {
            memset(_Bx._Buf, 0, sizeof(_Bx._Buf));
            strcpy(_Bx._Buf, str.c_str());
        }
        else
        {
            rrsize(str.ssize);
            strcpy(_Bx._ptr, str.c_str());
        }
    }
    else
    {
        if (str.ssize <= 15)
        {
            delete[] _Bx._ptr;
            memset(_Bx._Buf, 0, sizeof(_Bx._Buf));
            strcpy(_Bx._Buf, str.c_str());
        }
        else
        {
            rrsize(str.ssize);
            memset(_Bx._ptr, 0, ssize);
            strcpy(_Bx._ptr, str.c_str());
        }
    }
    ssize = str.size();
    return *this;
}

myString &myString::operator+=(const char *s)
{
    size_t len = strlen(s);
    if (len + ssize <= 15)
    {
        strcat(_Bx._Buf, s);
        ssize = strlen(_Bx._Buf);
    }
    else
    {
        if (ssize <= 15)
        {
            ssize += len;
            char *tp = new char[ssize * 2];
            strcpy(tp, _Bx._Buf);
            strcat(tp, s);
            _Bx._ptr = tp;
        }
        else
        {
            ssize += len;
            char *tp = new char[ssize * 2];
            strcpy(tp, _Bx._ptr);
            strcat(tp, s);
            delete[] _Bx._ptr;
            _Bx._ptr = tp;
        }
    }
    return *this;
}

myString &myString::operator+=(char c)
{
    if (1 + ssize <= 15)
    {
        strcat(_Bx._Buf, (char *)&c);
        ssize++;
    }
    else
    {
        if (ssize <= 15)
        {
            ssize += 1;
            char *tp = new char[ssize * 2];
            strcpy(tp, _Bx._Buf);
            strcat(tp, (char *)&c);
            _Bx._ptr = tp;
        }
        else
        {
            ssize += 1;
            char *tp = new char[ssize * 2];
            strcpy(tp, _Bx._ptr);
            strcat(tp, (char *)&c);
            delete[] _Bx._ptr;
            _Bx._ptr = tp;
        }
    }
    return *this;
}

myString &myString::operator+=(const myString &str)
{
    std::cout << str.length() + ssize << std::endl;
    if (str.length() + ssize <= 15)
    {
        strcat(_Bx._Buf, str.c_str());
        ssize = strlen(_Bx._Buf);
    }
    else
    {
        if (ssize <= 15)
        {
            ssize += str.ssize;
            char *tp = new char[ssize * 2];
            strcpy(tp, _Bx._Buf);
            strcat(tp, str.c_str());
            _Bx._ptr = tp;
        }
        else
        {
            ssize += str.ssize;
            char *tp = new char[ssize * 2];
            strcpy(tp, _Bx._ptr);
            strcat(tp, str.c_str());
            delete[] _Bx._ptr;
            _Bx._ptr = tp;
        }
    }
    return *this;
}

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

myString operator+(const myString &lhs, const char *rhs)
{
    myString str(lhs);
    str += rhs;
    return str;
}

myString operator+(const char *lhs, const myString &rhs)
{
    myString str(lhs);
    str += rhs;
    return str;
}

myString operator+(const myString &lhs, char rhs)
{
    myString str(lhs);
    str += rhs;
    return str;
}

myString operator+(char lhs, const myString &rhs)
{
    myString str(&lhs);
    str += rhs;
    return str;
}

myString::myString()
{
    ssize = 0;
    memset(&_Bx, 0, sizeof(_Bx));
}

myString::myString(const myString &str)
{
    ssize = 0;
    memset(&_Bx, 0, sizeof(_Bx));
    if (str.ssize <= 15)
    {
        strcpy(_Bx._Buf, str.c_str());
    }
    else
    {
        rrsize(str.length());
        strcpy(_Bx._ptr, str.c_str());
    }
    ssize = str.length();
}

myString::myString(const char *s)
{
    ssize = 0;
    memset(&_Bx, 0, sizeof(_Bx));
    size_t tp = strlen(s);
    if (tp <= 15)
    {
        strcpy(_Bx._Buf, s);
        _Bx._Buf[tp] = '\0';
    }
    else
    {
        rrsize(tp);
        strcpy(_Bx._ptr, s);
        _Bx._ptr[tp] = '\0';
    }
    ssize = tp;
}

myString::myString(size_t n, char c)
{
    ssize = 0;
    memset(&_Bx, 0, sizeof(_Bx));
    if (n <= 15)
    {
        for (size_t i = 0; i < n; i++)
            _Bx._Buf[i] = c;
    }
    else
    {
        rrsize(n);
        for (size_t i = 0; i < n; i++)
            _Bx._ptr[i] = c;
    }
    ssize = n;
}

myString::myString(const char *s, size_t n)
{
    ssize = 0;
    memset(&_Bx, 0, sizeof(_Bx));
    if (strlen(s) <= n)
    {
        ssize = strlen(s);
        if (n <= 15)
        {
            strcpy(_Bx._Buf, s);
        }
        else
        {
            rrsize(n);
            strcpy(_Bx._ptr, s);
        }
    }
    else
    {
        if (n <= 15)
        {
            strncpy(_Bx._Buf, s, n);
        }
        else
        {
            rrsize(n);
            strncpy(_Bx._ptr, s, n);
        }
        ssize = n;
    }
}

myString::myString(const myString &str, size_t pos, size_t len)
{
    ssize = 0;
    memset(&_Bx, 0, sizeof(_Bx));
    if (pos > str.ssize)
    {
        ssize = 0;
    }
    else
    {
        if (pos + len > str.ssize)
            ssize = str.ssize - pos;
        else
            ssize = len;

        if (ssize <= 15)
        {
            for (size_t i = 0; i < ssize; i++)
            {
                const char *p = str.c_str() + pos;
                _Bx._Buf[i] = p[i];
            }
            _Bx._Buf[ssize] = '\0';
        }
        else
        {
            rrsize(len + 1);
            const char *p = str.c_str() + pos;
            for (size_t i = 0; i < ssize; i++)
            {
                _Bx._ptr[i] = p[i];
            }
            _Bx._ptr[ssize] = '\0';
        }
    }
}

myString::~myString()
{
    if (ssize > 15 && _Bx._ptr != nullptr)
    {
        delete[] _Bx._ptr;
    }
}

inline  size_t myString::length() const noexcept
{
    return ssize;
}

inline  size_t myString::size() const noexcept
{
    return ssize;
}

inline void myString::clear() noexcept
{
    if (ssize <= 15)
    {
        _Bx._Buf[0] = '\0';
    }
    else
    {
        delete[] _Bx._ptr;
        _Bx._Buf[0] = '\0';
    }
    ssize = 0;
}

inline bool myString::empty() const
{
    if (ssize == 0)
    {
        return true;
    }
    else
        return false;
}

char myString::front() const
{
    if (ssize == 0)
        return '\0';
    else
    {
        if (ssize <= 15)
        {
            return _Bx._Buf[0];
        }
        else
        {
            return _Bx._ptr[0];
        }
    }
}

char myString::back() const
{
    if (ssize == 0)
        return '\0';
    else
    {
        if (ssize <= 15)
        {
            return _Bx._Buf[ssize - 1];
        }
        else
        {
            return _Bx._ptr[ssize - 1];
        }
    }
}

myString &myString::append(const myString &str)
{
    *this += str;
    return *this;
}
myString &myString::append(const char *s)
{
    *this += s;
    return *this;
}

inline myString &myString::assign(const myString &str)
{
    *this = str;
    return *this;
}
inline myString &myString::assign(const char *s)
{
    *this = s;
    return *this;
}

inline const char *myString::data() const
{
    if (ssize <= 15)
    {
        return _Bx._Buf;
    }
    else
    {
        return _Bx._ptr;
    }
}

inline char &myString::at(size_t pos)
{
    if (pos <= 15)
        return _Bx._Buf[pos];
    else
    {
        return _Bx._ptr[pos];
    }
}

inline const char &myString::at(size_t pos) const
{
    if (pos <= 15)
        return _Bx._Buf[pos];
    else
    {
        return _Bx._ptr[pos];
    }
}

const char *myString::getnext(const char *w)
{
    int wlen = strlen(w);

    char *next1 = new char[wlen + 1];
    int j = 0, k = -1;
    next1[0] = -1;

    while (j < wlen)
    {
        if (k == -1 || w[k] == w[j])
        {
            ++k;
            ++j;
            next1[j] = k;
        }
        else
        {
            k = next1[k];
        }
    }
    return next1;
}

const char *myString::fastfind(const myString &w)
{

    int tlen = w.ssize;
    const char *next1 = getnext(w.c_str());

    int i = 0, j = 0;
    while (j < tlen)
    {
        if (i == -1 || w[i] == at(j))
        {
            i++;
            j++;
        }
        else
        {
            i = next1[i];
        }
    }
    if (next1 != NULL)
    {
        delete[] next1;
    }

    if (j == tlen)
    {
        return (char *)&at(i - j);
    }
    else
    {
        return NULL;
    }
}

const char *myString::find(const myString &w) const
{
    return strstr(c_str(), w.c_str());
}

void myString::swap(myString &str)
{
    myString temp = std::move(*this);
    *this = std::move(str);
    str = std::move(temp);
    //mySwap(*this, str);
}

Dbug.cpp

#include <iostream>
#include "myString.h"
using namespace std;
int main(){
    std::pair<int, myString> ls{1, "aaa"} ;
    std :: cout << ls.first << "    " << ls.second << std::endl ;
     myString a("aaaaaaaaa");
    myString b = "aaaa";
    myString c(10,'c');
    myString aa;
    cin>>aa;
    cout<<aa<<endl;
    cout<<a<<endl;
    cout<<b<<endl;
    cout<<c<<endl;
    char x = a.at(1);
    cout<<x<<endl;
    cout<<a.length()<<endl;
    cout<<a.size()<<endl;

    a.swap(b);
    /* mySwap(a,b); */
    cout<<a<<endl;
    cout<<b<<endl;
    cout<<a.length()<<endl;
    cout<<b.size()<<endl;

    cout<<a.at(0)<<endl;
    const char *ptr = b.c_str();
    cout<<ptr<<endl;

    const char *ptr2 = b.fastfind(a);
    const char *ptr1 = b.find(a);
    cout<<ptr2<<"  "<<ptr1<<endl;

    a.append(b);
    a+=b;
    a+="dasda";
    a+='c';
    cout<<a<<" "<<a.length()<<endl;

    myString d(a);
    d.size();
    d = a+b;
    cout<<d<<endl;

    if(d == a){
        cout<<"aadadad"<<endl;
    }
    if(d != a){
        cout<<"ccccccc"<<endl;
    }
    if(d > a){
        cout<<"ddddddddd"<<endl;
    }
    if(d < a){
        cout<<"aaaaaaaa"<<endl;
    }
    if(d <= a){
        cout<<"aaaaaaaa"<<endl;
    }
    if(d >= a){
        cout<<"ddddddddd"<<endl;
    }

    const char *e = "dsadasasdddsdasfsafddddddddd";
    myString f = myString(e,5);
    cout<<f<<" "<<f.size()<<endl;
    myString h = myString(e,17);
    cout<<h<<" "<<h.size()<<endl;

    cout<<h.front()<<" "<<h.back()<<endl;

    cout<<b.compare("dads")<<endl;
    return 0;
}

Another one with as little water as possible in the future

Twenty-four original articles were published. 86 were praised. 1136 were visited
Private letter follow

Tags: less

Posted on Sun, 12 Jan 2020 19:07:36 -0800 by BrianWald