string·模拟實作

你好，我是安然無虞。

文章目錄

• ​​自學網站​​
• ​​string 面試題​​
• ​​深淺拷貝問題​​

• ​​淺拷貝​​
• ​​深拷貝​​

• ​​模拟實作​​

• ​​疊代器​​

自學網站

推薦給老鐵們兩款學習網站：

面試利器&算法學習：​​​牛客網​​​ 風趣幽默的學人工智能：​​人工智能學習​​

下面我們模拟實作 string

string 面試題

面試官: 給你十分鐘, 在隻考慮資源管理深淺拷貝, 不考慮增删查改的情況下, 模拟實作string.

乍一聽, 好像很難的樣子, 其實非也, 簡直就是送分題, 不信你看:

#include<cassert>
#include<cstring>
#include<algorithm>

class string
{
public:
    //構造函數
    string(const char* str = " ")
    {
        if(str == nullptr)
        {
            assert(str);
            return;
        }
        _str = new char[strlen(str) + 1];
        strcpy(_str, str);
    }

    //析構函數
    ~string()
    {
        if(_str)
        {
            delete[] _str;
            _str = nullptr;
        }
    }

    //拷貝構造
    //過時寫法
    // string(const string& s)
    //     :_str(new char[strlen(s._str) + 1])
    // {
    //     strcpy(_str, s._str);
    // }

    //現代寫法
    void swap(string& s)
    {
        std::swap(_str, s._str);
    }
    //string s2(s1);
    string(const string& s)
        :_str(nullptr)
    {
        string tmp(s._str);
        swap(tmp);
    }

    //指派重載
    //過時寫法
    // string& operator=(const string& s)
    // {
    //     if(this != &s)
    //     {
    //         char* tmp = new char[strlen(s._str) + 1];
    //         strcpy(tmp, _str);
    //         delete[] _str;
    //         _str = tmp;
    //     }
    //     return *this;
    // }

    //現代寫法
    //s1 = s2;
    string& operator=(string s/*傳值過來就是拷貝構造*/)
    {
        swap(s);
        return *this;
    }

private:
    char* _str;
};      

深淺拷貝問題

我們看到, 上面我們是自己實作拷貝構造和指派重載函數的, 因為涉及到資源管理, 是以需要我們顯示實作成深拷貝, 如果我們沒有顯示實作成深拷貝, 而是采用編譯器預設生成的拷貝構造和指派重載函數, 那麼執行下面代碼時會有問題:

string s1("hello string");
string s2(s1);//用s2拷貝構造s1      

當編譯器采用預設生成的拷貝構造時會導緻s1和s2共用同一塊空間, 在釋放時同一塊空間會被釋放兩次,導緻程式崩潰, 這種拷貝方式稱為淺拷貝.

淺拷貝的問題:

• 同一塊空間會析構兩次;
• 其中一個修改資料也會影響另外一個(共用同一塊空間)

淺拷貝

淺拷貝, 也稱值拷貝, 編譯器隻是将對象中的值拷貝過來. 如果對象中管理資源, 最後就會導緻多個對象共用同一份資源, 當其中一個對象銷毀時該資源就被釋放掉了, 而此時另一些對象不知道該資源已經被釋放, 以為還有效, 當繼續對該資源進行操作時, 就會發生違規通路. 是以要解決淺拷貝問題, C++特意引入了深拷貝.

深拷貝

如果一個類中涉及資源的管理, 其拷貝構造函數, 指派運算符重載以及析構函數必須要顯示給出, 一般都是按照深拷貝方式實作.

模拟實作

好的, 那下面我們快來看看C++官方庫中是怎麼來實作string的, 我們自己來模拟實作一下:

首先實作string的構造, 析構, 拷貝構造, 指派重載:

namespace sl
{
    class string
    {
    public:

        //構造函數
        string(const char* str = " ")
            :_size(strlen(str))
            ,_capacity(_size)
        {
            _str = new char[_capacity + 1];//+1是因為始終要為'\0'多開一個空間
            strcpy(_str, str);
        }

        //析構函數
        ~string()
        {
            if(_str)
            {
                delete[] _str;
                _str = nullptr;
                _size = _capacity = 0;
            }
        }

        void swap(string& s)
        {
            std::swap(_str, s._str);
            std::swap(_size, s._size);
            std::swap(_capacity, s._capacity);
        }

        //拷貝構造
        string(const string& s)
            :_str(nullptr)
            ,_size(0)
            ,_capacity(0)
        {
            string tmp(s._str);
            swap(tmp);
        }

        //指派重載
        string& operator=(string s)
        {
            swap(s);
            return *this;
        }

    private:
        char* _str;
        size_t _size;//有效字元的個數
        size_t _capacity;//實際存儲有效字元的空間
    };
}      

下面再看對空間的管理:

namespace sl
{
    class string
    {
    public:
                ......
                
        size_t size()const
        {
            return _size;
        }

        size_t capacity()const
        {
            return _capacity;
        }

        void reserve(size_t n)
        {
            if(n > capacity())
            {
                char* tmp = new char[n + 1];
                strcpy(tmp, _str);
                delete[] _str;
                _str = tmp;

                _capacity = n;
            }
        }
        
        //分三種情況考慮
        void resize(size_t n, char ch = '\0')
        {
            if(n < _size)
            {
                _size = n;
                _str[_size] = ch;
            }
            else
            {
                if(n > _capacity)
                {
                    reserve(n);
                }
                for(size_t i = _size; i < n; i++)
                {
                    _str[i] = ch;
                }
                _size = n;
                _str[_size] = '\0';
            }
        }

    private:
        char* _str;
        size_t _size;
        size_t _capacity;
    };
}      

上面的接口都挺簡單的,我們在這裡就不做過多闡述了, 關于resize() 需要畫圖去了解哦, 一共有三種情況.

OK, 下面我們來看看插入删除的接口:

void push_back(char ch)
{
    if (_size == _capacity)
    {
        reserve(_capacity == 0 ? 4 : _capacity * 2);
    }

    _str[_size] = ch;
    _size++;
    _str[_size] = '\0'; // string與順序表不同, 要單獨處理末尾的'\0'
}

string &operator+=(char ch)
{
    push_back(ch);
    return *this;
}

//注意追加一個字元串不同于追加一個字元, 需要小心處理
void append(const char *str)
{
    size_t len = _size + strlen(str);
    if (len > _capacity)
    {
        reserve(len);
    }
    strcpy(_str + _size, str);
    _size = len;
}

string &operator+=(const char *str)
{
    append(str);
    return *this;
}

const char *c_str() const
{
    return _str;
}

//随機插入
string &insert(size_t pos, char ch)
{
    assert(pos <= _size);

    if (_size == _capacity)
        reserve(_capacity == 0 ? 4 : _capacity * 2);

    size_t end = _size + 1; //注意, 遇到size_t時處理起來要格外小心
    while (end > pos)
    {
        _str[end] = _str[end - 1];
        end--;
    }
    _str[pos] = ch;
    _size++;

    return *this;
}

//随機插入
string &insert(size_t pos, const char *str)
{
    assert(pos <= _size);

    size_t len = strlen(str);
    if (_size + len > _capacity)
    {
        reserve(_size + len);
    }

    //往後挪 len 個位置
    //注意這個過程較複雜需要畫圖了解
    size_t end = _size + len;
    while (end > pos + len - 1) //注意這個循環條件
    {
        _str[end] = _str[end - len];
        end--;
    }
    strncpy(_str + pos, str, len); // strcpy()會拷貝'\0'
    _size += len;

    return *this;
}

//随機删除
string &erase(size_t pos, size_t len = std::string::npos) //注意哦
{
    assert(pos < _size);

    if (len == std::string::npos || len + pos >= _size)
    {
        _str[pos] = '\0';
        _size = pos;
    }
    else
    {
        size_t begin = pos + len;
        while (begin <= _size) //注意判斷循環條件
        {
            _str[begin - len] = _str[begin];
            begin++;
        }
        _size -= len;
    }
    return *this;
}      

其實我們之前有認真實作常見的資料結構會發現這個真的不難, 對于insert() 和 erase() 接口如果不了解需要自己動手畫圖哦.

疊代器

下面我們談談疊代器部分:

疊代器可以認為就是指針或者是像指針一樣的東西, 具體看容器底層的實作.

namespace sl
{
    class string
    {
    public:
                .......
                
        typedef char *iterator;
        typedef const char *const_iterator;

        iterator begin()
        {
            return _str;
        }

        iterator end()
        {
            return _str + _size;
        }

        const_iterator begin() const
        {
            return _str;
        }

        const_iterator end() const
        {
            return _str + _size;
        }

    private:
        char *_str;
        size_t _size;
        size_t _capacity;
    };
}      

//流插入
//不需要設計成友元函數, 因為沒有通路私有成員
ostream &operator<<(ostream &out, const string &s)
{
    for (auto& e : s)
    {
        out << e;
    }
    return out;
}

//流提取
// istream& operator>>(istream& in, string& s)
// {
//     char ch;
//     //in >> ch;//注意cin不能讀取到空格和換行
//     ch = in.get();//get()便是從流中提取字元
//     while(ch != ' ' && ch != '\n')
//     {
//         s += ch;
//         ch = in.get();
//     }

//     return in;
// }

//上面實作的流提取不夠高效, 原因在于會頻繁插入資料導緻經常擴容影響效率
//優化
//流提取
istream &operator>>(istream &in, string &s)
{
    s.clear(); //将資料全部清理掉

    char ch;
    ch = in.get();
    char buff[128] = {'\0'};
    size_t i = 0;
    while(ch != '\n')
    {
        buff[i++] = ch;
        if(i == 127)
        {
            s += buff;
            memset(buff, '\0', 128);
            i = 0;
        }
        ch = in.get();
    }
    s += buff;
    
    return in;
}      

namespace sl
{
    class string
    {
    public:
            ......

        void clear()
        {
            _str[0] = '\0';
            _size = 0;//不必釋放空間
        }

        const char* c_str()const
        {
            return _str;
        }

        size_t find(const char* str, size_t pos = 0)const
        {
            const char* p = strstr(_str + pos, str);
            if(p == nullptr)
                return std::string::npos;
            else
                return p - _str;
        }

    private:
        char *_str;
        size_t _size;
        size_t _capacity;
    };
}