AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【C++】一文带你吃透string的模拟实现 (万字详解)(下）

2023-01-14 70
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【C++】一文带你吃透string的模拟实现 (万字详解)(下）

⚡push_back & append


⚡push_back


满了就扩容，注意如果capacity是0的情况要判断一下

注意处理'\0'

void push_back(char ch)
{
  //满了就扩容
  if (_size = _capacity)
  {
  reserve(_capacity == 0 ? 4 : _capacity * 2);
  }
  _str[_size] = ch;
  ++_size;
  _str[_size] = '\0';
}


⚡append


不能又一味的开两倍空间，要重新计算串的长度


void append(const char* str)
{
  size_t len = strlen(str);
  //超了就扩容
  if (_size + len > _capacity)
  {
  reserve(_size + len);
  }
  strcpy(_str+_size, str);
  _size += len;
}


strcat也能实现，但是每次都要找'\0',效率很低（个人认为是失败的设计）


⚡+=


+= 可插入字符/字符串，复用push_back和append即可


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


⚡insert


任意位置的插入，可插入字符\字符串，这里有点绕，要画图理解


🌊插入字符


0a2653c851af460fa595bd959398a8f1.png


此处有一个很经典的越界问题，就是pos=0时，end会减减变成-1（实际上是整数的最大值此处可以对end进行强转：（int）end ，但是pos的类型还是size_t ,会发生整形提升，所以把end=size+1就不但心越界问题了

string& insert(size_t pos, char ch)
{
  assert(pos <= _size);
  //满了就扩容
  if (_size == _capacity)
  {
  reserve(_capacity == 0 ? 4:_capacity * 2);
  }
  //挪动数据
  size_t end = _size+1;
  while (end > pos)
  {
  _str[end] = _str[end - 1];
  --end;
  }
  _str[pos] = ch;
  ++_size;
  return *this;
}


🌊插入字符串


0a2653c851af460fa595bd959398a8f1.png


把要插入的字符串拷贝过来，但是注意不能拷贝\0，因此要用strncpy

有点难理解就要画图

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 + len;
  while(end >= pos + len)
  {
  _str[end] = _str[end - len];
  --end;
  }
  strncpy(_str + pos, str, len);
  _size += len;
  return *this;
}


四. 删

🌌erase


npos是string类的静态成员变量，必须在类外的全局定义

size_t string::npos = -1;//类外定义


ps:唯独一个特例：const静态成员变量可以在声明时定义


private:
  size_t _size;
  size_t _capacity;
  char* _str;
  //特例：const static 可以在声明时定义
  const static size_t npos = -1;//类里声明


情况1️⃣：len足够长，可以删完pos后的

情况2️⃣：删一点点，要挪动数据


void erase(size_t pos, size_t len = npos)
{
  assert(pos < _size);
  //情况1：不够删
  if(len == npos || pos +len >= _size)
  {
  _str[pos] = '\0';
  _size = pos;
  }
  //删一点点，要挪动数据
  else
  {
  strcpy(_str + pos, _str + pos + len);
  _size -= len;
  }
}


🌌clear


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


六、find & substr

💚find


从pos位置开始查找字符或字符串。找到了就返回下标；没找到，返回npos


查找字符串复用了strstr

size_t find(char ch, size_t pos = 0)
  {
    assert(pos < _size);
    size_t i = pos;
    for (i = 0; i < _size; ++i)
    {
    if (ch == _str[i])
    {
      return i;
    }
    }
    return npos;
  }
  //"hello world"  
  size_t find(const char* sub, size_t pos = 0)
  {
    //strstr
    const char* ptr = strstr(_str + pos, sub);
    if(ptr == nullptr)
    {
    return npos;
    }
    else
    {
    return ptr - _str;//指针-指针 
    }
  }


💚substr


//"hello world bit"   [0, 10}，右开减左闭就是真实长度
  string substr(size_t pos, size_t len = npos) const
  {
    assert(pos < _size);
    size_t realLen = len;//取真实长度
    if (len == npos || pos + len > _size)
    {
    realLen = _size - pos;
    }
    string sub;
    for (size_t i = 0; i < realLen; ++i)
    {
    sub +=_str[pos + i];
    }
    return sub;
  }


七、运算符重载

🐋大小运算符的比较


任何类的比较大小都只需要实现两个：> ==，其他的复用即可

借助了c语言的strcmp函数，比较ascll码，谁大就谁大，

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


🐋 >> & <<


流插入&流提取因为流对象和对象抢占左操作数的位置所以必须重载成全局。但不一定是友元吗？关键看是否需要访问私有成员

🔥输出<<


遍历输出

不能out << s.c_str（） << endl，这样关注的就是'\0',而我们的要关注的是_size

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


🔥输入>>


cin的特性和scanf一样，编译器以为是分隔符，是获取不到 ' ' 和 '\0',会被忽略掉

get函数登场：一个一个字符地读取

不论s中是否有字符串，其实输入再打印是不会打出来的，需要先clear清除所有数据

istream& operator>>(istream& in, string& s)
  {
     s.clear();
  char ch;
  //in >> ch;
  ch = in.get();
  while (ch != ' ' && ch != '\n')
  {
    s += ch;
    ch = in.get();
  }
  return in;
  }


如果输入内容很长，不断+=，会频繁扩容，导致效率很低，怎么样优化呢？


开辟一个数组，缓冲区思路

//优化后
  istream& operator>>(istream& in, string& s)
  {
     s.clear();
  char ch;
  ch = in.get();
  const size_t N = 32;
  char buff[N];
  size_t i = 0;
  while (ch != ' ' && ch != '\n')
  {
    buff[i++] = ch;
    if (i == N - 1)
    {
    buff[i] = '\0';
    s += buff;
    i = 0;//轮回
    }
    ch = in.get();
  }
  buff[i] = '\0';//不等于空格或者换行也要补'\0'
  s += buff;
  return in;
  }


附源码:string.h & test.c

完整代码：现代写法+主要实现


String.h
#pragma once
#include<iostream>
#include<assert.h>
#include<string>
//为了和库里的string进行区分
namespace bit
{
  class string
  {
  public: 
  //为什么不能给指针呢？ c_str 解引用会出错
  //string()
  //  : _str(nullptr)
  //  , _size(0)
  //  , _capacity(0)
  //{}
  //全缺省
  //string(const char* str = "\0")
  //不推荐
  //string(const char* str= "")
  //  :_size(strlen(str))
  //  , _capacity(_size)
  //  ,_str(new char[_capacity + 1])
  //{
  //  strcpy(_str, str);
  //}
  //string(const char* str)
  //  :_str(new char[strlen(str) + 1])//多开一个空间
  //  , _size(strlen(str))
  //  , _capacity(strlen(str))
  //{
  //  strcpy(_str, str);
  //}
  //构造
  string(const char* str = "")
  {
    _size = strlen(str);
    _capacity = _size;
    _str = new char[_capacity + 1];
    strcpy(_str, str);
  }
  //s2(s1)  拷贝构造
  string(const string& s)
    :_str(new char[s._capacity+1])
    ,_size(s._size)
    ,_capacity(s._capacity)
  {
    strcpy(_str, s._str);
  }
  // s1 = s3
  //string& operator=(const string& s)
  //{
  //  if (this != &s)
  //  {
  //  delete[] _str;
  //  _str = new char[strlen(s._str)];
  //  strcpy(_str, s._str);
  //  _size = s._size;
  //  _capacity = s._capacity;
  //  return *this;
  //  }
  //}
  //传统写法：优化后
  //string& operator=(const string& s)
  //{
  //  if (this != &s)
  //  {
  //  char* tmp = new char[s._capacity + 1];
  //  strcpy(tmp, s._str);
  //  delete[] _str;
  //  _str = tmp;
  //  _size = s._size;
  //  _capacity = s._capacity;
  //  }
  //}
  //现代写法：——————  资本家思维
  //s2(s1)
  //string(const string& s)
  //  :_str(nullptr)
  //  ,_size(0)
  //  ,_capacity(0)
  //{
  //  string tmp(s._str);
  //  swap(tmp);//this -> swap(tmp)
  //}
  void swap(string& tmp)
  {
    ::swap(_str, tmp._str);
    ::swap(_size, tmp._size);
    ::swap(_capacity, tmp._capacity);
  }
  s1 = s3   赋值：现代写法 
  //string& operator=(const string& s)
  //{
  //  if (this != &s)
  //  {
  //  string tmp(s);
  //  ::swap(*this, tmp);
  //  //swap(tmp); //this ->swap(tmp)
  //  return *this;
  //  }
  //}
  //最简洁
  string& operator=(string s)
  {
    swap(s);
    return *this;
  }
  //析构
  ~string()
  {
    delete[] _str;
    _str = nullptr;
    _size = _capacity = 0;
  }
  //c_str
  const char* c_str() const
  {
    return _str;//解引用找到'\0'
  }
  //size
  size_t size() const
  {
    return _size;
  }
  //capacity
  size_t capacity() const
  {
    return _capacity;
  }
  //[]
  char& operator[](size_t pos)
  {
    assert(pos < _size);
    return _str[pos];
  }
  //const对象
  const char& operator[](size_t pos) const
  {
    assert(pos < _size);
    return _str[pos];
  }
  //迭代器
  typedef char* iterator;
  typedef const char* const _iterator;
  iterator begin()
  {
    return _str;
  }
  iterator end()
  {
    return _str + _size;
  }
  const _iterator begin() const
  {
    return _str;
  }
  const _iterator end() const
  {
    return _str;
  }
  //保留 
  void reserve(size_t n)
  {
    if (n > _capacity)
    {
    char* tmp = new char[n + 1];//考虑'\0'
    strcpy(tmp, _str);
    delete[] _str;
    _str = tmp;
    _capacity = n;
    }
  }
  //"helloxxxxxxxxx"
  void resize(size_t n, char ch = '\0')
  {
    if (n > _size)
    { 
    //插入数据
    reserve(n);
    for (size_t i = _size; i < n; ++i)
    {
      _str[i] = ch;
    }
    _str[n] = '\0';
    _size = n;
    }
    else
    {
    //删除数据
    _str[n] = '\0';
    _size = n;
    }
  }
  void push_back(char ch)
  {
    //满了就扩容
    if (_size = _capacity)
    {
    reserve(_capacity == 0 ? 4 : _capacity * 2);
    }
    _str[_size] = ch;
    ++_size;
    _str[_size] = '\0';
    //insert(_size , ch);
  }
  void append(const char* str)
  {
    size_t len = strlen(str);
    //超了就扩容
    if (_size + len > _capacity)
    {
    reserve(_size + len);
    }
    strcpy(_str+_size, str);
    _size += len;
    //insert(_size, str);
  }
  string& operator+= (char ch)
  {
    push_back(ch);
    return *this;
  }
  string& operator += (const char* str)
  {
    append(str);
    return *this;
  }
  string& insert(size_t pos, char ch)
  {
    assert(pos <= _size);
    //满了就扩容
    if (_size == _capacity)
    {
    reserve(_capacity == 0 ? 4:_capacity * 2);
    }
    //挪动数据
    size_t end = _size + 1;
    while (end > pos)
    {
    _str[end] = _str[end - 1];
    --end;
    }
    _str[pos] = ch;
    ++_size;
    return *this;
  }
  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 + len;
    while (end >= pos + len)
    {
    _str[end] = _str[end - len];
    --end;
    }
    strncpy( _str + pos, str, len);
    _size += len;
    return *this;
  }
  void erase(size_t pos, size_t len = npos)
  {
    assert(pos < _size);
    //情况1：不够删
    if(len == npos || pos +len >= _size)
    {
    _str[pos] = '\0';
    _size = pos;
    }
    else
    {
    strcpy(_str + pos, _str + pos + len);
    _size -= len;
    }
  }
  void clear()
  {
    _str[0] = '\0';
    _size = 0;
  }
  size_t find(char ch, size_t pos = 0)
  {
    assert(pos < _size);
    size_t i = pos;
    for (i = 0; i < _size; ++i)
    {
    if (ch == _str[i])
    {
      return i;
    }
    }
    return npos;
  }
  //"hello world"  
  size_t find(const char* sub, size_t pos = 0)
  {
    //strstr
    const char* ptr = strstr(_str + pos, sub);
    if(ptr == nullptr)
    {
    return npos;
    }
    else
    {
    return ptr - _str;
    }
  }
  //"hello world bit"   [0, 10}，右开减左闭就是真实长度
  string substr(size_t pos, size_t len = npos) const
  {
    assert(pos < _size);
    size_t realLen = len;//取真实长度
    if (len == npos || pos + len > _size)
    {
    realLen = _size - pos;
    }
    string sub;
    for (size_t i = 0; i < realLen; ++i)
    {
    sub +=_str[pos + i];
    }
    return sub;
  }
  bool operator>(const string& s) const
  {
    return strcmp(_str, s._str) > 0;
  }
  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);
  }
  bool operator!=(const string& s) const
  {
    return !(*this == s);
  }
  private:
  size_t _size;
  size_t _capacity;
  char* _str;
  public:
  //特例：const static 可以在声明时 可以定义
  const static size_t npos = -1;//类里声明
  };
  //size_t string::npos = -1;//类外定义
  //注意流插入不一定是友元，没有访问私有成员函数
  ostream& operator<<(ostream& out, const string& s)
  {
  for (size_t i = 0; i < s.size(); ++i)
  {
    out << s[i];
  }
  return out;
  }
  //istream& operator>>(istream& in, string& s)
  //{
  //  //输入内容很长，不断+=，会频繁扩容，效率很低
  //  char ch;
  //  //in >> ch;
  //  ch = in.get();
  //  while (ch != ' ' && ch != '\n')
  //  {
  //  s += ch;
  //  ch = in.get();
  //  }
  //  return in;
  //}
  //优化后
  istream& operator>>(istream& in, string& s)
  {
  char ch;
  ch = in.get();
  const size_t N = 32;
  char buff[N];
  size_t i = 0;
  while (ch != ' ' && ch != '\n')
  {
    buff[i++] = ch;
    if (i == N - 1)
    {
    buff[i] = '\0';
    s += buff;
    i = 0;//轮回
    }
    ch = in.get();
  }
  buff[i] = '\0';
  s += buff;
  return in;
  }
  //测试流插入流提取运算符重载
  void testString7()
  {
  //string s;
  string s("Always");
  cin >> s;
  cout << s << endl;
  // 不能以字符串形式输出，测试标准库
  string s1("more than");
  s1 += '\0';
  s1 += "words";
  cout << s1 << endl;
  cout << s1.c_str() << endl;
  }
  // 测试比较大小运算符重载
  void testString6()
  {
  string s1("abcd");
  string s2("abcd");
  cout << (s1 <= s2) << endl;
  string s3("abcd");
  string s4("abcde");
  cout << (s3 <= s4) << endl;
  string s5("abcde");
  string s6("abcd");
  cout << (s5 <= s6) << endl;
  }
  // 测试insert和erase
  void testString5()
  {
  string s(" lumos maxima");
  s.insert(0, "lumos");
  cout << s.c_str() << endl;
  s.insert(5, '!');
  cout << s.c_str() << endl;
  s.erase(0, 7);
  cout << s.c_str() << endl;
  s.erase(6);
  cout << s.c_str() << endl;
  }
  // 测试查找
  void testString4()
  {
  string s("lumos maxima");
  cout << s.find('m') << endl;
  cout << s.find("max") << endl;
  }
  // 测试resize
  void testString3()
  {
  string s("lumos maxima"); // capacity - 12
  s.resize(5);
  cout << s.c_str() << endl;
  s.resize(7, '!');
  cout << s.c_str() << endl;
  s.resize(20, '~');
  cout << s.c_str() << endl;
  }
  // 测试尾插字符及字符串push_back/append，同时测试reserve
  void testString2()
  {
  string s("more than words");
  s.push_back('~');
  s.push_back(' ');
  cout << s.c_str() << endl;
  s.append("is all you have to do to make it real");
  cout << s.c_str() << endl;
  s += '~';
  s += "then you wouldn't have to say that you love me, cause I'd already know";
  cout << s.c_str() << endl;
  }
  // 测试现代写法的成员函数
  void testString1()
  {
  string s0;
  string s1("Always");
  string s2(s1);
  cout << s2.c_str() << endl;
  string s3("more than words");
  s3 = s1;
  cout << s3.c_str() << endl;
  s3 = s3;
  }
}


test.c


#include<iostream>
#include<string>
using namespace std;
#include "string.h"
int main()
{
  try
  {
  bit::testString1();
  //bit::testString2();
  //bit::testString3();
  //bit::testString4();
  //bit::testString5();
  //bit::testString6();
  }
  catch (const exception& e)
  {
  cout << e.what() << endl;
  }
  return 0;
}


文章标签：
云数据库 ClickHouse
C++
C语言
编译器
关键词：
C++ string
张小姐的猫
目录
相关文章
努力学习的小廉
|
1月前
|
C++ 容器
【C++】 —— string的使用（二）
【C++】 —— string的使用
努力学习的小廉
67 2
【C++】 —— string的使用（二）
白子寰
|
1月前
|
存储 安全 C++
【C++打怪之路Lv8】-- string类
【C++打怪之路Lv8】-- string类
白子寰
22 1
努力学习的小廉
|
1月前
|
C++ 容器
【C++】—— string模拟实现（二）
【C++】—— string模拟实现
努力学习的小廉
34 1
努力学习的小廉
|
1月前
|
C++ 容器
【C++】—— string模拟实现（一）
【C++】—— string模拟实现
努力学习的小廉
67 1
努力学习的小廉
|
1月前
|
存储 C++ 容器
【C++】 —— string的使用（一）
【C++】 —— string的使用
努力学习的小廉
28 1
半截诗
|
1月前
|
安全 C语言 C++
【C++篇】探寻C++ STL之美：从string类的基础到高级操作的全面解析
【C++篇】探寻C++ STL之美：从string类的基础到高级操作的全面解析
半截诗
36 4
半截诗
|
1月前
|
存储 编译器 程序员
【C++篇】手撕 C++ string 类：从零实现到深入剖析的模拟之路
【C++篇】手撕 C++ string 类：从零实现到深入剖析的模拟之路
半截诗
65 2
是店小二呀
|
1月前
|
编译器 C语言 C++
【C++】C++ STL 探索：String的使用与理解（三）
【C++】C++ STL 探索：String的使用与理解
是店小二呀
63 2
是店小二呀
|
1月前
|
存储 编译器 C++
【C++】C++ STL 探索：String的使用与理解（二）
【C++】C++ STL 探索：String的使用与理解
是店小二呀
41 1
是店小二呀
|
1月前
|
编译器 C语言 C++
【C++】C++ STL 探索：String的使用与理解（一）
【C++】C++ STL 探索：String的使用与理解
是店小二呀
70 1