库中是如何实现string类的?

简介: 库中是如何实现string类的?

前言

我们先认识一下string类的框架.

class string
   {
    public:
      //成员函数
    private:
        char* _str;                 //字符串指针 
        size_t _capacity;           //容量
        size_t _size;               //当前字符有效个数
   }:

650120adfaf7499db76cbd8614333dd1.png

框架图:

0c4ad68df5a4481eaddee818fdadb7f9.png

一、构造函数与析构函数

1b5ab897b48e4f95861014742babb1cd.png

(1) 无参构造:

我们可以试着看一下库里面是如何赋值的?

  std::string s1;
  cout << "s1= " << s1 << endl;

7bf2cc87a8fb42ee931ae8141885a62e.png

所以,对于无参构造,我们只需要将*str赋值为空串就行了.

注意:

""(中间没有空格)

(2) 使用常量字符串构造

1.先计算字符串的长度.

2.将长度值赋值给_size 和_capacity .

3.申请一块为_capacity+1大小的空间.(+1是为了存储'\0')

4.将字符串中的值按字节拷贝至string类中的_str.


代码实现:

//全缺省构造函数,,默认初始化为空字符
string(const char* str = "")//无参也是调用这个 
  {
      _size = strlen(str);
      _capacity = _size;
      _str = new char[_capacity + 1];//里面其实有一个字符'\0'
     // strcpy(_str, str);              //遇到'\0'结束拷贝,也会吧'\0'拷贝过去
      memcpy(_str, str, _size + 1);
  }

(3) 拷贝构造

这里注意实现深拷贝即可.

string(const string& s)       //注意这里+const  普通对象可以调用,const对象也可以调用
{
    _size = s._size;
    _capacity = s._capacity;
    _str = new char[_capacity + 1];//需要多一个字节存放,字符'\0'
    memcpy(_str,s._str,s._size+1);      
}

(4) 析构函数

析构函数注意释放动态申请的空间即可.

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

二、capacity相关操作

(1) reserve函数

reserve():请求改变容量的大小,类似于扩容从操作.

  1. 向堆区申请一块n+1大小的新空间.
  2. 将旧空间的数据拷贝到新空间,
  3. 释放旧空间
  4. _str指向新空间
  5. 更新容量capacity
void reserve(size_t n)
{
    if (n > _capacity)
    {
    //申请一块新空间
        char* tmp = new char[n + 1];
        memcpy(tmp, _str, _size + 1);//不建议使用strcpy,可能存在中间有'\0'的强开
        delete[] _str;//释放旧空间
        _str = tmp;
        _capacity = n;
    }
}

(2) resize函数

resize():用于改变字符串的有效字符长度.不够的地方用第二个参数填充.

2df6bab542bf407ba67a6b7f08971d64.png

步骤:

  1. 如果n<size(即n<当前长度):
    ①直接在n位置处赋值为’\0’.
    ②_size更新为n
  2. 如果n>=size:
    ①调用扩容函数,扩容至n大小.
    ②超出部分用字符'c'填充
    ③更新_size,并在最后一个位置设置为’\0’


代码实现:

  void resize(size_t n, char c = '\0')
  {
      if (n < _size)
      {
          _str[n] = '\0';
          _size = n;
      }
      else
      {
          reserve(n);//无论需不要扩容,不需要扩容时reserve内部会什么也不做,需要扩容时,reserve会扩容.
          memset(_str + _size, c, n - _size);
          _size = n;
          _str[_size] = '\0';
      }
  }

(3) empty函数

如果_size值为0,则为空,返回true.

否则返回false;

  bool empty()const
   {
       //size=0则为空,返回true
       return _size == 0 ? true : false;
   }

(4) size和capacity函数

这两个函数,直接返回值即可.

  size_t size()const
  {
    return _size;
  }
     size_t capacity()const
     {
         return _capacity;
     }

三、访问与遍历

(1) 迭代器

迭代器的介绍

C++迭代器是一个用于遍历容器(如vector、list、set等)中的元素的对象。迭代器的作用类似于指针,可以通过解引用操作符(*)获取容器中的元素值,也可以通过自增操作符(++)移动迭代器指向下一个元素。迭代器可以访问容器中的元素,也可以修改容器中的元素值。

da8b1f3a779f480d93ca18a71eac86f2.png

注意迭代器的定义,迭代器是左闭右开的区间.

public:
    typedef char* iterator;
    typedef const char* const_iterator;
    //普通迭代器
    iterator begin()
    {
        return _str;             //返回第一个字符位置
    }
    iterator end()
    {
        return _str + _size;     //返回最后一个有效字符的下一个位置
    }
  //常类迭代器
    const const_iterator begin()const
    {
        return _str;             //返回第一个字符位置
    }
    const const_iterator end()const
    {
        return _str + _size;     //返回最后一个有效字符的下一个位置
    }

(2)下标访问符 方括号[ ]重载

返回_str中第index的位置

 char& operator[](size_t index)
 {
  //判断位置是否合法
     assert(index >= 0 && index < _size);
     return *(_str + index);
 }
 const char& operator[](size_t index)const
 {
     assert(index >= 0 && index < _size);
     return *(_str + index);
 }

四、修改与查找

(1) push_back函数

push_back尾部插入一个字符

在进行插入操作之前,要先考虑扩容的情况.

需要注意的是,如果采用无参构造,刚开始容量是0.

这就导致是初次扩容,容量开始是0,所以这里要判断扩容前,容量是否是0,再考虑1.5倍或者二倍扩容.

void push_back(char c)
{
    if (_size + 1 > _capacity)
    {
      //如果capacity是0,则无法进行1.5倍扩容
        //reserve(_capacity * 1.5);
        reserve(_capacity == 0 ? 4 : _capacity * 1.5);//扩容多少没有标准,2倍或者1.5倍扩容都可,
    }
    _str[_size] = c;
    _size++;        //有效数据+1
    _str[_size] = '\0';
}

(2) append函数

append尾部追加字符串

 void append(const char* str)
 {
     int sz=strlen(str);
     //如果容量不够,就申请新空间
     if (_size + sz > _capacity)
     {
         reserve(_capacity +sz);
     }
     //追加新的字符串
     memcpy(_str + _size, str, sz);
     _size += sz;
     _str[_size] = '\0';
 }

(3) find函数

在string中查找目标字符,通过遍历比较.

第二个参数表示从pos位置开始查找.


顺序查找即可

size_t find(char c, size_t pos = 0) const
{
    assert(pos < _size);
    for (int i = pos; i < _size; i++)
    {
        if (_str[i] == c)
        {
            return i;
        }
    }
    return npos;
}

字符串匹配:查找string类的中的目标字串


字符串匹配算法,这里简化,直接调用库函数strstr,就不手撕算法了.

 // 返回子串s在string中第一次出现的位置
 size_t find(const char* s, size_t pos = 0) const
 {
     assert(pos < _size);
     const char* ptr = strstr(_str + pos, s);//通过调用库函数strstr找到字符串出现的位置的指针
     if (ptr)
     {
         return ptr - _str;
     }
     else
     {
         return npos;
     }
 }

(4) insert函数

在pos位置插入一个字符:

老规矩,先扩容,学过数据结构的小伙伴应该知道,需要先移动数据再进行插入数据操作.


顺序表任意位置插入

// 在pos位置上插入字符c/字符串str,并返回该字符的位置
string& insert(size_t pos, char c)
{
    assert(pos >= 0 && pos<= _size);
    if (_size + 1 > _capacity)
    {
        reserve(_capacity * 1.5);
    }
    int i = 0;
    //移动数据
    for (i = _size; i > pos - 1; i--)
    {
        _str[i] = _str[i - 1];
    }
    _str[pos - 1] = c;
    _size++;
    return *this;
}

在pos位置插入一段字符串:


这里在移动数据时,注意0号位置插入时移动.

如果我们只是将前面的数据直接往后移动字符串长度大小的位置,则到插入0号位置时,前面的数据是非法的,此处设计时,需要注意.

string& insert(size_t pos, const char* str)
{
    assert(pos >= 0 && pos <= _size);
    int sz = strlen(str);
    //如果容量不够,就申请新空间
    if (_size + sz > _capacity)
    {
        reserve(_capacity + sz);
    }
    int i = 0;
    //移动数据,这里需要注意0号位置插入时是否移动数据非法.
    size_t end = _size;
    while (end >= pos && end != npos)
    {
        _str[end + sz] = _str[end];
        --end;
    }
    //插入字符串
    for (i = pos; i <pos+sz; i++)
    {
        _str[i] = str[i-pos];
    }
    _size+=sz;
    return *this;
}

(5) erase函数

erase:删除从pos位置开始往后len长度的元素,并返回删除后的string.

31d1757e4dbd403bae2283ccc0ef6666.png

af5e9cad20654993a60fff7b0fdf493e.png

 // 删除pos位置上的元素,并返回该元素的下一个位置
 string& erase(size_t pos, size_t len=npos)
 {
     assert(pos <= _size);
     if (len == npos || pos + len >= _size)//如果要求删除的长度+pos超过了string中有效字符的长度
     {
         _size = pos;
         _str[_size] = '\0';
     }
     else
     {
         size_t end = pos + len;
         while (end <= _size)
         {
             _str[pos++] = _str[end++];
         }
         _size -= len;
     }
     return *this;
 }

五、运算符重载

(1) 流运算符重载

采用友元函数的方式,实现流提取与流插入运算符重载.

流插入运算符

 ostream& operator<<(ostream& _cout, const cjn::string& s)//记得包在cjn命名空间里面
 {
     //在实现了迭代器的情况下,可以使用范围for
     for (auto& in : s)      //依次取出string类中的全部字符,插入进流
     {
         _cout << in;
     }
     return _cout;   //返回输出流
 }

流提取运算符

 istream& operator>>(istream& in, string& s)
 {
     s.clear();//如果s中本身有数据,先将有效数据清除
     char ch = in.get();
     //处理缓冲区的空格和换行,因为可能有人先输入了空格或者换行导致读取数据失败
     while (ch == ' ' || ch == '\n')
     {
         ch = in.get();
     }
     //有效数据插入进s
     char buff[128];//为了避免从小的容量一次次扩容
     int i = 0;
     while (ch != ' ' && ch != '\n')
     {
         buff[i++] = ch;//将读取到的数据先存放进临时数组
         if (i == 127)//只有等数据满127时,才将数据插入进s
         {
             buff[i] = '\0';
             s += buff;
             i = 0;
         }
         ch = in.get();//继续获取有效数据
     }
     if (i != 0)//最后,如果buff数组中还有数据,则将这些剩余数据插入
     {
         buff[i] = '\0';
         s += buff;
     }
     return in;
 }

(2) 比较运算符重载

两个字符串比较,我们利用memcmp函数比较两字符串中较短字符串的长度位数.

然后根据memcmp返回值进行进一步判断.

 bool operator<(const string& s)
 {
     int length = s._size;
     //谁短,length就等于谁
     if (_size < length)   length = _size;
     int ret=memcmp(_str, s._str, length);
     if (ret == 0)//如果短的 与长的前半部分相等
     {
         if (_size< s._size)//比比较的字符串短,则<成立,true
         {
             return true;
         }
         return false;
     }
     if(ret==-1)//表示右操作数大,<满足
         return true;
     if (ret == 1)//表示左操作数大,<不满足
         return false;
 }

三目运算符写起来可能不大好理解,但是代码看起来很简洁

 bool operator<(const string& s) const
 {
     int ret = memcmp(_str, s._str, _size < s._size ? _size : s._size);//按短的进行比较
     //如果ret==0,则比较长度,s长则返回真,否则返回假
     //ret!=0则-1表示真,1表示假
     return ret == 0 ? _size < s._size : ret < 0;                      
 }

其他运算符直接复用或者比较简单,这里不做解释.

bool operator<=(const string& s)
 {
     return *this < s || *this == s;
 }
 bool operator>(const string& s)
 {
     return !(*this <= s);
 }
 bool operator>=(const string& s)
 {
     return !(*this < s);
 }
 bool operator==(const string& s)
 {
     if (memcmp(_str, s._str, _size) == 0)
     {
         if (_size == s._size)
         {
             return true;
         }
         return false;
     }
 }
 bool operator!=(const string& s)
 {
     return !(*this == s);
 }

博主能力有限,无法严格按照库中的方法实现,比如采用内存池等技术,还有部分函数并未实现,模拟实现string的目的只是为了我们更好的理解string类,而不是真正让我们去写一个库函数.

拜了.

c7e3ed8f662a43f88d72dbe05bc0d9f9.gif

目录
相关文章
|
3月前
|
Java 索引
java基础(13)String类
本文介绍了Java中String类的多种操作方法,包括字符串拼接、获取长度、去除空格、替换、截取、分割、比较和查找字符等。
45 0
java基础(13)String类
|
25天前
|
存储 编译器 C语言
【c++丨STL】string类的使用
本文介绍了C++中`string`类的基本概念及其主要接口。`string`类在C++标准库中扮演着重要角色,它提供了比C语言中字符串处理函数更丰富、安全和便捷的功能。文章详细讲解了`string`类的构造函数、赋值运算符、容量管理接口、元素访问及遍历方法、字符串修改操作、字符串运算接口、常量成员和非成员函数等内容。通过实例演示了如何使用这些接口进行字符串的创建、修改、查找和比较等操作,帮助读者更好地理解和掌握`string`类的应用。
38 2
|
2月前
|
Java
【编程基础知识】(讲解+示例实战)方法参数的传递机制(值传递及地址传递)以及String类的对象的不可变性
本文深入探讨了Java中方法参数的传递机制,包括值传递和引用传递的区别,以及String类对象的不可变性。通过详细讲解和示例代码,帮助读者理解参数传递的内部原理,并掌握在实际编程中正确处理参数传递的方法。关键词:Java, 方法参数传递, 值传递, 引用传递, String不可变性。
68 1
【编程基础知识】(讲解+示例实战)方法参数的传递机制(值传递及地址传递)以及String类的对象的不可变性
|
2月前
|
安全 Java 测试技术
Java零基础-StringBuffer 类详解
【10月更文挑战第9天】Java零基础教学篇,手把手实践教学!
52 2
|
3月前
|
安全 Java
String类-知识回顾①
这篇文章回顾了Java中String类的相关知识点,包括`==`操作符和`equals()`方法的区别、String类对象的不可变性及其好处、String常量池的概念,以及String对象的加法操作。文章通过代码示例详细解释了这些概念,并探讨了使用String常量池时的一些行为。
String类-知识回顾①
|
2月前
|
存储 安全 C++
【C++打怪之路Lv8】-- string类
【C++打怪之路Lv8】-- string类
26 1
|
2月前
|
数据可视化 Java
让星星月亮告诉你,通过反射创建类的实例对象,并通过Unsafe theUnsafe来修改实例对象的私有的String类型的成员属性的值
本文介绍了如何使用 Unsafe 类通过反射机制修改对象的私有属性值。主要包括: 1. 获取 Unsafe 的 theUnsafe 属性:通过反射获取 Unsafe类的私有静态属性theUnsafe,并放开其访问权限,以便后续操作 2. 利用反射创建 User 类的实例对象:通过反射创建User类的实例对象,并定义预期值 3. 利用反射获取实例对象的name属性并修改:通过反射获取 User类实例对象的私有属性name,使用 Unsafe`的compareAndSwapObject方法直接在内存地址上修改属性值 核心代码展示了详细的步骤和逻辑,确保了对私有属性的修改不受 JVM 访问权限的限制
64 4
|
2月前
|
存储 安全 Java
【一步一步了解Java系列】:认识String类
【一步一步了解Java系列】:认识String类
28 2
|
2月前
|
安全 C语言 C++
【C++篇】探寻C++ STL之美:从string类的基础到高级操作的全面解析
【C++篇】探寻C++ STL之美:从string类的基础到高级操作的全面解析
46 4
|
2月前
|
存储 编译器 程序员
【C++篇】手撕 C++ string 类:从零实现到深入剖析的模拟之路
【C++篇】手撕 C++ string 类:从零实现到深入剖析的模拟之路
75 2