【c++_containers】string的模拟实现
前言
在学习数据结构时，如何证明自己彻底掌握了一个容器的各种特性？最直接的办法就是自己写一个。下面我们将围绕下图展开对与string的深度了解：
一.string的成员变量
string是表示字符序列的对象，同时增加了专门用于操作单字节字符的字符串的功能。
所以他的成员变量应该为
private:
size_t _size;
size_t _capacity;
char* _str;二、初始化和清理
2.1构造函数
其中最为常用的是1，2，4这几种，而第一种又可以通过第二种加上缺省参数而写成。
作为构造函数最重要的就是开辟空间和将成员变量初始化。
string(const char* str = "")
{
_size = strlen(str);
_capacity = _size;
_str = new char[_capacity + 1];
memcpy(_str, str, _size + 1);
}
string(const string& s)
{
_str = new char[s._capacity + 1];
_size = s._size;
_capacity = s._capacity;
memcmp(_str, s._str, _size + 1);
}这里使用memcmp而不是直接使用赋值，涉及深浅拷贝的问题，这里简单提一下
1.深拷贝和浅拷贝一样，都会创建一个新的容器对象(compound object) 2.和浅拷贝的不同点在于，深拷贝对于对象中的元素，深拷贝都会重新生成一个新的对象
比如这个string如果是浅拷贝，拷贝前后两个string中的_str（指针）所存的地址一样，也就是指向同一片空间，这明显不符合我们的预期。
2.2析构函数
string的析构函数较为简单，但是由于string是一个动态开辟空间的容器，所以空间需要自己手动释放，不能依赖系统自己生成的析构函数
~string()
{
_size = 0;
_capacity = 0;
delete[] _str;
_str = nullptr;
}三、string的增加
3.1扩容（reserve）
作为一个动态容器，在使用过程中不可避免的就是容量的变化，在string中直接集成成了一个函数。也就是reserve。
从上面我们可以看出当n>_capacity时直接扩容到n，而在n<=_capacity时，编译器自行优化但不能改变字符串的长度。也就是这个函数不会发生截断的情况，无法改变_size.
这里我们当：n < _size时将其容量缩小到_size.
void reserve(size_t n)
{
if (n > _capacity)
{
char* tmp = new char[n + 1];
memcpy(tmp, _str, _size + 1);
delete[] _str;
_str = tmp;
_capacity = n;
}
//理论上这个函数也能缩小capacity,但是不能发生截断的情况，_size不能变
else if (n < _capacity)
{
if (n >= _size)
{
char* tmp = new char[n + 1];
memcpy(tmp, _str, n);
tmp[n] = '\0';
delete[] _str;
_str = tmp;
_capacity = n;
}
else
{
char* tmp = new char[_size + 1];
memcpy(tmp, _str, _size);
tmp[_size] = '\0';
delete[] _str;
_str = tmp;
_capacity = n;
}
}
}3.2插入
作为线性的容器，在扩容实现后，插入就变的十分轻松了。只要确定插入的位置，其他的向后跟着遍历一遍就可以了。而在这之前我们可以先实现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];
}当所有前置条件都集齐后，插入的就变得十分好写了。
void push_back(char c)
{
if (_size == _capacity)
{
reserve(_capacity == 0 ? 4 : _capacity * 2);
}
_str[_size] = c;
++_size;
_str[_size] = '0';
}
//在字符串尾添加字符串
void append(const char* str)
{
size_t len = strlen(str);
if (_size + len > _capacity)
{
// 至少扩容到_size + len
reserve(_size + len);
}
//strcpy(_str + _size, str);
memcpy(_str + _size, str, len + 1);
_size += len;
}
string& operator+=(char ch)
{
push_back(ch);
return *this;
}
string& operator+=(const char* str)
{
append(str);
return *this;
}
//在pos位置插入n个字符
void insert(size_t pos, size_t n, char ch)
{
assert(pos <= _size);
if (_size + n > _capacity)
{
reserve(_size + n);
}
size_t end = _size;
while (end > pos && end != npos)
{
_str[end + n] = _str[end];
end--;
}
for (size_t i = 0; i < n; i++)
{
_str[pos + i] = ch;
}
_size += n;
}
//在pos位置插入字符串
void insert(size_t pos, char* ch)
{
assert(pos <= _size);
size_t n = strlen(ch);
if (_size + n > _capacity)
{
reserve(_size + n);
}
size_t end = _size;
while (end > pos && end != npos)
{
_str[end + n] = _str[end];
end--;
}
for (size_t i = 0; i < n; i++)
{
_str[pos + i] = ch[i];
}
_size += n;
}四、string的删除
在删除前，我们要先清楚string的本质，即他是一个字符串。而对于一个字符串来说，终止是用“\0”
所以在删除字符串时我们只需要替换与将结尾替换成“\0”就可以了。
//从pos向后删除len个字符
void esase(size_t pos,size_t len=npos)
{
assert(pos <= _size);
if (len == npos || pos + len >= _size)
{
//_str[pos] = '\0';
_size = pos;
_str[_size] = '\0';
}
else
{
size_t end = pos + len;
while (end <= _size)
{
_str[pos++] = _str[end++];
}
_size -= len;
}
}五、string的查找
作为一个容器最重要的就是精确的找到所储存的数据，而string的查找其实就是直接遍历
//从pos开始查找ch
size_t find(char ch, size_t pos = 0)
{
assert(pos < _size);
for (size_t i = pos; i < _size; i++)
{
if (_str[i] == ch)
{
return i;
}
}
return npos;
}
size_t find(const char* str, size_t pos = 0)
{
assert(pos < _size);
const char* ptr = strstr(_str + pos, str);
if (ptr)
{
return ptr - _str;
}
else
{
return npos;
}
}六、string的operator
对于自定义类来说，将必要的符号重载成我们所需要的操作可以大大方便代码的编写。
bool operator==(const string& s)const
{
return _size == s._size && memcmp(_str, s._str, _size) == 0;
}
bool operator<(const string& s) const
{
int ret = memcmp(_str, s._str, _size < s._size ? _size : s._size);
// "hello" "hello" false
// "helloxx" "hello" false
// "hello" "helloxx" true
return ret == 0 ? _size < s._size : ret < 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);
}七、迭代器
对于string的迭代器只需要使用char*就可以了。
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;
}当迭代器完成后，for的自动变历就可以实现了。
腾讯云开发者
