string模拟实现
基本结构
天选之子
构造函数
析构函数
拷贝构造函数
空间
size()函数
capacity()函数
clear()函数
empty()函数
reverse()函数
resize()函数
迭代器
iterator
begin()函数
end()函数
const_iterator
begin()函数
end()函数
增
push_back()函数
append()函数
operator+=
insert()函数
删
erase()函数
查
find()函数
改
swap()函数
operator[]函数
operator= 函数
比较
流操作
流插入 <<
流提取 >>
C接口
c_str()函数
substr()函数
源码
放在前面: 我们实现string类, 并不是跟源码一模一样(并不是造一个新的轮子), 只是了解每个接口的实现过程 ⇒ 我们以后也用的放心(比如时间复杂度, 空间复杂度等等)
基本结构
private: size_t _size; // 实际长度 size_t _capacity; // 空间 char* _str;
习惯把不可能为负数的值的类型 定义为 size_t
天选之子
构造函数
考虑到 无参调用和有参调用 && 只有一个参数 ⇒ 我们可以采用 全缺省的形式
传参类型应该为 常量字符串 ⇒ const char* ⇐ 一般用于初始化, 咋们给的值都是常量
缺省值初始化为 ""(空字符串) ⇐ 常量字符串默认就会有 \0, 即 “” (空字符串) 里面就是一个 \0
_size 和 _capacity 的大小不包括 \0 ⇒ 所以, 我们初始化长度的时候, 用 strlen(str)
_str要先开空间
👇👇👇
string(const char* str = "") :_size(strlen(str)) ,_capacity(_size) ,_str(new char[_capacity+1]) { memcpy(_str, str, _capacity+1); }
注意: 初始化的顺序是按照 声明的顺序来的 ⇒ 我们尽量保持 初始化和声明的顺序一致, 要不然就会出现问题 由于 _size 和 _capacity不包括 \0 的长度 ⇒ 我们_str开空间的时候要多开一个, 给 \0用
🗨️为啥要用 memcpy函数? 为啥不用strcpy函数呢?
1. memcpy函数 和 strcpy函数的 区别 : memcpy函数是 逐个字节进行copy的, 而strcpy是 遇到 \0就停止 copy
2 我们标准库中 string类的输出是按照 _size 来的. 即遇到下面的情况, strcpy 和 strcpy的区别就体现出来了👇👇👇
// 字符串如下: // hello // world! // 来做以下几组实验 // 1. 库里的string std::string str1 = "hello"; str1 += "\0"; str1 += "world!"; cout << str1 << endl; // 2. 用strcpy来实现 // ... //.. // 3. 用memcpy来实现 // ... // ... ***** 1. helloworld! 2. hello 3. helloworld! *****
- memcpy默认是不会copy
\0, 所以memcpy函数里面的长度 传的是_capacity+1
析构函数
~string() { delete[] _str; // 清理动态申请空间 // 置零(置空) _str = nullptr; _size = _capacity = 0; }
拷贝构造函数
- 我们不写构造函数, 系统自动生成的是一种
浅拷贝⇒ 对有动态资源申请的对象来说, 会对同一块空间析构两次 - 我们写的是
深拷贝⇒ 找一块新的空间给this->_str, 然后将s的内容copy过去, 更新_capacity 和 _size
String(const string& s) { _str = new char[s._capacity + 1]; memcpy(_str, s._str, s._capacity + 1); _capacity = s._capacity; _size = s._size; }
空间
size()函数
size_t size()const { return _size; }
capacity()函数
size_t capacity()const { return _capacity; }
clear()函数
void clear() { _size = 0; _str[_size] = '\0'; }
clear()函数 并不是用来清理空间的, 而是让空间置空(置零)
empty()函数
bool empty()const { if(_size == 0) return true; return false; }
reverse()函数
void reverse(size_t n) { assert(n >= 0); // 扩容逻辑 -- 一般我们不进行缩容 if(n > _capacity) { char* tem = new char[n+1]; memcpy(tem._str, _str, _capacity+1); delete[] _str; _str = tem; _capacity = n; } }
resize()函数
void resize(size_t n, char ch = '\0') { assert(n >= 0); if(n <= _size) { _size = n; _str[_size] = '\0'; } else { reverse(n); for(int i = _size; i < _size+n; i++) { _str[i] = ch; } _size = _size + n; _str[_size] = '\0'; } }
迭代器
迭代器是属于类的 ⇐ 我们声明迭代器的时候要声明类域 👇👇👇
std::string str = "hello world"; iterator it = str.begin(); ***** error C2955: “std::iterator”: 使用 类 模板 需要 模板 参数列表 *****
但要在 string类里面,定义一种类型, 有两种方式:
typedef 一个变量
定义一个内部类 (内部类一般都是自定义类型)
而我们这里iterator其实就是数组_str各个下标对应的地址, 是一种 内置类型 ⇒ 所以, 我们采用typedef的方式来实现 iterator
iterator
typedef char* iterator;
begin()函数
iterator begin() { return _str; }
end()函数
iterator end() { return _str + _size; }
const_iterator
typedef const char* const_iterator;
begin()函数
const_iterator begin()const { return _str; }
end()函数
const_iterator end()const { return _str + _size; }
增
push_back()函数
尾插一个字符的操作:
是否需要扩容 ⇐ _size == _capacity
扩容逻辑:
_capacity == 0 ⇒ 传个 4 过去扩容
_capacity > 0 ⇒ 2倍扩容
_size++, _str[_size] = ‘\0’;
void push_back(const char ch) { // 是否扩容 if (_size == _capacity) { size_t newcapacity = (_capacity == 0 ? 4 : _capacity * 2); reverse(newcapacity); } _str[_size] = ch; _size++; _str[_size] = '\0'; }
append()函数
尾插一个字符串的操作:
是否需要扩容
扩容逻辑:
1. _size + len <= _capacity — — 不需要扩容
2. _size + len > _capacity — — 扩容(_size + len)
_size = _size + len, _str[_size] = ‘\0’;
void append(const char* ch) { size_t len = strlen(ch); // 是否扩容 if (len + _size > _capacity) { reverse(len + _size); } for (size_t i = 0; i < len; i++) { _str[_size + i] = ch[i]; } _size += len; _str[_size] = '\0'; }
operator+=
复用 push_back() 和 append()
void operator+=(const char ch) { push_back(ch); } void operator+=(const char* ch) { append(ch); }
insert()函数
在 下标为pos的位置插入n个字符:
是否需要扩容
扩容逻辑:
_size + n <= _capacity — — 不需要扩容
_size + n > _capacity — — 扩容(_size + n)
挪动数据
_size = _size + n, _str[_size] = ‘\0’;
void insert(size_t pos, const char* ch) { assert(pos >= 0); // 是否需要扩容 size_t len = strlen(ch); if (_size + len > _capacity) { reverse(_size + pos); } // 挪动数据 size_t end = _size; // 挪动数据时, 下标不能小于0(即不能等于 -1) while (end >= pos && end != _nops) { _str[end + len] = _str[end]; end--; } // 插入数据 for (size_t i = 0; i < len; i++) { _str[pos + i] = ch[i]; } _size = _size + len; }
对了, 这里的 _nops是我么定义的一个静态成员变量
// 类里面的声明 public: static size_t _nops; // 类外面的初始化 size_t muyu::string::_nops = -1; // 这里的muyu是我定义的一个命名空间域
🗨️为啥要定义一个nops? 为啥要初始化为 -1?
前面, 我们有说过: 不可能为负数的, 我们定义成 size_t (无符号整数)
如果 下标减到 -1 — ---- 由于是 size_t, 变量是不会比 -1 小的
那么 size_t 类型如何区分开 -1 呢?
size_t i = -1; ⇒ i 等于 2 ^ 32 -1;
那么 下标 不等于 nops不就行了~~
还有就是, 插入函数 和 删除函数中 字符串的长度如果不写, 就是nops
删
erase()函数
void erase(size_t pos, size_t n = _nops) { assert(pos >= 0); // 是否把pos位置后面全部删除 if (n == _nops || pos + n >= _size) { _str[pos] = '\0'; _size = pos; } else { for (size_t i = pos; i < pos + n; i++) { _str[i] = _str[i + n]; } _size = _size - n; } }
查
find()函数
size_t find(size_t pos = 0, const char ch ) { assert(pos < _size); for (int i = pos; i < _size; i++) { if (_str[i] == ch) { return i; } } return _nops; } size_t find(size_t pos = 0, const char* ch ) { assert(pos < _size); // 如果找到返回地址, 否则返回nullptr const char* res = strstr(_str, ch); if (res) { return res - _str; } else { return _nops; } }
改
swap()函数
void swap(string& s) { std::swap(_size, s._size); std::swap(_capacity, s._capacity); std::swap(_str, s._str); }
operator[]函数
//不是&, 那就返回的是常量临时拷贝 char& operator[](size_t n) { assert(n <= _size); return _str[n]; } const char& operator[](size_t n)const { assert(n <= _size); return _str[n]; }
operator= 函数
//string& operator=(const string& s) //{ // // 传统写法 -- 找一块空间, 把s的内容搞过去, 然后和*this交换 // // 1. 找空间, 移内容; 2. 释放this的空间 // string tem; // tem.reverse(s._capacity + 1); // memcpy(tem._str, s._str, s._capacity + 1); // tem._size = s._size; // swap(tem); // return *this; //} string& operator=(string s) { swap(s); return *this; }
比较
bool operator==(const string& s) { // 如果_size都不相等, 那么何谈相等 return _size == s._size && memcmp(_str, s._str, _size) == 0; } bool operator>(const string& s) { // 取较小长度进行比较 size_t size = std::min(_size, s._size); int ret = memcmp(_str, s._str, size); // 由于是取较小长度进行比较, 那么会出现如下几种情况: // 1. str1 = hello, str2 = hello // 2. str1 = hello\0xxx, str2 = hello // 3. str1 = hello, str2 = hello\00xxx // 这几种情况都是根据较小长度比较的结果都是 相等 if (ret == 0) { if (_size > s._size) return true; else return false; } return ret > 0; } bool operator!=(const string& s) { return !(*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); }
流操作
流操作要写在全局位置 ⇐ cout/cin 要抢占第一个参数. 若要是在类中, 第一个参数就默认是this
流插入 <<
ostream& operator<<(ostream& out, const string& s) { for (auto ch : s) { out << ch; } return out; }
流提取 >>
istream& operator>>(istream& in, string& s) { // 每一次新的读取要进行清理一下 // 要不然就会接着读取, 而不是覆盖 s.clear(); // get()函数可以读到每一个字符, 包括空格 和 换行 char ch = in.get(); // 处理前缓冲区前面的空格或者换行 while (ch == ' ' || ch == '\n') { ch = in.get(); } // in >> ch; char buff[128]; // buff数组的作用是: 减少开空间的次数 int i = 0; while (ch != ' ' && ch != '\n') { buff[i++] = ch; if (i == 127) { buff[i] = '\0'; s += buff; i = 0; } //in >> ch; ch = in.get(); } // 如果最后 buff数组还有数据, 那么就加到s中 if (i != 0) { buff[i] = '\0'; s += buff; } return in; }
C接口
c_str()函数
const char* c_str()const { return _str; }
substr()函数
string substr(size_t pos = 0, size_t n = _nops) { assert(pos >= 0); // 是否需要扩容 int len = n; // 默认是n if (n == _nops || pos + n >= _size) { len = _size - pos; } string tem; tem.reverse(len); //for (size_t i = pos; i < len; i++) //{ // tem[i] = _str[i + pos]; //} //tem._size = len; //tem[_size] = '\0'; for (size_t i = pos; i < pos + len; i++) { tem += _str[i]; } return tem; }
源码
#pragma once #include <string.h> #include<assert.h> #include<iostream> namespace muyu { class string { public: typedef char* iterator; typedef const char* const_iterator; // friend ostream& operator<<(ostream& out, const string& s); iterator begin() { return _str; } const_iterator begin()const { return _str; } iterator end() { return _str + _size; } const_iterator end()const { return _str + _size; } string(const char* str = "") :_size(strlen(str)) ,_capacity(_size) ,_str(new char[_capacity+1]) { memcpy(_str, str, _capacity+1); } string(const string& tem) { _str = new char[tem._capacity + 1]; memcpy(_str, tem._str, tem._capacity + 1); _capacity = tem._capacity; _size = tem._size; } ~string() { delete[] _str; _str = nullptr; _size = _capacity = 0; } const char* c_str()const { return _str; } void reverse(size_t n) { if (n > _capacity) { char* tem = new char[n + 1]; memcpy(tem, _str, _capacity + 1); _capacity = n; delete[] _str; _str = tem; } } void resize(size_t n, char ch = '\0') { if (_size > n) { _str[n] = '\0'; _size = n; } else { reverse(n); // 不管需不需要扩容,都丢给reverse. reverse内部有判断是否需要扩容 for (size_t i = _size; i < n; i++) { _str[i] = ch; } _str[n] = '\0'; } } void push_back(const char ch) { // 是否扩容 if (_size == _capacity) { size_t newcapacity = (_capacity == 0 ? 4 : _capacity * 2); reverse(newcapacity); } _str[_size] = ch; _size++; _str[_size] = '\0'; } void append(const char* ch) { size_t len = strlen(ch); // 是否扩容 if (len + _size > _capacity) { reverse(len + _size); } for (size_t i = 0; i < len; i++) { _str[_size + i] = ch[i]; } _size += len; _str[_size] = '\0'; } void operator+=(const char ch) { push_back(ch); } void operator+=(const char* ch) { append(ch); } void insert(size_t pos, const char* ch) { assert(pos >= 0); // 是否需要扩容 size_t len = strlen(ch); if (_size + len > _capacity) { reverse(_size + pos); } // 挪动数据 size_t end = _size; // 挪动数据时, 下标不能小于0(即不能等于 -1) while (end >= pos && end != _nops) { _str[end + len] = _str[end]; end--; } // 插入数据 for (size_t i = 0; i < len; i++) { _str[pos + i] = ch[i]; } _size = _size + len; } void erase(size_t pos, size_t n = _nops) { assert(pos >= 0); if (n == _nops || pos + n >= _size) { _str[pos] = '\0'; _size = pos; } else { for (size_t i = pos; i < pos + n; i++) { _str[i] = _str[i + n]; } _size = _size - n; } } size_t size()const { return _size; } void clear() { _size = 0; _str[_size] = '\0'; } bool empty()const { return _size > 0; } void swap(string& s) { std::swap(_size, s._size); std::swap(_capacity, s._capacity); std::swap(_str, s._str); } //不是&, 那就返回的是常量临时拷贝 char& operator[](size_t n) { assert(n <= _size); return _str[n]; } const char& operator[](size_t n)const { assert(n <= _size); return _str[n]; } string substr(size_t pos = 0, size_t n = _nops) { assert(pos >= 0); int len = n; // 默认是n if (n == _nops || pos + n >= _size) { len = _size - pos; } string tem; tem.reverse(len); //for (size_t i = pos; i < len; i++) //{ // tem[i] = _str[i + pos]; //} //tem._size = len; //tem[_size] = '\0'; for (size_t i = pos; i < pos + len; i++) { tem += _str[i]; } return tem; } bool operator==(const string& s) { return _size == s._size && memcmp(_str, s._str, _size) == 0; } bool operator>(const string& s) { // 取较小长度进行比较 size_t size = std::min(_size, s._size); int ret = memcmp(_str, s._str, size); if (ret == 0) { if (_size > s._size) return true; else return false; } return ret > 0; } bool operator!=(const string& s) { return !(*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); } size_t find(const char ch, size_t pos = 0) { assert(pos < _size); for (int i = pos; i < _size; i++) { if (_str[i] == ch) { return i; } } return _nops; } size_t find(const char* ch, size_t pos = 0) { assert(pos < _size); const char* res = strstr(_str, ch); if (res) { return res - _str; } else { return _nops; } } //string& operator=(const string& s) //{ // // 传统写法 -- 找一块空间, 把s的内容搞过去, 然后和*this交换 // // 1. 找空间, 移内容; 2. 释放this的空间 // //string tem; // //tem.reverse(s._capacity + 1); // //memcpy(tem._str, s._str, s._capacity + 1); // //tem._size = s._size; // //swap(tem); // //return *this; //} string& operator=(string s) { swap(s); return *this; } private: size_t _size; size_t _capacity; char* _str; public: static size_t _nops; }; size_t string::_nops = -1; ostream& operator<<(ostream& out, const string& s) { for (auto ch : s) { out << ch; } return out; } istream& operator>>(istream& in, string& s) { // 每一次新的读取要进行清理一下 // 要不然就会接着读取, 而不是覆盖 s.clear(); // get()函数可以读到每一个字符, 包括空格 和 换行 char ch = in.get(); // 处理前缓冲区前面的空格或者换行 while (ch == ' ' || ch == '\n') { ch = in.get(); } // in >> ch; char buff[128]; // buff数组的作用是: 减少开空间的次数 int i = 0; while (ch != ' ' && ch != '\n') { buff[i++] = ch; if (i == 127) { buff[i] = '\0'; s += buff; i = 0; } //in >> ch; ch = in.get(); } // 如果最后 buff数组还有数据, 那么就加到s中 if (i != 0) { buff[i] = '\0'; s += buff; } return in; } }
