通过模拟实现string类的主要接口可以使我们对string类的理解更加透彻,深入理解内存管理,可以更好地理解字符串在内存中的存储方式,以及如何进行内存分配和释放,从而避免常见的内存泄漏和溢出问题,加深对面向对象编程理念的理解,比如封装、继承和多态。
模拟实现string
类,主要是实现string
类的构造、拷贝构造、运算符重载、析构等。
为了防止与标准库中string
类命名冲突,我们在空间域yjz
中来模拟实现我们的string
类。
namespace yjz
{
class string
{
public:
typedef char* iterator;
typedef const char* const_iterator;
//无参构造
string()
{}
//带参构造
string(const char* str = "")//合二为一为缺省参数,空字符串表示'\0'
{}
//拷贝构造
string(const string& str)
{}
//赋值重载
string& operator=(const string& str)
{}
//析构
~string()
{}
size_t size() const
{}
size_t capacity() const
{}
//清理数据
void clear()
{}
//返回C格式
const char* c_str() const
{}
char& operator[](size_t n)//可修改
{}
const char& operator[](size_t n) const//常量
{}
//迭代器
iterator begin()
{}
iterator end()
{}
const_iterator begin() const
{}
const_iterator end() const
{}
void reserve(size_t n = 0);//扩容
void push_back(char ch);//尾插
void append(const char* str);//追加字符串
string& operator+=(char ch);//尾插
string& operator+=(const char* str);//追加字符串
void insert(size_t pos, char ch);//插入字符
void insert(size_t pos, const char* str);//插入字符串
void erase(size_t pos, size_t len = npos);//删除
size_t find(char ch, size_t pos = 0) const;//返回字符位置
size_t find(const char* str, size_t pos = 0) const;//返回字符串位置
string substr(size_t pos, size_t len = npos) const;//截取n个字符返回
private:
char* _str = nullptr;
size_t _size = 0;
size_t _capacity = 0;
static const size_t npos;
};
//实现成全局函数,支持字符串和string对象比较
bool operator<(const string& s1, const string& s2);
bool operator<=(const string& s1, const string& s2);
bool operator>(const string& s1, const string& s2);
bool operator>=(const string& s1, const string& s2);
bool operator==(const string& s1, const string& s2);
bool operator!=(const string& s1, const string& s2);
ostream& operator<<(ostream& out, const string& str);
istream& operator>>(istream& in, string& str);
}
nullptr
,可以给空字符串" "
,用'\0'
初始化_capacity
不包含'\0'
,每次开空间都要多开一个strcpy
将原字符串拷贝给新对象无参构造
//string()
// :_str(new char[1]{'\0'})
// ,_size(0)
// ,_capacity(0)
//{}
//带参构造
string(const char* str = "")//合二为一为缺省参数,空字符串表示'\0'
{
_size = strlen(str);
_capacity = _size;
_str = new char[_size + 1];//多开一个存'\0'
strcpy(_str, str);//strcpy把'\0'也拷贝
}
//拷贝构造
string(const string& str)
{
_str = new char[str._capacity + 1];//多开一个存'\0'
strcpy(_str, str._str);
_size = str._size;
_capacity = str._capacity;
}
//析构
~string()
{
delete[] _str;
_str = nullptr;
_size = _capacity = 0;
}
size_t size() const
{
return _size;
}
size_t capacity() const
{
return _capacity;
}
void clear()
{
_str[0] = '\0';
_size = 0;
}
//返回C格式
const char* c_str() const
{
return _str;
}
| 拷贝构造的现代写法:
上面实现的拷贝构造函数是我们自己申请一块新空间,再将数据拷贝过来,是比较传统的写法。
除了自己申请空间外还有一种办法也可以完成拷贝构造,就是借助构造函数+swap
函数掠夺,间接完成拷贝构造。
void swap(string& tmp)
{
std::swap(_str, tmp._str);
std::swap(_size, tmp._size);
std::swap(_capacity, tmp._capacity);
}
//拷贝构造(现代写法)
//string s2 = s1;
string(const string& str)
{
string tmp(str._str);//构造
swap(tmp);
}
string
类对象s1
拷贝构造一个新对象s2
,可以用构造函数构造一个临时对象tmp
,然后再让s2
通过swap
函数掠夺tmp
的所有数据,最后释放掉tmp
_str
需要在声明的位置给缺省值nullptr
string& operator=(const string& str)
{
//防止自己给自己赋值
if (this != &str)
{
delete[] _str;
_str = new char[str._capacity + 1];
strcpy(_str, str._str);
_size = str._size;
_capacity = str._capacity;
}
return *this;
}
| 赋值重载的现代写法:
//赋值重载(现代写法)
//s2 = s1;
string& operator=(const string& str)
{
//防止自己给自己赋值
if (this != &str)
{
//string tmp(str._str);
string tmp(str);//构造和拷贝构造都可
swap(tmp);
}
return *this;
}
s2
指向一块和s1
一样大小的空间,再把s1
的内容赋值给s2
,也是可以构造 / 拷贝构造一个临时对象tmp
,让s2
通过swap
函数掠夺tmp
的所有数据tmp
出作用域后自动析构,s2
和tmp
交换了所以此时析构的是s2
原来指向的空间,因为s2
原来指向的空间本来就要析构所以一举两得虽然上面的做法很绝,但是还有更绝的,我们直接一步做到位:
//赋值重载(现代写法)
string& operator=(string tmp)
{
swap(tmp);
return *this;
}
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& string::operator+=(char ch)//尾插
{
push_back(ch);
return *this;
}
string& string::operator+=(const char* str)//追加字符串
{
append(str);
return *this;
}
ostream& operator<<(ostream& out, const string& str)
{
for (auto ch : str)
{
out << ch;
}
return out;
}
str
中,该序列将被覆盖istream
提取操作使用空格作为分隔符istream& operator>>(istream& in, string& str)
{
char ch;
in >> ch;
while (ch != ' ' && ch != '\n')
{
str += ch;
in >> ch;
}
return in;
}
上面的流提取重载是存在问题的,我们期望的是读到空格或者换行就结束,但是对于字符而言是不需要分割的,没有分隔符的概念,所以提取字符会跳过空格和换行,因次不能用复用库中的流提取。
get
clear
清空原始数据,但不改变空间大小istream& operator>>(istream& in, string& str)
{
str.clear();
char ch;
//cin >> ch;
ch = in.get();
while (ch != ' ' && ch != '\n')
{
str += ch;
//in >> ch;
ch = in.get();
}
return in;
}
| >>重载优化
上面我们实现的>>
重载虽然没什么绝对的问题,但是存在缺陷。如果输入的字符串太长,不断+=
要扩容很多次,消耗还是比较大的。虽然可以提前扩容解决,但是到底扩容多大又是个问题。
为了减少拷贝,我们可以模拟一个缓冲区。先在栈上开一个大小适中的数组(理论上越大越好,实际几百比较合适),将读到的字符先放到数组中,等数组满了再拷贝到string类对象中,这样可以大大减少堆上空间的扩容次数。
虽然在栈上开了空间,但是在栈上开空间高效且消耗小,出作用域自动销毁。
istream& operator>>(istream& in, string& str)
{
str.clear();
char ch;
const size_t N = 256;
char buff[N];
size_t i = 0;
ch = in.get();
while (ch != ' ' && ch != '\n')
{
buff[i++] = ch;
if (i == N - 1)
{
buff[i] = '\0';
str += buff;
i = 0;
}
ch = in.get();
}
if (i > 0)
{
buff[i] = '\0';
str += buff;
}
return in;
}
bool operator<(const string& s1, const string& s2)
{
return strcmp(s1.c_str(), s2.c_str()) < 0;
}
bool operator<=(const string& s1, const string& s2)
{
return s1 < s2 || s1 == s2;
}
bool operator>(const string& s1, const string& s2)
{
return !(s1 <= s2);
}
bool operator>=(const string& s1, const string& s2)
{
return !(s1 < s2);
}
bool operator==(const string& s1, const string& s2)
{
return strcmp(s1.c_str(), s2.c_str()) == 0;
}
bool operator!=(const string& s1, const string& s2)
{
return !(s1 == s2);
}
typedef char* iterator;
iterator begin()
{
return _str;//指向第一个字符
}
iterator end()
{
return _str + _size;//指向'\0'
}
typedef const char* const_iterator;
const_iterator begin() const
{
return _str;//指向第一个字符
}
const_iterator end() const
{
return _str + _size;//指向'\0'
}
'\0'
void string::reserve(size_t n)//【异地扩容】
{
if (n > _capacity)
{
char* tmp = new char[n + 1];//多开一个存'\0'
strcpy(tmp, _str);
delete[] _str;
_str = tmp;
tmp = nullptr;
_capacity = n;//不包含'\0'
}
}
reserve
来扩容++_size
'\0'
,所以我们还要在字符串末尾手动加上'\0'
void string::push_back(char ch)//尾插
{
if (_size == _capacity)
{
reserve(_capacity == 0 ? 4 : 2 * _capacity);
}
_str[_size++] = ch;
_str[_size] = '\0';//尾插完后不要忘了补上'\0'
}
strcpy
拷贝追加的字符串时,要追加到_str + _size
的位置_size
的值void string::append(const char* str)//追加字符串
{
size_t len = strlen(str);
if (_size + len > _capacity)
{
reserve(_size + len > 2 * _capacity ? _size + len : 2 * _capacity);
}
strcpy(_str + _size, str);
_size += len;//更新_size
}
这里有一个比较容易踩坑的点,像下面实现的函数,当我们在除了_size == 0
位置插入字符外其他地方都是可以正常实现的,但是头插会陷入死循环。
void string::insert(size_t pos, char ch)//插入字符
{
assert(pos <= _size);
if (_size == _capacity)
{
reserve(_capacity == 0 ? 4 : 2 * _capacity);
}
size_t end = _size;
while (end >= pos)
{
_str[end + 1] = _str[end--];
}
_str[pos] = ch;
_str[_size + 1] = '\0';
}
头插会失败的原因是:我们定义的end
是无符号整型,所以end
始终都是不小于0的,有同学可能会说把end
改为int
类型不就好了?但是就算用int
定义end
,这个函数还是会陷入死循环。
因为
pos
是无符号整型,pos
和end
比较时pos
会使end
转换为无符号整型,然后再参与比较。
关于算数转换更多详细内容请跳转阅读 —> C语言(操作符)2
要解决这个问题可以强制类型转换,但更建议像下面这样修改:
void string::insert(size_t pos, char ch)//插入字符
{
assert(pos <= _size);
if (_size == _capacity)
{
reserve(_capacity == 0 ? 4 : 2 * _capacity);
}
size_t end = _size + 1;
while (end > pos)
{
_str[end--] = _str[end - 1];
}
_str[pos] = ch;
_size++;
}
strcpy
函数,因为strcpy
函数可以将'\0'
也拷贝过来,而插入字符串不需要将'\0'
插入进来,所以不适合使用strcpy
,可以考虑循环插入void string::insert(size_t pos, const char* str)//插入字符串
{
assert(pos <= _size);
size_t len = strlen(str);
if (len + _size > _capacity)
{
reserve(len + _size > 2 * _capacity ? len + _size : 2 * _capacity);
}
size_t end = _size + len;
while (end > pos + len - 1)
{
_str[end--] = _str[end - len];
}
for (size_t i = 0; i < len; i++)
{
_str[pos + i] = str[i];
}
_size += len;
}
string
类里面声明函数时可以给一个缺省值npos
,如果函数调用时只给一个实参则默认pos
位置后面的内容全部删除void erase(size_t pos, size_t len = npos);//删除
npos
我们也只能在.h
文件中声明(声明在string类private
成员变量下,为静态常量),在.cpp
文件中定义,npos
为无符号整型,-1的补码为全1,经过算数转换后就成了整型最大值const size_t string::npos = -1;
len
字符的部分,如果内容太短或 len
为 string::npos
,则擦除直到字符串末尾的部分len
大于pos
位置后面字符串的长度和小于后面字符串的长度_size
的值void string::erase(size_t pos, size_t len)//删除
{
assert(pos < _size);
if (len >= _size - pos)//pos后面全删
{
_str[pos] = '\0';
_size = pos;
}
else//pos后面不全删
{
for (size_t i = pos; i < _size - len + 1; i++)
{
_str[i] = _str[i + len];
}
_size -= len;
}
}
pos
时,搜索仅包括位置 pos
处或位置后的字符,而忽略任何可能出现的包含 pos
之前字符的情况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;//没找到则返回npos
}
strstr
来完成,注意第一个参数不是_str
,而是_str + pos
ptr - _str
两指针相减来获得下标size_t string::find(const char* str, size_t pos) const//返回字符串位置
{
assert(pos < _size);
const char* ptr = strstr(_str + pos, str);
if (nullptr == ptr)
{
return npos;
}
else
{
return ptr - _str;
}
}
pos
位置后面的整个子串sub += _str[pos + i];
是尾插一个字符,这一步骤不能写sub[i] = _str[pos + i];
因为虽然运算符重载的operator[]
可以返回指定位置的值,但是此时sub
只是开了len
个长度的空间,没有元素,_size
为0,assert(pos < _size)
会报错string string::substr(size_t pos, size_t len) const//截取n个字符返回
{
assert(pos < _size);
if (len > _size - pos)
{
len = _size - pos;
}
string sub;
sub.reserve(len);
for (size_t i = 0; i < len; i++)
{
sub += _str[pos + i];
}
return sub;
}
string.h:
#pragma once
#include <iostream>
#include <assert.h>
using namespace std;
namespace yjz
{
class string
{
public:
typedef char* iterator;
typedef const char* const_iterator;
无参构造
//string()
// :_str(new char[1]{'\0'})
// ,_size(0)
// ,_capacity(0)
//{}
//带参构造
string(const char* str = "")//合二为一为缺省参数,空字符串表示'\0'
{
_size = strlen(str);
_capacity = _size;
_str = new char[_size + 1];//多开一个存'\0'
strcpy(_str, str);//strcpy把'\0'也拷贝
}
//拷贝构造(传统写法) 1
//string(const string& str)
//{
// _str = new char[str._capacity + 1];//多开一个存'\0'
// strcpy(_str, str._str);
// _size = str._size;
// _capacity = str._capacity;
//}
void swap(string& tmp)
{
std::swap(_str, tmp._str);
std::swap(_size, tmp._size);
std::swap(_capacity, tmp._capacity);
}
//拷贝构造(现代写法)
string(const string& str)
{
string tmp(str._str);//构造
swap(tmp);
}
赋值重载(传统写法) 1
//string& operator=(const string& str)
//{
// //防止自己给自己赋值
// if (this != &str)
// {
// delete[] _str;
// _str = new char[str._capacity + 1];
// strcpy(_str, str._str);
// _size = str._size;
// _capacity = str._capacity;
// }
// return *this;
//}
赋值重载(现代写法) 2
//string& operator=(const string& str)
//{
// 防止自己给自己赋值
// if (this != &str)
// {
// string tmp(str._str);
// string tmp(str);//构造和拷贝构造都可
// swap(tmp);
// }
// return *this;
//}
//赋值重载(现代写法)
string& operator=(string tmp)
{
swap(tmp);
return *this;
}
//析构
~string()
{
delete[] _str;
_str = nullptr;
_size = _capacity = 0;
}
size_t size() const
{
return _size;
}
size_t capacity() const
{
return _capacity;
}
void clear()
{
_str[0] = '\0';
_size = 0;
}
//返回C格式
const char* c_str() const
{
return _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];
}
//迭代器
iterator begin()
{
return _str;//指向第一个字符
}
iterator end()
{
return _str + _size;//指向'\0'
}
const_iterator begin() const
{
return _str;//指向第一个字符
}
const_iterator end() const
{
return _str + _size;//指向'\0'
}
void reserve(size_t n = 0);//扩容
void push_back(char ch);//尾插
void append(const char* str);//追加字符串
string& operator+=(char ch);//尾插
string& operator+=(const char* str);//追加字符串
void insert(size_t pos, char ch);//插入字符
void insert(size_t pos, const char* str);//插入字符串
void erase(size_t pos, size_t len = npos);//删除
size_t find(char ch, size_t pos = 0) const;//返回字符位置
size_t find(const char* str, size_t pos = 0) const;//返回字符串位置
string substr(size_t pos, size_t len = npos) const;//截取n个字符返回
private:
char* _str = nullptr;
size_t _size = 0;
size_t _capacity = 0;
static const size_t npos;
};
//实现成全局函数,支持字符串和string对象比较
bool operator<(const string& s1, const string& s2);
bool operator<=(const string& s1, const string& s2);
bool operator>(const string& s1, const string& s2);
bool operator>=(const string& s1, const string& s2);
bool operator==(const string& s1, const string& s2);
bool operator!=(const string& s1, const string& s2);
ostream& operator<<(ostream& out, const string& str);
istream& operator>>(istream& in, string& str);
}
string.cpp:
#define _CRT_SECURE_NO_WARNINGS
#include "string.h"
namespace yjz
{
const size_t string::npos = -1;
void string::reserve(size_t n)//【异地扩容】
{
if (n > _capacity)
{
char* tmp = new char[n + 1];//多开一个存'\0'
strcpy(tmp, _str);
delete[] _str;
_str = tmp;
_capacity = n;//不包含'\0'
}
}
void string::push_back(char ch)//尾插
{
if (_size == _capacity)
{
reserve(_capacity == 0 ? 4 : 2 * _capacity);
}
_str[_size++] = ch;
_str[_size] = '\0';//尾插完后不要忘了补上'\0'
}
void string::append(const char* str)//追加字符串
{
size_t len = strlen(str);
if (_size + len > _capacity)
{
reserve(_size + len > 2 * _capacity ? _size + len : 2 * _capacity);
}
strcpy(_str + _size, str);
_size += len;//更新_size
}
string& string::operator+=(char ch)//尾插
{
push_back(ch);
return *this;
}
string& string::operator+=(const char* str)//追加字符串
{
append(str);
return *this;
}
void string::insert(size_t pos, char ch)//插入字符
{
assert(pos <= _size);
if (_size == _capacity)
{
reserve(_capacity == 0 ? 4 : 2 * _capacity);
}
size_t end = _size + 1;
while (end > pos)
{
_str[end--] = _str[end - 1];
}
_str[pos] = ch;
_size++;
}
void string::insert(size_t pos, const char* str)//插入字符串
{
assert(pos <= size());
int length = strlen(str);
if (size() + length > capacity())
{
reserve(size() + length > 2 * capacity() ? size() + length : 2 * capacity());
}
for (size_t i = size(); i >= pos; i--)
{
_str[i + length] = _str[i];
}
for (size_t i = 0; i < length; i++)
{
_str[i + pos] = *(str + i);
}
_size += length;
}
void string::erase(size_t pos, size_t len)//删除
{
assert(pos < _size);
if (len >= _size - pos)//pos后面全删
{
_str[pos] = '\0';
_size = pos;
}
else//pos后面不全删
{
for (size_t i = pos; i < _size - len + 1; i++)
{
_str[i] = _str[i + len];
}
_size -= len;
}
}
size_t string::find(char ch, size_t pos) const//返回字符位置
{
assert(pos < _size);
for (size_t i = pos; i < _size; i++)
{
if (_str[i] == ch)
{
return i;
}
}
return npos;//没找到则返回npos
}
size_t string::find(const char* str, size_t pos) const//返回字符串位置
{
assert(pos < _size);
const char* ptr = strstr(_str + pos, str);
if (nullptr == ptr)
{
return npos;
}
else
{
return ptr - _str;
}
}
string string::substr(size_t pos, size_t len) const//截取n个字符返回
{
assert(pos < _size);
if (len > _size - pos)
{
len = _size - pos;
}
string sub;
sub.reserve(len);
for (size_t i = 0; i < len; i++)
{
sub += _str[pos + i];
}
return sub;
}
bool operator<(const string& s1, const string& s2)
{
return strcmp(s1.c_str(), s2.c_str()) < 0;
}
bool operator<=(const string& s1, const string& s2)
{
return s1 < s2 || s1 == s2;
}
bool operator>(const string& s1, const string& s2)
{
return !(s1 <= s2);
}
bool operator>=(const string& s1, const string& s2)
{
return !(s1 < s2);
}
bool operator==(const string& s1, const string& s2)
{
return strcmp(s1.c_str(), s2.c_str()) == 0;
}
bool operator!=(const string& s1, const string& s2)
{
return !(s1 == s2);
}
ostream& operator<<(ostream& out, const string& str)
{
for (auto ch : str)
{
out << ch;
}
return out;
}
//istream& operator>>(istream& in, string& str)
//{
// str.clear();
// char ch;
// //cin >> ch;
// ch = in.get();
// while (ch != ' ' && ch != '\n')
// {
// str += ch;
// //in >> ch;
// ch = in.get();
// }
// return in;
//}
istream& operator>>(istream& in, string& str)
{
str.clear();
char ch;
const size_t N = 256;
char buff[N];
size_t i = 0;
ch = in.get();
while (ch != ' ' && ch != '\n')
{
buff[i++] = ch;
if (i == N - 1)
{
buff[i] = '\0';
str += buff;
i = 0;
}
ch = in.get();
}
if (i > 0)
{
buff[i] = '\0';
str += buff;
}
return in;
}
}
test.cpp:
#define _CRT_SECURE_NO_WARNINGS
#include "string.h"
namespace yjz
{
void test_string1()
{
string s1;
string s2("hello world");
cout << s1.c_str() << endl;
cout << s2.c_str() << endl;
for (size_t i = 0; i < s2.size(); i++)
{
cout << s2[i] << " ";
}
cout << endl;
string s3("hello world");
string::iterator it = s3.begin();
while (it != s3.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
void test_string2()
{
string s1("hello world");
s1.push_back('#');
cout << s1.c_str() << endl;
s1.append("Are you ok?");
cout << s1.c_str() << endl;
s1 += '%';
cout << s1.c_str() << endl;
s1 += "Are you ok?";
cout << s1.c_str() << endl;
s1.insert(1, '&');
s1.insert(0, '*');
cout << s1.c_str() << endl;
s1.insert(6, "Are you ok?");
cout << s1.c_str() << endl;
s1.erase(1, 5);
cout << s1.c_str() << endl;
}
void test_string3()
{
string s("hello world");
size_t pos = s.find('l');
string suffix = s.substr(pos, 6);
cout << suffix.c_str() << endl;
string s1("hello world");
string s2 = s1;
cout << s2.c_str() << endl;
string s3("Are you ok?");
s1 = s3;
cout << s1.c_str() << endl;
}
void test_string4()
{
string s1("hello world");
string s2;
s2 = s1;
cout << s1 << endl;
cout << s2 << endl;
}
}
int main()
{
yjz::test_string4();
return 0;
}