当前位置：首页 > news >正文

string模拟

news 来源：原创 2024/9/19 5:16:23

本章准备对string模拟进行讲解，以下是string的学习网址：

string - C++ Reference (cplusplus.com)

string本质可以理解为储存char类型的顺序表，其中string的迭代器用一个char*就可以解决。所以string类成员变量如下：

这里用了一个命名空间是为了区分库里面的string。接下来就对需要实现的函数一一讲解。

一、构造函数

二、迭代器

三、运算符重载

1.关系运算符重载

2.<<和>>的重载

四、Capacity

1.resize接口：

2.reserve接口：

五、增删查

六、源码

一、构造函数

涉及到动态内存申请的类是不能直接用编译器提供的默认构造函数，因为它无法完成深拷贝等等问题，所以需要我们自己来完成这一部分。

1.默认构造

string(const char* st = "")
{size_t sz = strlen(st);_str = new char[sz+1];strcpy(_str, st);_size = sz;_capacity = sz;
}

在写这个函数时需要注意，不能用sizeof来计算st的所占字节空间，这里sizeof只能计算到st这个变量所储存的内容占用的字节空间，而st所储存的是字符串的地址，所以占用的空间为4/8字节。

这里还要注意一个点strlen做计算时并没有算入'\0'，所以在申请内存时需要加上1。

2.拷贝构造

string拷贝构造函数的最本质还是用了字符串拷贝函数strcpy，如下：

string(const string& st)
{_str = new char[st._capacity];strcpy(_str, st._str);_size = st._size;_capacity = st._capacity;
}

当然还有更方便的写法，我们可以借助已写好的默认构造函数去构造一个对象然后与需要拷贝的对象交换，那么我们就得先写swap函数，而不能用库里面的swap，该方法称为现代写法，在效率上并没有提升只是相当于让编译器去帮我们写，如下：

void swap(string& str)
{std::swap(_str, str._str);std::swap(_capacity, str._capacity);std::swap(_size, str._size);
}
string(const string& st)
{string sv(st._str);swap(sv);
}

3.赋值运算重载

该函数也一样可以用现代写法，如下：

string operator=(string st)
{swap(st);return *this;
}

这里需要注意，因为这里用到swap直接对形参进行改变，所以这个不能加const和不能用引用传参。

4.析构函数

只要涉及到动态内存申请一定要自己写析构函数，默认生成的析构函数释放不了内存。如下：

~string()
{delete[] _str;_str = nullptr;_capacity = _size = 0;
}

注意：对于一次性申请多个元素的内存空间要用delete[ ]去释放，用delete释放内存则会出现内存泄漏，或者不确定的问题。

二、迭代器

每个容器都有迭代器，平时写代码我们并不用关心它们内部怎么实现，只要需要知道它的用法和功能，而且会用一个容器的迭代器就会用其他所有容器的迭代器，这就是封装的好处，而对于string的迭代器是相对比较简单的，因为string本质就是一个顺序表可以对数据随机访问。

如下：

三、运算符重载

运算符重载方面我们依次来设计以下函数：

char 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);
bool operator!=(const string& s);
ostream& operator<<(ostream& out, string& s);
istream& operator>>(istream& put, string& s);

对于[ ]的重载我们直接返回一个_str[index]就可以解决

       char operator[](size_t index)
       {
                return _str[index];
       }

1.关系运算符重载

<符号重载的实现底层还是调用了strcmp函数，如下：
       bool operator<(const string& s)
       {
                return strcmp(_str, s._str) < 0;
       }
       bool operator==(const string& s)
       {
                return strcmp(_str, s._str) == 0;
       }

对于剩下的关系运算符只需复用<和==运算符即可，具体实现在最后源码给出。对于+和+=重载会在下面增删查部分进行讲解。

2.<<和>>的重载

需要注意因为每个类的成员函数的参数都隐藏着一个this指针，而且this指针处于第一个参数位置，对于<<和>>运算符都是双目运算符（即只能有两个操作数）所以重载的函数只能有两个参数，而如果把<<，>>重载成类的成员函数的话，this指针已经占用了第一个参数位置，最后在使用的时候只能这样：操作对象<<cout 或操作对象>>cin，这样用上去是十分别扭的而且很容易出错，所以这两个重载函数就不能作为类成员，需要在类外声明或实现。

对于<<，>>重载函数是避免不了访问类成员变量的，而类成员变量我们已经把它设置为私有，在类外是无法访问的，所以这里把这两个重载函数设为类的友元函数就可以很好的解决。

对于<<（即输出）重载比较简单，就不过多讲解，如下：

接下来是>>

这里有一个细节，在给一个对象输入数据之前，是先要把原数据清空的，所以需要用一个clear函数，在等会我们会实现，这里先使用。

为了处理频繁扩容可以会消耗效率的问题，我们可以先用一个数组储存用户输入的内容，然后最后一次性储入对象中，字符读取终止的条件我们可以用空格或换行，但是由于cin会自动忽略空格字符和换行符，所以可以用cin.get()读取，然后再用while循环做判断。

注意：在把所有读取到的数据储入对象后还需要手动添加'\0'

这里的+=重载同样我们在后面再来实现。

四、Capacity

该部分我们主要实现库函数接口的以下红圈部分。

对于size和capacity接口的实现比较简单直接返回相应的成员函数即可，empty的话返回_size==0即可，现在重点来看一看其它接口。

1.resize接口：

它的功能是改变string对象中的元素个数。如str.resize(n，m)表示把str字符串的元素改为n个，如n大于str的size那么多余部分用m字符填充。

void resize(size_t n,char m='?')
{while (_size < n){_str[_size++] = m;}_size = n;
}

2.reserve接口：

它的功能是预开空间，如str.reserve(n)表示把str的空间改为n个元素的空间大小，但它分有以下情况：

n > str._capacity，进行扩容。
str. _size < n < str._capacity，进行缩容。
n==str. _capacity，不做任何处理
n<str. _size，行为未定义（即没有明确的标准，具体取决于编译器，可能会把原数据缩小到n，也可能不做任何更改）

那么这里为了方便当n<str. _size时我们就不做任何更改，注意这里_capacity的实现跟库里面保持一致并不用把'\0'占的空间算入。如下：

void reserve(size_t n)
{if (n < _size)return;char* st = new cha[n + 1];strcpy(st, _str);delete[] _str;_str = nullptr;_size = n;_capacity = n;
}

clear接口的话直接把_size置为0即可，不必要对其他数据进行改动数据。

五、增删查

该部分我们主要实现库函数接口的以下红圈部分。

其中前三个接口核心在于push_back，可以先完成第三个接口，剩下两个接口对push_back复用即可。首先需要判断是否需要扩容，如果需要就进行扩容然后存放数据，不要忘记存放完数据后需要存入'\0'。如果函数是在类外实现的所以需要添加string::来指明类域。如下：

swap函数在拷贝构造部分已经实现，pop_back函数的话直接把_size减减即可，现在重点来分析一下insert和erase。

insert函数功能是在指定位置之前插入数据，erase的作用是删除指定位置的数据。string类本质是顺序表那么在做这个操作时就需要挪动数据。比如在pos位置之前插入数据那么就需要把pos位置及以后的所有数据都往后移动一位，从而把pos位置空出来填入新的位置。删除pos位置的数据就是要把pos以后的所有数据整体往前挪动一位，把pos位置覆盖。

需要注意的是这里会引发一个迭代器失效的问题，因为如果往pos位置之前插入数据，那么pos位置就不是原来的数据了，而是新插入的数据，那么也就是在无形中改变了pos的指向导致pos失效，删除数据也同理。而对于扩容并不会对pos的指向有影响因为pos表示的是数据的下标，扩容可能会换一块储存空间但是对应pos下标的数据并没变化。

为考虑迭代器失效的问题库里面的规定是insert函数最后需要返回原pos指向的迭代器。esare函数最后要返回被删除数据的下一位数据的迭代器。

实现如下：

string::iterator string::insert(size_t pos,char c)
{if (_size == _capacity)reserve(_capacity == 0 ? 4 : _capacity * 2);int end = _size;while (end != pos - 1){_str[end + 1] = _str[end];end--;}_str[pos] = c;_size++;return begin() + pos + 1;
}
string::iterator string::erase(size_t pos)
{int bin = pos;while (bin != _size){_str[bin] = _str[bin + 1];bin++;}_size--;return begin() + pos;
}

六、源码


#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
namespace byte
{class string{public:typedef char* iterator;friend ostream& operator<<(ostream& out, string& s);friend istream& operator>>(istream& put, string& s);public:string(const char* st = ""){size_t sz = strlen(st);_str = new char[sz + 1];strcpy(_str, st);_size = sz;_capacity = sz;}void swap(string& str){std::swap(_str, str._str);std::swap(_capacity, str._capacity);std::swap(_size, str._size);}string(const string& st){string sv(st._str);swap(sv);}string operator=(string& st){swap(st);return *this;}~string(){delete[] _str;_str = nullptr;_capacity = _size = 0;}size_t size(){return _size;}size_t capacity(){return _capacity;}typedef char* iterator;iterator begin(){return _str;}iterator end(){return _str + _size;}iterator cbegin() const{return _str;}iterator cend() const{return _str + _size;}char operator[](size_t index){return _str[index];}bool operator<(const string& s){return strcmp(_str, s._str) < 0;}bool operator==(const string& s){return strcmp(_str, s._str) == 0;}bool operator<=(const string& s){return *this < s || *this == s;}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);}void resize(size_t n, char m = '?'){if (n <= _size)return;while (_size < n){_str[_size++] = m;}}void reserve(size_t n){if (n < _size)return;char* st = new char[n + 1];strcpy(st, _str);delete[] _str;_str = st;_capacity = n;}void clear(){_size = 0;}void push_back(char c);string& operator+=(char c);void append(const char* str);string& operator+=(const char* str);iterator insert(size_t pos, char c);iterator erase(size_t pos);private:char* _str;size_t _capacity;size_t _size;};
}
namespace byte
{void string::push_back(char c){if (_size == _capacity)reserve(_capacity == 0 ? 4 : 2 * _capacity);_str[_size++] = c;_str[_size] = '\0';}void string::append(const char* str){reserve(_size + strlen(str) + 1);//提前开空间减少扩容带来的效率损耗for (int i = 0; str[i] != '\0'; i++){push_back(str[i]);}}string& string::operator+=(char c){push_back(c);return *this;}string& string::operator+=(const char* str){append(str);return *this;}ostream& operator<<(ostream& out, string& s){for (auto vul : s){out << vul;}return out;}istream& operator>>(istream& put, string& s){s.clear();const size_t N = 256;char arr[N];char c;c = put.get();int i = 0;while (c != '\n' && c != ' '){if (i != N - 1){arr[i++] = c;}else{arr[i++] = '\0';s += arr;i = 0;}c = put.get();}if (i != 0){arr[i] = '\0';s += arr;}return put;}string::iterator string::insert(size_t pos, char c){if (_size == _capacity)reserve(_capacity == 0 ? 4 : _capacity * 2);int end = _size;while (end != pos - 1){_str[end + 1] = _str[end];end--;}_str[pos] = c;_size++;return begin() + pos + 1;}string::iterator string::erase(size_t pos){int bin = pos;while (bin != _size){_str[bin] = _str[bin + 1];bin++;}_size--;return begin() + pos;}
}
namespace byte
{void string_test1(){string x("123456");cout << x << endl;string k(x);cout << k << endl;string mstr;cin >> mstr;for (auto n : mstr){cout << n;}}void string_test2(){//reservestring str("zxcvbnm");cout << "capacity:" << str.capacity() << endl;str.reserve(20);cout << "capacity:" << str.capacity() << endl;str.reserve(15);cout << "capacity:" << str.capacity() << endl;str.reserve(3);cout << "capacity:" << str.capacity() << endl;//resizestr.resize(10, '0');cout << "size:" << str.size() << ' ' << str << endl;str.resize(3, '0');cout << "size:" << str.size() << ' ' << str << endl;}void string_test3(){string s("123456");s.push_back('x');cout << s << endl;s.append("vvv");cout << s << endl;s += "hhh";cout << s << endl;}void string_test4(){string s("12345678");s.erase(5);cout << s << endl;s.erase(2);cout << s << endl;s.insert(0,'0');cout << s << endl;}
}
int main()
{byte::string_test1();//byte::string_test2();//byte::string_test3();//byte::string_test4();return 0;
}