【C++ STL】模拟实现 string

花瓣小跑 · 2024-6-13 19:49:52

标题：【C++ :: STL】手撕 STL _string

@水墨不写bug

（图片来源于网络）

         C++标准模板库（STL）中的string是一个可变长的字符序列，它提供了一系列操作字符串的方法和功能。
    本篇文章，我们将模拟实现STL的string类的部分功能，以增强对STL的熟练度，相识STL容器的工作原理，积聚项目履历，也为将来自主实现和改造容器奠定坚固的基础。
STL的string类是一个模板，而我们为了方便实现，以达到练习的目标，我们临时先实现一个成员变量为（下图示）的string类。

char* _str;
size_t _size;//字符串长度，不加上\0
size_t _capacity;

复制代码

C++ STL的string类提供了以下常用的成员函数和接口：

构造函数和赋值操作函数接口：
- 默认构造函数：创建一个空字符串。
- 带string参数的构造函数：将一个string对象复制到另一个string对象中。
- 带字符数组参数的构造函数：将字符数组转换为string对象。
- 带整数参数的构造函数：将整数转换为字符串。
- 赋值操作符：用另一个string对象、字符数组或字符来赋值。
访问字符串内容相关函数接口：
- at()：返回指定位置的字符。
- operator[]：返回指定位置的字符。
- front()：返回第一个字符。
- back()：返回末了一个字符。
- c_str()：返回一个以空字符末端的字符数组。
修改字符串内容接口：
- insert()：在指定位置插入字符、字符串或字符数组。
- erase()：删除指定位置的字符。
- replace()：更换指定位置的字符串或字符。
- append()：在字符串末尾添加字符、字符串或字符数组。
- clear()：清空字符串。
字符串操作接口：
- size() 或 length()：返回字符串的长度。
- empty()：判断字符串是否为空。
- find()：查找指定字符串或字符的位置。
- substr()：返回指定位置和长度的子字符串。
- compare()：比力两个字符串

（具体用法在上一篇讲解：【Cpp::STL】标准模板库_ string详解）

（一）头文件

我们在C语言阶段实现声明和定义分离的时间，只是单一的把函数的定义放在.c（源）文件，把函数的声明，头文件的包罗，宏定义等放在.h（头）文件。
但是，在C++，不光要服从以上的规则，由于类的出现，必要域作用限定符（：：）来限定方位；由于成员的访问权限的出现，必要思量访问权限的问题；此外差别范例的成员的定义的位置也有讲究，比如静态成员尽量不要直接定义在头文件中，由于这会引发多次包罗多文件在链接时的头文件内的对象的重定义问题。
本文根据STL标准模板库的功能，给出头文件，包括string类的定义，众多成员函数，部分非成员函数（流插入，流提取的重载），并在后半节具体讲解各个函数的实现思绪。

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<iostream>
#include<cstring>
#include<cassert>
using namespace std;
namespace ddsm
{
class string
{
friend ostream& operator<<(ostream& out, const string& s1);
public:
//迭代器
typedef char* iterator;
typedef const char* const_iterator;
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
//传参构造,默认构造，给默认值为空串，巧妙
string(const char* str = "");
string(const string& s);//copy constructor
//string& operator=(const string& s);传统写法
string& operator=(const char* s);
string& operator=(string s);//现代写法
//析构
~string();
//C类型字符串
const char* c_str() const;
//保留
void reserve(int n);
string& push_back(const char ch);//尾插字符
string& append(const char* str);//尾插字符串
string& operator+=(char ch);
string& operator+=(const char* str);
string& insert(size_t pos, const char ch);
string& insert(size_t pos, const char* str);
//缺省值代表最一般的情况
string& erase(size_t pos = 0,size_t len = npos);
//找一个字符
size_t find(const char ch, size_t pos = 0);
//找一个子串
size_t find(const char* str, size_t pos = 0);
void swap(string& s);
string substr(size_t pos = 0,size_t len = npos);
string& clear();
private:
char* _str;
size_t _size;//字符串长度，不加上\0
size_t _capacity;
//特例，const静态整形对象可声明定义和一,但是可能造成链接时的错误
static size_t npos;
};
istream& operator>>(istream& in, string& s);
};

复制代码

（二）string类的功能实现

（1）默认成员函数

i，构造函数

我们知道，构造函数的作用是在对象实例化时初始化对象，对于string类对象，含有三个基本成员变量：

char* _str;
size_t _size;//字符串长度，不加上\0
size_t _capacity;

复制代码

经太过析，我们得知在构造函数内部，必要申请动态的堆区空间给_str;必要根据_str的长度变化来动态更新_size；同时根据申请的动态空间的长度来更新_capacity。
于是，我们理所当然的想到这样写构造函数：

string::string(const char* str = "")
// 缺省参数为一个空字符串，如果不传参，空字符串就是一个单独的'\0'
:_size(strlen(str))
,_capacity(strlen(str))
{
_str = new char[_size + 1];
strcpy(_str, str);
}

复制代码

但是，这种简朴易懂的写法也袒露出了毛病：多次无意义的重复调用strlen，这会造成额外的消耗。于是，为了淘汰strlen的调用次数，我们思量这样修改:

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

复制代码

这样修改虽然办理了strlen重复无意义调用的问题，但是也带来了新的问题：
步伐稳定性下降的问题：
￥￥我们知道：初始化列表的初始化次序是成员函数在类中的声明次序：按照此例：

char* _str;
size_t _size;//字符串长度，不加上\0
size_t _capacity;

复制代码

先初始化_size,再初始化_capacity；在这种背景下，如果代码有一些微小的改变，或许就会造成意想不到的问题。
如果改变成员变量的次序，那么初始化列表就会按照差别的次序初始化。具体来说，如果_capacity在_size之前，初始化列表就会先初始化_capacity：

char* _str;
size_t _capacity;
size_t _size;//字符串长度，不加上\0

复制代码

这时_size还没有初始化，是随机值，那么就造成了_capacity为随机值的问题。
办理这个问题着实很简朴，将对_capacity的初始化放入函数体：

string::string(const char* str)
//strlen较低效，调用一次用size记录返回值
//size/capacity不包含\0，但是其需要存储
:_size(strlen(str))
{
_str = new char[_size + 1];
_capacity = _size;
strcpy(_str, str);
}

复制代码

这样就确定了是先初始化_size,再初始化_capacity。￥￥

    （将声明和定义分离，必要将缺省参数放在声明处，同时函数名之前必要加上域作用限定符，表示这个函数在你实现的string类里面声明过。）
  ii，析构函数

   析构函数的作用是：清理资源。
  由于比力简朴，这里直接给出实现：

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

复制代码

（函数名之前必要加上域作用限定符，表示这个函数在你实现的string类里面声明过。）
  iii，拷贝构造

   拷贝构造，完成创建对象时的初始化。
  一样平常环境下，我们会这样写：

//拷贝构造
string::string(const string& s)
{
char* tem = new char[s._capacity+1];//多开一个，存储'\0'
strcpy(tem, s._str);
delete[] _str;//销毁原空间
_str = tem;
_size = s._size;
_capacity = s._capacity;
}

复制代码

但是，着实有更简朴的写法：

void string::swap(string& s)
{
//调用模板swap交换内置类型，损失不大
std::swap(_str, s._str);
std::swap(_capacity, s._capacity);
std::swap(_size, s._size);
}
//拷贝构造的现代写法
string::string(const string& s)
:_str(nullptr)
{
string tem(s._str);
swap(tem);
}

复制代码

仔细分析，我们着实在无形之中让构造函数给我们“打工”了：

string tem(s._str);

复制代码

就是用拷贝对象的字符串来构造一个tem对象，而这个tem对象就是我们必要的，所以我们实现一个swap函数，将*this与tem完全交换，同时tem在出作用域时也会主动析构，同样也达到了拷贝构造的目标。
iv，赋值重载

赋值重载：实现对象之间的赋值。
我们一样平常会这样实现：

//赋值重载
string& string::operator=(const char* s)
{
int len = strlen(s);
char* tem = new char[len + 1];
strcpy(tem, s);
delete[] _str;
_str = tem;
_size = _capacity = len;
return *this;
}

复制代码

但是，同样也有更简朴的写法：

void string::swap(string& s)
{
//调用模板swap交换内置类型，损失不大
std::swap(_str, s._str);
std::swap(_capacity, s._capacity);
std::swap(_size, s._size);
}
//赋值重载的现代写法
string& string::operator=(string tem)
{
//自动调用拷贝构造
swap(tem);
//出作用域自动完成析构
return *this;
}

复制代码

在无形之中，我们让拷贝构造为我们“打工”。
  我们通过传值传参，拷贝构造一个临时对象tem，这个tem就是我们必要的，所以完全交换*this就得到了构造的对象，同时tem出作用域也会主动析构。
  （2）迭代器

          对于迭代器，本质上是一个指针，也可以是一个类（对指针的封装），在这里，我们不妨用指针来作为迭代器：

//声明：
typedef char* iterator;
typedef const char* const_iterator;
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;

复制代码

//定义
string::iterator string::begin()
{
return _str;
}
string::const_iterator string::begin() const
{
return _str;
}
string::iterator string::end()
{
return _str + _size;
}
string::const_iterator string::end() const
{
return _str + _size;
}

复制代码

const迭代器用于const对象调用；平凡迭代器用于平凡迭代器调用。
  平凡迭代器可读可写，const迭代器只可读不可写。
  （3）容量和长度

  i.reserve()

    改变string的容量，若要求值n大于现在的容量，则容量扩大到n；若要求值小于便是现有容量，则改变容量。
    reserve对于size没有影响，不会改变string的内容。
  实现如下：

//保留指定容量,容量只增不减
void string::reserve(int n)
{
//要求保留的大于现有容量,需要扩容
if (n > _capacity)
{
char* tem = new char[n + 1];
// 申请新空间完毕,转移数据
strcpy(tem, _str);
delete[] _str;
_str = tem;
_capacity = n;
//reserve不改变size
}
}

复制代码

ii,resize()

//resize()不改变capacity，可能改变size
void string::resize(int size,int ch)
//size为设定值，_size为现有值
{
if (size < _size)
{
_size = size;
_str[size] = '\0';
}
else if (size > _size)
{
if (size > _capacity)
{
reserve(size);
}
int i = _size;
while (i != size)
{
_str[i++] = '\0';
}
_size = size;
_str[_size] = '\0';
}
}

复制代码

如果设定值小于现有值，减小_size，相当于截断_str；
    如果设定值便是现有值，不做处理；
    如果设定值大于现有值，有三种环境：
    size <_capacity: 不扩容，并在[ _size,size)之间补0；
    size == _capacity: 不扩容，并在[ _size,size)之间补0；
    size > _capzcity: 扩容，并在[ _size,size)之间补0；
  （4）元素访问

  i,operator[]

    下标的随机访问：

//声明
char& operator[](size_t pos);
const char& operator[](size_t pos) const;

复制代码

//定义
char& string::operator[](size_t pos)
{
assert(pos >= 0 && pos < _size);
return _str[pos];
}
const char& string::operator[](size_t pos) const
{
assert(pos >= 0 && pos < _size);
return _str[pos];
}

复制代码

对于at，front，back可以复用operator[]来实现。
（5）修改方式

i,push_back()

实现尾插字符，实现如下：

//尾插字符,由于是一个一个插入，扩容不能太频繁，所以采用二倍扩容
string& string::push_back(const char ch)
{
if (_size == _capacity)
//不一定需要扩容，若长度等于容量，再次插入需要扩容
{
int Newcapacity = _capacity == 0 ? 4 : 2 * _capacity;
reserve(Newcapacity);
}
//扩容完毕，尾插字符
_str[_size++] = ch;
_str[_size] = '\0';
return *this;
}

复制代码

这里使用了一个扩容本领，就是二倍扩容。
ii，append()

追加，这里简化为追加一段字符串。

//尾插字符串，直接reserve到指定长度字符串
string& string::append(const char* str)
{
int len = strlen(str);
if (len + _size > _capacity)
{
reserve(len + _size);//不改变size
}
//扩容完毕
strcpy(_str + _size, str);
_size += len;
return *this;
}

复制代码

起首要先保存原来的len，这样如果必要扩容，在扩容完毕之后，只需更新_size为原_size+=len即可。
    否则，如果不保存len，在必要扩容的环境下，就会出现问题了：
  ##
  （）
  ##
  iii，operator+=复用上两函数即可

          尾插一个字符

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

复制代码

尾插一个字符串

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

复制代码

iv，insert()

在恣意位置插入一个字符

//插入一个字符
//用push_back逻辑来扩容
string& string::insert(size_t pos, const char ch)
{
assert(pos >= 0 && pos <= _size);
if (_size == _capacity)
{
int Newcapacity = _capacity == 0 ? 4 : 2 * _capacity;
reserve(Newcapacity);//不改变size
}
int end = _size+1;
//细节问题，int与size_t参与比较，
//int隐式类型转化为size_t
//size_t(-1)会变成很大的整数
while(end>pos)
{
_str[end] = _str[end-1];
--end;
}
_str[pos] = ch;
_size += 1;
return *this;
}

复制代码

在恣意位置插入一个字符串

//插入一个字符串
//用reserve逻辑扩容
string& string::insert(size_t pos, const char* str)
{
assert(pos >= 0 && pos <= _size);
int len = strlen(str);
if (len + _size > _capacity)
{
reserve(len+_size);
}
int end = _size + len;
while (end>pos+len-1)
{
_str[end] = _str[end - len];
--end;
}
memmove(_str + pos, str, len);
_size += len;
return *this;
}

复制代码

v,erase()

在恣意位置处删除长度为len的字符串：

string& string::erase(size_t pos, size_t len)
//两种情况；删除部分string，pos之后全删
{
assert(pos >= 0 && pos <= _size);
if ((len == npos) ||(pos + len >= _size))//全删的情况
{
_str[pos] = '\0';
_size = pos;
}
else
//删除部分string
{
int end = pos + len;
while (_str[end]!='\0')
{
_str[end - len] = _str[end];
++end;
}
_str[end-len] = '\0';
}
return *this;
}

复制代码

（6）串操作

i,find()

找字符

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

复制代码

找字符串
用到了strstr（）：字符串匹配函数。

size_t string::find(const char* str, size_t pos)
{
char* ret = strstr(_str, str);
return (size_t)(ret - _str);
}

复制代码

ii,c_str()

返回C范例的字符串：

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

复制代码

iii，substr()

得到字符串的子串：

string string::substr(size_t pos, size_t len)
{
assert(pos >= 0 && pos <= _size);
if ((len == npos) || (pos + len >= _size))
{
string sub(_str + pos);
return sub;
}
else
{
string sub;
sub.reserve(len);
for (size_t i = 0; i < len; ++i)
{
sub._str[i] = _str[pos + i];
}
sub._str[len] = '\0';
sub._size =sub._capacity = len;
return sub;
}
}

复制代码

（7）成员常量

//特例，const静态整形对象可声明定义和一,但是可能造成链接时的错误
const static size_t npos = -1;

复制代码

无符号整数size_t(-1)是一个很大的整数。
（8）流插入和流提取

i,operator<<()

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

复制代码

ii,operator>>()

cin的get（）函数可以提取空白字符和‘\n’，这也是循环逻辑竣事的条件。

//流提取改进，用buf临时数组，防止string频繁扩容
istream& operator>>(istream& in,string& s)
{
s.clear();
char buff[128] = { 0 };
char ch = in.get();
int i = 0;
while(ch != ' ' && ch != '\n')
{
buff[i++] = ch;
ch = in.get();
if (i == 127)
{
buff[i] = '\0';
s += buff;
i = 0;
}
}
buff[i] = '\0';
if (i != 0)
{
s += buff;
}
return in;
}

复制代码

整体使用了用临时栈区数组的方式来淘汰扩容次数，进步效率。

完~

未经作者同意禁止转载

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

		自动登录	找回密码
密码			立即注册

【C++ STL】模拟实现 string

本帖子中包含更多资源

0 个回复

快速回复

楼主热帖

标签云