[C++随笔录] string模拟实现

简介: [C++随笔录] string模拟实现

string模拟实现

基本结构

天选之子

构造函数

析构函数

拷贝构造函数

空间

size()函数

capacity()函数

clear()函数

empty()函数

reverse()函数

resize()函数

迭代器

iterator

begin()函数

end()函数

const_iterator

begin()函数

end()函数

push_back()函数

append()函数

operator+=

insert()函数

erase()函数

find()函数

swap()函数

operator[]函数

operator= 函数

比较

流操作

流插入 <<

流提取 >>

C接口

c_str()函数

substr()函数

源码

放在前面:
我们实现string类, 并不是跟源码一模一样(并不是造一个新的轮子), 只是了解每个接口的实现过程 ⇒ 我们以后也用的放心(比如时间复杂度, 空间复杂度等等)

基本结构

private:
  size_t _size; // 实际长度
  size_t _capacity; // 空间
  char* _str;

习惯把不可能为负数的值的类型 定义为 size_t


天选之子

构造函数

考虑到 无参调用和有参调用 && 只有一个参数 ⇒ 我们可以采用 全缺省的形式

传参类型应该为 常量字符串 ⇒ const char* ⇐ 一般用于初始化, 咋们给的值都是常量

缺省值初始化为 ""(空字符串) ⇐ 常量字符串默认就会有 \0, 即 “” (空字符串) 里面就是一个 \0

_size 和 _capacity 的大小不包括 \0 ⇒ 所以, 我们初始化长度的时候, 用 strlen(str)

_str要先开空间

👇👇👇

string(const char* str = "")
    :_size(strlen(str))
    ,_capacity(_size)
    ,_str(new char[_capacity+1])
  {
    memcpy(_str, str, _capacity+1);
  }
注意:
初始化的顺序是按照 声明的顺序来的 ⇒ 我们尽量保持 初始化和声明的顺序一致, 要不然就会出现问题
由于 _size 和 _capacity不包括 \0 的长度 ⇒ 我们_str开空间的时候要多开一个, 给 \0用

🗨️为啥要用 memcpy函数? 为啥不用strcpy函数呢?


1. memcpy函数 和 strcpy函数的 区别 : memcpy函数是 逐个字节进行copy的, 而strcpy是 遇到 \0就停止 copy

2 我们标准库中 string类的输出是按照 _size 来的. 即遇到下面的情况, strcpy 和 strcpy的区别就体现出来了👇👇👇

  // 字符串如下:
  // hello 
  // world!
  // 来做以下几组实验
  // 1. 库里的string
  std::string str1 = "hello";
  str1 += "\0";
  str1 += "world!";
  cout << str1 << endl;
  // 2. 用strcpy来实现
  // ...
  //..
  // 3. 用memcpy来实现
  // ...
  // ...
*****
1. helloworld!
2. hello
3. helloworld!
*****
  1. memcpy默认是不会copy \0, 所以memcpy函数里面的长度 传的是 _capacity+1

析构函数

~string()
{
  delete[] _str; // 清理动态申请空间
  // 置零(置空)
  _str = nullptr;
  _size = _capacity = 0;
}

拷贝构造函数

  1. 我们不写构造函数, 系统自动生成的是一种 浅拷贝 ⇒ 对有动态资源申请的对象来说, 会对同一块空间析构两次
  2. 我们写的是 深拷贝 ⇒ 找一块新的空间给 this->_str, 然后将 s的内容 copy过去, 更新 _capacity 和 _size
String(const string& s)
{
  _str = new char[s._capacity + 1];
  memcpy(_str, s._str, s._capacity + 1);
  _capacity = s._capacity;
  _size = s._size;
}

空间

size()函数

size_t size()const
{
  return _size;
}

capacity()函数

size_t capacity()const
{
  return _capacity;
}

clear()函数

void clear()
{
  _size = 0;
  _str[_size] = '\0';
}
clear()函数 并不是用来清理空间的, 而是让空间置空(置零)

empty()函数

bool empty()const 
{
  if(_size == 0)
    return true;
  return false;
}

reverse()函数

void reverse(size_t n)
{
  assert(n >= 0);
  // 扩容逻辑 -- 一般我们不进行缩容
  if(n > _capacity)
  {
    char* tem = new char[n+1];
    memcpy(tem._str, _str, _capacity+1);
    delete[] _str;
    _str = tem;
    _capacity = n;
  } 
}

resize()函数

void resize(size_t n, char ch = '\0')
{
  assert(n >= 0);
  if(n <= _size)
  {
    _size = n;
    _str[_size] = '\0';
  }
  else
  {
    reverse(n);
    for(int i = _size; i < _size+n; i++)
    {
      _str[i] = ch;
    }
    _size = _size + n;
    _str[_size] = '\0';
  }
}

迭代器

迭代器是属于类的 ⇐ 我们声明迭代器的时候要声明类域
👇👇👇
std::string str = "hello world";
iterator it = str.begin();
*****
error C2955: “std::iterator”: 使用 类 模板 需要 模板 参数列表
*****

但要在 string类里面,定义一种类型, 有两种方式:


typedef 一个变量

定义一个内部类 (内部类一般都是自定义类型)

而我们这里iterator其实就是数组_str各个下标对应的地址, 是一种 内置类型 ⇒ 所以, 我们采用typedef的方式来实现 iterator


iterator

typedef char* iterator;

begin()函数

iterator begin()
{
  return _str;
}

end()函数

iterator end()
{
  return _str + _size;
}

const_iterator

typedef const char* const_iterator;

begin()函数

const_iterator begin()const
{
  return _str;
}

end()函数

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

push_back()函数

尾插一个字符的操作:


是否需要扩容 ⇐ _size == _capacity


扩容逻辑:


_capacity == 0 ⇒ 传个 4 过去扩容

_capacity > 0 ⇒ 2倍扩容

_size++, _str[_size] = ‘\0’;

void push_back(const char ch)
{
  // 是否扩容
  if (_size == _capacity)
  {
    size_t newcapacity = (_capacity == 0 ? 4 : _capacity * 2);
    reverse(newcapacity);
  }
  _str[_size] = ch;
  _size++;
  _str[_size] = '\0';
}

append()函数

尾插一个字符串的操作:


是否需要扩容


扩容逻辑:

1. _size + len <= _capacity — — 不需要扩容

2. _size + len > _capacity — — 扩容(_size + len)


_size = _size + len, _str[_size] = ‘\0’;

void append(const char* ch)
{
  size_t len = strlen(ch);
  // 是否扩容
  if (len + _size > _capacity)
  {
    reverse(len + _size);
  }
  for (size_t i = 0; i < len; i++)
  {
    _str[_size + i] = ch[i];
  }
  _size += len;
  _str[_size] = '\0';
}

operator+=

复用 push_back() 和 append()

void operator+=(const char ch)
{
  push_back(ch);
}
void operator+=(const char* ch)
{
  append(ch);
}

insert()函数

在 下标为pos的位置插入n个字符:


是否需要扩容


扩容逻辑:


_size + n <= _capacity — — 不需要扩容

_size + n > _capacity — — 扩容(_size + n)

挪动数据


_size = _size + n, _str[_size] = ‘\0’;

void insert(size_t pos, const char* ch)
{
  assert(pos >= 0);
  // 是否需要扩容
  size_t len = strlen(ch);
  if (_size + len > _capacity)
  {
    reverse(_size + pos);
  }
  // 挪动数据
  size_t end = _size;
  // 挪动数据时, 下标不能小于0(即不能等于 -1)
  while (end >= pos && end != _nops)
  {
    _str[end + len] = _str[end];
    end--;
  }
  // 插入数据
  for (size_t i = 0; i < len; i++)
  {
    _str[pos + i] = ch[i];
  }
  _size = _size + len;
}

对了, 这里的 _nops是我么定义的一个静态成员变量

// 类里面的声明
public:
  static size_t _nops;
// 类外面的初始化
size_t muyu::string::_nops = -1; // 这里的muyu是我定义的一个命名空间域

🗨️为啥要定义一个nops? 为啥要初始化为 -1?


前面, 我们有说过: 不可能为负数的, 我们定义成 size_t (无符号整数)

如果 下标减到 -1 — ---- 由于是 size_t, 变量是不会比 -1 小的

那么 size_t 类型如何区分开 -1 呢?

size_t i = -1; ⇒ i 等于 2 ^ 32 -1;

那么 下标 不等于 nops不就行了~~

还有就是, 插入函数 和 删除函数中 字符串的长度如果不写, 就是nops

erase()函数

void erase(size_t pos, size_t n = _nops)
{
  assert(pos >= 0);
  // 是否把pos位置后面全部删除
  if (n == _nops || pos + n >= _size)
  {
    _str[pos] = '\0';
    _size = pos;
  }
  else
  {
    for (size_t i = pos; i < pos + n; i++)
    {
      _str[i] = _str[i + n];
    }
    _size = _size - n;
  }
}

find()函数

size_t find(size_t pos = 0, const char ch )
{
  assert(pos < _size);
  for (int i = pos; i < _size; i++)
  {
    if (_str[i] == ch)
    {
      return i;
    }
  }
  return _nops;
}
size_t find(size_t pos = 0, const char* ch )
{
  assert(pos < _size);
  // 如果找到返回地址, 否则返回nullptr
  const char* res = strstr(_str, ch);
  if (res)
  {
    return res - _str;
  }
  else
  {
    return _nops;
  }
}

swap()函数

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

operator[]函数

//不是&, 那就返回的是常量临时拷贝
char& operator[](size_t n)
{
  assert(n <= _size);
  return _str[n];
}
const char& operator[](size_t n)const 
{
  assert(n <= _size);
  return _str[n];
}

operator= 函数

//string& operator=(const string& s)
//{
//  // 传统写法 -- 找一块空间, 把s的内容搞过去, 然后和*this交换
//  // 1. 找空间, 移内容;  2. 释放this的空间
//  string tem;
//  tem.reverse(s._capacity + 1);
//  memcpy(tem._str, s._str, s._capacity + 1);
//  tem._size = s._size;
//  swap(tem);
//  return *this;
//}
string& operator=(string s)
{
  swap(s);
  return *this;
}

比较

bool operator==(const string& s)
{
  // 如果_size都不相等, 那么何谈相等
  return _size == s._size &&
    memcmp(_str, s._str, _size) == 0;
}
bool operator>(const string& s)
{
  // 取较小长度进行比较
  size_t size = std::min(_size, s._size);
  int ret = memcmp(_str, s._str, size);
  // 由于是取较小长度进行比较, 那么会出现如下几种情况:
  // 1. str1 = hello, str2 = hello
  // 2. str1 = hello\0xxx, str2 = hello
  // 3. str1 = hello, str2 = hello\00xxx
  // 这几种情况都是根据较小长度比较的结果都是 相等
  if (ret == 0)
  {
    if (_size > s._size)
      return true;
    else
      return false;
  }
  return ret > 0;
}
bool operator!=(const string& s)
{
  return !(*this == s);
}
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);
}

流操作

流操作要写在全局位置 ⇐ cout/cin 要抢占第一个参数. 若要是在类中, 第一个参数就默认是this

流插入 <<

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

流提取 >>

istream& operator>>(istream& in, string& s)
{
  // 每一次新的读取要进行清理一下
  // 要不然就会接着读取, 而不是覆盖
  s.clear();
  // get()函数可以读到每一个字符, 包括空格 和 换行
  char ch = in.get();
  // 处理前缓冲区前面的空格或者换行
  while (ch == ' ' || ch == '\n')
  {
    ch = in.get();
  }
  // in >> ch;
  char buff[128]; // buff数组的作用是: 减少开空间的次数
  int i = 0;
  while (ch != ' ' && ch != '\n')
  {
    buff[i++] = ch;
    if (i == 127)
    {
      buff[i] = '\0';
      s += buff;
      i = 0;
    }
    //in >> ch;
    ch = in.get();
  }
  // 如果最后 buff数组还有数据, 那么就加到s中
  if (i != 0)
  {
    buff[i] = '\0';
    s += buff;
  }
  return in;
}

C接口

c_str()函数

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

substr()函数

string substr(size_t pos = 0, size_t n = _nops)
{
  assert(pos >= 0);
  // 是否需要扩容
  int len = n; // 默认是n
  if (n == _nops || pos + n >= _size)
  {
    len = _size - pos;
  }
  string tem;
  tem.reverse(len);
  //for (size_t i = pos; i < len; i++)
  //{
  //  tem[i] = _str[i + pos];
  //}
  //tem._size = len;
  //tem[_size] = '\0';
  for (size_t i = pos; i < pos + len; i++)
  {
    tem += _str[i];
  }
  return tem;
}

源码

#pragma once
#include <string.h>
#include<assert.h>
#include<iostream>
namespace muyu
{
  class string
  {
  public:
    typedef char* iterator;
    typedef const char* const_iterator;
    // friend ostream& operator<<(ostream& out, const string& s);
    iterator begin()
    {
      return _str;
    }
    const_iterator begin()const
    {
      return _str;
    }
    iterator end()
    {
      return _str + _size;
    }
    const_iterator end()const
    {
      return _str + _size;
    }
    string(const char* str = "")
      :_size(strlen(str))
      ,_capacity(_size)
      ,_str(new char[_capacity+1])
    {
      memcpy(_str, str, _capacity+1);
    }
    string(const string& tem)
    {
      _str = new char[tem._capacity + 1];
      memcpy(_str, tem._str, tem._capacity + 1);
      _capacity = tem._capacity;
      _size = tem._size;
    }
    ~string()
    {
      delete[] _str;
      _str = nullptr;
      _size = _capacity = 0;
    }
    const char* c_str()const
    {
      return _str;
    }
    void reverse(size_t n)
    {
      if (n > _capacity)
      {
        char* tem = new char[n + 1];
        memcpy(tem, _str, _capacity + 1);
        _capacity = n;
        delete[] _str;
        _str = tem;
      }
    }
    void resize(size_t n, char ch = '\0')
    {
      if (_size > n)
      {
        _str[n] = '\0';
        _size = n;
      }
      else
      {
        reverse(n); // 不管需不需要扩容,都丢给reverse. reverse内部有判断是否需要扩容
        for (size_t i = _size; i < n; i++)
        {
          _str[i] = ch;
        }
        _str[n] = '\0';
      }
    }
    void push_back(const char ch)
    {
      // 是否扩容
      if (_size == _capacity)
      {
        size_t newcapacity = (_capacity == 0 ? 4 : _capacity * 2);
        reverse(newcapacity);
      }
      _str[_size] = ch;
      _size++;
      _str[_size] = '\0';
    }
    void append(const char* ch)
    {
      size_t len = strlen(ch);
      // 是否扩容
      if (len + _size > _capacity)
      {
        reverse(len + _size);
      }
      for (size_t i = 0; i < len; i++)
      {
        _str[_size + i] = ch[i];
      }
      _size += len;
      _str[_size] = '\0';
    }
    void operator+=(const char ch)
    {
      push_back(ch);
    }
    void operator+=(const char* ch)
    {
      append(ch);
    }
    void insert(size_t pos, const char* ch)
    {
      assert(pos >= 0);
      // 是否需要扩容
      size_t len = strlen(ch);
      if (_size + len > _capacity)
      {
        reverse(_size + pos);
      }
      // 挪动数据
      size_t end = _size;
      // 挪动数据时, 下标不能小于0(即不能等于 -1)
      while (end >= pos && end != _nops)
      {
        _str[end + len] = _str[end];
        end--;
      }
      // 插入数据
      for (size_t i = 0; i < len; i++)
      {
        _str[pos + i] = ch[i];
      }
      _size = _size + len;
    }
    void erase(size_t pos, size_t n = _nops)
    {
      assert(pos >= 0);
      if (n == _nops || pos + n >= _size)
      {
        _str[pos] = '\0';
        _size = pos;
      }
      else
      {
        for (size_t i = pos; i < pos + n; i++)
        {
          _str[i] = _str[i + n];
        }
        _size = _size - n;
      }
    }
    size_t size()const
    {
      return _size;
    }
    void clear()
    {
      _size = 0;
      _str[_size] = '\0';
    }
    bool empty()const
    {
      return _size > 0;
    }
    void swap(string& s)
    {
      std::swap(_size, s._size);
      std::swap(_capacity, s._capacity);
      std::swap(_str, s._str);
    }
     //不是&, 那就返回的是常量临时拷贝
    char& operator[](size_t n)
    {
      assert(n <= _size);
      return _str[n];
    }
    const char& operator[](size_t n)const 
    {
      assert(n <= _size);
      return _str[n];
    }
    string substr(size_t pos = 0, size_t n = _nops)
    {
      assert(pos >= 0);
      int len = n; // 默认是n
      if (n == _nops || pos + n >= _size)
      {
        len = _size - pos;
      }
      string tem;
      tem.reverse(len);
      //for (size_t i = pos; i < len; i++)
      //{
      //  tem[i] = _str[i + pos];
      //}
      //tem._size = len;
      //tem[_size] = '\0';
      for (size_t i = pos; i < pos + len; i++)
      {
        tem += _str[i];
      }
      return tem;
    }
    bool operator==(const string& s)
    {
      return _size == s._size &&
        memcmp(_str, s._str, _size) == 0;
    }
    bool operator>(const string& s)
    {
      // 取较小长度进行比较
      size_t size = std::min(_size, s._size);
      int ret = memcmp(_str, s._str, size);
      if (ret == 0)
      {
        if (_size > s._size)
          return true;
        else
          return false;
      }
      return ret > 0;
    }
    bool operator!=(const string& s)
    {
      return !(*this == s);
    }
    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);
    }
    size_t find(const char ch, size_t pos = 0)
    {
      assert(pos < _size);
      for (int i = pos; i < _size; i++)
      {
        if (_str[i] == ch)
        {
          return i;
        }
      }
      return _nops;
    }
    size_t find(const char* ch, size_t pos = 0)
    {
      assert(pos < _size);
      const char* res = strstr(_str, ch);
      if (res)
      {
        return res - _str;
      }
      else
      {
        return _nops;
      }
    }
    //string& operator=(const string& s)
    //{
    //  // 传统写法 -- 找一块空间, 把s的内容搞过去, 然后和*this交换
    //  // 1. 找空间, 移内容;  2. 释放this的空间
    //  //string tem;
    //  //tem.reverse(s._capacity + 1);
    //  //memcpy(tem._str, s._str, s._capacity + 1);
    //  //tem._size = s._size;
    //  //swap(tem);
    //  //return *this;
    //}
    string& operator=(string s)
    {
      swap(s);
      return *this;
    }
  private:
      size_t _size;
      size_t _capacity;
      char* _str;
  public:
      static size_t _nops;
  };
  size_t string::_nops = -1;
  ostream& operator<<(ostream& out, const string& s)
  {
    for (auto ch : s)
    {
      out << ch;
    }
    return out;
  }
  istream& operator>>(istream& in, string& s)
  {
    // 每一次新的读取要进行清理一下
    // 要不然就会接着读取, 而不是覆盖
    s.clear();
    // get()函数可以读到每一个字符, 包括空格 和 换行
    char ch = in.get();
    // 处理前缓冲区前面的空格或者换行
    while (ch == ' ' || ch == '\n')
    {
      ch = in.get();
    }
    // in >> ch;
    char buff[128]; // buff数组的作用是: 减少开空间的次数
    int i = 0;
    while (ch != ' ' && ch != '\n')
    {
      buff[i++] = ch;
      if (i == 127)
      {
        buff[i] = '\0';
        s += buff;
        i = 0;
      }
      //in >> ch;
      ch = in.get();
    }
    // 如果最后 buff数组还有数据, 那么就加到s中
    if (i != 0)
    {
      buff[i] = '\0';
      s += buff;
    }
    return in;
  }
}


相关文章
|
5天前
|
安全 编译器 C语言
【C++数据结构】string的模拟实现
【C++数据结构】string的模拟实现
|
11天前
|
安全 程序员 C++
C++ --> string类的使用(详细介绍)
C++ --> string类的使用(详细介绍)
26 5
|
11天前
|
存储 编译器 C语言
C++ --> string类模拟实现(附源码)
C++ --> string类模拟实现(附源码)
34 4
|
6天前
|
编译器 C语言 C++
【C++】模拟实现string类
【C++】模拟实现string类
|
6天前
|
存储 算法 C语言
【C++】认识使用string类
【C++】认识使用string类
|
1月前
|
C++
C++ string中的函数和常用用法
C++ 中string中的函数和常用用法
22 4
|
1月前
|
C语言 C++
【C++】string模拟实现(下)
本文档介绍了自定义`string`类的一些关键功能实现,包括`reserve()`用于内存管理,`push_back()`和`append()`添加字符或字符串,运算符`+=`的重载,以及`insert()`, `erase()`进行插入和删除操作。此外,还涵盖了`find()`查找函数,字符串的比较运算符重载,`substr()`获取子串,`clear()`清除内容,以及流插入和提取操作。常量`npos`用于表示未找到的标记。文档以代码示例和运行结果展示各功能的使用。
|
1月前
|
编译器 程序员 C语言
【C++】string模拟实现
这篇博客探讨了自定义实现C++ `string` 类的关键功能,包括构造、拷贝构造、赋值运算符重载及析构函数。作者强调了理解并实现这些功能对于面试的重要性。博客介绍了`string` 类的头文件`string.h`,其中定义了迭代器、基本成员函数如`swap()`、`size()`、`c_str()`等,并提到了深拷贝概念。此外,还展示了构造函数、析构函数和赋值运算符的实现,以及迭代器的定义与使用。博客还包括对C语言字符串函数的引用,以辅助读者理解实现细节。
|
1月前
|
编译器 C++
【C++】string类的使用④(字符串操作String operations )
这篇博客探讨了C++ STL中`std::string`的几个关键操作,如`c_str()`和`data()`,它们分别返回指向字符串的const char*指针,前者保证以&#39;\0&#39;结尾,后者不保证。`get_allocator()`返回内存分配器,通常不直接使用。`copy()`函数用于将字符串部分复制到字符数组,不添加&#39;\0&#39;。`find()`和`rfind()`用于向前和向后搜索子串或字符。`npos`是string类中的一个常量,表示找不到匹配项时的返回值。博客通过实例展示了这些函数的用法。
|
1月前
|
存储 C++
【C++】string类的使用③(非成员函数重载Non-member function overloads)
这篇文章探讨了C++中`std::string`的`replace`和`swap`函数以及非成员函数重载。`replace`提供了多种方式替换字符串中的部分内容,包括使用字符串、子串、字符、字符数组和填充字符。`swap`函数用于交换两个`string`对象的内容,成员函数版本效率更高。非成员函数重载包括`operator+`实现字符串连接,关系运算符(如`==`, `&lt;`等)用于比较字符串,以及`swap`非成员函数。此外,还介绍了`getline`函数,用于按指定分隔符从输入流中读取字符串。文章强调了非成员函数在特定情况下的作用,并给出了多个示例代码。

热门文章

最新文章