@TOC
本文着重介绍深浅拷贝;模拟实现string类以 注意事项 + 代码 方式组织。
正文开始@边通书
1. 构造 & 拷贝构造 & 赋值重载 & 析构
【面试题】实现一个简洁的string类,即只考虑_str
这个成员,着重考察深浅拷贝。
1.1 传统写法
:heart: 1. 构造函数
构造函数,我们一般是带参/无参两种构造方式。其中文档可查到无参时默认构造空串""
,给一个缺省值即可,注意不是给空指针nullptr
.
string(const char* str = "")
: _size(strlen(str))
, _capacity(_size)
{
_str = new char[_capacity + 1];
strcpy(_str, str);
}
注:capacity表示的是能存储有效字符的个数。因此开空间时要注意给\0
预留空间,string类要特别注意\0
的存在。
:heart: 2. 拷贝构造
众所周知,拷贝构造&赋值重载这两个特殊的成员函数,如果自己不写编译器会自动生成一份。这份默认的拷贝构造(赋值重载)对于内置类型完成浅拷贝;对于自定义类型会调用它的拷贝构造(赋值重载).
如果我们使用默认的拷贝构造,会有如下问题 ——
" title="">
因此,我们必须要自己实现深拷贝,自己动态开空间,再把数据拷贝过来。
// 拷贝构造 s2(s1)
string(const string& s)
: _size(strlen(s._str))
, _capacity(s._capacity)
{
_str = new char[_capacity + 1];
strcpy(_str, s._str);
}
:heart: 3. 赋值重载
若使用默认的赋值重载,会有如下问题 ——
因此,我们必须要自己实现深拷贝,释放旧空间,开辟新空间,把数据拷贝过来。
注意:
如果上来直接销毁,如果自己给自己赋值
s3 = s3
就会有问题,因此最好要判断一下地址是否相同。// 错误示范 s3 = s3; string& operator=(const string& s) { if(this != &s) { delete[] _str; _str = new char[strlen(s._str) + 1]; strcpy(_str,s._str); } return *this; }
- 另外new可能失败。在上段代码中,若开空间失败会直接跳到异常处,然而在此之前我还手欠把s1的_str释放了。因此我先开空间,并把它给tmp,若空间开辟成功,我再释放旧空间,把tmp赋给_str
// s1 = s3;
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;
}
其实如果这样写,不判断也没有问题,就是效率高一些。
:heart: 4. 析构函数
释放对象中资源。
~string()
{
delete[] _str;
_str = nullptr;
_capacity = _size = 0;
}
1.2 现代写法
传统写法就是老老实实自己开空间、自己拷贝,现代写法有点kind of投机取巧,但是真的很妙!这里着重关注深浅拷贝,关于其他变量的交换的细节在附录中详谈。
:heart: 1. 构造函数&析构函数
现代写法,本质是一种复用行为。构造函数和析构函数不作更改。
:heart: 2. 拷贝构造
复用含参构造 构造tmp
,把tmp
深拷贝出来的_str换给s2
.
" title="">
注意s2
的_str必须给nullptr。如果不置空,会把随机值换给tmp
,tmp
是局部变量出作用域调用析构函数时,会崩溃。因为只有new/malloc出来的空间才能释放;而对空指针释放啥也不干(文档可查)。
// 拷贝构造 - 复用构造
// s1(s2);
string(const string& s)
: _str(nullptr)
{
string tmp(s._str);
swap(_str,tmp._str);
}
现代写法在list中的优势更明显,链表中可就不是strcpy这样简单了,要一个节点一个节点的拷。
:heart: 3. 赋值重载
复用拷贝构造帮助我们深拷贝,并且一石二鸟,tmp
局部变量出作用域还帮你把空间释放了。
" title="">
// 方法1:
// s3 = s1;
string& operator=(string& s)
{
string tmp(s);
swap(_str, tmp._str);
return *this;
}
传值调用拷贝构造,形参s
同样是局部变量,出作用域也会调用析构函数 ——
// 方法2:
// s3 = s1;
string& operator=(string s)
{
swap(s);
return *this;
}
注:是否还需要判断自己给自己赋值?不可能出现这样的问题。拷贝构造出来的对象已经是深拷贝了,地址变了,不会误销毁。
2. 基本接口
下面沿着逻辑链来模拟实现,就是缺啥写啥呗。随写随测的都附在附录中嘞。
2.1 size & capacity
size_t size() const
{
return _size;
}
size_t capacity() const
{
return _capacity;
}
2.2 c_str
返回 C-string,打印方便(内置类型),当然了一会儿也会重载string类的流插入流提取的。
const char* c_str() const
{
return _str;
}
2.3 []
// 可读可写
char& operator[](size_t pos)
{
assert(pos < _size);
return _str[pos];
}
// const对象提供重载版本 - 可读不可写
const char& operator[](size_t pos) const
{
assert(pos < _size);
return _str[pos];
}
2.4 迭代器
- 普通迭代器:可读可写
- const迭代器:const对象优先调用最匹配的const成员函数,可读不可写。
typedef char* iterator;
typedef const 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;
}
当然了,有迭代器就支持范围for:candy:.可通过更改函数名验证。
3. 增
3.0 reserve & resize
插入字符/字符串要考虑扩容。
:heart: reserve
开新空间,拷贝数据,释放旧空间。
void reserve(size_t n)
{
if (n > _capacity)
{
char* tmp = new char[n + 1];
strcpy(tmp, _str);
delete[] _str;
_str = tmp;
_capacity = n;
}
}
:heart: resize
reszie要考虑三种情况。
" title="">
resize(5);
resize(9,'x');
resize(20,'y')
- 如果是将元素个数减少,要把多出size的字符抹去
- 如果是将元素个数增多,默认用
\0
来填充多出的元素空间,也可指定字符来填充
void resize(size_t n, char ch = '\0')
{
if (n <= _size)
{
_size = n;
_str[_size] = '\0';
}
else
{
if (n > _capacity)
{
reserve(n);
}
for (size_t i = _size; i < n; i++)
{
_str[i] = ch;
}
_size = n;
_str[_size] = '\0';
}
}
3.1 push_back & append
:heart: push_back
void push_back(const char ch)
{
if (_size == _capacity)
{
reserve(_capacity == 0 ? 4 : 2 * _capacity);
}
_str[_size] = ch;
_size++;
_str[_size] = '\0';
//insert(_size, ch);
}
- 注意处理
\0
,其余跟顺序表差不多
:heart: append
插入字符串单纯扩2倍可不行,要计算新串儿长度。
void append(const char* str)
{
size_t len = strlen(str);
if (_size + len > _capacity)
{
reserve(_size + len);
}
strcpy(_str + _size, str);
_size += len;
//insert(_size, str);
}
当然了,实现了后面的insert后可以复用。
3.2 +=
+= 可插入字符/字符串,复用push_back和append即可。
string& operator+=(const char ch)
{
push_back(ch);
return *this;
}
string& operator+=(const char* str)
{
append(str);
return *this;
}
3.3 insert
任意位置的插入,重载了插入字符&字符串两个版本。这个强烈建议写的时候自己画图。
1.插入字符
- 注意,挪动数据采取的站在后面拽数据过来的方式,否则头删时会发生越界访问(size_t引起的,end最后为-1,实际上是整数的最大值,可以强转int,但不建议,因为size_t这个类型极度合理,你要学会控制它)
- 不建议使用头插,挪动数据效率低
// 插入字符
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];
end--;
}
_str[pos] = ch;
_size++;
return *this;
}
2.插入字符串
- 边界条件的控制,请自己画图
- 把要插入的字符串拷贝过来,但是注意不能拷贝
\0
,因此要用strncpy
// 插入字符串
string& insert(size_t pos, const char* str)
{
assert(pos <= _size);
size_t len = strlen(str);
if (_size + len > _capacity)
{
reserve(_size + len);
}
size_t end = _size + len;
while (end >= pos + len)
{
_str[end] = _str[end - len];
end--;
}
strncpy(_str + pos, str, len);
_size += len;
return *this;
}
4. 删
4.1 erase
erase同样分大致两种情况。
npos是string类的静态成员变量,必须在类外的全局定义。
const size_t string::npos = -1;
- 串儿够删的时候,直接把后面剩的串儿拷过来覆盖。
string& erase(size_t pos = 0, size_t len = npos)
{
assert(pos < _size);
if (len == npos || len >= _size - pos)
{
_str[pos] = '\0';
_size = pos;
}
else
{
strcpy(_str + pos, _str + pos + len);
_size -= len;
}
return *this;
}
4.2 clear
void clear()
{
_size = 0;
_str[0] = '\0';
}
5. 查 find
从pos位置开始查找字符或字符串。找到了就返回下标;没找到,返回npos.
- 查找字符串复用了strstr
size_t find(const char ch, size_t pos = 0)
{
assert(pos < _size);
size_t i = pos;
for (i = 0; i < _size; i++)
{
if (_str[i] == ch)
return i;
}
return 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;
}
}
6. 一些运算符重载
6.1 大小比较
- 任何类的比较操作符的重载,写完两个,其它的复用即可
- 可以重载成全局/成员。我们常有这样的错觉,觉得除了<<和>>,其他的运算符都要重载成成员函数,其实不是的。重载成成员函数的好处是不必借助友元就可访问私有,那你不用访问私有就随意了~
重载成全局,借助了strcmp和c_str ——
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 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 !(s1 == s2);
}
重载成成员函数,意思意思得嘞 ——
bool operator<(const string& s) const
{
return strcmp(_str, s._str) < 0;
}
也可以不复用strcmp ——
// "abcd" "abcd"
// "abcd" "abcde" <
// "abcde" "abcd"
bool operator<(const string& s1, const string& s2)
{
size_t i1 = 0,i2 = 0;
while (i1 < s1.size() && i2 < s2.size())
{
if (s1[i1] < s2[i2])
{
return true;
}
else if (s1[i1] > s2[i2])
{
return false;
}
else
{
i1++;
i2++;
}
}
if (s1.size() < s2.size())
{
return true;
}
return false;
}
6.2 >> & <<
流插入&流提取因为流对象和对象抢占左操作数的位置所以必须重载成全局。那必须友元吗?不是的,关键看是否需要访问私有。
:heart: 输出>>
- 不能使用
out << s._str << endl;
打印,因为这样关注的是\0
,而这里关注的是_size。可以看到,s1 += '\0'
这样尾插字符,\0
是不作为结尾标识字符的(标准库可验)。" title="">
- 遍历输出
ostream& operator<<(ostream& out, const string& s)
{
for (auto e: s)
{
out << e;
}
//for (size_t i = 0; i < s.size(); i++)
//{
// out << s[i];
//}
return out;
}
:heart: 输入<<
- 输入的字符串是动态增长的,用get一个一个字符往里读
\0
呢?构造时已带。- 不论s中是否有字符串,其实输入再打印是不会打出来的(标准库可验),需要先clear清除所有数据
" title="">
istream& operator>>(istream& in, string& s)
{
s.clear();
char ch = in.get();
while (ch != ' ' && ch != '\n')
{
s += ch;
ch = in.get();
}
return in;
}
附:
说明:
- 为了避免和标准库发生命名冲突,我们自己定义一个命名空间,像我就是
beatles
哈哈。 - 整个模拟实现都是写在
.h
文件中的,因为模板不支持分离编译,原因是什么模板进阶详谈。
现代写法完整版 —— 构造 & 拷贝构造 & 赋值重载 & 析构
为了交换所有成员变量,干脆写一个交换接口。
string的标准库中提供了一个swap,全局也有一个swap的模板函数(适用于内置类型),底层都是对两个对象的成员进行交换,结果相同,那为什么还要有呢string类中的?
std::string s1("Always");
std::string s2("more than words");
s1.swap(s2);
swap(s1, s2);
这是因为string类中的成员函数仅仅是对成员变量进行交换,效率高;而全局的进行了三次string类的深拷贝(拷贝构造 + 赋值)。因此我们优先选择类中的。
" title="">
要交换三个成员,那就封装一个函数接口swap,我们自己写的和string类中的实现原理一致。为了防止命名冲突,swap中的swap要指定库中的作用域。
string(const char* str = "")
: _size(strlen(str))
, _capacity(_size)
{
_str = new char[_capacity + 1];
strcpy(_str, str);
}
void swap(string& s)
{
std::swap(_str, s._str);
std::swap(_size, s._size);
std::swap(_capacity, s._capacity);
}
// 拷贝构造 - 复用构造
// s1(s2);
string(const string& s)
: _str(nullptr)
, _size(0)
, _capacity(0)
{
string tmp(s._str);
swap(tmp);
//swap(_str, tmp._str);
//swap(_size, tmp._size);
//swap(_capacity, tmp._capacity);
}
// 1.赋值重载
// s3 = s1;
string& operator=(string s)
{
//swap(_str, s._str);
//swap(_size, s._size);
//swap(_capacity, s._capacity);
swap(s);
return *this;
}
//// 2.赋值重载
//// s3 = s1;
//string& operator=(string& s)
//{
// string tmp(s);
// swap(_str, tmp._str);
// return *this;
//}
~string()
{
delete[] _str;
_str = nullptr;
_size = _capacity = 0;
}
string.h & string.cpp
完整代码,是 现代写法 + 增删查改string类的主要接口。随写随测。
#include<iostream>
#include<assert.h>
#include<string.h>
//#include<string> //测试标准库时用了一下
using namespace std;
// 现代写法
namespace beatles
{
class string
{
public:
typedef char* iterator;
typedef const char* const_iterator;
string(const char* str = "")
: _size(strlen(str))
, _capacity(_size)
{
_str = new char[_capacity + 1];
strcpy(_str, str);
}
void swap(string& s)
{
std::swap(_str, s._str);
std::swap(_size, s._size);
std::swap(_capacity, s._capacity);
}
// 拷贝构造 - 复用构造
// s1(s2);
string(const string& s)
: _str(nullptr)
, _size(0)
, _capacity(0)
{
string tmp(s._str);
swap(tmp);
//swap(_str, tmp._str);
//swap(_size, tmp._size);
//swap(_capacity, tmp._capacity);
}
// 1.赋值重载
// s3 = s1;
string& operator=(string s)
{
//swap(_str, s._str);
//swap(_size, s._size);
//swap(_capacity, s._capacity);
swap(s);
return *this;
}
//// 2.赋值重载
//// s3 = s1;
//string& operator=(string& s)
//{
// string tmp(s);
// swap(_str, tmp._str);
// return *this;
//}
~string()
{
delete[] _str;
_str = nullptr;
_size = _capacity = 0;
}
size_t size() const
{
return _size;
}
size_t capacity() const
{
return _capacity;
}
const char* c_str() const
{
return _str;
}
char& operator[](size_t pos)
{
assert(pos < _size);
return _str[pos];
}
const char& operator[](size_t pos) const
{
assert(pos < _size);
return _str[pos];
}
iterator begin()
{
return _str;
}
iterator end()
{
return _str + _size;
}
const_iterator begin() const
{
return _str;
}
const_iterator end() const
{
return _str + _size;
}
void resize(size_t n, char ch = '\0')
{
if (n <= _size)
{
_size = n;
_str[_size] = '\0';
}
else
{
if (n > _capacity)
{
reserve(n);
}
for (size_t i = _size; i < n; i++)
{
_str[i] = ch;
}
_size = n;
_str[_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 push_back(const char ch)
{
if (_size == _capacity)
{
reserve(_capacity == 0 ? 4 : 2 * _capacity);
}
_str[_size] = ch;
_size++;
_str[_size] = '\0';
//insert(_size, ch);
}
void append(const char* str)
{
size_t len = strlen(str);
if (_size + len > _capacity)
{
reserve(_size + len);
}
strcpy(_str + _size, str);
_size += len;
//insert(_size, str);
}
string& operator+=(const char ch)
{
push_back(ch);
return *this;
}
string& operator+=(const char* str)
{
append(str);
return *this;
}
size_t find(const char ch, size_t pos = 0)
{
assert(pos < _size);
size_t i = pos;
for (i = 0; i < _size; i++)
{
if (_str[i] == ch)
return i;
}
return 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& 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];
end--;
}
_str[pos] = ch;
_size++;
return *this;
}
string& insert(size_t pos, const char* str)
{
assert(pos <= _size);
size_t len = strlen(str);
if (_size + len > _capacity)
{
reserve(_size + len);
}
size_t end = _size + len;
while (end >= pos + len)
{
_str[end] = _str[end - len];
end--;
}
strncpy(_str + pos, str, len);
_size += len;
return *this;
}
string& erase(size_t pos = 0,size_t len = npos)
{
assert(pos < _size);
if (len == npos || len >= _size - pos)
{
_str[pos] = '\0';
_size = pos;
}
else
{
strcpy(_str + pos, _str + pos + len);
_size -= len;
}
return *this;
}
void clear()
{
_size = 0;
_str[0] = '\0';
}
//bool operator<(const string& s) const
//{
// return strcmp(_str, s._str) < 0;
//}
private:
char* _str;
size_t _size;
size_t _capacity;
static const size_t npos;
};
const size_t string::npos = -1;
//// "abcd" "abcd"
//// "abcd" "abcde" <
//// "abcde" "abcd"
//bool operator<(const string& s1, const string& s2)
//{
// size_t i1 = 0,i2 = 0;
// while (i1 < s1.size() && i2 < s2.size())
// {
// if (s1[i1] < s2[i2])
// {
// return true;
// }
// else if (s1[i1] > s2[i2])
// {
// return false;
// }
// else
// {
// i1++;
// i2++;
// }
// }
// if (s1.size() < s2.size())
// {
// return true;
// }
// return false;
//}
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 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 !(s1 == s2);
}
ostream& operator<<(ostream& out, const string& s)
{
for (auto e: s)
{
out << e;
}
//for (size_t i = 0; i < s.size(); i++)
//{
// out << s[i];
//}
return out;
}
istream& operator>>(istream& in, string& s)
{
s.clear();
char ch = in.get();
while (ch != ' ' && ch != '\n')
{
s += ch;
ch = in.get();
}
return in;
}
//测试流插入流提取运算符重载
void testString7()
{
//string s;
string s("Always");
cin >> s;
cout << s << endl;
// 不能以字符串形式输出,测试标准库
string s1("more than");
s1 += '\0';
s1 += "words";
cout << s1 << endl;
cout << s1.c_str() << endl;
}
// 测试比较大小运算符重载
void testString6()
{
string s1("abcd");
string s2("abcd");
cout << (s1 <= s2) << endl;
string s3("abcd");
string s4("abcde");
cout << (s3 <= s4) << endl;
string s5("abcde");
string s6("abcd");
cout << (s5 <= s6) << endl;
}
// 测试insert和erase
void testString5()
{
string s(" lumos maxima");
s.insert(0, "lumos");
cout << s.c_str() << endl;
s.insert(5,'!');
cout << s.c_str() << endl;
s.erase(0, 7);
cout << s.c_str() << endl;
s.erase(6);
cout << s.c_str() << endl;
}
// 测试查找
void testString4()
{
string s("lumos maxima");
cout << s.find('m') << endl;
cout << s.find("max") << endl;
}
// 测试resize
void testString3()
{
string s("lumos maxima"); // capacity - 12
s.resize(5);
cout << s.c_str() << endl;
s.resize(7,'!');
cout << s.c_str() << endl;
s.resize(20, '~');
cout << s.c_str() << endl;
}
// 测试尾插字符及字符串push_back/append,同时测试reserve
void testString2()
{
string s("more than words");
s.push_back('~');
s.push_back(' ');
cout << s.c_str() << endl;
s.append("is all you have to do to make it real");
cout << s.c_str() << endl;
s += '~';
s += "then you wouldn't have to say that you love me, cause I'd already know";
cout << s.c_str() << endl;
}
// 测试现代写法的成员函数
void testString1()
{
string s0;
string s1("Always");
string s2(s1);
cout << s2.c_str() << endl;
string s3("more than words");
s3 = s1;
cout << s3.c_str() << endl;
s3 = s3;
}
}
string.cpp
#define _CRT_SECURE_NO_WARNINGS 1
#include"string.h"
int main()
{
beatles::testString1();
//beatles::testString2();
//beatles::testString3();
//beatles::testString4();
//beatles::testString5();
//beatles::testString6();
//beatles::testString7();
return 0;
}
持续更新~@边通书