【C++练级之路】【Lv.6】【STL】string类的模拟实现-阿里云开发者社区

【C++练级之路】【Lv.6】【STL】string类的模拟实现

2024-03-27 98

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【C++练级之路】【Lv.6】【STL】string类的模拟实现

引言

关于STL容器的学习，我会采用模拟实现的方式，以此来更加清楚地了解其底层原理和整体架构。而string类更是有100多个接口函数，所以模拟实现的时候只会调重点和常见的函数进行实现，以此加强对重点函数的掌握。

一、成员变量

string类中包含了

_str（指向动态开辟的字符数组）
_size（当前有效数据个数）
_capacity（最大有效容量）

同时，还包含了一个static修饰的静态成员变量npos，赋值为-1，因其类型为无符号整型，则表示最大值。

class string
{
private:
  char* _str;
  size_t _size;
  size_t _capacity;
  static size_t npos;
};

size_t string::npos = -1;

标准的静态成员变量，是在类内声明，类外定义。但是，这里设计出了一种奇怪的语法，加上const修饰，就可以在类内声明加定义。

static const size_t npos = -1;

二、默认成员函数

2.1 constructor

细节：

因为计算_size和_capacity都要调用strlen函数，为了防止频繁调用，在初始化列表中调用一次将_size初始化，后续再把_size赋值给_capacity
_capacity初始化时，防止后续二倍扩容时_capacity为0，则加上判断，如果_size为0，初始_capacity为3
开辟空间的大小为_capacity + 1，因为要留一个空间给\0
缺省参数为空串

string(const char* str = "")
  :_size(strlen(str))
{
  _capacity = _size == 0 ? 3 : _size;
  _str = new char[_capacity + 1];
  strcpy(_str, str);
}

2.2 copy constructor

string(const string& s)
  :_size(s._size)
  , _capacity(s._capacity)
{
  _str = new char[_capacity + 1];
  strcpy(_str, s._str);
}

2.3 destructor

~string()
{
  delete[] _str;
  _str = nullptr;
  _size = _capacity = 0;
}

2.4 operator=

细节：

先开辟一段新空间，再释放旧空间，防止空间不足（一般空间相等的很少，所以大多数情况下不相等，直接开辟新空间）
原地赋值则什么都不做，否则释放了旧空间，就没办法拷贝字符串

string& operator=(const string& s)
{
  if (this != &s)
  {
    char* tmp = new char[s._capacity + 1];
    delete[] _str;
    _str = tmp;
    strcpy(_str, s._str);
    _size = s._size;
    _capacity = s._capacity;
  }

  return *this;
}

三、迭代器

3.1 begin

迭代器的实现和编译器有关，不同的编译器有不同的实现方式。这里简单的用指针来实现迭代器。

同时，重载了普通迭代器和const迭代器。

typedef char* iterator;
typedef const char* const_iterator;

iterator begin()
{
  return _str;
}

const_iterator begin() const
{
  return _str;
}

3.2 end

迭代器遵循左闭右开的原则，begin指向首元素，end指向末元素的下一位。

typedef char* iterator;
typedef const char* const_iterator;

iterator end()
{
  return _str + _size;
}

const_iterator end() const
{
  return _str + _size;
}

悄悄告诉你：范围for的底层实现，就是运用了迭代器。

四、元素访问

4.1 operator[ ]

为了方便的访问元素，我们重载了[ ]运算符。同时，也分为普通版本和const版本，对应不同string类的权限。

char& operator[](size_t pos)
{
  assert(pos < _size);
  return _str[pos];
}

const char& operator[](size_t pos) const
{
  assert(pos < _size);
  return _str[pos];
}

五、容量

5.1 size

获取当前有效数据个数

细节：const修饰，保证普通和const类型string类都能访问

size_t size() const
{
  return _size;
}

5.2 capacity

获取当前最大有效容量

细节：同上

size_t capacity() const
{
  return _capacity;
}

5.3 reserve

改变当前_capacity（将其变为指定大小n）

细节：

只扩容，不缩容（因为缩容也是有代价的）
异地扩容，新开辟一个新空间，将内容拷贝过去，再释放旧空间（事实上，原地扩容只占极少数，绝大部分扩容都是异地扩容）

void reserve(size_t n)
{
  if (n > _capacity)
  {
    char* tmp = new char[n + 1];
    strcpy(tmp, _str);
    delete[] _str;
    _str = tmp;
    _capacity = n;
  }
}

5.4 resize

改变当前_size（将其变为指定大小n），分为三种情况：

n <= _size，在_size位置写入\0
_size < n <= _capacity，填充指定字符ch直到_size为n，再重复步骤1
n > _capacity，先扩容，再重复步骤2

void resize(size_t n, char ch = '\0')
{
  if(n > _size)
  {
    reserve(n);
    memset(_str + _size, ch, n - _size);
  }
  _size = n;
  _str[_size] = '\0';
}

六、修改

6.1 push_back

尾插一个字符

细节：

如果空间不够，则二倍扩容
插入字符后，在尾部添加\0

void push_back(char ch)
{
  if (_size + 1 > _capacity)
  {
    reserve(_capacity * 2);
  }

  _str[_size] = ch;
  ++_size;
  _str[_size] = '\0';
}

6.2 append

尾插（追加）一个字符串

细节：

如果空间不够，扩容到刚好可以容纳的空间（因为二倍扩容有可能也不够）
strcpy会自动把\0也拷贝过去

void append(const char* str)
{
  size_t len = strlen(str);
  if (_size + len > _capacity)
  {
    reserve(_size + len);
  }

  strcpy(_str + _size, str);
  _size += len;
}

悄悄说一句：其实这个函数写成push_back的重载函数更好哦~

6.3 operator+=

为了更加方便地使用尾插，我们重载了+=运算符，这样无论尾插字符或者字符串都极为方便。

string& operator+=(char ch)
{
  push_back(ch);
  return *this;
}

string& operator+=(const char* str)
{
  append(str);
  return *this;
}

6.4 insert

在指定位置插入一个字符

细节：

如果空间不够，二倍扩容
从pos位置开始，字符都后移一格（这里end = _size + 1 就是为了避免end == pos的判断，因为头插时pos为0，而end为无符号整数恒大于等于0，所以会导致死循环）
在pos位置插入指定字符

string& insert(size_t pos, char ch)
{
  assert(pos <= _size);

  if (_size + 1 > _capacity)
  {
    reserve(_capacity * 2);
  }

  size_t end = _size + 1;
  while (end > pos)
  {
    _str[end] = _str[end - 1];
    --end;
  }

  _str[pos] = ch;
  ++_size;

  return *this;
}

其实，步骤2的字符后移，可以使用memmove函数（专门处理重叠空间的移动）

memmove(_str + pos + 1, _str + pos, _size + 1 - pos);

在指定位置插入一个字符串

细节：

如果空间不够，扩容到刚好可以容纳的空间
从pos位置开始，字符都后移 len 格（这里len为1的时候，其实就是上一种情况）
在pos位置用strncpy插入指定字符串（不带\0)

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 + 1;
  while (end > pos)
  {
    _str[end + len - 1] = _str[end - 1];
    --end;
  }

  strncpy(_str + pos, str, len);
  _size += len;

  return *this;
}

同样，步骤2的字符后移 len 格，也可以使用memmove函数。

memmove(_str + pos + len, _str + pos, _size + 1 - pos);

那么，完成了指定位置的插入，我们就可以复用代码，让push_back和append复用insert函数。

void push_back(char ch)
{
  insert(_size, ch);
}

void append(const char* str)
{
  insert(_size, str);
}

6.5 erase

在指定位置删除指定长度的字符串

细节：

npos要单独判断（要不然npos加上pos会溢出）
len为npos，或者pos+len >= _size，代表将删除pos位置往后的所有字符串
如果pos+len < _size，则将后面未删除的字符串用strcpy拷贝到pos位置

string& erase(size_t pos, size_t len = npos)
{
  assert(pos < _size);

  if(len == npos || pos + len >= _size)
  {
    _size = pos;
    _str[_size] = '\0';
  }
  else
  {
    strcpy(_str + pos, _str + pos + len);
    _size -= len;
  }

  return *this;
}

6.6 swap

交换两个string类的值

细节：使用std库中的swap函数，交换各个成员变量的值

void swap(string& s)
{
  std::swap(_str, s._str);
  std::swap(_size, s._size);
  std::swap(_capacity, s._capacity);
}

6.7 clear

清空字符串

void clear()
{
  _str[0] = '\0';
  _size = 0;
}

七、操作

7.1 c_str

获取字符串

细节：const修饰，保证普通和const类型string类都能访问

const char* c_str() const
{
  return _str;
}

7.2 find

查找指定字符或者字符串，返回其下标

细节：

使用缺省参数pos = 0，可以从指定位置开始向后查找，如果未指定，则从头查找
查找字符串用strstr函数，找到返回指针，用指针-指针的方式得到下标

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);
  
  char* p = strstr(_str, str);
  if (p == nullptr)
  {
    return npos;
  }
  return p - _str;
}

八、非成员函数

8.1 relational operators

重载比较关系的运算符

细节：

一般实现了两个，剩下的都可以复用
this指针用const修饰，保证普通和const的string类都可以相互比较（正着比，反着比都可以）

bool operator==(const string& s) const
{
  return strcmp(_str, s._str) == 0;
}

bool operator!=(const string& s) const
{
  return !(*this == s);
}

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);
}

8.2 operator<<

重载流插入运算符

细节：遍历字符串，可以采用下标+[ ]的循环形式，也可以使用范围for

ostream& operator<<(ostream& out, const string& s)
{
  for (auto& ch : s)
  {
    out << ch;
  }
  return out;
}

8.3 operator>>

重载流提取运算符

细节：

每次流插入之前，先清理字符串，防止写入的内容连接在之前的内容后面
提取字符时使用get函数。因为>>运算符在缓冲区中提取字符时，会自动忽略空格和换行，而get函数可以全部提取出来。

istream& operator>>(istream& in, string& s)
{
  s.clear();

  char ch = in.get();
  while (ch != ' ' && ch != '\n')
  {
    s += ch;
    ch = in.get();
  }
  return in;
}

以上代码是能够完成功能的实现，但是从效率的角度考虑，还是不够高效。所以，我们可以优化一下：

创建一个小型字符数组buf
提取的字符先填充到buf
等buf填充满后，再将buf尾插到s
如果循环结束，buf中还有剩余字符，则再尾插到s

istream& operator>>(istream& in, string& s)
{
  s.clear();
  
  char ch = in.get();
  size_t i = 0;
  char buf[128] = { 0 };
  while (ch != ' ' && ch != '\n')
  {
    buf[i++] = ch;
    if(i == 127)
    {
      s += buf;
      i = 0;
    }
    ch = in.get();
  }

  if (i != 0)
  {
    s += buf;
  }
  return in;
}

总结

我们来模拟实现string类，不是为了造一个更好的轮子，而是熟练掌握重点函数的功能与应用，顺便巩固之前学习的C++语法。常言道，没学过STL，那你根本没学过C++！C++的梦幻之旅，才刚刚开始……

真诚点赞，手有余香

【C++练级之路】【Lv.6】【STL】string类的模拟实现

引言

一、成员变量

二、默认成员函数

2.1 constructor

2.2 copy constructor

2.3 destructor

2.4 operator=

三、迭代器

3.1 begin

3.2 end

四、元素访问

4.1 operator[ ]

五、容量

5.1 size

5.2 capacity

5.3 reserve

5.4 resize

六、修改

6.1 push_back

6.2 append

6.3 operator+=

6.4 insert

6.5 erase

6.6 swap

6.7 clear

七、操作

7.1 c_str

7.2 find

八、非成员函数

8.1 relational operators

8.2 operator<<

8.3 operator>>

总结

热门文章

最新文章

相关课程

相关电子书

探索云世界

热门

云计算

大数据

云原生

人工智能

数据库

开发与运维

活动广场

任务中心

训练营

直播

乘风者计划

下载

镜像站

技术资料

【C++练级之路】【Lv.6】【STL】string类的模拟实现

引言

一、成员变量

二、默认成员函数

2.1 constructor

2.2 copy constructor

2.3 destructor

2.4 operator=

三、迭代器

3.1 begin

3.2 end

四、元素访问

4.1 operator[ ]

五、容量

5.1 size

5.2 capacity

5.3 reserve

5.4 resize

六、修改

6.1 push_back

6.2 append

6.3 operator+=

6.4 insert

6.5 erase

6.6 swap

6.7 clear

七、操作

7.1 c_str

7.2 find

八、非成员函数

8.1 relational operators

8.2 operator<<

8.3 operator>>

总结

热门文章

最新文章

相关课程

相关电子书