【C++】STL之string类模拟-2

简介: 【C++】STL之string类模拟

4、Capacity —— 容量

下面四个接口我们一起来看看,然后一同测试

size

  • 首先是 size(),这里的话我们直接返回_size即可,因为不会去修改成员变量,所以我们可以加上一个【const成员】
size_t size() const
{
  return _size;
}

capacity

  • 对于 capacity() 也是同样的道理
size_t capacity() const
{
  return _capacity;
}

clear

  • 对于 clear() 而言就是去清除当前对象的数据,我们直接在_str[0]这个位置放上一个\0即可,并且再去修改一下它的_size = 0即可
  • 不过这个接口来说我们不要去加【const成员】,因为修改了其成员变量_size
void clear()
{
  _str[0] = '\0';
  _size = 0;
}

empty

  • 对于 empty() 来说呢就是对象中没有数据,那么使用0 == _size即可
bool empty() const
{
  return 0 == _size;
}

💬 然后我们来测试一下

image.png

reserve

然后我们来看【reserve】扩容

  • 很明显,只有当这个 新容量大于旧容量的时候,才会去选择去开空间,这里的扩容逻辑和我们在实现旧版本的拷贝构造函数时类似的:也是先开出一块新的空间(这里主要使用这个newCapacity 去开),然后再将原本的数据拷贝过来,释放旧空间的数据后让_str指向新空间即可。最后的话不要忘了去更新一下容量大小
  • 但是呢对于VS下如何去实现 1.5倍 的扩容就不做展开了,读者有兴趣可以自己试试
// 扩容(修改_capacity)
void reserve(size_t newCapacity = 0)
{
  // 当新容量大于旧容量的时候,就开空间
  if (newCapacity > _capacity)
  {
    // 1.以给定的容量开出一块新空间
    char* tmp = new char[newCapacity + 1];
    // 2.将原本的数据先拷贝过来
    memcpy(tmp, _str, _size);
    // 3.释放旧空间的数据
    delete[] _str;
    // 4.让_str指向新空间
    _str = tmp;
    // 5.更新容量大小
    _capacity = newCapacity;
  }
}

马上来做一个测试

image.png通过调试再去看一下,可以发现_str的空间确实发生了一个很大的改变

https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/695e7c9cee6a44e88fc91fdd5febc3cb~tplv-k3u1fbpfcp-jj-mark:3024:0:0:0:q75.awebp#?w=1228&h=546&s=164159&e=gif&f=77&b=cde8d3

resize

然后我们再来讲讲【resize】,博主觉得下面的这个算法是比较优的,读者可以参考一下

  • 首先我们来分析一下,对于【resize】而言主要对对象中的数据去做一个变化,那就需要去进行分类讨论
  • 如果这个 newSize < _size 的话,那我们要选择去删除数据
  • 如果这个 newSize > _size,但是呢 newSize < _capacity 的话,此时要做的就是新增数据但是呢不去做扩容
  • 如果这个 newSize > _size 的话,我们便要选择去进行扩容了

image.png

  • 在分析完了之后,我们立即来实现一下相关的代码。可以看到,一上来我就直接去判断了newSize 是否大于_size,然后在内部又做了一层判断,只有当newSize > _capacity时,才去执行【reserve】的扩容逻辑
  • 如果newSize并没有超过容量大小的话我们要做的事情就是去填充数据,这里用到的是一个内存函数【memset
  • 我们从_str + _size 的位置开始填充;
  • 填充的个数是newSize - _size个;
  • 填充的内容是c
  • 若是newSize <= _size的话,我们所要做的就是去截取数据,到newSize为止直接设置一个 \0,然后更新一下当前对象的_size大小
// 改变大小
void resize(size_t newSize, char c = '\0')
{
  // 1.当新的_size比旧的_size来得小的话,则进行删除数据
  if (newSize > _size)
  {
    // 只有当新的size比容量还来的大,才去做一个扩容
    if (newSize > _capacity)
    {
      reserve(newSize);
    }
    // 如果newSize <= _capacity,填充新数据即可
    memset(_str + _size, c, newSize - _size);
  }
  // 如果 newSize <= _size,不考虑扩容和新增数据
  _size = newSize;
  _str[newSize] = '\0';
}

💬 马上我们就来分类测试一下

  • 首先是resize(8),可以看到这里发生了一个数据截断的情况,_size也相对应地发生了一个变化

  • 接下去的话是resize(12),这并没有超过其容量值,但是却超出了_size 大小,所以我们要去做一个扩容

  • 最后一个则是resize(18),此时的话就需要去走一个扩容逻辑了,并且在扩完容之后还要再进一步去填充数据


5、Modifiers —— 修改器

好,接下去我们来讲讲修改器这一块

push_back

  • 首先第一块的话简单一点,我们去追加一个字符,那首先要考虑到的也是一个扩容逻辑,因为我们是一个字符一个字符去进行插入的,那么当这个_size == _capacity的时候,就要去执行一个扩容的逻辑了,这边的话是运用到了这个三目运算符,若是容量的大小为0的话,默认开个大小为4的空间就可以了;其他的情况都是以2倍的形式去进行扩充
  • 最后在扩完容之后我们就在末尾去增加数据了,因为_size指向的就是 \0 的位置,所以就把字符放在这个位置上就可以了,顺带地记得去后移一下这个_size,再放上一个 \0
// 追加一个字符
void push_back(char ch)
{
  // 如果数据量大于容量的话,则需要进行扩容
  if (_size == _capacity)
  {   
    reserve(_capacity == 0 ? 4 : _capacity * 2);
  }
  _str[_size++] = ch;
  _str[_size] = '\0';
}
  • 立马来测试一下看看

append

  • 接下去的话是【append】,要追加的是一个字符串,所以我们要先去算出它的长度,接下去判断一下在加上这个长度后是否要去做一个扩容,最后的话还是通过我们熟悉的【memcpy】通过字节的形式一一拷贝到_str + _size的位置(注意拷贝len + 1个,带上最后 \0),最后再把大小_size给增加一下即可
// 追加一个字符串
void append(const char* s)
{
  int len = strlen(s);  // 获取到待插入字符串的长度
  // 若是加上len长度后超出容量大小了,那么就需要扩容
  if (_size + len > _capacity)
  {
    reserve(_size + len);
  }
  // 将字符串拷贝到末尾的_size位置
  memcpy(_str + _size, s, len + 1);
  // 大小增加
  _size += len;
}
  • 也是一样来测试一下

读者一定会觉得上面的函数调用太过于冗余,不过没关系,我们还有【+=】呢

operator+=(char ch)

  • 首先的话是去【+=】一个字符,这里我们直接复用前面的push_back()接口即可,最后因为【+=】改变的是自身,所以我们return *this,那么返回一个出了作用域不会销毁的对象,可以采取 引用返回 减少拷贝
string& operator+=(char ch)
{
  push_back(ch);
  return *this;
}

operator+=(const char* s)

  • 而对于【+=】一个字符串,我们则是去复用前面的append()即可
string& operator+=(const char* s)
{
  append(s);
  return *this;
}

💬 立马来测试一下吧

image.png

从pos位置开始插入n个字符

接下去我们就要来实现一下【insert】这个接口了

  • 不过在这之前呢我们先要去声明并初始化一个静态的成员变量npos,它是最大的无符号整数值。但是对于 静态的成员变量 来说我们需要 在类内声明并且在类外进行初始化

cpp

// 类内声明
static size_t npos;
// 类外初始化
size_t string::npos = -1;

  • 首先第一个的话就是要在pos位置插入n个字符
void insert(size_t pos, size_t n, char ch)


  • 因为这里会传入一个pos位置,所以第一步我们就是要去考虑这个pos位置是否合法
assert(pos <= _size);
  • 接下去第二步的话就是去考虑过扩容的问题了,如果_size + n之后的大小大于_capacity的话那就要调用【reserve】接口去实现一个扩容的逻辑了
// 考虑扩容
if (_size + n > _capacity)
{
  reserve(_size + n);
}
  • 第三步呢并不是直接去插入数据,而是要先给需要插入的n个字符腾出位置。从_size位置开始,让字符以n个单位地从后往前挪即可,若是从前往后挪的话就会造成覆盖的问题

image.png

// 挪动数据
size_t end = _size;
while (end >= pos)
{
  _str[end + n] = _str[end];
  --end;
}
  • 不过呢,我们在这里还要考虑一种极端的情况,如果这个pos == 0的话,也就是在这个位置开始插入数据,那也就相当于头插,此时需要将全部的数据向后进行挪动,可是呢当这个end超出pos的范围时,也就减到了-1,但是呢这个end的数据类型则是【size_t】,为一个无符号整数,我们知道对于无符号整数来说是不可能为负数的,那么这个时候就会发生一个轮回,变成最大的无符号正数

image.png

  • 我们可以来看看当这个end在不断减少直至减到0的时候就会突然变成一个很大的数字,这个其实就是npos的值了,此时就会造成一个死循环,导致程序崩溃

  • 所以我们应该在循环的结束条件中加上一个end != npos才对
// 挪动数据
size_t end = _size;
while (end >= pos && end != npos)
{
  _str[end + n] = _str[end];
  --end;
}
  • 当这个挪动的逻辑结束后,我们就可以从pos这个位置去插入n个字符了。最后再去更新一下这个_size的大小即可
// 插入n个字符
for (size_t i = 0; i < n; i++)
{
  _str[pos + i] = ch;
}
_size += n;

image.png

从pos位置开始插入一个字符串

void insert(size_t pos, const char* s)


  • 对于在【pos位置插入一个字符串】来说,其他逻辑和上面这个接口都是一样,也是要经过 扩容移位放数据 这些操作,只是这里在放数据的时候换成了字符串而言
// 插入字符串
for (size_t i = 0; i < len; i++)
{
  _str[pos + i] = s[i];
}
_size += len;

删除从pos位置开始的len个有效长度字符

void erase(size_t pos, int len = npos)


  • 意思很简单,就是从pos位置开始去删,删除len个有效长度的字符,那这几个字符就相当于是不要了,但是呢后面的字符串还是要的,所以有的同学就会想到用这个 拼接 的方法去完成
  • 但是呢没必要这样,这只会增加算法的复杂性,对于【erase】来说更多地还是去做一个 ==移位覆盖==

读者可以通过下面的算法分解图去思考一下代码该如何书写,我们是从【w】这个位置开始删除长度为3的有效字符

image.png

  • 但是呢,我们还要考虑到一些特殊的情况,例如说我们要取的长度len很大很大,甚至是最大的无符号整数npos,或者呢在pos + len之后的长度超出了当前_size的大小,此时我们可以直接对pos之后的字符去做一个截断的操作,让这个位置变成新的_size

image.png下面就是具体的代码展示,对于正常的情况而言,最后呢不要忘记了在覆盖字符后去改变一下这个_size的大小

// 删除从pos位置开始的len个有效长度字符
void erase(size_t pos, int len = npos)
{
  if (len == npos || pos + len > _size)
  {
    _size = pos;
    _str[_size] = '\0';
  }
  else
  {
    size_t end = pos + len;
    while (end <= _size)
    {
      _str[pos++] = _str[end++];
    }
    _size -= len;
  }
}
  • 首先呢我们从第五个位置开始,去删除长度为5的有效字符

image.png

  • 接下去呢我们再从pos == 2的位置开始,删除长度为30的字符,那这个就是pos + len > _size的情况

image.png

  • 那如果第二个参数不传递呢?那使用的便是缺省值【npos】,这就是len == npos的情况

image.png

swap

  • 对于【swap】函数我们在上面已经有讲解过了,此处不再过度赘述
void swap(string& s)
{
  std::swap(_str, s._str);
  std::swap(_size, s._size);
  std::swap(_capacity, s._capacity);
}

相关文章
|
1天前
|
算法 安全 Linux
【c++】STL简介(了解)
【c++】STL简介(了解)
【c++】STL简介(了解)
|
1天前
|
C++
【c++】模板---类模板
【c++】模板---类模板
|
1天前
|
Java C++ Python
【c++】理解类和对象
【c++】理解类和对象
【c++】理解类和对象
|
1天前
|
C++
【c++】日期类的实现-Class Date
【c++】日期类的实现-Class Date
【c++】日期类的实现-Class Date
|
1天前
|
存储 编译器 C语言
【c++】类对象模型
【c++】类对象模型
【c++】类对象模型
|
1天前
|
存储 C语言 C++
【c++】类和对象 - 类的访问限定符及封装/作用域和实例化
【c++】类和对象 - 类的访问限定符及封装/作用域和实例化
【c++】类和对象 - 类的访问限定符及封装/作用域和实例化
|
1天前
|
编译器 C语言 C++
【c++】类和对象 - 类的引入和定义
【c++】类和对象 - 类的引入和定义
【c++】类和对象 - 类的引入和定义
|
2天前
|
存储 前端开发 C++
【C++入门到精通】C++入门 —— deque(STL)
在C++中,deque(双端队列)是一种容器。deque是缩写形式,表示"double-ended queue",即双向队列。deque是C++标准库提供的一种方便、**高效的双向队列容器,提供了在两端进行插入和删除操作的能力,同时支持随机访问**
17 2
|
2天前
|
存储 C++
C++类与对象【多态】
C++类与对象【多态】
|
2天前
|
存储 编译器 C++
C++类与对象【继承】
C++类与对象【继承】