C++_String增删查改模拟实现

简介: C++_String增删查改模拟实现

前言

本篇博客仅仅实现存储字符的string。同时由于C++string库设计的不合理,博主仅实现一些最常见的增删查改接口!

接下来给出的接口都是基于以下框架:

namespace achieveString
{
  class string
  {

  private:
    char* _str;
    size_t _capacity;
    size_t _size;
  };
}

一、string默认构造、析构函数、拷贝构造、赋值重载

1.1 默认构造

博主在这仅仅提供如无参和带参默认构造接口:

//无参默认构造
string()
  :_str(new char[1]{'\0'})
  ,_capacity(0)
  ,_size(0)
{ }
//带参默认构造
string(const char* str = "")
  :_capacity(strlen(str))
  ,_size(_capacity)
{
  _str = new char[_capacity + 1];
  strcpy(_str, str);
}

小tips:

  1. C++string标准库中,无参构造并不是空间为0,直接置为空指针。而是开一个字节,并存放‘\0’。(C++中支持无参构造一个对象后,直接在后面插入数据,也从侧面说明了这点)
  2. 由于C++构造函数不管写不写都会走初始化列表的特性,所以这里博主也走初始化列表。
  3. string中,_capacity和_size都不包含空指针,所以带参构造要多开一个空间,用来存储’\0’。

1.2 析构函数

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

1.3 拷贝构造

传统写法:

string(const string& s)
{
  _str = new char[s._capacity + 1];
  strcpy(_str, s._str);
  _size = s._size;
  _capacity = s._capacity;
}

现代写法:现代写法的核心在于:将拷贝数据的工作交给别人来做,最后将成果交换一样即可。

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

//现代写法
string(const string& s)
  :_str(nullptr)
  ,_size(0)
  ,_capacity(0)
{
  string tmp(s._str);
  swap(tmp);
}

tips:现代写法中,拷贝构造是数据需初始化为空。原因在于C++中,编译器对内置类型不会做处理(个别如vs2019等编译器会做处理的),这也就意味这_str是一个随机值,指向任意一块空间。调用析构函数时会报错。

1.4 赋值重载

赋值重载同样分为传统写法和现代写法。

传统写法:

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;
  }
  return *this;
}

现代写法:

//现代写法
//法一
/*string& operator=(const string& s)
{
  if (this != &s)
  {
    string tmp(s._str);
    swap(tmp);
  }
  return *this;
}*/

//法二
string& operator=(string tmp)
{
  swap(tmp);
  return *this;
}

二、迭代器和范围for

在C++中,范围for在底层是通过迭代器来实现的。所以只要实现了迭代器,就支持范围for。

而迭代器类似于指针,迭代器可以被看作是指针的一种泛化,它提供了类似指针的功能,可以进行解引用操作、指针运算等。

 

以下提供了const迭代器和非const迭代器:

typedef char* iterator;
const typedef char* const_iterator;

  iterator begin()
  {
    return _str;
  }
  iterator end()
  {
    return _str + _size;
  }

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

三、元素相关:operator[ ]

这里我们和库中一样,提供以下两个版本

//可读可写
char operator[](size_t pos)
{
  assert(pos < _size);
  return _str[pos];
}
//只读
const char operator[](size_t pos)const
{
  assert(pos < _size);
  return _str[pos];
}

四、容量相关:size、resize、capacity、reserve

4.1 size、capacity

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

4.2 reserve

在C++中,我们一般不缩容。

所以实现reserve时(容量调整到n),首先判断目标容量n是否大于当前容量。如果小于就不做处理,否则先开辟n+1个内存空间(多出来的一个用于存储‘\0’),然后将原有数据拷贝到新空间(strcpy会将’\0’一并拷贝过去)。然后释放就空间,并让_str指向新空间,同时更新_capacity。

void reserve(size_t n)
{
  if (n > _capacity)
  {
    char* tmp = new char[n + 1];
    strcpy(tmp, _str);
    delete[] _str;
    _str = tmp;
    _capacity = n;
  }
}

4.3 resize

resize到目标大小分为以下3中情况:

  1. 当n<_size时,只需将下标为n的地址处的数据改为’\0’。
  2. 其他情况,我们直接统一处理。直接复用reserve()函数将_capacity扩到n。然后用将[_size, n)中的数据全部初始化为ch。(这里博主给ch一个初始值’\0’,但ch不一定为’\0’,所以要将下标为n处的地址初始化为’\0’)
void resize(size_t n, char ch='\0')
{
  if (n <= _size)
  {
    _str[n] = '\0';
    _size = n;
  }
  else
  {
    reserve(n);
    while (_size < n)
    {
      _str[_size] = ch;
      _size++;
    }
    _str[_size] = '\0';
  }
}

五、数据相关:push_bach、append、operator+=、insert、erase

5.1 尾插:push_back

尾插首先检查扩容,在插入数据

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

}

5.2 append尾部插入字符串

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

5.3 operator+=()字符、字符串

operator+=()字符、字符串可以直接复用push_back和append。

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

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

5.4 insert插入字符、字符串

5.4.1 insert插入字符(在这提醒下,博主是所有的拷贝数据都是从’\0’开始,这样就不需要单独对’\0’做处理)

insert插入字符逻辑上还是很简单的。

首先判断插入字符时是否需要扩容。然后从下标为pos开始,所有数据依次往后挪动。最后将待插入字符给到pos处即可。

初学者最容易范的一个错误

但对于初学者来说,貌似也不太轻松。。。。。。

下面给出各位初学者容易犯的错误:

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

这样对吗?答案是错误的。

假设是在头插字符,end理论上和pos(即0)比较完后就减到-1,在下一次循环条件比较时失败,退出循环。

遗憾的是end是size_t类型,始终>=0, 会导致死循环。

博主在这给出两种解决方法:

  1. 将pos强转为整型。
void insert(size_t pos, char ch)
{
  assert(pos <= _size);
  //扩容
  if (_size == _capacity)
  {
    reserve(_capacity == 0 ? 4 : _capacity * 2);
  }
  //挪动数据
  int end = _size;
  while (end >= (int)pos)
  {
    _str[end+1] = _str[end];
    end--;
  }
  _str[pos] = ch;
  _size++
}

2.从end从最后数据的后一位开始,每次将前一个数据移到当前位置。最后条件判断就转化为end>pos,不会出现死循环这种情况。

void 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--;
  }
  //插入数据,更新_size
  _str[pos] = ch;
  _size++;
}

5.4.2 insert插入字符串

insert同样存在相同问题,并且思路一样。博主就直接给出代码了。

法一:

void insert(size_t pos, const char* str)
{
  int len = strlen(str);
  if (_size + len > _capacity)
  {
    reserve(_size + len);
  }

  int end = _size;
  while (end >= (int)pos)
  {
    _str[end + len] = _str[end];
    end--;
  }
  strncpy(_str + pos, str, len);
  _size += len;
}

法二:

void insert(size_t pos, const char* str)
{
  int len = strlen(str);
  if (_size + len > _capacity)
  {
    reserve(_size + len);
  }
  
  size_t end = _size+1;
  while (end > pos)
  {
    _str[end + len-1] = _str[end-1];
    end--;
  }
  strncpy(_str + pos, str, len);
  _size += len;
}

5.5 erase

erase分两种情况:

  1. 从pos开始,要删的数据个数超过的字符串,即将pos后序所有数据全部情况。(直接将pos处数据置为’\0’即可)
  2. 从pos开始,要删的数据个数没有超出的字符串。所以只需要从pos+len位置后的所有数据向前移动从pos位置覆盖原数据即可。
void erase(size_t pos, size_t len = npos)
{
  if (len==npos || pos + len >= _size)
  {
    //有多少,删多少
    _str[pos] = '\0';
    _size = pos;
  }
  else
  {
    size_t begin = pos + len;
    while (begin <= _size)
    {
      _str[begin - len] = _str[begin];
      begin++;
    }
    _size -= len;
  }
}

六、 关系操作符重载:< 、 ==、 <=、 >、>=、!=

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);
}

七、find查找字符、字符串、substr

7.1 find查找字符

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

  return npos;
}

7.2 find查找字符串

size_t find(const char* sub, size_t pos = 0)
{
  const char* p = strstr(_str + pos, sub);
  if (p)
  {
    return p - _str;
  }
  else
  {
    return npos;
  }
}

7.3 strsub( ) 模拟实现

strsub目标长度可能越界string,也可能还有没有。但不管是那种情况,最后都需要拷贝数据。所以这里我们可以先将len真实长度计算出来,在拷贝数据。

string substr(size_t pos, size_t len = npos)const
{
  string s;
  size_t end = pos + len;
  //目标字符越界string,更新len
  if (len == npos || end >= _size)
  {
    len = _size - pos;
    end = _size;
  }
  
  //拷贝数据
  s.reserve(len);
  for (size_t i = pos; i < end; i++)
  {
    s += _str[i];
  }

  return s;
}

八、流插入和流提取(<<、>>)(实现在string类外)

8.1 流插入<<

由于前面我们实现了迭代器,所以最简单的方式就是范围for

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

  return out;
}

8.1 流提取>>

流提取比较特殊。在流提取前需要将原有数据全部清空。同时由于>>无法获取空字符和换行符()(都是作为多个值之间的间隔),直接流提取到ostream对象中,没法结束。(类似于C语言中scanf, 换行符和空字符仅仅只是起到判断结束的作用,但scanf无法获取到它们)

所以这里博主直接调用istream对象中的get()函数。(类似于C语言中的getchar()函数)

get详细文档

class string
{
  void clear()
  {
    _str[0] = '\0';
    _size = 0;
  }
private:
  char* _str;
  size_t _capacity;
  size_t _size;
};

istream& operator>>(istream& in, string& s)
  {
    s.clear();
    char ch;
    //in >> ch;
    ch = in.get();

    while (ch != ' ' && ch != '\n')
    {
      s += ch;
      //in >> ch;
      ch = in.get();
    }
    return in;
  }

上面这种方法虽然可以达到目的。但还有一个问题,每次插入数据都面临可扩容问题。那如何优化呢?

优化

其中一种办法就是调用reserve()提前开好空间,但这样面临这另一个问题:开大了浪费空间;开小了,同样面临这扩容的问题。

所以在这博主采用和vs底层实现的思路:首先开好一段数组(包含’\0’,以16为例)。当数据个数小于16时,字符串存在数组中;当数据个数大于等于16时,将数据存在_str指向的空间。

这是一种以空间换时间的思路,同时也能很好的减少内存碎片的问题。

class string
{
  void clear()
  {
    _str[0] = '\0';
    _size = 0;
  }
private:
  char* _str;
  size_t _capacity;
  size_t _size;
};

istream& operator>>(istream& in, string& s)
{
  s.clear();

  char buff[16];
  size_t i = 0;

  char ch;
  ch = in.get();
  while (ch != ' ' && ch != '\n')
  {
    buff[i++] = ch;
    if (i == 16)
    {
      buff[i] = '\0';
      s += buff;
      i = 0;
    }
  ch = in.get();
  }

  if (i != 0)
  {
    buff[i] = '\0';
    s += buff;
  }
  return in;
}

九、所有代码

namespace achieveString
{
  class string
  {
  public:
  typedef char* iterator;
  const typedef char* const_iterator;

  iterator begin()
  {
    return _str;
  }
  iterator end()
  {
    return _str + _size;
  }

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

    //构造函数
    /*string()
      :_str(new char[1]{'\0'})
      ,_capacity(0)
      ,_size(0)
    { }*/
    string(const char* str = "")
      :_capacity(strlen(str))
      , _size(_capacity)
    {
      _str = new char[_capacity + 1];
      strcpy(_str, str);
    }

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

    //析构函数
    ~string()
    {
      delete[] _str;
      _str = nullptr;
      _size = _capacity = 0;
    }

    //拷贝构造
    /*string(const string& s)
    {
      _str = new char[s._capacity + 1];
      strcpy(_str, s._str);
      _size = s._size;
      _capacity = s._capacity;
    }*/

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

    //现代写法
    string(const string& s)
      :_str(nullptr)
      ,_size(0)
      ,_capacity(0)
    {
      string tmp(s._str);
      swap(tmp);
    }

    // 赋值重载
    /*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;
      }
      return *this;
    }*/
    //现代写法
    //法一
    /*string& operator=(const string& s)
    {
      if (this != &s)
      {
        string tmp(s._str);
        swap(tmp);
      }
      return *this;
    }*/
    //法二
    string& operator=(string tmp)
    {
      swap(tmp);
      return *this;
    }

    //可读可写
    char operator[](size_t pos)
    {
      assert(pos < _size);
      return _str[pos];
    }
    //只读
    const char operator[](size_t pos)const
    {
      assert(pos < _size);
      return _str[pos];
    }

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

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

    void reserve(size_t n)
    {
      if (n > _capacity)
      {
        char* tmp = new char[n + 1];
        strcpy(tmp, _str);
        delete[] _str;
        _str = tmp;
        _capacity = n;
      }
    }

    void resize(size_t n, char ch='\0')
    {
      if (n <= _size)
      {
        _str[n] = '\0';
        _size = n;
      }
      else
      {
        reserve(n);
        while (_size < n)
        {
          _str[_size] = ch;
          _size++;
        }
        _str[_size] = '\0';
      }
    }

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

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

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

    string& operator+=(const char* str)
    {
      append(str);
      return *this;
    }
    
    void 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--;
      }
      //插入数据,更新_size
      _str[pos] = ch;
      _size++;
    }
    void insert(size_t pos, const char* str)
    {
      int len = strlen(str);
      if (_size + len > _capacity)
      {
        reserve(_size + len);
      }

      //法一
      /*int end = _size;
      while (end >= (int)pos)
      {
        _str[end + len] = _str[end];
        end--;
      }
      strncpy(_str + pos, str, len);
      _size += len;*/

      //法二
      size_t end = _size+1;
      while (end > pos)
      {
        _str[end + len-1] = _str[end-1];
        end--;
      }
      strncpy(_str + pos, str, len);
      _size += len;
    }

    void erase(size_t pos, size_t len = npos)
    {
      if (len==npos || pos + len >= _size)
      {
        //有多少,删多少
        _str[pos] = '\0';
        _size = pos;
      }
      else
      {
        size_t begin = pos + len;
        while (begin <= _size)
        {
          _str[begin - len] = _str[begin];
          begin++;
        }
        _size -= len;
      }
    }
    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);
    }

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

    size_t find(const char* sub, size_t pos = 0)
    {
      const char* p = strstr(_str + pos, sub);
      if (p)
      {
        return p - _str;
      }
      else
      {
        return npos;
      }
    }

    string substr(size_t pos, size_t len = npos)
    {
      string s;
      size_t end = pos + len;
      if (len == npos || end >= _size)
      {
        len = _size - pos;
        end = _size;
      }
      
      s.reserve(len);
      for (size_t i = pos; i < end; i++)
      {
        s += _str[i];
      }

      return s;
    }
    void clear()
    {
      _str[0] = '\0';
      _size = 0;
    }
  private:
    char* _str;
    size_t _capacity;
    size_t _size;

    //const static size_t npos = -1;  // C++支持const整型静态变量在声明时给值初始化,但不建议
    //const static double npos = 1.1;  // 不支持

    const static size_t npos;
  };
  const size_t string::npos = -1;

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

    return out;
  }

  //istream& operator>>(istream& in, string& s)
  //{
  //  s.clear();
  //  char ch;
  //  //in >> ch;
  //  ch = in.get();

  //  while (ch != ' ' && ch != '\n')
  //  {
  //    s += ch;
  //    //in >> ch;
  //    ch = in.get();
  //  }
  //  return in;
  //}

  istream& operator>>(istream& in, string& s)
  {
    s.clear();

    char buff[16];
    size_t i = 0;

    char ch;
    ch = in.get();
    while (ch != ' ' && ch != '\n')
    {
      buff[i++] = ch;
      if (i == 16)
      {
        buff[i] = '\0';
        s += buff;
        i = 0;
      }
      ch = in.get();
    }

    if (i != 0)
    {
      buff[i] = '\0';
      s += buff;
    }

    return in;
  }
}


相关文章
|
2天前
|
C++ 容器
黑马c++ STL部分 笔记(2) string容器
黑马c++ STL部分 笔记(2) string容器
|
5天前
|
存储 编译器 C++
【C++】String -- 详解(下)
【C++】String -- 详解(下)
|
5天前
|
存储 JavaScript C语言
【C++】String -- 详解(上)
【C++】String -- 详解(上)
|
5天前
|
C语言 C++
从C语言到C++_13(string的模拟实现)深浅拷贝+传统/现代写法(下)
从C语言到C++_13(string的模拟实现)深浅拷贝+传统/现代写法
15 0
|
5天前
|
存储 C语言
从C语言到C++_13(string的模拟实现)深浅拷贝+传统/现代写法(中)
从C语言到C++_13(string的模拟实现)深浅拷贝+传统/现代写法
10 0
|
5天前
|
存储 编译器 测试技术
从C语言到C++_13(string的模拟实现)深浅拷贝+传统/现代写法(上)
从C语言到C++_13(string的模拟实现)深浅拷贝+传统/现代写法
13 0
|
5天前
|
机器学习/深度学习 canal NoSQL
从C语言到C++_12(string相关OJ题)(leetcode力扣)
从C语言到C++_12(string相关OJ题)(leetcode力扣)
17 0
|
5天前
|
编译器 测试技术 C语言
从C语言到C++_11(string类的常用函数)力扣58和415(下)
从C语言到C++_11(string类的常用函数)力扣58和415
6 0
|
5天前
|
存储 编译器 C语言
从C语言到C++_11(string类的常用函数)力扣58和415(中)
从C语言到C++_11(string类的常用函数)力扣58和415
8 0
|
5天前
|
存储 C语言 C++
从C语言到C++_11(string类的常用函数)力扣58和415(上)
从C语言到C++_11(string类的常用函数)力扣58和415
9 0