C++_String增删查改模拟实现
- 前言
- 一、string默认构造、析构函数、拷贝构造、赋值重载
- 1.1 默认构造
- 1.2 析构函数
- 1.3 拷贝构造
- 1.4 赋值重载
- 二、迭代器和范围for
- 三、元素相关：operator[ ]
- 四、容量相关：size、resize、capacity、reserve
- 4.1 size、capacity
- 4.2 reserve
- 4.3 resize
- 五、数据相关：push_bach、append、operator+=、insert、erase
- 5.1 尾插：push_back
- 5.2 append尾部插入字符串
- 5.3 operator+=()字符、字符串
- 5.4 insert插入字符、字符串
- 5.4.1 insert插入字符（在这提醒下，博主是所有的拷贝数据都是从'\0'开始，这样就不需要单独对'\0'做处理）
- 初学者最容易范的一个错误
- 5.4.2 insert插入字符串
- 5.5 erase
- 六、 关系操作符重载：< 、 ==、 <=、 >、>=、!=
- 七、find查找字符、字符串、substr
- 7.1 find查找字符
- 7.2 find查找字符串
- 7.3 strsub( ) 模拟实现
- 八、流插入和流提取（<<、>>）(实现在string类外)
- 8.1 流插入<<
- 8.1 流提取>>
- 优化
- 九、所有代码
前言
本篇博客仅仅实现存储字符的string。同时由于C++string库设计的不合理，博主仅实现一些最常见的增删查改接口！
接下来给出的接口都是基于以下框架：
namespace achieveString
{
class string
{
private:
char* _str;
size_t _capacity;
size_t _size;
};
}
一、string默认构造、析构函数、拷贝构造、赋值重载
1.1 默认构造
博主在这仅仅提供如无参和带参默认构造接口：
//无参默认构造
string()
:_str(new char[1]{'\0'})
,_capacity(0)
,_size(0)
{ }
//带参默认构造
string(const char* str = "")
:_capacity(strlen(str))
,_size(_capacity)
{
_str = new char[_capacity + 1];
strcpy(_str, str);
}
小tips：
- C++string标准库中，无参构造并不是空间为0，直接置为空指针。而是开一个字节，并存放‘\0’。（C++中支持无参构造一个对象后，直接在后面插入数据，也从侧面说明了这点）
- 由于C++构造函数不管写不写都会走初始化列表的特性，所以这里博主也走初始化列表。
- string中，_capacity和_size都不包含空指针，所以带参构造要多开一个空间，用来存储’\0’。
1.2 析构函数
~string()
{
delete[] _str;
_str = nullptr;
_size = _capacity = 0;
}
1.3 拷贝构造
传统写法：
string(const string& s)
{
_str = new char[s._capacity + 1];
strcpy(_str, s._str);
_size = s._size;
_capacity = s._capacity;
}
现代写法：现代写法的核心在于：将拷贝数据的工作交给别人来做，最后将成果交换一样即可。
//交换
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);
}
tips：现代写法中，拷贝构造是数据需初始化为空。原因在于C++中，编译器对内置类型不会做处理（个别如vs2019等编译器会做处理的），这也就意味这_str是一个随机值，指向任意一块空间。调用析构函数时会报错。
1.4 赋值重载
赋值重载同样分为传统写法和现代写法。
传统写法：
string& operator=(const string& s)
{
if (this != &s)
{
char* tmp = new char[s._capacity + 1];
strcpy(tmp, s._str);
delete[] _str;
_str = tmp;
_size = s._size;
_capacity = s._capacity;
}
return *this;
}
现代写法：
//现代写法
//法一
/*string& operator=(const string& s)
{
if (this != &s)
{
string tmp(s._str);
swap(tmp);
}
return *this;
}*/
//法二
string& operator=(string tmp)
{
swap(tmp);
return *this;
}
二、迭代器和范围for
在C++中，范围for在底层是通过迭代器来实现的。所以只要实现了迭代器，就支持范围for。
而迭代器类似于指针，迭代器可以被看作是指针的一种泛化，它提供了类似指针的功能，可以进行解引用操作、指针运算等。
以下提供了const迭代器和非const迭代器：
typedef char* iterator;
const typedef 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;
}
三、元素相关：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];
}
四、容量相关：size、resize、capacity、reserve
4.1 size、capacity
size_t size()const
{
return _size;
}
size_t capacity()const
{
return _capacity;
}
4.2 reserve
在C++中，我们一般不缩容。
所以实现reserve时（容量调整到n），首先判断目标容量n是否大于当前容量。如果小于就不做处理，否则先开辟n+1个内存空间（多出来的一个用于存储‘\0’），然后将原有数据拷贝到新空间（strcpy会将’\0’一并拷贝过去）。然后释放就空间，并让_str指向新空间，同时更新_capacity。
void reserve(size_t n)
{
if (n > _capacity)
{
char* tmp = new char[n + 1];
strcpy(tmp, _str);
delete[] _str;
_str = tmp;
_capacity = n;
}
}
4.3 resize
resize到目标大小分为以下3中情况：
- 当n<_size时，只需将下标为n的地址处的数据改为’\0’。
- 其他情况，我们直接统一处理。直接复用reserve()函数将_capacity扩到n。然后用将[_size, n)中的数据全部初始化为ch。（这里博主给ch一个初始值’\0’，但ch不一定为’\0’，所以要将下标为n处的地址初始化为’\0’）
void resize(size_t n, char ch='\0')
{
if (n <= _size)
{
_str[n] = '\0';
_size = n;
}
else
{
reserve(n);
while (_size < n)
{
_str[_size] = ch;
_size++;
}
_str[_size] = '\0';
}
}
五、数据相关：push_bach、append、operator+=、insert、erase
5.1 尾插：push_back
尾插首先检查扩容，在插入数据
void push_back(char ch)
{
//扩容
if (_size == _capacity)
{
reserve(_capacity == 0 ? 4 : _capacity * 2);
}
//插入数据
_str[_size] = ch;
_size++;
_str[_size] = '\0';
}
5.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;
}
5.3 operator+=()字符、字符串
operator+=()字符、字符串可以直接复用push_back和append。
string& operator+=(char ch)
{
push_back(ch);
return *this;
}
string& operator+=(const char* str)
{
append(str);
return *this;
}
5.4 insert插入字符、字符串
5.4.1 insert插入字符（在这提醒下，博主是所有的拷贝数据都是从’\0’开始，这样就不需要单独对’\0’做处理）
insert插入字符逻辑上还是很简单的。
首先判断插入字符时是否需要扩容。然后从下标为pos开始，所有数据依次往后挪动。最后将待插入字符给到pos处即可。
初学者最容易范的一个错误
但对于初学者来说，貌似也不太轻松。。。。。。
下面给出各位初学者容易犯的错误：
void insert(size_t pos, char ch)
{
assert(pos <= _size);
//扩容
if (_size == _capacity)
{
reserve(_capacity == 0 ? 4 : _capacity * 2);
}
//挪动数据
size_t end = _size;
while (end >= pos)
{
_str[end+1] = _str[end];
end--;
}
_str[pos] = ch;
_size++
}
这样对吗？答案是错误的。
假设是在头插字符，end理论上和pos(即0)比较完后就减到-1，在下一次循环条件比较时失败，退出循环。
遗憾的是end是size_t类型，始终>=0, 会导致死循环。
博主在这给出两种解决方法：
- 将pos强转为整型。
void insert(size_t pos, char ch)
{
assert(pos <= _size);
//扩容
if (_size == _capacity)
{
reserve(_capacity == 0 ? 4 : _capacity * 2);
}
//挪动数据
int end = _size;
while (end >= (int)pos)
{
_str[end+1] = _str[end];
end--;
}
_str[pos] = ch;
_size++
}
2.从end从最后数据的后一位开始，每次将前一个数据移到当前位置。最后条件判断就转化为end>pos，不会出现死循环这种情况。
void insert(size_t pos, char ch)
{
assert(pos <= _size);
//扩容
if (_size == _capacity)
{
reserve(_capacity == 0 ? 4 : _capacity * 2);
}
//挪动数据
size_t end = _size+1;
while (end > pos)
{
_str[end] = _str[end-1];
end--;
}
//插入数据，更新_size
_str[pos] = ch;
_size++;
}
5.4.2 insert插入字符串
insert同样存在相同问题，并且思路一样。博主就直接给出代码了。
法一：
void insert(size_t pos, const char* str)
{
int len = strlen(str);
if (_size + len > _capacity)
{
reserve(_size + len);
}
int end = _size;
while (end >= (int)pos)
{
_str[end + len] = _str[end];
end--;
}
strncpy(_str + pos, str, len);
_size += len;
}
法二：
void insert(size_t pos, const char* str)
{
int len = strlen(str);
if (_size + len > _capacity)
{
reserve(_size + len);
}
size_t end = _size+1;
while (end > pos)
{
_str[end + len-1] = _str[end-1];
end--;
}
strncpy(_str + pos, str, len);
_size += len;
}
5.5 erase
erase分两种情况：
- 从pos开始，要删的数据个数超过的字符串，即将pos后序所有数据全部情况。（直接将pos处数据置为’\0’即可）
- 从pos开始，要删的数据个数没有超出的字符串。所以只需要从pos+len位置后的所有数据向前移动从pos位置覆盖原数据即可。
void erase(size_t pos, size_t len = npos)
{
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;
}
}
六、 关系操作符重载：< 、 ==、 <=、 >、>=、!=
bool operator<(const string& s) const
{
return strcmp(_str, s._str) < 0;
}
bool operator==(const string& s) const
{
return strcmp(_str, s._str) == 0;
}
bool operator<=(const string& s) const
{
return *this < s || *this == s;
}
bool operator>(const string& s) const
{
return !(*this <= s);
}
bool operator>=(const string& s) const
{
return !(*this < s);
}
bool operator!=(const string& s) const
{
return !(*this == s);
}
七、find查找字符、字符串、substr
7.1 find查找字符
size_t find(char ch, size_t pos = 0)
{
for (size_t i = pos; i < _size; i++)
{
if (_str[i] == ch)
{
return i;
}
}
return npos;
}
7.2 find查找字符串
size_t find(const char* sub, size_t pos = 0)
{
const char* p = strstr(_str + pos, sub);
if (p)
{
return p - _str;
}
else
{
return npos;
}
}
7.3 strsub( ) 模拟实现
strsub目标长度可能越界string，也可能还有没有。但不管是那种情况，最后都需要拷贝数据。所以这里我们可以先将len真实长度计算出来，在拷贝数据。
string substr(size_t pos, size_t len = npos)const
{
string s;
size_t end = pos + len;
//目标字符越界string,更新len
if (len == npos || end >= _size)
{
len = _size - pos;
end = _size;
}
//拷贝数据
s.reserve(len);
for (size_t i = pos; i < end; i++)
{
s += _str[i];
}
return s;
}
八、流插入和流提取（<<、>>）(实现在string类外)
8.1 流插入<<
由于前面我们实现了迭代器，所以最简单的方式就是范围for
ostream& operator<<(ostream& out, const string& s)
{
/*for (size_t i = 0; i < s.size(); i++)
{
out << s[i];
}*/
for (auto ch : s)
out << ch;
return out;
}
8.1 流提取>>
流提取比较特殊。在流提取前需要将原有数据全部清空。同时由于>>无法获取空字符和换行符()(都是作为多个值之间的间隔)，直接流提取到ostream对象中，没法结束。（类似于C语言中scanf, 换行符和空字符仅仅只是起到判断结束的作用，但scanf无法获取到它们）
所以这里博主直接调用istream对象中的get()函数。（类似于C语言中的getchar()函数）
get详细文档
class string
{
void clear()
{
_str[0] = '\0';
_size = 0;
}
private:
char* _str;
size_t _capacity;
size_t _size;
};
istream& operator>>(istream& in, string& s)
{
s.clear();
char ch;
//in >> ch;
ch = in.get();
while (ch != ' ' && ch != '\n')
{
s += ch;
//in >> ch;
ch = in.get();
}
return in;
}
上面这种方法虽然可以达到目的。但还有一个问题，每次插入数据都面临可扩容问题。那如何优化呢？
优化
其中一种办法就是调用reserve()提前开好空间，但这样面临这另一个问题：开大了浪费空间；开小了，同样面临这扩容的问题。
所以在这博主采用和vs底层实现的思路：首先开好一段数组（包含’\0’，以16为例）。当数据个数小于16时，字符串存在数组中；当数据个数大于等于16时，将数据存在_str指向的空间。
这是一种以空间换时间的思路，同时也能很好的减少内存碎片的问题。
class string
{
void clear()
{
_str[0] = '\0';
_size = 0;
}
private:
char* _str;
size_t _capacity;
size_t _size;
};
istream& operator>>(istream& in, string& s)
{
s.clear();
char buff[16];
size_t i = 0;
char ch;
ch = in.get();
while (ch != ' ' && ch != '\n')
{
buff[i++] = ch;
if (i == 16)
{
buff[i] = '\0';
s += buff;
i = 0;
}
ch = in.get();
}
if (i != 0)
{
buff[i] = '\0';
s += buff;
}
return in;
}
九、所有代码
namespace achieveString
{
class string
{
public:
typedef char* iterator;
const typedef 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;
}
//构造函数
/*string()
:_str(new char[1]{'\0'})
,_capacity(0)
,_size(0)
{ }*/
string(const char* str = "")
:_capacity(strlen(str))
, _size(_capacity)
{
_str = new char[_capacity + 1];
strcpy(_str, str);
}
const char* c_str() const
{
return _str;
}
//析构函数
~string()
{
delete[] _str;
_str = nullptr;
_size = _capacity = 0;
}
//拷贝构造
/*string(const string& s)
{
_str = new char[s._capacity + 1];
strcpy(_str, s._str);
_size = s._size;
_capacity = s._capacity;
}*/
//交换
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=(const string& s)
{
if (this != &s)
{
char* tmp = new char[s._capacity + 1];
strcpy(tmp, s._str);
delete[] _str;
_str = tmp;
_size = s._size;
_capacity = s._capacity;
}
return *this;
}*/
//现代写法
//法一
/*string& operator=(const string& s)
{
if (this != &s)
{
string tmp(s._str);
swap(tmp);
}
return *this;
}*/
//法二
string& operator=(string tmp)
{
swap(tmp);
return *this;
}
//可读可写
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()const
{
return _size;
}
size_t capacity()const
{
return _capacity;
}
bool empty()const
{
return _size == 0;
}
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)
{
_str[n] = '\0';
_size = n;
}
else
{
reserve(n);
while (_size < n)
{
_str[_size] = ch;
_size++;
}
_str[_size] = '\0';
}
}
void push_back(char ch)
{
//扩容
if (_size == _capacity)
{
reserve(_capacity == 0 ? 4 : _capacity * 2);
}
//插入数据
_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 ch)
{
push_back(ch);
return *this;
}
string& operator+=(const char* str)
{
append(str);
return *this;
}
void insert(size_t pos, char ch)
{
assert(pos <= _size);
//扩容
if (_size == _capacity)
{
reserve(_capacity == 0 ? 4 : _capacity * 2);
}
//挪动数据
size_t end = _size+1;
while (end > pos)
{
_str[end] = _str[end-1];
end--;
}
//插入数据，更新_size
_str[pos] = ch;
_size++;
}
void insert(size_t pos, const char* str)
{
int len = strlen(str);
if (_size + len > _capacity)
{
reserve(_size + len);
}
//法一
/*int end = _size;
while (end >= (int)pos)
{
_str[end + len] = _str[end];
end--;
}
strncpy(_str + pos, str, len);
_size += len;*/
//法二
size_t end = _size+1;
while (end > pos)
{
_str[end + len-1] = _str[end-1];
end--;
}
strncpy(_str + pos, str, len);
_size += len;
}
void erase(size_t pos, size_t len = npos)
{
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;
}
}
bool operator<(const string& s)const
{
return strcmp(_str, s._str) < 0;
}
bool operator==(const string& s)const
{
return strcmp(_str, s._str) == 0;
}
bool operator<=(const string& s)const
{
return *this == s && *this < s;
}
bool operator>(const string& s)const
{
return !(*this <= s);
}
bool operator>=(const string& s)const
{
return !(*this < s);
}
bool operator!=(const string& s)const
{
return !(*this == s);
}
size_t find(char ch, size_t pos = 0)
{
for (size_t i = pos; i < _size; i++)
{
if (_str[i] == ch)
return i;
}
return npos;
}
size_t find(const char* sub, size_t pos = 0)
{
const char* p = strstr(_str + pos, sub);
if (p)
{
return p - _str;
}
else
{
return npos;
}
}
string substr(size_t pos, size_t len = npos)
{
string s;
size_t end = pos + len;
if (len == npos || end >= _size)
{
len = _size - pos;
end = _size;
}
s.reserve(len);
for (size_t i = pos; i < end; i++)
{
s += _str[i];
}
return s;
}
void clear()
{
_str[0] = '\0';
_size = 0;
}
private:
char* _str;
size_t _capacity;
size_t _size;
//const static size_t npos = -1; // C++支持const整型静态变量在声明时给值初始化，但不建议
//const static double npos = 1.1; // 不支持
const static size_t npos;
};
const size_t string::npos = -1;
ostream& operator<<(ostream& out, const string& s)
{
/*for (size_t i = 0; i < s.size(); i++)
{
out << s[i];
}*/
for (auto ch : s)
out << ch;
return out;
}
//istream& operator>>(istream& in, string& s)
//{
// s.clear();
// char ch;
// //in >> ch;
// ch = in.get();
// while (ch != ' ' && ch != '\n')
// {
// s += ch;
// //in >> ch;
// ch = in.get();
// }
// return in;
//}
istream& operator>>(istream& in, string& s)
{
s.clear();
char buff[16];
size_t i = 0;
char ch;
ch = in.get();
while (ch != ' ' && ch != '\n')
{
buff[i++] = ch;
if (i == 16)
{
buff[i] = '\0';
s += buff;
i = 0;
}
ch = in.get();
}
if (i != 0)
{
buff[i] = '\0';
s += buff;
}
return in;
}
}
![2023年中国宠物清洁用品分类、市场规模及发展特征分析[图]](https://img-blog.csdnimg.cn/img_convert/c98b948fcd445fa5c73bbadb65db6e88.png)
