STL中string的模拟实现
目录
1.string类的总体设计
string类中有四个成员变量分别是：
- _str：指向当前字符串
- _size：记录有效元素的个数
- _capacity：记录容量大小
- npos：表示一个很大的无符号整数
其他的成员函数都是在成员变量的基础上进行操作。
string类的设计总览（string.h）：
namespace dw // 防止命名冲突
{
class string
{
public:
/* 迭代器 */
typedef char* iterator; // 定义非const版本的迭代器类型
typedef const char* const_iterator; // 定义const版本的迭代器类型
iterator begin() { return _str; } // 返回非const版本的指向第一个有效元素的迭代器
iterator end() { return _str + _size; } // 返回非const版本的指向最后一个有效元素的后一个位置的迭代器
const_iterator begin() const { return _str; } // 返回const版本的指向第一个有效元素的迭代器
const_iterator end() const { return _str + _size; } // 返回const版本的指向最后一个有效元素的后一个位置的迭代器
/*四个特殊的成员函数*/
string(const char* str = ""); // 默认构造函数
string(const string& s); // 拷贝构造函数
string& operator=(string s); // 赋值运算符重载函数
~string(); // 析构函数
/* 增 */
void insert(size_t pos, char ch); // 在指定位置插入一个字符
void insert(size_t pos, const char* str); // 在指定位置插入一个C风格的字符串
void push_back(char ch); // 尾插
void append(const char* str); // 追加字符串
string& operator+=(char ch); // += 一个字符
string& operator+=(const char* str); // += 一个C风格的字符串
/* 删 */
void erase(size_t pos, size_t len = npos); // 从指定位置删除指定长度的字符串
void clear(); // 清空字符串
/* 查 */
size_t find(char ch, size_t pos = 0); // 从指定位置查找指定字符（默认从0下标开始找）
size_t find(const char* str, size_t pos = 0); // 从指定位置查找指定字符串（默认从0下标开始找）
/* 改 */
const char& operator[](size_t pos) const; // 重载const版本的[]
char& operator[](size_t pos); // 重载非const版本的[]
/* 容量相关操作 */
bool empty() const { return 0 == _size; } // 判断是否为空
size_t size() const { return _size; } // 返回有效元素的个数
size_t capacity() const { return _capacity; } // 返回容量大小
void resize(size_t newSize, char c = '\0'); // 改变 _size
void reserve(size_t n); // 改变 _capacity（不缩容）
/* 其他操作 */
void swap(string& s); // 交换两个字符串
string substr(size_t pos = 0, size_t len = npos); // 从指定位置提取指定长度的子串
const char* c_str() const { return _str; } // 返回C风格的字符串
private:
size_t _capacity = 0; // 记录容量大小
size_t _size = 0; // 记录有效元素的个数
char* _str = nullptr; // 指向当前字符串
const static size_t npos = -1; // 无符号整数类型的-1表示成2进制为32位全1，是一个非常大的整数
};
istream& operator>>(istream& in, string& s); // 重载流提取
ostream& operator<<(ostream& out, const string& s); // 重载流插入
}2.string类的迭代器的模拟实现
string的底层空间是连续的，而迭代器模仿的是指针的行为，所以char*类型的指针可以直接作为string的迭代器使用。
/* 迭代器 */
typedef char* iterator; // 定义非const版本的迭代器类型
typedef const char* const_iterator; // 定义const版本的迭代器类型
iterator begin() { return _str; } // 返回非const版本的指向第一个有效元素的迭代器
iterator end() { return _str + _size; } // 返回非const版本的指向最后一个有效元素的后一个位置的迭代器
const_iterator begin() const { return _str; } // 返回const版本的指向第一个有效元素的迭代器
const_iterator end() const { return _str + _size; } // 返回const版本的指向最后一个有效元素的后一个位置的迭代器
3.四个特殊的成员函数的模拟实现
构造函数
无参的默认构造函数：当我们定义一个空串时，空串表示有效字符个数为零的串，但是字符串末尾的结束标志 '\0' 是要有的，所以我们可以申请一个字节大小的空间用来存放 '\0'。
string()
:_str(new char[1])
,_size(0)
,_capacity(0)
{
_str[0] = '\0';
}带缺省值的默认构造函数：缺省值为空串，空串末尾自带 '\0'。
- 值得注意的是，开辟空间的时候需要多开一个字节用来存放 '\0'。
string(const char* str = "")
{
_size = strlen(str);
_capacity = _size;
_str = new char[_capacity + 1];
strcpy(_str, str);
}注意：上面两种构造函数都时不需要传参即可调用的构造函数，所以不能同时存在，否则编译器不知道调用哪一个。
拷贝构造函数
传统写法：根据被拷贝的对象动态开辟资源，构造出当前对象。
- 注意：string类中涉及到资源的管理，资源的拷贝需要按照深拷贝的方式给出。
// 传统写法
string(const string& s)
{
_str = new char[s._capacity + 1]; // 动态开辟资源，避免浅拷贝问题
strcpy(_str, s._str);
_size = s._size;
_capacity = s._capacity;
}现代写法： 复用带缺省值的构造函数构造出一个临时的string对象，复用string的交换函数将临时对象和当前对象交换。
// 现代写法
string(const string& s)
{
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;
}现代写法：参数类型还是引用类型，参数对象还是被赋值的对象，利用该对象的拷贝构造函数构造出一个临时变量tmp，然后复用交换函数交换tmp和当前对象。
- 巧妙的地方是不需要手动释放原来的资源，当tmp对象销毁的时候，自动调用析构函数，销毁的是赋值对象原来的值。
string& operator=(const string& s)
{
if (this != &s)
{
string tmp(s);
swap(tmp);
}
return *this;
}现代写法的优化版本：现代写法需要构造出一个临时对象暂存被赋值对象的资源，而传值传参时，形参就是实参的一份拷贝，所以我们可以将参数传递设置为传值传参，然后交换参数对象和当前对象的值。
string& operator=(string s)
{
swap(s);
return *this;
}析构函数
因为string类中涉及资源的管理，需要手动释放资源，所以析构函数需要显示给出。
~string()
{
delete[] _str;
_str = nullptr;
_size = 0;
_capacity = 0;
}4.string类的增删改查
string类的增操作
在指定位置插入一个字符：
void insert(size_t pos, char ch)
{
assert(pos <= _size);
if (_size == _capacity) // 判断是否需要扩容
{
size_t newCapacity = _capacity == 0 ? 4 : _capacity * 2;
reserve(newCapacity);
}
size_t end = _size + 1;
while (end > pos) // 从结束标志'\0'开始挪动，
{
_str[end] = _str[end - 1]; // 当end == pos+1的时候，移动的就是pos位置的值。
--end;
}
_str[pos] = ch;
_size++;
}在指定位置插入一个C风格的字符串：和插入字符串同理，将指定位置后面的数据进行挪动，空出能够存放数据的空间，然后将数据拷贝过来即可。
void insert(size_t pos, const char* str)
{
assert(pos <= _size);
size_t len = strlen(str); // 计算插入字符串的长度
if (_size + len > _capacity) // 判断是否需要扩容
{
reserve(_size + len);
}
int end = _size; // 从'\0'的位置开始挪动数据
while (end >= (int)pos) // 强转pos为int类型，避免隐式类型转换导致的死循环
{
_str[end + len] = _str[end];
--end;
}
strncpy(_str + pos, str, len); // 拷贝指定长度的字符到指定位置
_size += len; // 不要忘记这一步哦
}尾插：在尾部插入一个字符。
void push_back(char ch)
{
if (_size == _capacity) // 判断是否需要扩容
{
size_t newCapacity = _capacity == 0 ? 4 : _capacity * 2;
reserve(newCapacity);
}
_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;
}+= 一个字符：相当于尾插一个字符，复用push_back即可。
string& operator+=(char ch)
{
push_back(ch);
return *this;
}+= 一个C风格的字符串：相当于追加一个字符串，复用append即可。
string& operator+=(const char* str)
{
append(str);
return *this;
}string类的删操作
从指定位置删除指定长度的字符串：
void erase(size_t pos, size_t len = npos)
{
assert(pos < _size);
if (len == npos || pos + len >= _size) // 需要删除的长度超过剩余字符的长度
{
_str[pos] = '\0';
_size = pos;
}
else
{
strcpy(_str + pos, _str + pos + len);
_size -= len;
}
}清空字符串：
void clear()
{
_size = 0;
_str[0] = '\0';
}string类的查操作
从指定位置查找指定字符（默认从0下标开始找）：找到了就返回下标，没找到就返回npos。
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;
}从指定位置查找指定字符串（默认从0下标开始找）：复用strstr实现，找到了返回第一个字符出现的下标，没找到返回npos。
size_t find(const char* str, size_t pos = 0)
{
const char* ptr = strstr(_str + pos, str);
if (ptr == nullptr)
{
return npos;
}
else
{
return ptr - _str;
}
}string类的改操作
string类的修改操作可以借助find和重载的 [ ] 来实现。如果使用find来实现，find返回的是下标，通过下标我们就能修改改位置的字符了。接下来讲解string类的 [ ] 的重载。
string类重载的[ ]：因为string的底层空间是连续的，所以我们可以重载[ ]运算符。返回值为对应位置的引用，此时就相当于我们拿到了改位置的值，如果该对象不是const修饰的，我们就能对其进行修改了。
// const版本的[]
const char& operator[](size_t pos) const
{
assert(pos <= _size);
return _str[pos];
}
// 非const版本的[]
char& operator[](size_t pos)
{
assert(pos <= _size);
return _str[pos];
}5.容量相关操作
判断是否为空：如果有效元素的个数为0则为空。
bool empty()const
{
return 0 == _size;
} 返回有效元素的个数：_size记录的就是有效元素的个数。
size_t size()const
{
return _size;
}返回容量的大小：_capacity记录的就是容量的打下。
size_t capacity()const
{
return _capacity;
} 改变_capacity：
void reserve(size_t n)
{
if (n > _capacity) // 当n <= _capacity的时候不需要进行操作
{
char* tmp = new char[n + 1]; // 开辟新空间
strcpy(tmp, _str); // 将数据拷贝至新空间
delete[] _str; // 释放旧空间
_str = tmp; // 重新赋值为新空间
_capacity = n; // 更新容量大小
}
}改变_size：
void resize(size_t newSize, char c = '\0')
{
if (newSize > _size)
{
// 如果newSize大于底层空间大小，则需要重新开辟空间
if (newSize > _capacity)
{
reserve(newSize);
}
memset(_str + _size, c, newSize - _size);
}
_size = newSize;
_str[newSize] = '\0';
}6.string类的其他操作
交换两个字符串：复用std中的交换函数实现。
void swap(string& s)
{
std::swap(_str, s._str);
std::swap(_size, s._size);
std::swap(_capacity, s._capacity);
}从指定位置提取指定长度的子串：
string substr(size_t pos = 0, size_t len = npos)
{
assert(pos < _size);
size_t end = pos + len; // 计算子串的结束位置
if (len == npos || pos + len >= _size) // 如果长度超过_size，则提取pos位置后的所有字符
{
end = _size;
}
string str;
str.reserve(end - pos);
for (size_t i = pos; i < end; i++)
{
str += _str[i]; // 复用 += 依次提取出每个字符
}
return str;
}返回C风格的字符串：返回成员变量 _str 即可。
const char* c_str() const
{
return _str;
} 7.string类的流插入和流提取运算符
流插入：因为this指针必须指向当前调用的对象，所以流插入不能重载为成员函数。同时，我们也不需要访问成员变量，所以也不需要使用友元。重载为全局的函数即可。
- 返回引用类型是为了连续的输出。
ostream& operator<<(ostream& out, const string& s)
{
for (auto ch : s)
{
out << ch;
}
return out;
}流提取：和流插入同理，流提取也重载为全局的函数。
- 返回引用类型是为了连续的输入。
istream& operator>>(istream& in, string& s)
{
s.clear(); // 清空当前字符串
char buff[128]; // 定义一个缓冲区
char ch = in.get(); // 获取第一个输入的字符
int i = 0;
while (ch != ' ' && ch != '\n') // 遇到空格 or 换行就停止
{
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;
}8.源代码
string.cpp
#include"string.h"
namespace dw
{
string::string(const char* str)
{
_size = strlen(str);
_capacity = _size;
_str = new char[_capacity + 1];
strcpy(_str, str);
}
string::string(const string& s)
{
string tmp(s._str);
swap(tmp);
}
string& string::operator=(string s)
{
swap(s);
return *this;
}
string::~string()
{
delete[] _str;
_str = nullptr;
_size = 0;
_capacity = 0;
}
void string::insert(size_t pos, char ch)
{
assert(pos <= _size);
if (_size == _capacity)
{
size_t newCapacity = _capacity == 0 ? 4 : _capacity * 2;
reserve(newCapacity);
}
size_t end = _size + 1;
while (end > pos)
{
_str[end] = _str[end - 1];
--end;
}
_str[pos] = ch;
_size++;
}
void string::insert(size_t pos, const char* str)
{
assert(pos <= _size);
size_t 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 string::push_back(char ch)
{
if (_size == _capacity)
{
size_t newCapacity = _capacity == 0 ? 4 : _capacity * 2;
reserve(newCapacity);
}
_str[_size] = ch;
_size++;
_str[_size] = '\0';
}
void string::append(const char* str)
{
size_t len = strlen(str);
if (_size + len > _capacity)
{
reserve(_size + len);
}
strcpy(_str + _size, str);
_size += len;
}
string& string::operator+=(char ch)
{
push_back(ch);
return *this;
}
string& string::operator+=(const char* str)
{
append(str);
return *this;
}
void string::erase(size_t pos, size_t len)
{
assert(pos < _size);
if (len == npos || pos + len >= _size)
{
_str[pos] = '\0';
_size = pos;
}
else
{
strcpy(_str + pos, _str + pos + len);
_size -= len;
}
}
void string::clear()
{
_size = 0;
_str[0] = '\0';
}
size_t string::find(char ch, size_t pos)
{
for (size_t i = pos; i < _size; i++)
{
if (_str[i] == ch)
{
return i;
}
}
return npos;
}
size_t string::find(const char* str, size_t pos)
{
const char* ptr = strstr(_str + pos, str);
if (ptr == nullptr)
{
return npos;
}
else
{
return ptr - _str;
}
}
const char& string::operator[](size_t pos) const
{
assert(pos <= _size);
return _str[pos];
}
char& string::operator[](size_t pos)
{
assert(pos <= _size);
return _str[pos];
}
void string::reserve(size_t n)
{
if (n > _capacity)
{
char* tmp = new char[n + 1];
strcpy(tmp, _str);
delete[] _str;
_str = tmp;
_capacity = n;
}
}
void string::resize(size_t newSize, char c = '\0')
{
if (newSize > _size)
{
// 如果newSize大于底层空间大小，则需要重新开辟空间
if (newSize > _capacity)
{
reserve(newSize);
}
memset(_str + _size, c, newSize - _size);
}
_size = newSize;
_str[newSize] = '\0';
}
void string::swap(string& s)
{
std::swap(_str, s._str);
std::swap(_size, s._size);
std::swap(_capacity, s._capacity);
}
string string::substr(size_t pos, size_t len)
{
assert(pos < _size);
size_t end = pos + len;
if (len == npos || pos + len >= _size)
{
end = _size;
}
string str;
str.reserve(end - pos);
for (size_t i = pos; i < end; i++)
{
str += _str[i];
}
return str;
}
ostream& operator<<(ostream& out, const string& s)
{
for (auto ch : s)
{
out << ch;
}
return out;
}
istream& operator>>(istream& in, string& s)
{
s.clear();
char buff[128];
char ch = in.get();
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;
}
}
原文地址：https://blog.csdn.net/D5486789_/article/details/143803157
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！