[C++] string类常用接口的模拟实现

短命女 2023-10-15 08:18 115阅读 0赞

![在这里插入图片描述][afbb78f1d81f445f8c0a26aea0717753.gif_pic_center]

#### 文章目录 ####

*  1、前言
 *  2、遍历
 *   *  2.1 operator\[ \]+下标方式
     *  2.2 迭代器
     *  2.3 范围for
     *  2.4 c\_str
 *  3、容量相关
 *   *  3.1 size（大小）
     *  3.2 capacity（容量）
     *  3.3 empty（判空）
     *  3.4 clear（清理）
     *  3.5 reserve
     *  3.6 resize
 *  4、增
 *   *  4.1 push\_back（尾插）
     *  4.2 operator+=（char ch）
     *  4.3 append
     *  4.4 operator+=（char\* str）
     *  4.5 insert（任意位置插入）
     *   *  4.5.1 任意位置插入字符
         *  4.5.2 任意位置插入字符串
 *  5、删
 *  6、查
 *   *  6.1 查找一个字符
     *  6.2 查找一个字符串
 *  7、字符串比较
 *  8、流插入、流提取重载
 *   *  8.1 流提取重载
     *  8.2 流插入重载

## 1、前言 ##

> string上篇我们实现了 各类构造与赋值重载 接口，点这里看[string类的介绍与构造的模拟实现][string]  
> 本篇我们对string常用的接口 **增删查改+遍历** 模拟实现一下。

以下就是要实现的接口：

namespace s
    {
        
    
      class string
      {
        
        friend ostream& operator<<(ostream& _cout, const bit::string& s);
        friend istream& operator>>(istream& _cin, bit::string& s);
    
      public:
        typedef char* iterator;
    
      public:
        //
        // iterator
        iterator begin()；
        iterator end()；
    
        /
        // modify
        void push_back(char c);
        string& operator+=(char c);
        void append(const char* str);
        string& operator+=(const char* str);
        void clear();
        void swap(string& s);
        const char* c_str()const;
    
        /
        // capacity
        size_t size()const
        size_t capacity()const
        bool empty()const
        void resize(size_t n, char c = '\0');
        void reserve(size_t n);
    
        /
        // access
        char& operator[](size_t index);
        const char& operator[](size_t index)const;
    
        /
        //relational operators
        bool operator<(const string& s);
        bool operator<=(const string& s);
        bool operator>(const string& s);
        bool operator>=(const string& s);
        bool operator==(const string& s);
        bool operator!=(const string& s);
    
        // 返回c在string中第一次出现的位置
        size_t find (char c, size_t pos = 0) const;
        // 返回子串s在string中第一次出现的位置
        size_t find (const char* s, size_t pos = 0) const;
        // 在pos位置上插入字符c/字符串str，并返回该字符的位置
        string& insert(size_t pos, char c);
        string& insert(size_t pos, const char* str);    
        // 删除pos位置上的元素，并返回该元素的下一个位置
        string& erase(size_t pos, size_t len);
    
      private:
        char* _str;
        size_t _capacity;
        size_t _size;
      }
    }；

## 2、遍历 ##

### 2.1 operator\[ \]+下标方式 ###

这种方式是我们最喜欢使用的一种，使用下标将字符逐个打印出来。

char& operator[](size_t pos)
    {
        
        assert(pos < _size);
    
        return _str[pos];
    }
    
    //只读
    const char& operator[](size_t pos) const
    {
        
        assert(pos < _size);
    
        return _str[pos];
    }
    
    int main()
    {
        
        string s1("hello world");
    
        for (int i = 0; i < s1.size(); ++i)
        {
        
        	cout << s1[i] << " ";
        }
        cout << endl;
        
        return 0;
    }

![在这里插入图片描述][88d7b5e5844f4e8baf96f809b4aa2a6b.png]

### 2.2 迭代器 ###

*string类的迭代器的底层是一个 char 原生指针*\*，string的迭代器使用方法就像是使用指针一样来用就可以了，**但是不是所有的迭代器都是指针。（list，对于顺序表来说，并不是连续的空间，因此底层就不是指针）。**

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

我们来试一下迭代器的遍历：

int main()
    {
        
        string s1("hello world");
        string::iterator it = s1.begin();
        while (it != s1.end())
        {
        
            cout << *it << " ";
            ++it;
        }
        cout << endl;
        
        return 0;
    }

### 2.3 范围for ###

我们在之前就接触过范围for，使用起来很简单，这次我们来深究一下范围for。

int main()
    {
        
        string s1("hello world");
        for (auto ch : s1)//范围for的底层就是迭代器，这里很严格，begin大小写变了都会出问题
        {
        
            cout << ch << " ";
        }
        cout << endl;
        
        return 0;
    }

我们来看看汇编代码中迭代器与范围for。  
![在这里插入图片描述][805e0935dd634043b8b42dc08b976487.png]  
![在这里插入图片描述][471a41d726dd4da5bdb42e2be265da5e.png]

我们可以看到在汇编代码中，**迭代器与范围for都是调用了begin与end函数**\*\*，**这里我们就能看到范围for的底层就是范围for。**\*\*

**注意：范围for是傻瓜式调用，我们将迭代器的名称字符改为大写范围for都使用不了。**  
![在这里插入图片描述][6a37a57e182b4197a9414b77103c2485.png]  
![在这里插入图片描述][758ef77e892b47859e813d0a4449393a.png]

### 2.4 c\_str ###

![在这里插入图片描述][8ff27719c7804d7fb2d8a09f0efed05d.png]  
由此我们知道，c\_str返回的就是字符串以及末尾的 ‘\\0’ ，因此我们就可以使用c\_str来打印字符串。

const char* c_str() const
    {
        
        return _str;
    }
    int main()
    {
        
    	cout << c_str << endl;
        return 0;
    }

![在这里插入图片描述][71b020ab12ae4a3bb83af2730811aebb.png]

## 3、容量相关 ##

### 3.1 size（大小） ###

直接返回字符串的大小，没什么讲的秒杀。

size_t size() const//对this不修改，加const保证安全
    {
        
        return _size;
    }

### 3.2 capacity（容量） ###

size_t capacity() const//对this不修改，加const保证安全
    {
        
        return _capacity;
    }

### 3.3 empty（判空） ###

bool empty() const//对this不修改，加const保证安全
    {
        
        return _size == 0;
    }

### 3.4 clear（清理） ###

void clear()
    {
        
        _str[0] = '\0';
        _size = 0;
    }

**这里我们不需要删掉字符串内容，直接将字符串首元素改为 ‘\\0’，大小置为0即可。**

### 3.5 reserve ###

![在这里插入图片描述][79cc031441344f6890c52049aa9a5217.png]

**由此我们可以得到，reserve函数特点是只扩不缩的。扩大到容量为n。**

因此我们在实现的时候，先判断 n是否大于capacity，如果小于就不处理，大于进行扩容。

void reserve(size_t n)//reserve只扩不缩
    {
        
        if (n > _capacity)
        {
        
            char* tmp = new char[n + 1];//多一个是\0的位置
            strcpy(tmp, _str);//strcpy会将\0一同拷贝过去
            delete[] _str;
            _str = tmp;
    
            _capacity = n;
        }
    }

### 3.6 resize ###

![在这里插入图片描述][837eda5ae8fb43f98a054a2245f443a1.png]

由此我们可以看出**resize是对字符串的size进行扩充的。**  
当n小于当前字符串的大小时，将字符串缩短到n，保留字符串前n个字符。  
当n大于当前字符串的大小时，字符串长度就增加，如果有指定字符，就用指定字符对大于n的空间初始化，如果没有指定，就初始化为 ‘\\0’。  
**我们对比一下resize与reserve：  
resize是对size的更改，可扩可缩，并支持初始化，会间接影响容量的大小；  
reserve是对capacity的更改，只能扩容，不支持初始化。**

**思路：**  
**先判断 n是否大于size**  
如果小于，就是缩小，直接将n位置改为 ‘\\0’，size改为n即可；  
如果大于，还需要判断n是否超过capacity，不超过原地修改，超过直接复用reserve，对超出当前字符串长度的空间初始化为c，**并将最后一个位置置为 ‘\\0’（reserve只负责扩容，不做初始化）。**

void resize(size_t n, char c = '\0')//c给为缺省最合适
    {
        
        if (n <= _size)
        {
        
            _str[n] = '\0';
            _size = n;
        }
        else
        {
        
            if(n > _capacity)
    	        reserve(n);
            
            while (_size < n)
            {
        
                _str[_size] = c;
                ++_size;
            }
    
            _str[_size] = '\0';
        }
    }

测试：

int main()
    {
        
        string s1("hello world");
        s1.resize(5);
        cout << s1 << endl;
    
        s1.resize(8, 'x');
        cout << s1 << endl;
        
        return 0;
    }

![在这里插入图片描述][5915e95ce4da497f89695c111f32924c.png]

## 4、增 ##

### 4.1 push\_back（尾插） ###

**思路：**  
先判满，如果满了（**\_size == \_capacity）**，就扩容（二倍方式扩容），再进行尾插字符；  
没有满，直接尾插字符。

void push_back(char ch)
    {
        
        if (_size == _capacity)
        {
        
            //reserve(2 * _capacity);//直接给二倍的话，对于空字符串来说，
                                     //二倍还是0，扩容里面有释放空间，会出问题
            reserve(_capacity == 0 ? 4 : 2 * _capacity);//三目才正确
        }
    
        _str[_size] = ch;
        _size++;
        _str[_size] = '\0';//别忘了还有\0，size指的是最后一个字符的下一个位置
    }

**注意：对于扩容的传参我们使用三目操作符，防止直接对空字符串进行尾插时给二倍，相当于没有扩容。**

### 4.2 operator+=（char ch） ###

\+=字符比尾插更常用，很有必要实现。逻辑与尾插是一致的，复用push\_back就可以。

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

### 4.3 append ###

![在这里插入图片描述][056121850c5548909ad85a7b5688ac7e.png]

由此我们知道，**append函数是在原有的字符串基础上追加字符串。**

此函数不常用，我们仅实现第三个接口就可以了。  
**思路：**  
先判断容量是否足够，不够先扩容，但是append的扩容与尾插的扩容的大小不一样，尾插在原容量基础上扩二倍一定足够，这里是插入字符串，扩二倍不一定足够，我们来分析一下：  
判断容量是否足够其实不难，我们对追加的字符串计算长度(strlen(str))，看看被追加的字符串+追加的字符串长度（\_size+len）是否大于\_capacity，大于就扩容，复用reserve，传值 size+len；  
再使用strcpy函数，从字符串的\_size位置开始，将追加的字符串拷贝到\_str后面。  
代码实现：

void append(const char* str)
    {
        
        size_t len = strlen(str);
        if (_size + len > _capacity)
        {
        
            reserve(_size + len);//这里扩容不能是二倍，因为插入的字符串长度可能大于二倍
        }
    
        strcpy(_str + _size, str);//strcpy会将\0一起拷贝过去
        _size += len;
    }

### 4.4 operator+=（char\* str） ###

\+=很常用，尾插字符串，直接复用刚写的append即可。

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

### 4.5 insert（任意位置插入） ###

![在这里插入图片描述][2f38187964944ef79dd2bb137c14deee.png]

虽然insert的函数很多，但是**常用的就两个，在任意位置插入字符或字符串**，我们就来实现这两个。

#### 4.5.1 任意位置插入字符 ####

**思路：**  
1、判断pos位置是否合法。  
2、先判断是否需要扩容，与尾插一样；  
3、挪动数据，从\_size位置开始，依次往后挪，直到到pos位置停下来；  
4、在pos位置插入数据，再++\_size。  
![在这里插入图片描述][cdab94db3a7b4657a7c9b8126fdecd12.png]

代码实现：

string& insert(size_t pos, char ch)
    {
        
        assert(pos <= _size);
        if (_size == _capacity)
        {
        
            reserve(_capacity == 0 ? 4 : 2 * _capacity);
        }
        
        size_t end = _size + 1;
        while (end > pos)//size_t是无符号整型，头插时end走到-1还是会进去，形成死循环
        {
        
            _str[end] = _str[end - 1];
            --end;
        }
        _str[end] = ch;
        _size++;
    
        return *this;
    }

#### 4.5.2 任意位置插入字符串 ####

思路与任意位置插入字符是类似的，只需要注意一下边界就好了。  
![在这里插入图片描述][5683b71c89eb4cc399a1eb3003a1d2bc.png]

代码实现：

string& insert(size_t pos, const char* str)
    {
        
        assert(pos <= _size);
        size_t len = strlen(str);
    
        if (_size + len > _capacity)
        {
        
            reserve(_size + len);
        }
    
        //挪动数据
        int end = _size;
        while (end >= (int)pos)//这里也存在提升，end变为-1仍然进去循环，因此需要强转
        {
        
            _str[end + len] = _str[end];
            --end;
        }
        strncpy(_str + pos, str, len);
        _size += len;
    
        return *this;
    }

## 5、删 ##

![在这里插入图片描述][aa6c931757f44f6abc37c6aad9aeef94.png]

这里的npos我们再来看看  
![在这里插入图片描述][dd94de15931843cc9fafcc47bedf7582.png]

我们可以看到**文档中nops是size\_t类型（无符号整型），值为-1，无符号整型的-1就是int类型的max。**  
对于erase函数，我们仅实现常用的第一个接口就可以。  
文档中可以看到，erase是从pos位置开始往后删长度为len个字符。  
这里erase我们要分情况来讨论：  
**情况一**：len == npos 或者 pos+len >= \_size，那么就是从pos位置到末尾全部删除，我们直接将pos位置改为 ‘\\0’，\_size改为pos即可。  
![在这里插入图片描述][17bde45775ae4a2484ddd4692d334030.png]

**情况二**：删除其中的一段，我们定义 begin=pos+len，\_str\[begin-len\] = \_str\[begin\]，begin++不断挪动数据，当 begin==\_size 的时候挪动完数据。因此循环结束的条件是 begin<=\_size，这时把 ‘\\0’ 也就挪过去了。  
![在这里插入图片描述][d103ac74807a48a799a592b5de411110.png]

string& erase(size_t pos, size_t len = npos)
    {
        
        assert(pos < _size);
    
        if (len == npos || pos + len >= _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;
    }

## 6、查 ##

![在这里插入图片描述][0167ff73d9c04965846dfb80bc702d47.png]

### 6.1 查找一个字符 ###

由文档中我们可以知道，找到后返回的是字符的位置，即就是下标。如果没有找到返回npos。

size_t find(char c, size_t pos = 0) const
    {
        
        for (size_t i = pos; i < _size; ++i)
        {
        
            if (_str[i] == c)
                return i;
        }
    
        return npos;
    }

### 6.2 查找一个字符串 ###

我们使用strstr来找。

size_t find(const char* s, size_t pos = 0) const
    {
        
        const char* p = strstr(_str + pos, s);
        if (p)
        {
        
            return p - _str;
        }
        else
        {
        
            return npos;
        }
    }

## 7、字符串比较 ##

比较的本质是ASCII码值，因此我们套用strcmp就可以。

bool operator<(const string& s)
    {
        
        return strcmp(_str, s._str) < 0;
    }
    
    bool operator==(const string& s) const
    {
        
        return strcmp(_str, s._str) == 0;
    }
    
    bool operator<=(const string& s)
    {
        
        return (*this < s) || (*this == s);//复用
    }
    
    bool operator>(const string& s)
    {
        
        return !(*this <= s);
    }
    
    bool operator>=(const string& s)
    {
        
        return !(*this < s);
    }
    
    bool operator!=(const string& s)
    {
        
        return !(*this == s);
    }

写好<与==，其他的直接复用就可以。

## 8、流插入、流提取重载 ##

### 8.1 流提取重载 ###

流提取使用在赋值或初始化上，因此，在赋值前我们先对空间清理一下，在对变量赋值。

istream& operator>>(istream& _cin, string& s)
    {
        
        s.clear();
    
        char buff[129];//这样可以避免扩容问题
        size_t i = 0;
    
        char ch;
        //_cin >> ch//本身是拿不到' '或'\n'的，因此循环条件就判断不了
        ch = _cin.get();
    
        while (ch != ' ' && ch != '\n')
        {
        
            buff[i++] = ch;
            if (i == 128)
            {
        
                buff[i] = '\0';
                s += buff;
                i = 0;//下一轮
            }
            //_cin >> ch;
            ch = _cin.get();
        }
        if (i != 0)
        {
        
            buff[i] = '\0';
            s += buff;
        }
    
        return _cin;
    }

### 8.2 流插入重载 ###

ostream& operator<<(ostream& _cout, const string& s)
        //for (int i = 0; i < s.size(); ++i)
        //{
        
        //	_cout << s[i];
        //}
        for (auto ch : s)
        {
        
            _cout << ch;
        }
    
        return _cout;
    }

\*\*\* 本篇结束 \*\*\*

[afbb78f1d81f445f8c0a26aea0717753.gif_pic_center]: https://img-blog.csdnimg.cn/afbb78f1d81f445f8c0a26aea0717753.gif#pic_center
[string]: https://blog.csdn.net/Ljy_cx_21_4_3/article/details/132339893
[88d7b5e5844f4e8baf96f809b4aa2a6b.png]: https://img-blog.csdnimg.cn/88d7b5e5844f4e8baf96f809b4aa2a6b.png
[805e0935dd634043b8b42dc08b976487.png]: https://img-blog.csdnimg.cn/805e0935dd634043b8b42dc08b976487.png
[471a41d726dd4da5bdb42e2be265da5e.png]: https://img-blog.csdnimg.cn/471a41d726dd4da5bdb42e2be265da5e.png
[6a37a57e182b4197a9414b77103c2485.png]: https://img-blog.csdnimg.cn/6a37a57e182b4197a9414b77103c2485.png
[758ef77e892b47859e813d0a4449393a.png]: https://img-blog.csdnimg.cn/758ef77e892b47859e813d0a4449393a.png
[8ff27719c7804d7fb2d8a09f0efed05d.png]: https://img-blog.csdnimg.cn/8ff27719c7804d7fb2d8a09f0efed05d.png
[71b020ab12ae4a3bb83af2730811aebb.png]: https://img-blog.csdnimg.cn/71b020ab12ae4a3bb83af2730811aebb.png
[79cc031441344f6890c52049aa9a5217.png]: https://img-blog.csdnimg.cn/79cc031441344f6890c52049aa9a5217.png
[837eda5ae8fb43f98a054a2245f443a1.png]: https://img-blog.csdnimg.cn/837eda5ae8fb43f98a054a2245f443a1.png
[5915e95ce4da497f89695c111f32924c.png]: https://img-blog.csdnimg.cn/5915e95ce4da497f89695c111f32924c.png
[056121850c5548909ad85a7b5688ac7e.png]: https://img-blog.csdnimg.cn/056121850c5548909ad85a7b5688ac7e.png
[2f38187964944ef79dd2bb137c14deee.png]: https://img-blog.csdnimg.cn/2f38187964944ef79dd2bb137c14deee.png
[cdab94db3a7b4657a7c9b8126fdecd12.png]: https://img-blog.csdnimg.cn/cdab94db3a7b4657a7c9b8126fdecd12.png
[5683b71c89eb4cc399a1eb3003a1d2bc.png]: https://img-blog.csdnimg.cn/5683b71c89eb4cc399a1eb3003a1d2bc.png
[aa6c931757f44f6abc37c6aad9aeef94.png]: https://img-blog.csdnimg.cn/aa6c931757f44f6abc37c6aad9aeef94.png
[dd94de15931843cc9fafcc47bedf7582.png]: https://img-blog.csdnimg.cn/dd94de15931843cc9fafcc47bedf7582.png
[17bde45775ae4a2484ddd4692d334030.png]: https://img-blog.csdnimg.cn/17bde45775ae4a2484ddd4692d334030.png
[d103ac74807a48a799a592b5de411110.png]: https://img-blog.csdnimg.cn/d103ac74807a48a799a592b5de411110.png
[0167ff73d9c04965846dfb80bc702d47.png]: https://img-blog.csdnimg.cn/0167ff73d9c04965846dfb80bc702d47.png