C++STL库String类实现

2022-05-14 09:17:58

前言：按照源码中String类的设计方式实现简单的写了一个myString，参考C++官网中的标准stringAPI完成几乎所有的String类的方法，尽量与源码实现风格类似，有部分没实现有的功能之间相似度较高，重复工作意义不大就没写，有的是没办法写。

亲自在我写的数据结构课设哈弗曼树中使用，没有出现特殊问题，自己测试也没有出问题，如果哪里有错希望大家可以给我指出来。

(一) 关于扩容

在开始写的时候我先查阅相关资料和源码，对与String的扩容，我发现在源码中String的实现里，它预先会有一个16字节的在栈区的缓冲区，如果你的String对象不到16字节，则不会申请堆区内存使用这部分栈区内存，在所占内存较小的情况下，直接使用栈区内存的会增强运行效率，提高CPU cage命中率，而当你使用的string类占据内存过大时，据我查我的系统（Deepin 15.10.1），默认栈内存只开辟8192KB。

如果String类对象所占内存过大，很有可能程序直接爆栈，所以，在字符串内存高于16字节时，会开辟堆区内存，在源码中，为了节省空间，在这里使用了一个联合体，下面是该联合体结构。

我自己模拟的结构

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

在扩容的时候，我采用一种二倍扩容的方法，我判断字符串占满以申请的空间，我会使用c语言库函数的realloc函数申请一块之前容量两倍的空间，由于在realloc在实现的时候是如果在你当时字符串后面有足够的内存，则直接扩容，如果没有，则在内存足够大的地方申请够内存，然后将数据复制到新内存，然后在free掉老内存，这样处理的效率比较高，既不会经常分配新内存，也不会因为分配内存的占据过多消耗，当时学长说可以自己写一个内存池来处理，我赶着写课设也就没去实现。
这是函数实现

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

（二）关于输入重载

这里我没有想到很好的解决方案，就很蠢的直接申请一块够大的内存让他往进写，写完之后在对这块内存进行处理，小于16字节，则复制到缓存区，大于则调用rrize()函数重新分配空间，然后在释放到之前申请的大块空间。
下面是代码实现

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;
}

关于Find()函数的实现

这里我写了两个find函数的实现，其中一个find()函数是直接调用c库函数strstr()，一个是手写KMP算法的fastfind()，听说c++源代码的find函数是使用的BF算法…我个人认为可能是感觉kmp算法还需要申请一段额外空间给next()数组，所以就没有使用，但是我也没具体查真是原因。
代码实现如下

//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());
}

就不多说了，直接看源码比较好

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);              //扩容
    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;
}

又水了一篇，以后尽量少水

Randy__Lambert 发布了24 篇原创文章 · 获赞 86 · 访问量 1140 私信关注

码农公寓

(一) 关于扩容

（二）关于输入重载

关于Find()函数的实现

就不多说了，直接看源码比较好

相关文章