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

简介: 【C++/STL】:string类底层的模拟实现

引言

点击跳转到文章【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 插入字符串时strcatstrcpy均可以实现。但是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;
}
目录
相关文章
|
6天前
|
设计模式 安全 编译器
【C++11】特殊类设计
【C++11】特殊类设计
25 10
|
11天前
|
C++
C++友元函数和友元类的使用
C++中的友元(friend)是一种机制,允许类或函数访问其他类的私有成员,以实现数据共享或特殊功能。友元分为两类:类友元和函数友元。类友元允许一个类访问另一个类的私有数据,而函数友元是非成员函数,可以直接访问类的私有成员。虽然提供了便利,但友元破坏了封装性,应谨慎使用。
41 9
|
6天前
|
存储 编译器 C语言
【C++基础 】类和对象(上)
【C++基础 】类和对象(上)
|
6天前
|
设计模式 算法 Java
【c++】STL之stack和queue详解
【c++】STL之stack和queue详解
8 1
|
14天前
|
C语言 C++
【C++】string模拟实现(下)
本文档介绍了自定义`string`类的一些关键功能实现,包括`reserve()`用于内存管理,`push_back()`和`append()`添加字符或字符串,运算符`+=`的重载,以及`insert()`, `erase()`进行插入和删除操作。此外,还涵盖了`find()`查找函数,字符串的比较运算符重载,`substr()`获取子串,`clear()`清除内容,以及流插入和提取操作。常量`npos`用于表示未找到的标记。文档以代码示例和运行结果展示各功能的使用。
|
14天前
|
编译器 程序员 C语言
【C++】string模拟实现
这篇博客探讨了自定义实现C++ `string` 类的关键功能,包括构造、拷贝构造、赋值运算符重载及析构函数。作者强调了理解并实现这些功能对于面试的重要性。博客介绍了`string` 类的头文件`string.h`,其中定义了迭代器、基本成员函数如`swap()`、`size()`、`c_str()`等,并提到了深拷贝概念。此外,还展示了构造函数、析构函数和赋值运算符的实现,以及迭代器的定义与使用。博客还包括对C语言字符串函数的引用,以辅助读者理解实现细节。
|
12天前
|
存储 算法 C++
【C++高阶】探索STL的瑰宝 map与set:高效数据结构的奥秘与技巧
【C++高阶】探索STL的瑰宝 map与set:高效数据结构的奥秘与技巧
19 0
|
14天前
|
C++
【C++】string类的使用④(常量成员Member constants)
C++ `std::string` 的 `find_first_of`, `find_last_of`, `find_first_not_of`, `find_last_not_of` 函数分别用于从不同方向查找目标字符或子串。它们都返回匹配位置,未找到则返回 `npos`。`substr` 用于提取子字符串,`compare` 则提供更灵活的字符串比较。`npos` 是一个表示最大值的常量,用于标记未找到匹配的情况。示例代码展示了这些函数的实际应用,如替换元音、分割路径、查找非字母字符等。
|
24天前
|
Java UED
Java中String强转int:一种常见的错误和解决方法
在Java中将非数字字符串转换为整数会导致`NumberFormatException`。要解决这个问题,可以使用`try-catch`捕获异常,正则表达式验证数字格式,或利用异常信息提供错误提示。例如,`Integer.parseInt()`会因遇到非数字字符如`&quot;123abc&quot;`而抛出异常,但通过异常处理或正则`\\d+`可确保安全转换。记得在编程时避免直接强转,以防止程序异常中断。
|
15天前
|
安全 Java
Java基础之StringBuffer
【7月更文挑战第1天】 Java中的`StringBuffer`是线程安全的字符串操作类,适合多线程环境,而`StringBuilder`非线程安全,速度更快,适用于单线程。两者提供`append()`、`insert()`、`delete()`等方法修改字符串,避免了频繁创建新对象的性能问题。在不需要线程安全时,推荐使用`StringBuilder`以提高效率。
14 1