| 你好，我是安然无虞。 |
文章目录
- 自学网站
- string 面试题
- 深浅拷贝问题
- 浅拷贝
- 深拷贝
- 模拟实现
- 迭代器
自学网站
推荐给老铁们两款学习网站：
面试利器&算法学习：牛客网 风趣幽默的学人工智能：人工智能学习
下面我们模拟实现 string
string 面试题
面试官: 给你十分钟, 在只考虑资源管理深浅拷贝, 不考虑增删查改的情况下, 模拟实现string.
乍一听, 好像很难的样子, 其实非也, 简直就是送分题, 不信你看:
#include<cassert>
#include<cstring>
#include<algorithm>
class string
{
public:
//构造函数
string(const char* str = " ")
{
if(str == nullptr)
{
assert(str);
return;
}
_str = new char[strlen(str) + 1];
strcpy(_str, str);
}
//析构函数
~string()
{
if(_str)
{
delete[] _str;
_str = nullptr;
}
}
//拷贝构造
//过时写法
// string(const string& s)
// :_str(new char[strlen(s._str) + 1])
// {
// strcpy(_str, s._str);
// }
//现代写法
void swap(string& s)
{
std::swap(_str, s._str);
}
//string s2(s1);
string(const string& s)
:_str(nullptr)
{
string tmp(s._str);
swap(tmp);
}
//赋值重载
//过时写法
// string& operator=(const string& s)
// {
// if(this != &s)
// {
// char* tmp = new char[strlen(s._str) + 1];
// strcpy(tmp, _str);
// delete[] _str;
// _str = tmp;
// }
// return *this;
// }
//现代写法
//s1 = s2;
string& operator=(string s/*传值过来就是拷贝构造*/)
{
swap(s);
return *this;
}
private:
char* _str;
}; 深浅拷贝问题
我们看到, 上面我们是自己实现拷贝构造和赋值重载函数的, 因为涉及到资源管理, 所以需要我们显示实现成深拷贝, 如果我们没有显示实现成深拷贝, 而是采用编译器默认生成的拷贝构造和赋值重载函数, 那么执行下面代码时会有问题:
string s1("hello string");
string s2(s1);//用s2拷贝构造s1 当编译器采用默认生成的拷贝构造时会导致s1和s2共用同一块空间, 在释放时同一块空间会被释放两次,导致程序崩溃, 这种拷贝方式称为浅拷贝.
浅拷贝的问题:
- 同一块空间会析构两次;
- 其中一个修改数据也会影响另外一个(共用同一块空间)
浅拷贝
浅拷贝, 也称值拷贝, 编译器只是将对象中的值拷贝过来. 如果对象中管理资源, 最后就会导致多个对象共用同一份资源, 当其中一个对象销毁时该资源就被释放掉了, 而此时另一些对象不知道该资源已经被释放, 以为还有效, 当继续对该资源进行操作时, 就会发生违规访问. 所以要解决浅拷贝问题, C++特意引入了深拷贝.
深拷贝
如果一个类中涉及资源的管理, 其拷贝构造函数, 赋值运算符重载以及析构函数必须要显示给出, 一般都是按照深拷贝方式实现.
模拟实现
好的, 那下面我们快来看看C++官方库中是怎么来实现string的, 我们自己来模拟实现一下:
首先实现string的构造, 析构, 拷贝构造, 赋值重载:
namespace sl
{
class string
{
public:
//构造函数
string(const char* str = " ")
:_size(strlen(str))
,_capacity(_size)
{
_str = new char[_capacity + 1];//+1是因为始终要为'\0'多开一个空间
strcpy(_str, str);
}
//析构函数
~string()
{
if(_str)
{
delete[] _str;
_str = nullptr;
_size = _capacity = 0;
}
}
void swap(string& s)
{
std::swap(_str, s._str);
std::swap(_size, s._size);
std::swap(_capacity, s._capacity);
}
//拷贝构造
string(const string& s)
:_str(nullptr)
,_size(0)
,_capacity(0)
{
string tmp(s._str);
swap(tmp);
}
//赋值重载
string& operator=(string s)
{
swap(s);
return *this;
}
private:
char* _str;
size_t _size;//有效字符的个数
size_t _capacity;//实际存储有效字符的空间
};
} 下面再看对空间的管理:
namespace sl
{
class string
{
public:
......
size_t size()const
{
return _size;
}
size_t capacity()const
{
return _capacity;
}
void reserve(size_t n)
{
if(n > capacity())
{
char* tmp = new char[n + 1];
strcpy(tmp, _str);
delete[] _str;
_str = tmp;
_capacity = n;
}
}
//分三种情况考虑
void resize(size_t n, char ch = '\0')
{
if(n < _size)
{
_size = n;
_str[_size] = ch;
}
else
{
if(n > _capacity)
{
reserve(n);
}
for(size_t i = _size; i < n; i++)
{
_str[i] = ch;
}
_size = n;
_str[_size] = '\0';
}
}
private:
char* _str;
size_t _size;
size_t _capacity;
};
} 上面的接口都挺简单的,我们在这里就不做过多阐述了, 关于resize() 需要画图去理解哦, 一共有三种情况.
OK, 下面我们来看看插入删除的接口:
void push_back(char ch)
{
if (_size == _capacity)
{
reserve(_capacity == 0 ? 4 : _capacity * 2);
}
_str[_size] = ch;
_size++;
_str[_size] = '\0'; // string与顺序表不同, 要单独处理末尾的'\0'
}
string &operator+=(char ch)
{
push_back(ch);
return *this;
}
//注意追加一个字符串不同于追加一个字符, 需要小心处理
void append(const char *str)
{
size_t len = _size + strlen(str);
if (len > _capacity)
{
reserve(len);
}
strcpy(_str + _size, str);
_size = len;
}
string &operator+=(const char *str)
{
append(str);
return *this;
}
const char *c_str() const
{
return _str;
}
//随机插入
string &insert(size_t pos, char ch)
{
assert(pos <= _size);
if (_size == _capacity)
reserve(_capacity == 0 ? 4 : _capacity * 2);
size_t end = _size + 1; //注意, 遇到size_t时处理起来要格外小心
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);
}
//往后挪 len 个位置
//注意这个过程较复杂需要画图理解
size_t end = _size + len;
while (end > pos + len - 1) //注意这个循环条件
{
_str[end] = _str[end - len];
end--;
}
strncpy(_str + pos, str, len); // strcpy()会拷贝'\0'
_size += len;
return *this;
}
//随机删除
string &erase(size_t pos, size_t len = std::string::npos) //注意哦
{
assert(pos < _size);
if (len == std::string::npos || len + pos >= _size)
{
_str[pos] = '\0';
_size = pos;
}
else
{
size_t begin = pos + len;
while (begin <= _size) //注意判断循环条件
{
_str[begin - len] = _str[begin];
begin++;
}
_size -= len;
}
return *this;
} 其实我们之前有认真实现常见的数据结构会发现这个真的不难, 对于insert() 和 erase() 接口如果不理解需要自己动手画图哦.
迭代器
下面我们谈谈迭代器部分:
迭代器可以认为就是指针或者是像指针一样的东西, 具体看容器底层的实现.
namespace sl
{
class string
{
public:
.......
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;
}
private:
char *_str;
size_t _size;
size_t _capacity;
};
} //流插入
//不需要设计成友元函数, 因为没有访问私有成员
ostream &operator<<(ostream &out, const string &s)
{
for (auto& e : s)
{
out << e;
}
return out;
}
//流提取
// istream& operator>>(istream& in, string& s)
// {
// char ch;
// //in >> ch;//注意cin不能读取到空格和换行
// ch = in.get();//get()便是从流中提取字符
// while(ch != ' ' && ch != '\n')
// {
// s += ch;
// ch = in.get();
// }
// return in;
// }
//上面实现的流提取不够高效, 原因在于会频繁插入数据导致经常扩容影响效率
//优化
//流提取
istream &operator>>(istream &in, string &s)
{
s.clear(); //将数据全部清理掉
char ch;
ch = in.get();
char buff[128] = {'\0'};
size_t i = 0;
while(ch != '\n')
{
buff[i++] = ch;
if(i == 127)
{
s += buff;
memset(buff, '\0', 128);
i = 0;
}
ch = in.get();
}
s += buff;
return in;
} namespace sl
{
class string
{
public:
......
void clear()
{
_str[0] = '\0';
_size = 0;//不必释放空间
}
const char* c_str()const
{
return _str;
}
size_t find(const char* str, size_t pos = 0)const
{
const char* p = strstr(_str + pos, str);
if(p == nullptr)
return std::string::npos;
else
return p - _str;
}
private:
char *_str;
size_t _size;
size_t _capacity;
};
}