文章目录
前言
在本篇文章中,我们将会学习到string相关的内容,并且对部分容器进行模拟实现,了解底层原理。
vs下ctrl+f可进行搜索
文档介绍
- 字符串是表示字符序列的类
- 标准的字符串类提供了对此类对象的支持,其接口类似于标准字符容器的接口,但添加了专门用于操作
单字节字符字符串的设计特性。 - 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,说明该对象时资源的最后一个使用者,将该资源释放;否则就不能释放,因为还有其他对象在使用该资源。
具体是这样实现的
总结
以上就是今天要讲的内容,本文仅仅详细介绍了 。希望对大家的学习有所帮助,仅供参考 如有错误请大佬指点我会尽快去改正 欢迎大家来评论~~
标签:const,string,pos,C++,char,size,ptr,String From: https://blog.csdn.net/lim6ere/article/details/139707244