文章目录
- 前言
- 文档介绍
- 经典题目讲解
- HJ1 字符串最后一个单词的长度
- 模拟实现
- 框架
- 构造函数
- 析构函数
- 迭代器
- c_str()
- 赋值
- size()
- capacity()
- reserve
- empty()
- [ ]访问
- front/back
- push_back
- append
- operator+=
- insert一个字符
- insert一个字符串
- erase
- swap
- find一个字符
- find一个字符串
- substr()
- clear()
- 拷贝
- 赋值
- operator<<
- operator>>
- 完整代码
- string总体介绍
- stoi/stod
- to_string
- Class instantiations
- vs和g++下string结构的
- 总结
前言
在本篇文章中，我们将会学习到string相关的内容，并且对部分容器进行模拟实现，了解底层原理。
vs下ctrl+f可进行搜索
文档介绍
string
- 字符串是表示字符序列的类
- 标准的字符串类提供了对此类对象的支持，其接口类似于标准字符容器的接口，但添加了专门用于操作
单字节字符字符串的设计特性。 - string类是使用char(即作为它的字符类型，使用它的默认char_traits和分配器类型(关于模板的更多信
息，请参阅basic_string)。 - string类是basic_string模板类的一个实例，它使用char来实例化basic_string模板类，并用char_traits
和allocator作为basic_string的默认参数(根于更多的模板信息请参考basic_string)。 - 注意，这个类独立于所使用的编码来处理字节:如果用来处理多字节或变长字符(如UTF-8)的序列，这个
类的所有成员(如长度或大小)以及它的迭代器，将仍然按照字节(而不是实际编码的字符)来操作。
string本质就是char的字符数组
三个成员函数：构造，析构，赋值
我们主要看一下这一个
npos是const静态成员变量,为-1
但是这个-1是size_t的，也就是无符号整形，这样算下来就是整形的最大值。
元素访问
我们string遍历可以通过下标+【】进行访问，但是其他容器不一定适合。
这个仅仅适合部分容器，要求底层有一定的连续物理空间。对于树，链表，迭代器才是主流。
迭代器的区间一般都是左闭右开的
at如果出错会抛异常，【】会直接报错。
迭代器
我们这里主要看一下这个一点
,
一个是const的一个是非const的，这里会走参数匹配。
这里是const_iterator。保证迭代器指向的内容不会被修改。
不是const iterator,对于这样，保证这个迭代器不会被修改，那就不能进行加加减减操作了。
一般不会直接定义const对象，多用于传参。
我们某些情况下也可以用auto代替，但是会降低代码可读性。
容量相关接口
capacity:容量
对于vs编译器是1.5倍扩容。对于g++,是2倍扩容。这里为什么不一样呢？？
C++只说明了不同编译器，不同平台要实现相应的接口，供用户使用。但是没有具体说明如何实现。
reserve：开空间，影响容量
一般用于知道空间大小，一下子开好，避免大量扩容。
在vs下也不是n传级就开多少空间，他是按照扩容机制实现的。
g++是n是多少，加开多少。
对于reserve缩容情况！！！
vs，不会进行缩容。
g++，会进行缩容，但是这个缩容也是有限度的，不会影响数据。（如果n比size小，最小缩到size）
resize:开空间+初始化，影响数据和容量
如果resize>capacity,扩容+尾插，不传参数c,默认为/0
如果resize在size和capacity之间，尾插
如果resize<size,capacity不变，size变为resize大小。
clear：清空数据
clear只会清空数据，不改变底层大小。
修改
注意：push_back只会尾插一个字符
我们最常用的就是+=
assign是赋值，我们一般不使用这个。
replace是替换，效率很低，能不用就不用。
字符串操作
c_str:返回c格式字符串，与data相同
下面这段代码不会编译通过。
int main()
{
string filename("main.cpp");
FILE* fout = fopen(filename, "r");
char ch = fgetc(fout);
while (ch != EOF)
{
cout << ch;
ch = fgetc(fout);
}
return 0;
}
fopen的参数是这样的
我们需要将string转换成c格式的字符串进行传参/
int main()
{
string filename("main.cpp");
FILE* fout = fopen(filename.c_str(), "r");
char ch = fgetc(fout);
while (ch != EOF)
{
cout << ch;
ch = fgetc(fout);
}
return 0;
}
substr:取子串，注意参数
find_first_of:查找这里面的任意一个
非成员函数
operator+
尽量少用，因为传值返回，导致深拷贝效率低
relational operators
大小比较
getline
获取一行字符串
我们在用scanf和cin输入多个值的时候，用空格或者换行进行分割
有些时候我们需要接收到空格，这时候就可以用getline,这个是遇到换行结束。
经典题目讲解
HJ1 字符串最后一个单词的长度
HJ1 字符串最后一个单词的长度
我们如果直接用cin输入，是错误的。
cin是以空格和换行为结束标志的，我们读取不到换行。
可以考虑用getline,这个是遇到换行才结束。
#include <iostream>
#include <string>
using namespace std;
int main()
{
string s;
getline(cin,s);
// cin>>s;
auto rit=s.rfind(' ');
if(rit!=-1)
{
cout<< s.size()-rit-1<<endl;
}
else {
cout<< s.size()<<endl;
}
return 0;
}
模拟实现
框架
class string
{
public:
private:
char* _ptr;
size_t _size;
size_t _capacity;
//特殊处理,只有整形才可以
static const size_t npos = -1;
};
这个特殊处理可以这样用
const static int N=10;
int a[N];
构造函数
我们看一下这样的构造函数是否正确
string(const char* ptr)
:_ptr(ptr)
, _size(strlen(ptr))
, _capacity(strlen(ptr))
{
}
这样子是不正确的，我们并不是直接把地址赋值给他，而是重新开一块同样大的空间，把数据拷贝过去。
string(const char* ptr)
//多开一个，放‘\0’
:_ptr(new char [strlen(ptr)]+1 )
, _size(strlen(ptr))
//容量不关心‘\0’,只关心有效空间
, _capacity(strlen(ptr))
{
//数据拷贝
strcpy(_ptr,ptr);
}
但是这样还是有一点小问题，strlen时间复杂度为O（N），
在这里我们需要计算三次。
我们可以直接给_size,通过_size进行传参，那麽我们再进行初始化列表的时候就必须按照声明顺序执行。
那我们如何解决呢？？
初始化列表在这种场景下又不是必须的，我们可以不用初始化列表，就用正常的构造函数。
我么还需要处理传递参数为空的情况。
string()
{
_size = strlen(ptr);
_ptr =nullptr;
_capacity = _size;
strcpy(_ptr, ptr);
}
我们将_ptr初始化为空是否可行呢？？
是不可以，如果我们直接这个string进行打印，就会出现空指针的解引用操作。
我们可以给一个空串。所以完整的构造应该是这样的
string(const char* ptr = "")
{
_size = strlen(ptr);
_ptr = new char[_size + 1];
_capacity = _size;
strcpy(_ptr, ptr);
}
析构函数
这个很简单，将开辟的资源释放就可以。
~string()
{
delete[] _ptr;
_ptr = nullptr;
_capacity = _size = 0;
}
delete对空机型特殊处理，delete nullptr不会报错。
迭代器
我们的迭代器区间是左闭右开的
我们需要实现普通迭代器和const迭代器
typedef char* iterator;
typedef const char* const_iterator;
iterator begin()
{
return _ptr;
}
const_iterator begin()const
{
return _ptr;
}
iterator end()
{
return _ptr + _size;
}
const_iterator end()const
{
return _ptr + _size;
}
范围for就是傻瓜式的替换，底层还是迭代器
c_str()
将一个string转换成一个char*使用
const char* c_str()const
{
return _ptr;
}
赋值
string operator=(string& str)
{
if (this != &str)
{
_size = str._size;
_capacity = str._capacity;
delete[]_ptr;
_ptr = new char[_size + 1];
strcpy(_ptr, str._ptr);
}
return *this;
}
size()
计算数据个数
size_t size()const
{
return _size;
}
capacity()
计算容量大小
size_t capacity()const
{
return _capacity;
}
reserve
开空间，n是多少我们就开多少。
我们这里不会进行缩容
void reserve(size_t n=0)
{
if (n > capacity())
{
char* tmp = new char[n + 1];
strcpy(tmp, _ptr);
delete _ptr;
_capacity = n;
_ptr = tmp;
}
}
empty()
判断是否为空
bool empty()const
{
return _size == 0;
}
[ ]访问
我们的【】范围需要实现两份
const与非const 版本
char& operator[](size_t pos)
{
assert(pos >= 0 && pos < _size);
return _ptr[pos];
}
const char& operator[](size_t pos)const
{
assert(pos >= 0 && pos < _size);
return _ptr[pos];
}
front/back
访问头和尾
char& back()
{
return _ptr[_size - 1];
}
char& front()
{
return _ptr[0];
}
const char& back()const
{
return _ptr[_size - 1];
}
const char& front()const
{
return _ptr[0];
}
push_back
尾插一个字符
void push_back(char c)
{
//是否扩容
if (_size == _capacity)
{
int newcapacity = _capacity == 0 ? 4 : _capacity * 2;
reserve(newcapacity);
}
_ptr[_size] = c;
_size++;
_ptr[_size] = '\0';
}
append
尾插一个字符串
void append(const string& str)
{
if (_capacity < str._size+_size)
{
reserve(str._size + _size);
}
strcpy(_ptr+_size, str._ptr);
_size += str._size;
_ptr[_size] = '\0';
}
operator+=
我们在实际使用中，最常用的就是+=
string& operator+=(const string& str)
{
append(str);
return *this;
}
string& operator+=(const char& ch)
{
push_back(ch);
return *this;
}
insert一个字符
string& insert(size_t pos, const char& ch)
{
assert(pos >= 0 && pos <= _size);
//扩容
if (_size == _capacity)
{
int newcapacity = _capacity == 0 ? 4 : _capacity * 2;
reserve(newcapacity);
}
int end = _size;
while (end >= pos)
{
if (end == 1)
{
int i = 0;
}
_ptr[end+1] = _ptr[end];
end--;
}
_ptr[pos] = ch;
_size++;
return *this;
}
我们看一下这段代码
正常情况下是没有问题的，但是如果在0位置插入就会出问题
我们调试看一下
继续下一步
我们发现end=-1,pos=0,end>=pos居然是真的。
那这是为什么呢？？
我们可以看到二者的类型是不一样的，这里会把end提升为unsigned_int进行比较。
-1如果是unsigned_int，就是整形的最大数，肯定大于0.
解决1
将pos强制转化成int类型，按照int进行比较
解决2
专门处理等于情况，不让等于发生。
我们上面是把end位置的值挪动到end+1位置，最后才可能end走到与pos相同的位置，二者可能相等。
但是我们如果把end-1的位置挪动到end位置就不会发生上面的情况了。
string& insert(size_t pos, const char& ch)
{
assert(pos >= 0 && pos <= _size);
//扩容
if (_size == _capacity)
{
int newcapacity = _capacity == 0 ? 4 : _capacity * 2;
reserve(newcapacity);
}
size_t end = _size + 1;
while (end > pos)
{
if (end == 1)
{
int i = 0;
}
_ptr[end] = _ptr[end - 1];
end--;
}
_ptr[pos] = ch;
_size++;
return *this;
}
insert一个字符串
string& insert(size_t pos, const char* str)
{
assert(pos >= 0 && pos <= _size);
//判断扩容
int n = strlen(str);
if (n + _size > _capacity)
{
reserve(n + _size);
}
//挪动数据
int end = _size;
while (end >= (int)pos)
{
_ptr[end+n] = _ptr[end ];
end--;
}
strncpy(_ptr + pos, str, n);
_size += n;
return *this;
}
erase
从pos位置开始删除len个字符。
string& erase(size_t pos=0, size_t len=npos)
{
if (len == npos || len + pos >= _size)
{
//删除直接给'\0'
_ptr[pos] = '\0';
_size = pos;
}
else
{
//数据挪动
strcpy(_ptr + pos, _ptr + pos + len);
_size -= len;
}
return *this;
}
if (len == npos || len + pos >= _size)
如果我们变成len+pos>=_size，不写前面的条件，很可能会越界。
swap
我们会发现库里面有三个swap
这个调用是为了减少string的拷贝。
这个与下面相比，如果我们是swap(s1,s2);
我们会优点调用这个，这个就是根据第一个实现的。
模板的匹配。
这个是所有STL库的交换函数
我们string的交换只需要交换三个变量的内容就饿可以，但是需要调用库里的，否则就会产生死递归。
void swap(string& str)
{
std::swap(_ptr, str. _ptr);
std::swap(_size, str._size);
std::swap(_capacity, str._capacity);
}
find一个字符
我们直接进行遍历就可以。
size_t find(const char ch, size_t pos=0)const
{
size_t i = 0;
for (i = pos; i < _size; i++)
{
if (_ptr[i] == ch)
{
return i;
}
}
return npos;
}
find一个字符串
借助strstr实现
size_t find(const char* ptr, size_t pos = 0)const
{
//strstr 查找字串
char* tmp = strstr(_ptr+pos, ptr);
if (tmp == nullptr)
{
return npos;
}
else
{
//返回位置
return tmp-_ptr;
}
}
substr()
取string一部分
string substr(size_t pos = 0, size_t len = npos)
{
size_t end = pos + len;
if (len == npos || pos + len > _size)
{
end = _size;
}
string tmp;
reserve(_capacity + 1);
for (size_t i = pos; i< end; i++)
{
tmp += _ptr[i];
}
return tmp;
}
clear()
清空数据
void clear()
{
_size = 0;
_ptr[0] = '\0';
}
拷贝
我们的string有资源，所以我们需要深拷贝。
默认的拷贝完成浅拷贝，完不成我们的任务。
String类没有显式定义其拷贝构造函数与赋值运算符重载，此时编译器会合成默认的，当用s1构造s2时，编译器会调用默认的拷贝构造。最终导致的问题是，s1、s2共用同一块内存空间，在释放时同一块空间被释放多次而引起程序崩溃，这种拷贝方式，称为浅拷贝
开一块同样大的空间，把值拷贝过去。
string(const string ptr)
{
_ptr = new char[ptr._size + 1];
_size = ptr._size;
_capacity = ptr._capacity;
strcpy(_ptr, ptr._ptr);
}
上面写的是传统写法。
我们看一种现代写法
void swap(string& str)
{
std::swap(_ptr, str. _ptr);
std::swap(_size, str._size);
std::swap(_capacity, str._capacity);
}
string(const string& ptr)
{
string tmp(ptr._ptr);
swap(tmp);
}
为什么这样就可以呢？？
我们画图看一下：
s1,s2各自的空间
tmp是根据s1拷贝出来的.
我们看一下swap之后的效果
s2指向tmp的空间，这不就是我们想要的吗！！
tmp指向s2的空间。
赋值
赋值按照传统写法
string operator=(string& str)
{
if (this != &str)
{
_size = str._size;
_capacity = str._capacity;
delete[]_ptr;
_ptr = new char[_size + 1];
strcpy(_ptr, str._ptr);
}
return *this;
}
现代写法
string operator=(string s)
{
swap(s);
return *this;
}
这里千万不能用引用
我们这里不需要进行判断，因为s已经拷贝出来了。
swap之后，s出了作用域要进行销毁，就自动把原来s3的空间进行释放了。
operator<<
<<不是必须是友元，我们用友元是为了可以拿到私有成员。
我们string直接对每个字符进行遍历及就可以了
ostream& operator<<(ostream& out, const string& s)
{
for (auto ch : s)
{
out << ch;
}
return out;
}
operator>>
这个运算符>>输入多个值，默认空格和换行进行分割。
.>>是一个个字符的拿。
但是我们用这个>>,默认是拿不到换行个空格的。
我们可以用get获取。
为了避免多次扩容，我们可以引入一个buff字符数组来缓解这个问题。
流提取会覆盖这个变量已有的内容，我们再进行输入之前需要先清空。
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;
}
完整代码
namespace peng
{
class string
{
public:
string(const char* ptr = "")
{
_size = strlen(ptr);
_ptr = new char[_size + 1];
_capacity = _size;
//
strcpy(_ptr, ptr);
}
string(const string& str, size_t pos, size_t len = npos)
{
size_t n = strlen(str._ptr);
if (len == npos || pos + len > n)
{
_size = n - pos;
_capacity = n - pos;
_ptr = new char[_size + 1];
strcpy(_ptr, str._ptr + pos);
}
_size = len;
_capacity = len;
_ptr = new char[len + 1];
strncpy(_ptr, str._ptr + pos + 1, len);
_ptr[_size] = '\0';
}
string(size_t n, char c = '\0')
{
_size = n;
_capacity = n;
_ptr = new char[n + 1];
for (size_t i = 0; i < n; i++)
{
_ptr[i] = 'c';
}
_ptr[_size] = '\0';
}
~string()
{
delete[] _ptr;
_ptr = nullptr;
_capacity = _size = 0;
}
const char* c_str()const
{
return _ptr;
}
//迭代器，左闭右开
typedef char* iterator;
typedef const char* const_iterator;
iterator begin()
{
return _ptr;
}
const_iterator begin()const
{
return _ptr;
}
iterator end()
{
return _ptr + _size;
}
const_iterator end()const
{
return _ptr + _size;
}
size_t size()const
{
return _size;
}
size_t capacity()const
{
return _capacity;
}
//开空间，n是多少开多少
//不进行缩容
void reserve(size_t n = 0)
{
if (n > capacity())
{
char* tmp = new char[n + 1];
strcpy(tmp, _ptr);
delete _ptr;
_capacity = n;
_ptr = tmp;
}
}
bool empty()const
{
return _size == 0;
}
char& operator[](size_t pos)
{
assert(pos >= 0 && pos < _size);
return _ptr[pos];
}
const char& operator[](size_t pos)const
{
assert(pos >= 0 && pos < _size);
return _ptr[pos];
}
char& back()
{
return _ptr[_size - 1];
}
char& front()
{
return _ptr[0];
}
const char& back()const
{
return _ptr[_size - 1];
}
const char& front()const
{
return _ptr[0];
}
void push_back(char c)
{
if (_size == _capacity)
{
int newcapacity = _capacity == 0 ? 4 : _capacity * 2;
reserve(newcapacity);
}
_ptr[_size] = c;
_size++;
_ptr[_size] = '\0';
}
void append(const string& str)
{
if (_capacity < str._size + _size)
{
reserve(str._size + _size);
}
strcpy(_ptr + _size, str._ptr);
_size += str._size;
_ptr[_size] = '\0';
}
string& operator+=(const string& str)
{
append(str);
return *this;
}
string& operator+=(const char& ch)
{
push_back(ch);
return *this;
}
string& insert(size_t pos, const char* str)
{
assert(pos >= 0 && pos <= _size);
//判断扩容
int n = strlen(str);
if (n + _size > _capacity)
{
reserve(n + _size);
}
//挪动数据
int end = _size;
while (end >= (int)pos)
{
_ptr[end + n] = _ptr[end];
end--;
}
strncpy(_ptr + pos, str, n);
_size += n;
return *this;
}
string& insert(size_t pos, const char& ch)
{
assert(pos >= 0 && pos <= _size);
//扩容
if (_size == _capacity)
{
int newcapacity = _capacity == 0 ? 4 : _capacity * 2;
reserve(newcapacity);
}
size_t end = _size + 1;
while (end > pos)
{
_ptr[end] = _ptr[end - 1];
end--;
}
_ptr[pos] = ch;
_size++;
return *this;
}
string& erase(size_t pos = 0, size_t len = npos)
{
if (len == npos || len + pos >= _size)
{
//删除直接给'\0'
_ptr[pos] = '\0';
_size = pos;
}
else
{
//数据挪动
strcpy(_ptr + pos, _ptr + pos + len);
_size -= len;
}
return *this;
}
size_t find(const char ch, size_t pos = 0)const
{
size_t i = 0;
for (i = pos; i < _size; i++)
{
if (_ptr[i] == ch)
{
return i;
}
}
return npos;
}
size_t find(const char* ptr, size_t pos = 0)const
{
//strstr 查找字串
char* tmp = strstr(_ptr + pos, ptr);
if (tmp == nullptr)
{
return npos;
}
else
{
//返回位置
return tmp - _ptr;
}
}
//取string一部分
string substr(size_t pos = 0, size_t len = npos)
{
size_t end = pos + len;
if (len == npos || pos + len > _size)
{
end = _size;
}
string tmp;
reserve(_capacity + 1);
for (size_t i = pos; i < end; i++)
{
tmp += _ptr[i];
}
return tmp;
}
void swap(string& str)
{
std::swap(_ptr, str._ptr);
std::swap(_size, str._size);
std::swap(_capacity, str._capacity);
}
//拷贝赋值
//s1(s2)
//string(const string ptr)
//{
// _ptr = new char[ptr._size + 1];
// _size = ptr._size;
// _capacity = ptr._capacity;
// strcpy(_ptr, ptr._ptr);
//}
//s1=s2;
//s1.operator(s2);
//string operator=(string& str)
//{
// if (this != &str)
// {
// _size = str._size;
// _capacity = str._capacity;
// delete[]_ptr;
// _ptr = new char[_size + 1];
// strcpy(_ptr, str._ptr);
// }
// return *this;
//}
string(const string& ptr)
{
string tmp(ptr._ptr);
swap(tmp);
}
string operator=(string s)
{
swap(s);
return *this;
}
void clear()
{
_size = 0;
_ptr[0] = '\0';
}
private:
char* _ptr = nullptr;
size_t _size = 0;
size_t _capacity = 0;
//特殊处理
static const size_t npos = -1;
};
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;
}
}
string总体介绍
stoi/stod
这几个函数可以把字符串转成整形或者浮点型
to_string
将整形或者浮点数转化成string
int main()
{
string s1("1111");
int m = stoi(s1);
cout << m << endl;
cout << typeid(m).name() << endl;
int n = 22222;
string s2 = to_string(n);
cout << typeid(s2).name() << endl;
cout << s2 << endl;
return 0;
}
Class instantiations
这些是编码表。
我们最熟悉的就是ASCII码，每个值都一一对应。
但是对于我们的汉字，需要用多个字节表示一个中文汉字，一般常见的汉字都是用两个字节表示。
随着历史的发展，产生了万国码
每一种又对应各自的编码方式。
在我们中国，自己设立一一套规范，称为GBK
string就是用到UTF-8的格式
vs和g++下string结构的
VS
下面代码的结果是什么？？？
int main()
{
string s1;
cout << sizeof(s1) <<endl;
string s2("12345");
cout << sizeof(s2) << endl;
string s3("1234sssssssssssssssssssssssssssssssssss5");
cout << sizeof(s3) << endl;
return 0;
}
结果是28,为什呢？？
我们看到库里还开了一个16字节大小的字符数组。
我们可以认为底层是这样的
当字符串长度小于16，使用内部固定的字符数组来存放
当字符串长度大于等于16，从堆上开辟空间
我们可以认为是这样
G++
但是如果我们在g++下测试，打印8。
一个指针的大小，g++下默认指针是8个字节。
g++下是如何通过一个char*指针解决的呢？？
浅拷贝问题：
1.析构两次
2.一个修改会影响另一个
g++解决浅拷贝：引用计数，写时拷贝
引用计数：用来记录资源使用者的个数。
在构造时，将资源的计数给成1，每增加一个对象使用该资源，就给计数增加1；
当某个对象被销毁时，先给该计数减1，然后再检查是否需要释放资源。
如果计数为1，说明该对象时资源的最后一个使用者，将该资源释放；否则就不能释放，因为还有其他对象在使用该资源。
具体是这样实现的
总结
以上就是今天要讲的内容，本文仅仅详细介绍了 。希望对大家的学习有所帮助，仅供参考 如有错误请大佬指点我会尽快去改正 欢迎大家来评论~~ 😘 😘 😘
