【C++】string类的模拟实现
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
大家好我是沐曦希💕
文章目录
一.前言
注意下述结构是在32位平台下进行验证32位平台下指针占4个字节.。
1.VS下string的结构
string总共占28个字节内部结构稍微复杂一点先是有一个联合体联合体用来定义string中字符串的存储空间
- 当字符串长度小于16时使用内部固定的字符数组来存放
- 当字符串长度大于等于16时从堆上开辟空间
union _Bxty
{ // storage for small buffer or pointer to larger one
value_type _Buf[_BUF_SIZE];
pointer _Ptr;
char _Alias[_BUF_SIZE]; // to permit aliasing
} _Bx;
这种设计也是有一定道理的大多数情况下字符串的长度都小于16那string对象创建好之后内部已经有了16个字符数组的固定空间不需要通过堆创建效率高。
其次还有一个size_t字段保存字符串长度一个size_t字段保存从堆上开辟空间总的容量
最后还有一个指针做一些其他事情。
故总共占16+4+4+4=28个字节。
2.g++下string的结构
g++下string是通过写时拷贝实现的string对象总共占4个字节内部只包含了一个指针该指针将来指向一块堆空间内部包含了如下字段
- 空间总大小
- 字符串有效长度
- 引用计数
- 指向堆空间的指针用来存储字符串。
struct _Rep_base
{
size_type _M_length;
size_type _M_capacity;
_Atomic_word _M_refcount;
};
二、string基本框架
1.构造函数
string的构造函数分为无参和带参数无参需要给一个缺省值“”。
string(const char* str = "")
{
// 构造String类对象时如果传递nullptr指针可以认为程序非法
if (nullptr == str)
{
assert(false);
return;
}
_size = strlen(str);
_capacity = _size;
_str = new char[_capacity + 1];
strcpy(_str, str);
}
这里的capacity取值是字符串的有效个数不算’\0’所以在进行扩容操作时候需要多扩容一个字节位置。
2.拷贝构造
因为拷贝构造函数和赋值函数都是默认构造函数所以我们不写编译器会自动生成。对于内置类型完成浅拷贝对于自定义类型调用拷贝构造。
对于string类型来说如果不写拷贝构造会导致浅拷贝问题只完成值拷贝
浅拷贝也称位拷贝编译器只是将对象中的值拷贝过来。如果对象中管理资源最后就会导致多个对象共享同一份资源当一个对象销毁时就会将该资源释放掉而此时另一些对象不知道该资源已经被释放以为还有效所以当继续对资源进项操作时就会发生发生了访问违规。
所以一个类中涉及到资源的管理其拷贝构造函数、赋值运算符重载以及析构函数必须要显式给出。
- 传统写法
string(const string& str)
{
_size = str._size;
_capacity = str._capacity;
_str = new char[_capacity + 1];
strcpy(_str, str._str);
}
- 现代写法
通过构造出tmp然后把tmp和s2进行交换swap
注意我们需要把s2的_str置为nullptr,如果不置为空tmp会变成随机值tmp是局部变量出作用域时会调用析构函数,会导致崩溃
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);//this->swap(tmp)
}
对于现代手法的swap有两个标准库有一个swapstring也有一个swap。
swap(s1,s2);
s1.swap(s2);
对于第一个swap交换代价比较大需要三次深拷贝(拷贝+赋值+赋值)造成空间损耗所以我们可以提供一个成员函数swap交换string直接交换swap中的swap要指定作用域std::否则需要从局部找再去全局找发现参数不匹配。
3.赋值重载
默认生成的赋值重载也会导致浅拷贝所以我们需要实现深拷贝。同时对于赋值重载我们不要直接去进行销毁有可能自己给自己赋值导致自身进行销毁。最好利用tmp来进行赋值
- 传统写法
string& operator=(const string& str)
{
if (this != &str)
{
char* tmp = new char[str._capacity + 1];
strcpy(tmp, str._str);
delete[] _str;
_str = tmp;
_size = str._size;
_capacity = str._capacity;
}
return *this;
}
- 现代写法
string& operator=(const string& str)
{
if (this != &str)
{
string tmp(str);
swap(tmp);
}
return *this;
}
另外一种写法:直接传值传参
string& operator=(string str)
{
swap(str);
return *this;
}
4.析构函数
需要用到delete[]放空间
~string()
{
delete[] _str;
_str = nullptr;
_size = _capacity = 0;
}
三、常用接口
1.迭代器和范围for
- 迭代器
迭代器有普通迭代器以及const修饰的迭代器所以我们可以实现两种不同的迭代器其中const迭代器可读不可写。
iterator begin()
{
return _str;
}
iterator end()
{
return _str + _size;
}
const_iterator begin() const
{
return _str;
}
const_iterator end() const
{
return _str + _size;
}
- 范围for
范围fro的底层原理就是迭代器实现范围for后我们可以直接使用
void test_string1()
{
string s1("hello world");
string::iterator it = s1.begin();
while (it < s1.end())
{
cout << *it;
it++;
}
cout << endl;
for (auto e : s1)
{
cout << e;
}
cout << endl;
}
2.[]重载
- 普通[]重载
适于普通对象,可读可写
char& operator[](size_t pos)
{
assert(pos < _size);
return _str[pos];
}
- const[]重载
适于const对象只可读不可写
const char& operator[](size_t pos) const
{
assert(pos < _size);
return _str[pos];
}
3.c_str
const char* c_str() const
{
return _str;
}
四、容量操作函数
1.size和capacity函数
size_t size()
{
return _size;
}
size_t capacity()
{
return _capacity;
}
2.empty函数
用于判断string类对象是否为空
bool empty()const
{
return _size == 0;
}
3.reserve函数
在已知开多少空间是调用避免频繁扩容具体实现要开辟新的空间在进行拷贝对旧空间进行释放。
只有n大于原来的_capacity时候才进行扩容不进行缩容。
void reserve(size_t n)
{
if (n > _capacity)
{
char* tmp = new char[n];
strcpy(tmp, _str);
delete[] _str;
_str = tmp;
_capacity = n;
}
}
4.resize函数
resize需要分情况
1.元素个数大于容量需要扩容多出来的用’\0’默认情况下来进行填充
2.元素个数小于原有的需要删除
void resize(size_t n, char c = '\0')
{
if (n > _size)
{
reserve(n);
size_t i = 0;
for (i = _size; i < n; ++i)
{
_str[i] = c;
}
_size += n;
_str[_size] = '\0';
}
else
{
_str[n] = '\0';
_size = n;
}
}
五、修改操作函数
1.push_back
尾插一个字符我们需要考虑扩容问题我们需要判断capacity是否为0的情况同时尾插之后’\0’要重新处理。
void push_back(const char ch = '\0')
{
if (_capacity == _size)
{
size_t newCapacity = _capacity == 0 ? 4 : _capacity * 4;
reserve(newCapacity);
}
_str[_size] = ch;
++_size;
_str[_size] = '\0';
}
2.append
尾插字符串这里开多少空间取决于插入字符串的长度。
void append(const char* str)
{
size_t len = strlen(str);
if (_size + len > _capacity)
{
reserve(_size + len);
}
strcpy(_str + _size, str);
_size += len;
}
3.+=重载
可以复用push_back和append来实现
string& operator+=(char c)
{
push_back(c);
return *this;
}
string& operator+=(const char* str)
{
append(str);
return *this;
}
4.insert
- 插入字符
string& insert(size_t pos, char ch)
{
assert(pos <= _size);
if (_capacity == _size)
{
size_t newCapacity = _capacity == 0 ? 4 : _capacity * 4;
reserve(newCapacity);
}
//挪动数据
size_t end = _size;
while (end >= pos)
{
_str[end] = _str[end - 1];
--end;
}
_str[pos] = ch;
++_size;
return *this;
}
可以看到当pos是0时候进行插入–end会变成-1进程崩溃但是不要忽略了end的类型是size_t,怎么可能是-1。可以把end改成int类型但是实际上这样子会发生隐式类型提升范围小往大的提升也就是int会提升为size_t,还是没解决问题
- 1.强转
- 2.去掉=
string& insert(size_t pos, char ch)
{
assert(pos <= _size);
if (_capacity == _size)
{
size_t newCapacity = _capacity == 0 ? 4 : _capacity * 4;
reserve(newCapacity);
}
//挪动数据
size_t end = _size;
while (end > pos)
{
_str[end] = _str[end - 1];
--end;
}
_str[pos] = ch;
++_size;
return *this;
}
- 插入字符串
要把插入的字符串拷贝过来但是不要把’\0’顺便拷贝过来所以不要用strcpy而是要用strncpy并且要注意检查是否越界。
string& insert(size_t pos, const char* str)
{
assert(pos <= _size);
size_t len = strlen(str);
if (_size + len > _capacity)
{
reserve(_size + len);
}
//挪动数据
size_t end = _size + len;
while (end > pos + len - 1)
{
_str[end] = _str[end - len];
--end;
}
_size += len;
return *this;
}
六、删除
1.clear
清空string类对象但不改变string类对象的_capacity
void clear()
{
_str[0] = '\0';
_size = 0;
}
2.erase
1.如果len太长直接把pos之后的删除即可
2.只需要删除部分挪动数据
string& erase(size_t pos, size_t len = npos)
{
assert(pos < _size);
if (len == npos || pos + len >= _size)
{
_str[pos] = '\0';
_size = pos;
}
//挪动数据
else
{
strcpy(_str + pos, _str + pos + len);
_size -= len;
}
return *this;
}
七、查找
从pos处开始查找字符或者字符串找到返回下标值没找到则返回npos,可以调用C接口strstr函数
size_t find(const char ch, size_t pos = 0)
{
assert(pos < _size);
while (pos < _size)
{
if (_str[pos] == ch)
{
return pos;
}
++pos;
}
return npos;
}
size_t find(const char* str, size_t pos = 0)
{
const char* ptr = strstr(_str + pos, str);
if (ptr == nullptr)
{
return npos;
}
else
{
return ptr - _str;
}
}
八、运算符重载
1.流插入<<
ostream& operator<<(ostream& out, const string& s)
{
for (size_t i = 0; i < s.size(); ++i)
{
out << s[i];
}
return out;
}
<<和c_str()的区别<<按照size进行打印跟\0没有关系而c_str()遇到\0结束。
2.流提取>>
scanf和cin一样都拿不到’ ‘和’\0’
所以要读取一个一个的字符我们可以用get函数
istream& operator>>(istream& in, string& s)
{
s.clear();
char ch = in.get();
while (ch != ' ' && ch != '\n')
{
s += ch;
ch = in.get();
}
return in;
}
另外一种
istream& operator>>(istream& in, string& s)
{
s.clear();
char buff[128] = { '\0' };
size_t i = 0;
char ch = in.get();
while (ch != ' ' && ch != '\n')
{
if (i == 127)
{
s += buff;
i = 0;
}
buff[i++] = ch;
ch = in.get();
}
if (i >= 0)
{
buff[i] = '\0';
s += buff;
}
return in;
}
九、完整代码
#include<assert.h>
#include<iostream>
#include<string.h>
using namespace std;
namespace lj
{
size_t npos = -1;
class string
{
public:
typedef char* iterator;
typedef const char* const_iterator;
//基本框架
string(const char* str = "")
{
// 构造String类对象时如果传递nullptr指针可以认为程序非法
if (nullptr == str)
{
assert(false);
return;
}
_size = strlen(str);
_capacity = _size;
_str = new char[_capacity + 1];
strcpy(_str, str);
}
//传统写法
/*string(const string& str)
{
_size = str._size;
_capacity = str._capacity;
_str = new char[_capacity + 1];
strcpy(_str, str._str);
}*/
//现代写法
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);//this->swap(tmp)
}
//传统写法
/*string& operator=(const string& str)
{
if (this != &str)
{
char* tmp = new char[str._capacity + 1];
strcpy(tmp, str._str);
delete[] _str;
_str = tmp;
_size = str._size;
_capacity = str._capacity;
}
return *this;
}*/
//现代写法
string& operator=(const string& str)
{
if (this != &str)
{
string tmp(str);
swap(tmp);
}
return *this;
}
/*string& operator=(string str)
{
swap(str);
return *this;
}*/
~string()
{
delete[] _str;
_str = nullptr;
_size = _capacity = 0;
}
//迭代器
iterator begin()
{
return _str;
}
iterator end()
{
return _str + _size;
}
const_iterator begin() const
{
return _str;
}
const_iterator end() const
{
return _str + _size;
}
//[]重载
char& operator[](size_t pos)
{
assert(pos < _size);
return _str[pos];
}
const char& operator[](size_t pos) const
{
assert(pos < _size);
return _str[pos];
}
//容器操作函数
size_t size()
{
return _size;
}
size_t capacity()
{
return _capacity;
}
bool empty()const
{
return _size == 0;
}
void resize(size_t n, char c = '\0')
{
if (n > _size)
{
reserve(n);
size_t i = 0;
for (i = _size; i < n; ++i)
{
_str[i] = c;
}
_size += n;
_str[_size] = '\0';
}
else
{
_str[n] = '\0';
_size = n;
}
}
void reserve(size_t n)
{
if (n > _capacity)
{
char* tmp = new char[n];
strcpy(tmp, _str);
delete[] _str;
_str = tmp;
_capacity = n;
}
}
//修改操作函数
void push_back(const char ch = '\0')
{
if (_capacity == _size)
{
size_t newCapacity = _capacity == 0 ? 4 : _capacity * 4;
reserve(newCapacity);
}
_str[_size] = ch;
++_size;
_str[_size] = '\0';
}
void append(const char* str)
{
size_t len = strlen(str);
if (_size + len > _capacity)
{
reserve(_size + len);
}
strcpy(_str + _size, str);
_size += len;
}
string& operator+=(char c)
{
push_back(c);
return *this;
}
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 (_capacity == _size)
{
size_t newCapacity = _capacity == 0 ? 4 : _capacity * 4;
reserve(newCapacity);
}
//挪动数据
size_t end = _size;
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);
}
//挪动数据
size_t end = _size + len;
while (end > pos + len - 1)
{
_str[end] = _str[end - len];
--end;
}
_size += len;
return *this;
}
void clear()
{
_str[0] = '\0';
_size = 0;
}
string& erase(size_t pos, size_t len = npos)
{
assert(pos < _size);
if (len == npos || pos + len >= _size)
{
_str[pos] = '\0';
_size = pos;
}
//挪动数据
else
{
strcpy(_str + pos, _str + pos + len);
_size -= len;
}
return *this;
}
size_t find(const char ch, size_t pos = 0)
{
assert(pos < _size);
while (pos < _size)
{
if (_str[pos] == ch)
{
return pos;
}
++pos;
}
return npos;
}
size_t find(const char* str, size_t pos = 0)
{
const char* ptr = strstr(_str + pos, str);
if (ptr == nullptr)
{
return npos;
}
else
{
return ptr - _str;
}
}
private:
char* _str;
size_t _size;
size_t _capacity;
};
ostream& operator<<(ostream& out, const string& s)
{
for (size_t i = 0; i < s.size(); ++i)
{
out << s[i];
}
return out;
}
istream& operator>>(istream& in, string& s)
{
s.clear();
char buff[128] = { '\0' };
size_t i = 0;
char ch = in.get();
while (ch != ' ' && ch != '\n')
{
if (i == 127)
{
s += buff;
i = 0;
}
buff[i++] = ch;
ch = in.get();
}
if (i >= 0)
{
buff[i] = '\0';
s += buff;
}
return in;
}
/*istream& operator>>(istream& in, string& s)
{
s.clear();
char ch = in.get();
while (ch != ' ' && ch != '\n')
{
s += ch;
ch = in.get();
}
return in;
}*/
}