C++ --＞ string类模拟实现（附源码）-阿里云开发者社区

前言：

C++中STL扮演着极其重要的角色，学习C++重中之重的就是学习STL，虽然string不作为containers的其中一员，但是也是值得学习的le类。下面就进行string的模拟实现

string的模拟实现和顺序表是差不多，就是增加了C++的特性。

string 模拟实现

存储结构

结构上使用命名空间mystr进行封装，防止与库冲突，使用class封装成为对象string:

定义 _size 方便记录string的大小。
定义 _capacity方便记录string的容量大小
定义 char* _str是存储数据，进行动态new出空间
nops：npos用于表示在字符串中未找到所查找的子串，或者表示一个超出字符串长度的有效索引位置。npos的值通常被定义为std::size_t类型的最大值，这是一个无符号整数类型，因此npos实际上是一个非常大的正整数，用于表示没有找到匹配项或字符串的结束位置.

namespace mystr
{
    class string
    {
        public:
        static const size_t npos = -1;
        private:    
        size_t _size;
        size_t _capacity;
        char* _str;
    };
}

默认构造函数

构造函数

全缺省的构造函数也是默认构造函数，结尾给""常量字符串末尾存在\0;

默认构造函数：全缺省、无参、编译器默认生成的构造函数称之为默认构造函数

采取初始化列表，对于常量引用可以进行初始化。strlen计算出大小，初始化_size
2. 注意：初始化顺序就是声明的顺序，这个也是为什么将char* _str放在最后；
_capacoty初始化容量+1的目的是给\0开辟空间；

最后将str进行拷贝，这里采用memcpy不采用strcpy
3. memcpy可以将全部内容拷贝，strcpy会识别\0停止，假使字符串hello\0 world构造就不会得到我们想要的结果

string(const char* str = "")
    :_size(strlen(str))
        , _capacity(_size)
        , _str(new char[_capacity + 1])
    { 
        memcpy(_str, str, _capacity + 1);
    }

拷贝构造函数

众所周知的是当不存在拷贝构造函数，编译器会自动生成拷贝构造函数；

编译器生成的仅仅会实现数值上的拷贝（浅拷贝）
_strnew出空间，要实现内容上的拷贝（深拷贝）

_capacoty初始化容量+1的目的是给\0开辟空间；

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

赋值运算符重载

赋值预算符重载的底层逻辑是和拷贝构造函数是一样的，在这里就不过多介绍了

string& operator=(const string& s)
{

    _capacity = s._capacity;
    _size = s._size;
    _str = new char[_capacity + 1];
    memcpy(_str, s._str, _capacity + 1);

}

析构函数

程序的整个历程开辟空间，不进行空间的释放不是一个好的习惯，这里析构函数就要上场了

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

迭代器（iterator）

string的迭代器的本质就是指针，根据C语言的指针很容易就可以理解，就是将 char * 进行
typefed char* iterator
迭代器实现两个版本 const和非const，只读和可读可写

begin（）

iterator begin()
{
    return _str;
}

iterator begin()const 
{
    return _str;
}

end（）

iterator end()
{
    return _str + _size;
}

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

容量（capacity）

size

mstr::string类定义了_size直接将其返回

size_t size()const
{
return _size;
}

capacity

mstr::string类定义了_capacity直接将其返回

size_t capacity() const
{
    return _capacity;
}

resize

resize是将后面指定大小初始化指定的字符（缺省：\0）
进行容量的检查，不够扩容
一层循环初始化为ch
修改_size长度为n

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

        for (size_t i = _size; i < n; i++)
        {
            _str[i] = ch;
        }

        _str[_size] = '\0';
        _size = n;
    }

}

reverse

由于很多地方进行复用，需要在函数内部进行判断提高效率
开辟一个大于原始空间的新的空间，将 _str拷贝过去，改变_str的指向，将新开辟的空间释放谨防内存泄漏

void reverse(size_t n)
{
    if (n > _capacity)
    {
        char* tmp = new char[n + 1];
        memcpy(tmp, _str, _capacity + 1);

        delete[] _str;
        _capacity = n;
        _str = tmp;
    }

}

empty

直接判断_size是否为0即可

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

clear

直接将首位置赋值为\0，修改_size大小即可

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

修改（modify）

push_back

C++string中 push_back 函数声明：void push_back (char c);在字符串后追加一个字符；

开始要检查容量进行扩容这里用 reverse 实现

由于一个字符，仅仅需要在_size位置上直接赋值，在_size+1的位置上赋值\0

 void push_back(char ch)
{
    if (_size == _capacity)
    {
        reverse(_capacity == 0 ? 4 : _capacity * 2);
    }

    _str[_size] = ch;
    _str[_size + 1] = '\0';
    _size++;
}

append

append后面追加一个字符可以进行复用 push_back
append后面追加一个字符串和添加一个string类是一样的思路是一样；

//追加一个字符
void append(const char ch)
{
push_back(ch);
}
//追加一个字符串
void append(const char* str)
{
size_t len = strlen(str);
if (_size + len > _capacity)
{
reverse(_capacity + len);
}
memcpy(_str + _size, str, len + 1);
}
//追加一个string类
void append(const string& str)
{
if (_size + str._size == _capacity)
{
reverse(_size + str._size);
}

memcpy(_str + _size, str._str, str._size+1);
}

operator+=

由于是实现了append实现运算符重载就方便跟多，功能一样，结果一样直接进行复用

//追加一个字符
string& operator+= (const char* str)
{
    append(str);

    return *this;
}
//追加一个字符串
string& operator+= (const string& str)
{
    append(str._str);

    return *this;
}
//追加一个string类
string& operator+= (char ch)
{
    push_back(ch);
    return *this;
}

inset

实现两个版本，插入字符和插入字符串
string类是没有实现push_front头插入，insert就有很大的作用了在pos位置进行插入
首先进行pos位置的断言，保证pos在字符串的有效位置
进行容量检查，进行扩容.

将pos位置后面的字符（以及pos位置）依次向后面移len个长度，在pos位置插入字符（字符串）
i!= npos在for循环中如果i变成了0，之后再去减1 ，size_t下的-1会变为无线大，会陷入死循环。
最后不要忘记将_size进行修改

//插入字符
string& insert(size_t pos, char c)
{
    assert(pos < _size);

    if (_capacity == _size)
    {
        reverse(_size+1);
    }

    for (size_t i = _size; i >= pos&& i!= npos; i--)
    {
        _str[i + 1] = _str[i];
    }
    _str[pos] = c;
    _size++;

    return *this;
}
//插入字符串
string& insert(size_t pos, const char* str)
{
    assert(pos < _size);
    size_t len = strlen(str);
    if (_capacity == _size)
    {     
        reverse(_size + len);
    }

    for (size_t i = _size; i >= pos&& i!= npos; i--)
    {
        _str[i + len] = _str[i];

    }
    memcpy(_str + pos, str, len);
    _size+=len;

    return *this;

}

erase

首先进行pos位置的断言，保证pos在字符串的有效位置
erase是在pos位置删除len个字符（缺省值：npos）
函数主体进入进len的判断，如果len == npos 或 pos + len >= _size超出字符串的长度，就是从pos后全部删除
否则没有超过将pos + len位置后面的数据将 pos位置移动直至移动到\0

string& erase(size_t pos, size_t len = npos)
{
    assert(pos < _size);
    if (len == npos || pos + len >= _size)
    {
        _str[pos] = '\0';
        _size = pos;

    }
    else
    {
        size_t end = pos + len;

        while (end <= _size)
        {
            _str[pos++] = _str[end++];
        }

        _size -= len;
    }

}

swap

利用C++库中的swap进行string类的交换

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

元素访问（Element access）

operator [ ]

实现const和非const两种，只读和可读可改
充分利用字符串特性可以进行下标的访问

//const
char& operator[](size_t index)
{
    assert(index < _size);

    return _str[index];
}
//nonconst
const char& operator[](size_t index)const
{
    assert(index < _size);

    return _str[index];
}

字符串操作（String operations）

c_str

直接返回_str

const char* c_str()
{
    return _str;
}

find

首先进行pos位置的断言，保证pos在字符串的有效位置
字符串查找利用C语言中的strstr函数进行查找
返回下面的下标，利用指针减指针的方法，没有找到返回npos

size_t find(const char* s, size_t pos = 0) const
{
    assert(pos < _size);
    char* p = strstr(_str, s);

    if (p)
    {
        return p - _str;
    }
    else
    {
        return npos;
    }

}

关系运算符(relational operators)

进行比较的重载

实现< ==其他的进行复用即可

使用memcpy进行比较，比较字符串较小的那个_size < s._size ?_size : s._size
返回为 0 返回比较长（_size < s._size）的那个否则返回假（ ret < 0）

//重载<
bool operator<(const string& s)
{
    int ret = memcmp(_str, s._str, (_size < s._size ?_size : s._size));

    return ret == 0 ? _size < s._size : ret < 0;
}
//重载==
bool operator==(const string& s)
{
    return _size == s._size && memcmp(_str, s._str, _size);
}
//重载<=
bool operator<=(const string& s)
{
    return !(*this > s);
}
//重载>
bool operator>(const string& s)
{
    return !(*this <= s);
}
//重载>=
bool operator>=(const string& s)
{
    return !(*this < s);
}
//重载!=
bool operator!=(const string& s)
{
    return !(*this == s);
}

流提取和插

operator<<

这个函数是写在类外面的一个友元函数
使用范围for进行实现

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

operator>>

s.clear();这句话是清理缓冲区上次cin的残留
第一个while循环是处理缓冲区的空格
创建一个数组，避免多次开辟空间，直至大小到128拷贝会加到string s 中
最后的if语句是字符遇见空格或者换行结束，末尾添加\0

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

    char ch = in.get();
    // 处理前缓冲区前面的空格或者换行
    while (ch == ' ' || ch == '\n')
    {
        ch = in.get();
    }
    char buff[128];
    int i = 0;

    while (ch != ' ' && ch != '\n')
    {
        buff[i++] = ch;
        if (i == 127)
        {
            buff[i] = '\0';
            s += buff;
            i = 0;
        }

        ch = in.get();
    }

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

    return in;
}

`mystr:: string` 源码

#pragma once

#include<iostream>

#include<string.h>
#include <assert.h>
#include <stdlib.h>

using namespace std;


namespace mystr
{
  class string
  {
    friend ostream& operator<<(ostream& _cout, const mystr::string& s);

    friend istream& operator>>(istream& _cin,mystr::string& s);
  public:
    typedef char* iterator;
    typedef const char* const_iterator;


    string(const char* str = "")
      :_size(strlen(str))
      , _capacity(_size)
      , _str(new char[_capacity + 1])
    { 
      memcpy(_str, str, _capacity + 1);
    }
    //析构函数
    ~string()
    {
      _size = 0;
      _capacity = 0;
      delete[] _str;
      _str = nullptr;
    }
    // 拷贝构造函数
    string(const string& s)
    {
      _capacity = s._capacity;
      _size = s._size;
      _str = new char[s._capacity+1];
      memcpy(_str, s._str, _capacity+1);
    }
    //赋值预算符重载
    string& operator=(const string& s)
    {

      _capacity = s._capacity;
      _size = s._size;
      _str = new char[_capacity + 1];
      memcpy(_str, s._str, _capacity + 1);

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

    //迭代器
    iterator begin()
    {
      return _str;
    }
    iterator end()
    {
      return _str + _size;
    }
    iterator begin()const 
    {
      return _str;
    }
    iterator end()const
    {
      return _str + _size;
    }
    
    //capacity

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

    void reverse(size_t n)
    {
      if (n > _capacity)
      {
        char* tmp = new char[n + 1];
        memcpy(tmp, _str, _capacity + 1);

        delete[] _str;
        _capacity = n;
        _str = tmp;
      }

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

        for (size_t i = _size; i < n; i++)
        {
          _str[i] = ch;
        }

        _str[_size] = '\0';
        _size = n;
      }

    }

    bool empty()const
    {
      return _size == 0 ? true : false;
    }
    
    //access

    //modify
    
    void push_back(char ch)
    {
      if (_size == _capacity)
      {
        reverse(_capacity == 0 ? 4 : _capacity * 2);
      }

      _str[_size] = ch;
      _str[_size + 1] = '\0';
      _size++;
    }

    void append(const char ch)
    {
      push_back(ch);
    }
    void append(const char* str)
    {
      size_t len = strlen(str);
      if (_size + len > _capacity)
      {
        reverse(_capacity + len);
      }
      memcpy(_str + _size, str, len + 1);
    }

    void append(const string& str)
    {
      if (_size + str._size == _capacity)
      {
        reverse(_size + str._size);
      }

      memcpy(_str + _size, str._str, str._size+1);
    }


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

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

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

    void clear()
    {
      _str[0] = '\0';
      _size = 0;
    }
    void swap(string& s)
    {
      string tmp(s);
      std::swap(_str, tmp._str);
      std::swap(_size, tmp._size);
      std::swap(_capacity, tmp._capacity);
    }
    //relational operators
    bool operator<(const string& s)
    {
      int ret = memcmp(_str, s._str, (_size < s._size ?_size : s._size));

      return ret == 0 ? _size < s._size : ret < 0;
    }

    bool operator==(const string& s)
    {
      return _size == s._size && memcmp(_str, s._str, _size);
    }

    bool operator<=(const string& s)
    {
      return !(*this > s);
    }


    bool operator>(const string& s)
    {
      return !(*this <= s);
    }

    bool operator>=(const string& s)
    {
      return !(*this < s);
    }

    bool operator!=(const string& s)
    {
      return !(*this == s);
    }

    // 返回c在string中第一次出现的位置

    size_t find(char c, size_t pos = 0) const
    {
      assert(pos < _size);

      for (size_t i = pos; i < _size; i++)
      {
        if (_str[i] == c)
        {
          return i;
        }
      }

      return npos;
    }


    // 返回子串s在string中第一次出现的位置

    size_t find(const char* s, size_t pos = 0) const
    {
      assert(pos < _size);
      char* p = strstr(_str, s);

      if (p)
      {
        return p - _str;
      }
      else
      {
        return npos;
      }
    
    }

    // 在pos位置上插入字符c/字符串str，并返回该字符的位置

    string& insert(size_t pos, char c)
    {
      assert(pos < _size);

      if (_capacity == _size)
      {
        reverse(_size+1);
      }

      for (size_t i = _size; i >= pos; i--)
      {
        _str[i + 1] = _str[i];
      }
      _str[pos] = c;
      _size++;
    
      return *this;
    }

    string& insert(size_t pos, const char* str)
    {
      assert(pos < _size);
      size_t len = strlen(str);
      if (_capacity == _size)
      {     
        reverse(_size + len);
      }

      for (size_t i = _size; i >= pos; i--)
      {
        _str[i + len] = _str[i];

      }
      memcpy(_str + pos, str, len);
      _size+=len;

      return *this;
    
    }

    string& erase(size_t pos, size_t len = npos)
    {
      assert(pos < _size);

      if (_capacity == _size)
      {
        reverse(_size + len);

      }
      if (len == npos || pos + len >= _size)
      {
        _str[pos] = '\0';
        _size = pos;

      }
      else
      {
        size_t end = pos + len;

        while (end <= _size)
        {
          _str[pos++] = _str[end++];
        }

        _size -= len;
      }
    
    }

  private:    
    size_t _size;

    size_t _capacity;
    char* _str;

    public:

    
    const static size_t npos;
  };

  const size_t string::npos = -1;
  
  ostream& operator<<(ostream& out, const mystr::string& s)
  {
    for (auto ch : s)
    {
      out << ch;
    }
    return out;
  }

  istream& operator>>(istream& in, string& s)
  {
    //清除缓冲区
    s.clear();

    char ch = in.get();

    while (ch == ' ' || ch == '\n')
    {
      ch = in.get();
    }

    char buff[128];
    int i = 0;

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

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

    return in;

  }

}

C++ --＞ string类模拟实现（附源码）

前言：