【C++/STL】：string类底层的模拟实现-阿里云开发者社区

引言

上一篇文章已经对string类进行了简单的介绍，大家只要能够正常使用即可。

这篇文章主要是对string类的一些重点接口函数进行模拟实现。本文依然采用多文件的方式，string.h放类的声明，string.cpp放成员函数的定义。

string.h

#pragma once
#include <iostream>
#include <assert.h>
#include <stdbool.h>
using namespace std;
//定义一个叫做bit的命名空间，隔离C++库里的string类
 namespace bit
{
   class string
   {
   public:
     //typedef实现二次封装
     //由于string类是连续的空间，所以可以定义为原生指针
     typedef char* iterator;
     //const迭代器，指针指向的内容不能修改
     typedef const char* const_iterator;
     //实现迭代器,一定要实现为begin 和end
     //迭代器屏蔽了底层细节，提供了一种简单通用的访问容器的方式
     iterator begin();
     iterator end();
     const_iterator begin()const;
     const_iterator end()const;
    // string();//无参构造
    
      //有参与无参构造用全缺省进行合并,在声明处给缺省值
     string(const char* str = "");//传参构造
     //析构函数
     ~string();
     //拷贝构造
     string(const string& s);
     //赋值运算重载(传统)
     //string& operator=(const string& s);
     //赋值运算重载(现代)
     string& operator=(string tmp);
     const char* c_str() const;
     //用下标的方式遍历字符串
     size_t size()const;
     char& operator[](size_t pos);
     const char& operator[](size_t pos)const;
     //用于扩容，一般不缩容
     void reserve(size_t n);
     void push_back(char ch);//尾插一个字符
     void append(const char* str);//尾插字符串
     //用运算符重载实现尾插
     string& operator+=(char ch);
     string& operator+=(const char* str);
     //在指定位置插入 字符或是字符串
     void insert(size_t pos, char ch);
     void insert(size_t pos, const char* str);
     //在指定位置删除长度为len
     void erase(size_t pos = 0, size_t len = npos);
     //从pos位置开始找字符或是字符串
     size_t find(char ch, size_t pos =0);
     size_t find(const char* str, size_t pos = 0);
     //交换函数
     void swap(string& s);
     //从pos位置找一个子串
     string substr(size_t pos = 0, size_t len = npos);
     //字符串的比较
     bool operator<(const string& s)const;
     bool operator>(const string& s)const;
     bool operator<=(const string& s)const;
     bool operator>=(const string& s)const;
     bool operator==(const string& s)const;
     bool operator!=(const string& s)const;
     //把当前数据清除，但是不清空间
     void clear();
   private:
     //这里的缺省值时给现代写法的构造函数的
     char* _str = nullptr;
     size_t _size = 0;//有效数据个数,指向最后一个有效数据的下一个位置\0
     size_t _capacity = 0;//容量
     //特例：静态成员变量只有无符号整形才可以在声明时给缺省值
     //const static size_t npos = -1;//ok
     //const static double d = 2.2;//err
     const static size_t npos;
   };
   //流插入，流提取 
   //不适合写成成员函数，涉及第一个参数的位置问题
   istream& operator>> (istream& is, string& str);
   ostream& operator<< (ostream& os, const string& str);
}

1，构造函数

为了避免多次strlen的计算，并且符合声明的顺序，只把_size放在初始化列表，其余放在函数体中。

string::string(const char* str)
  :_size(strlen(str))
{
    //_str = nullptr;//err 防止对空指针的解引用
    
  _str = new char[_size + 1];//多开一个是给\0的
  _capacity = _size;
  strcpy(_str, str);//把初始化内容拷贝进空间
}

2，析构函数

string::~string()
{
  delete[] _str;//析构销毁资源
  _str = nullptr;//置空
  _size = _capacity = 0;//置0
}

3，取出字符串的地址

const char* string::c_str()const
{
  return _str;//返回字符串的首地址，用于打印数据
}

4，计算有效数据个数

size_t string::size()const
{
  return _size;
}

5，[ ]运算符重载

4.1 [ ]运算符重载有两种类型，可读可写的和可读的(const修饰)。

4.2 模拟[ ]运算符重载的几个问题：

(1) 引用返回的作用：一是减少拷贝，二是修改返回对象。

(2) 为什么可以用引用返回：_str[i]出了作用域还在，因为_str开辟在堆上，它返回的是堆上的一个字符的引用别名。

(3) 重载的底层也是用assert断言的，只要下标越界直接终止报错。

//_str是new出来的，出了这个函数不会销毁，可以用引用返回
char& string::operator[](size_t pos)
{
  assert(pos < _size);//防止越界
  return _str[pos];
}
const char& string::operator[](size_t pos)const
{
  assert(pos < _size);//防止越界
  return _str[pos];
}

6，简单迭代器

6.1 迭代器也有有两种类型，可读可写的和可读的(const修饰)。根据声明可知，这里的迭代器可以暂时简单的理解为类似指针的东西。

6.2 这里直接利用用原生指针进行实现的原因是：string类底层的物理结构的连续的。

6.3 为什么要用typedef，而不是直接用char*呢？

一是不同编译器底层实现迭代器的方式是不同的。

二是可以实现二次封装，屏蔽了底层的实现细节，统一了上层访问容器的方式(用begin和end)。

string::iterator string::begin()
{
  return _str;
}
string::iterator string::end()
{
  return _str + _size;
}
string::const_iterator string::begin()const
{
  return _str;
}
string::const_iterator string::end()const
{
  return _str + _size;
}

7，预开空间(扩容)

void string::reserve(size_t n)
{
  if (n > _capacity)
  {
    //手动扩容，手动释放
    char* tmp = new char[n + 1];//多开一个给\0
    strcpy(tmp, _str);
    delete[] _str;
    _str = tmp;
    _capacity = n;
  }
}

8，尾插一个字符

8.1 先判断容量是否足够，再插入。

8.2 注意\0的处理。

//尾插一个字符
void string::push_back(char ch)
{
  if (_size == _capacity)
  {
    //先计算容量，2倍增
    size_t newcapacity = _capacity == 0 ? 4 : _capacity * 2;
    //再扩容
    reserve(newcapacity);
  }
  _str[_size] = ch;//覆盖\0的位置
  _str[_size + 1] = '\0';//补上\0
  ++_size;
}

9，尾插一个字符串

9.1 先判断容量是否足够，再插入。

9.2 插入字符串时strcat 和strcpy均可以实现。但是strcat的底层需要遍历找到\0再进行拼接，最后自动补上\0，效率不高；所以推荐使用strcpy。

//尾插字符串
void string::append(const char* str)
{
  size_t len = strlen(str);
  if (_size + len > _capacity)
  {
    reserve(_size + len);
  }
  //strcat:从\0的位置开始追加，最后自动补上\0
  //strcat(_str, str);
  strcpy(_str + _size, str);
  _size += len;
}

10，+=运算符重载

它的功能也是用来尾插字符或是字符串的，而且它比push_back和append使用的更广泛。

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

11，在pos位置插入字符/字符串

11.1 在pos位置插入字符

错误示范：

原因：当pos为0，即头插时，程序崩溃！因为end是无符号整形，减到0再减后会变成整形最大值(40多亿)，造成死循环。

猜想解决方法：

只把end的类型改为int，也不行。因为当一个操作符两边的操作数类型不一样时，会产生隐式类型转换，比如有符号与无符号，有符号会隐式转换成无符号类型。

void string::insert(size_t pos, char ch)
{
  assert(pos <= _size);//避免下标越界
  if (_size == _capacity)
  {
    size_t newcapacity = _capacity == 0 ? 4 : _capacity * 2;
    reserve(newcapacity);
  }
  size_t end = _size;
  while (end >= pos)
  {
    _str[end + 1] = _str[end];
    --end;
  }
  _str[pos] = ch;
  ++_size;
}

解决方法1：
把end的类型改为int，end指向最后一位有效位的下一位，把pos也强转为int类型。

//在指定位置插入 
void string::insert(size_t pos, char ch)
{
  assert(pos <= _size);//避免下标越界
  if (_size == _capacity)
  {
    size_t newcapacity = _capacity == 0 ? 4 : _capacity * 2;
    reserve(newcapacity);
  }
  int end = _size;
  while (end >= (int)pos)
  {
    _str[end + 1] = _str[end];
    --end;
  }
  _str[pos] = ch;
  ++_size;
}

解决方法2：
让end指向\0的下一位。

//在指定位置插入 
void string::insert(size_t pos, char ch)
{
  assert(pos <= _size);//避免下标越界
  if (_size == _capacity)
  {
    size_t newcapacity = _capacity == 0 ? 4 : _capacity * 2;
    reserve(newcapacity);
  }
  size_t end = _size + 1;
  while (end > pos)
  {
    _str[end] = _str[end - 1];
    --end;
  }
  _str[pos] = ch;
  ++_size;
}

11.2 尾插一个字符串

遇到的问题与上面的相同。

void string::insert(size_t pos, const char* str)
{
  assert(pos <= _size);//避免下标越界
  size_t len = strlen(str);
  if (_size + len > _capacity)
  {
    reserve(_size + len);
  }
  
  //方式1
  /*int end = _size;
  while (end >= (int)pos)
  {
    _str[end + len] = _str[end];
    end--;
  }*/
  
  //方式2
  size_t end = _size + len;
  while (end > pos+len-1)
  {
    _str[end] = _str[end - 1];
    end--;
  }
  memcpy(_str + pos, str, len);
  _size += len;
}

12，从pos位置开始删除长度为len的字符串

注意：

1.此处在声明中两个形参的缺省值，size_t pos = 0， size_t len = npos。

npos是const类型的静态成员变量，npos = -1，表示无符号整形的最大值(40多亿)。

2.声明和定义分离时，静态成员变量的初始化。当是const修饰的size_t类型的静态变量时，是可以在声明时给缺省值的！这是个特例！ 但是一般不这样，声明和定义分离时，只要在.cpp中初始化即可。

void string::erase(size_t pos, size_t len )
{
  assert(pos  < _size);
  
  //当len大于前面的字符个数时，有多少删多少
  if (pos+len >= _size)
  {
    _str[pos] = '\0';
    _size = pos;
  }
  else
  {
    strcpy(_str + pos, _str + pos + len);
    _size -= len;
  }
}

13，从pos位置开始查找字符/字符串

13.1 查找字符

size_t string::find(char ch, size_t pos)
{
  for (size_t i = pos; i < _size; i++)
  {
    if (_str[i] == ch)
    {
      return i;
    }
  }
  return npos;
}

13.2 查找字符串

size_t string::find(const char* str, size_t pos)
{
  //strstr：str存在时返回所在位置的指针
  const char* p = strstr(_str + pos, str);
  
  return p - _str;
}

14，拷贝构造(传统)

当我们不显示实现深拷贝时，使用编译器默认的浅拷贝有两个危害：

14.1 s1和s2指向同一块空间，出了作用域时调用两次析构函数，造成程序崩溃。

14.2 修改一个，另外一个也会修改。

//要用深拷贝进行拷贝构造
//s2(s1);把s1拷贝给s2,*this是s2,s是s1的别名
string::string(const string& s)
{
  //开一个和要拷贝的一样大小的空间
  _str = new char[s._capacity + 1];
  strcpy(_str, s._str);//把数据拷贝进新空间
  _size = s._size;
  _capacity = s._capacity;
}

15，=赋值拷贝(传统)

开新空间，拷贝数据，释放原空间，改变指针指向。

//s1 = s3;//s1是*this,s是s3的别名
string& string::operator=(const string& s)
{
  //避免自己给自己赋值
  if (this != &s)
  {
       //多开一个空间给\0
    char* tmp = new char[s._capacity + 1];
    strcpy(tmp, s._str);
    delete[] _str;
    _str = tmp;
    _size = s._size;
    _capacity = s._capacity;
    return *this;
  }
}

16，交换函数swap

//s1.swap(s3)
void string::swap(string& s)
{
  //调用库中的swap函数，交换内置类型
  //不直接交换数据，而是交换两块空间的指针
  std::swap(_str, s._str);
  std::swap(_size, s._size);
  std::swap(_capacity, s._capacity);
}

17，从pos位置开始取len个字符的串

复用了前面的构造函数和+=运算符。

string string::substr(size_t pos, size_t len)
{
  //len大于pos后面剩余的字符，有多少取多少
  if (len > _size - pos)
  {
    string sub(_str + pos);//直接构造子串返回
    return sub;
  }
  else
  {
    string sub;
    sub.reserve(len);
    for (size_t i = 0; i < len; i++)
    {
      sub += _str[pos + i];
    }
    return sub;
  }
}

18. 字符串的比较

只要实现>运算符(或<运算符)和==运算符，其他运算符直接复用即可。

bool string::operator<(const string& s)const
  {
    return strcmp(_str, s._str) < 0;
  }
  bool string::operator>(const string& s)const
  {
    return !(*this <= s);
  }
  bool string::operator<=(const string& s)const
  {
    return *this < s || *this == s;
  }
  bool string::operator>=(const string& s)const
  {
    return !(*this < s);
  }
  bool string::operator==(const string& s)const
  {
    return strcmp(_str, s._str) == 0;
  }
  bool string::operator!=(const string& s)const
  {
    return !(*this == s);
  }

19，清除函数clear

清除当前对象里的内容，影响的是_size，不影响_capacity。

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

20，流插入，流提取

(1) 不适合写成成员函数，涉及第一个参数的位置问题。

(2) 根据声明可知，这两个函数并没有重载成友元函数，而是放在类外。

(3) 在日期类中写成友元是为了访问私有成员，这里可以不写成友元函数，不访问私有成员，直接访问公有成员。

20.1 流插入

ostream& operator<< (ostream& os, const string& str)
{
  for (size_t i = 0; i < str.size(); i++)
  {
    os << str[i];
  }
  return os;
}

20.2 流提取

注意：

(1) C语言中的scanf：%c时可以拿到空格，拿不到换行，遇到换行直接忽略； %s时两个都拿不到，遇到直接忽略。

C++中的cin:拿不到空格和换行，遇到直接忽略。

在C++中不能用scanf，因为C++的流和C语言的流缓冲区不同。

(2) 为了避免一次性输入够多导致频繁扩容，开辟一个局部数组buff(类似缓冲区)，先把字符存在buff中，到达一定数量后再存入str。

istream& operator>> (istream& is, string& str)
{
  str.clear();
  char buff[128];
  int i = 0;
  char ch = is.get();
  
  while (ch != ' ' && ch != '\n')
  {
    buff[i++] = ch;
    //0 - 126
    if (i == 127)
    {
      buff[i] = '\0';
      str += buff;
      i = 0;
    }
    ch = is.get();
  }
  //如果buff没有装满
  if (i != 0)
  {
    buff[i] = '\0'; 
    str += buff;
  }
  return is;
}

21，拷贝构造和赋值拷贝的现代写法(重点)

21.1 拷贝构造

复用构造函数，构造一个tmp，再用tmp对象和this交换。此时如果不在声明时给缺省值，刚开始s2是随机值，tmp和s2交换后，tmp就是随机值，tmp出了函数会调用析构函数，此时程序可能会崩溃，所以好给缺省值。

string::string(const string& s)
{
  //写法1：常用
  string tmp(s._str);
  swap(tmp);
  //写法2：
  //string tmp(s._str);
  //std::swap(_str, tmp._str);
  //std::swap(_size, tmp._size);
  //std::swap(_capacity, tmp._capacity);
}

21.2 赋值拷贝

写法1：

string& string::operator=(const string& s)
{
  //避免自己给自己赋值
  if (this != &s)
  {
    string tmp(s._str);
    swap(tmp);
  }
  return *this;
}

写法2：常用

这里使用传值传参：

(1) 传值传参会进行拷贝构造，s1会拷贝一份给临时变量tmp，tmp里的东西就是s3想要的，再让tmp与s3交换；

(2) 当tmp 的生命周期结束时，刚好又会调用析构函数，把原来s3中的东西清理掉。

//s3 = s1   
//这里的传参不能用引用，
string& string::operator=(string tmp)
{
  swap(tmp);//一行搞定赋值拷贝
  return *this;
}

【C++/STL】：string类底层的模拟实现

引言

1，构造函数

2，析构函数

3，取出字符串的地址

4，计算有效数据个数

5，[ ]运算符重载

6，简单迭代器

7，预开空间(扩容)

8，尾插一个字符

9，尾插一个字符串

10，+=运算符重载

11，在pos位置插入字符/字符串

11.1 在pos位置插入字符

11.2 尾插一个字符串

12，从pos位置开始删除长度为len的字符串

13，从pos位置开始查找字符/字符串

13.1 查找字符

13.2 查找字符串

14，拷贝构造(传统)

15，=赋值拷贝(传统)

16，交换函数swap

17，从pos位置开始取len个字符的串

18. 字符串的比较

19，清除函数clear

20，流插入，流提取

20.1 流插入

20.2 流提取

21，拷贝构造和赋值拷贝的现代写法(重点)

21.1 拷贝构造

21.2 赋值拷贝

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【C++/STL】：string类底层的模拟实现

引言

1，构造函数

2，析构函数

3，取出字符串的地址

4，计算有效数据个数

5，[ ]运算符重载

6，简单迭代器

7，预开空间(扩容)

8，尾插一个字符

9，尾插一个字符串

10，+=运算符重载

11，在pos位置插入字符/字符串

11.1 在pos位置插入字符

11.2 尾插一个字符串

12，从pos位置开始删除长度为len的字符串

13，从pos位置开始查找字符/字符串

13.1 查找字符

13.2 查找字符串

14，拷贝构造(传统)

15，=赋值拷贝(传统)

16，交换函数swap

17，从pos位置开始取len个字符的串

18. 字符串的比较

19，清除函数clear

20，流插入，流提取

20.1 流插入

20.2 流提取

21，拷贝构造和赋值拷贝的现代写法(重点)

21.1 拷贝构造

21.2 赋值拷贝

热门文章

最新文章

相关课程

相关电子书

相关实验场景