feng

started from 11.28.2025

首页·个人博客

String

STL

STL(standard template library)标准模板库,是C++标准库的重要组成部分,是一个主要包含了数据结构和算法的软件框架.

Pasted image 20251006100126.png

C语言中,string字符串是以\0结尾来标志着结束的,但是在C语言中,提供的库函数与字符串是分离的,导致操作极其不方便,而且底层空间需要自己进行管理,较为复杂.于是就有了string类.string类是一个管理字符串的数组,支持对字符串的”增删查改”.我们使用的string实际上是一个basic_string<char>的模板.

string的构造

Pasted image 20251006102644.png

具体的使用见cplusplus.com/reference/string/string/string/
我们列出常见的几个

Pasted image 20251006103115.png
int main()
{
	string s1;
	string s2("hello");
	string s3(s2);//拷贝构造
	string s4(10,'a');//10个字符"a"
	string s5="hello";
	string s6=s5;
	string s7(s2,1,2);
	cout << s1 << endl;
	return 0;
}

可以看到我们可以直接使用cout对字符串进行打印,原因是它的源码对”<<“和”>>”进行了重载类和对象

Pasted image 20251006103326.png

对于s5的构造,实际上也是在调用拷贝函数,他会先调用拷贝构造将这个字符串拷贝到临时对象,然后再用临时对象被拷贝构造s5,但是会被优化为直接调用构造函数.
对于s7的构造,使用了子串拷贝,拷贝了s2从第一个字符开始往后两个,也就是“el”。对于子串拷贝操作,它的len参数有一个缺省值npos。如果不传入参数或者传入的“len”大于了字符串的长度,都认为是传入了npos.npos的意义是指到字符串的结束.定义为

static const size_t npos=-1;

由于是无符号整形类型,-1实际上是整形的最大值,所以传入npos一定能够将整个string读完.

string的容量操作

Pasted image 20251110163923.png

length() 和size() 返回字符串的长度,但是为什么会同时存在?对于字符串而言,size和length是没有区别的,但是对于其他数据结构,比如链表,树等等,用“长度”来刻画显然不再合适,所以改用size。
string还有个方法叫做max_size(),但是没有任何意义,返回值都是9223372036854775807(整形的最大值)
capacity:返回当前容量,会自动增容。增容是按倍数进行的,所以空间越大,一次增容的量就越大,增容的速度就会越慢。因为每次增容需要开辟空间,拷贝内容,然后释放原来的空间,这些步骤都是会消耗时间的,所以不能频繁地去增容,这也就是为什么自动增容通常是成倍数的。
clear用于清除字符的内容,但是不释放空间。
empty用于判断字符串是否为空。

int main()
{
	string s1("hello world");
	cout << s1.size() << endl;//11
	cout << s1.length() << endl;//11
	cout << s1.max_size() << endl;//9223372036854775807
	cout << s1.capacity() << endl;//15
	s1 += "111111";//追加后原来15的容量不够了,它会自动进行增容
	cout << s1.capacity() << endl;//31
	s1.clear();
	cout << s1.capacity() << endl;//31,说明clear不会释放内存
	cout << s1.empty() << endl;//1
	return 0;
}

reserve定义为

void reserve (size_type n = 0);

用于申请容量的改变。比如我已知我这段字符串最多会消耗100个空间,我可以

int main()
{
	string s1;
	s1.reserve(100);
	s1 = "hello world";
	cout << s1.capacity() << endl;//111
	s1.append(" 11111");
	cout << s1.capacity() << endl;//111
	return 0;
}

打印的结果是111,但实际上有112个空间,多的那个空间给\0.我设置的是100,但是为什么是111.原因是用reserve开辟空间的时候,会像结构体一样遵从特定的对齐规则
resize() 同样可以用于开辟空间,定义为

void resize (size_type n);
void resize (size_type n, charT c);

用于开辟长度为n的空间,并将这些空间填充为字符C.也就是说,使用resize改变的不仅仅是capacity,size也会发生改变

int main()
{
	string s1("hello world");
	s1.resize(100);
	cout << s1 << endl;//hello world
	cout << s1.capacity() << endl;//111
	cout << s1.size() << endl;//100
	return 0;
}

int main()
{
	string s1("hello world");
	s1.resize(100,'x');
	cout << s1 << endl;//hello worldxxxxx....
	cout << s1.capacity() << endl;//111
	cout << s1.size() << endl;//100
	return 0;
}

那么使用resize就会有多种情况了.如果resize的值小于字符串的初值,会将字符截断,即把size减小.如果再resize为20,现在的size是5,那么会再开辟出一段空间,并把6-20这块区域填上x

int main()
{
	string s1("hello world");
	s1.resize(5,'x');
	cout << s1 << endl;//hello
	cout << s1.capacity() << endl;//15
	cout << s1.size() << endl;//5
	s1.resize(20, 'x');
	cout << s1 << endl;//helloxxxxx...
	cout << s1.capacity() << endl;//15
	cout << s1.size() << endl;//5
	return 0;
}

resize和reserve的最大的区别在于是否改变string的size

string的遍历操作

operator[]

假设现在我要把字符串转为整形,我需要对其进行遍历,我们在上面提到的可以获取字符串的长度,并且由于其还对[]进行了重载,于是就可以实现遍历

int main()
{
	string s1("123456");
	int sum = 0;
	for (size_t i = 0; i < s1.size(); i++)
	{
		sum *= 10;
		sum += (s1[i]-'0');
	}
	return 0;
}

迭代器

遍历string除了使用[]的重载外,还可以使用迭代器.

int main()
{
	string s1("123456");
	int sum = 0;
	string::iterator it = s1.begin();
	while (it != s1.end())
	{
		cout << *it << " ";
		it++;
	}
	return 0;
}

其中iterator相当于定义在string里的一种类型.实际上每种容器都有自己的迭代器,所以应当指定使用的是在string类里的.
迭代器的使用非常类似于指针,但是实际上迭代器不一定是指针.s1.begin()返回首位置的迭代器(“1″位置),s1.end()返回末位置的迭代器(注意不是”6″位置,而是”6″位置的后一位);
使用迭代器的好处在于迁移性较好,所有容器都可以通过这种方式进行访问.
现在再利用迭代器实现我们的字符串转整形,我们传入的参数是const类型的,相比普通的迭代器来说,它是只读的,因此const也有专属的迭代器.

int string2int(const string& str)
{
	int val=0;
	//string::iterator it = str.begin();此处会报错,因为我们的数据是const类型的,必须创建const类型的迭代器.
	string::const_iterator it = str.begin();
	while (it != str.end())
	{
		val*=10;
		val+=(*it-'0');
		it++;
	}
	return val;
}

如果我们想要反着遍历,C++还为我们提供了反向迭代器

int main()
{
	string s1("123456");
	int sum = 0;
	string::reverse_iterator rit = s1.rbegin();
	while (rit != s1.rend())
	{
		cout << *rit << " ";
		rit++;
	}
	return 0;
}

此时begin变为rbegin,返回的位置变成了末位置(“6″位置)的迭代器;end变成rend,返回的是首位置的前一个位置的迭代器.
所以总的来说,迭代器有四种;从方向来区分为正向和反向,从属性的角度来区分为普通和const类型,两两组合为4种.

范围for

此外,还可以使用范围for去进行遍历C++入门

int main()
{
	string s1("123456");
	int sum = 0;
	for (auto ch1 : s1)
	{
		cout << ch1 << " ";
	}
	return 0;
}

范围for的底层原理实际上就是迭代器,也就是说这段代码会被替换成上面那一段代码.如果要对本身做修改,需要改为auto&

string对象的操作接口

Pasted image 20251006105304.png

可见其提供了非常多的接口,我们选取一部分常用的操作.

Pasted image 20251006105440.png
int main()
{
	string s1("1234");
	s1.push_back('6');
	s1.append("78");
	s1 += "90";
	return 0;
}

增删

push_back是尾插一个字符,append是在末尾追加一个字符串.而 += 既可以追加一个字符,也可也追加一个字符串,相当前两个的结合版,使用更加方便.

Pasted image 20251115221237.png

可以看到,+=的重载是通过引用返回的,于是就直接在原字符串上做了修改,而+是返回了一个string,对其本身不做修改

Pasted image 20251115221346.png

如果想在中间插入,可以调用insert

Pasted image 20251110172140.png

如果想要删除,可以调用erase

Pasted image 20251110172516.png
int main()
{
	string s1("hello world");
	string s2("hell world");
	s1.insert(s1.begin(), '0');
	cout << s1 << endl;
	s1.insert(2, s2);
	cout << s1 << endl;
	s1.erase(2, 10);
	cout << s1 << endl;
	return 0;
}

c_str

string提供了C的接口:c_str
定义如下:

const char* c_str() const;

作用是返回一个C类型的字符串,也就是会返回一个指针,并且最后一位是’/0′,这样我们就可以按C语言的方式去遍历string,也可以调用strlen等操作

int main()
{
	string s2("hell world");
	const char* ch = s2.c_str();
	while (*ch)
	{
		cout<<*ch;
		ch++;
	}
	
	return 0;
}

现在来看这段代码

int main()
{
	string s2("hell world");
	s2 += '\0';
	s2 += "world";
	cout << s2 << endl;		   //hell world world
	cout << s2.c_str() << endl;//hell world
	return 0;
}

补充:字符是怎么打印的?
对于英文字符,采用ascii码进行编码,每一个码对应着一个字符.存储的时候存储ascii码,由于ascii和字符存在一一映射关系,所以打印的时候去查ascii码表就能正常打印.但是对于中文,255位的ascii码表远远不够,就出现了支持中文的编码–UTF-8,unicode,GBK编码等等.
如果只要编码常用汉字,实际上只需要使用两个字符就可以进行编码.一个字符有256种编码,两个字符就是\(256\times256\),这样就能编码大部分常用汉字了.但是现在计算机已经普及到了全世界,于是就出现了对全世界文字进行编码的编码表–Unicode.里面分为了UTF-8,UTF-16,UTF-32.里面的编码存在编码方式的差异.UTF-8代表以一个字节为最小单位,UTF-16代表以两个字节为最小单位,UTF-32则是以4个字节为最小单位.Linux下基本上使用UTF-8.后来中国又制定了另一套编码–GBK编码.
我们之所以可以直接用cout<<s2;是因为s2是string类型,是一个内置类型,其内部实现的时候已经对<<进行了重载.

getline

获取一行字符串

istream& getline (istream& is, string& str, char delim);
istream& getline (istream& is, string& str);

对于cin而言,遇到空格或者换行就直接结束了.所以如果字符串中本身就有空格就没法使用cin进行输入,就需要使用getline,使用方法如下

getline(cin,s)

查

find:可以找:对象/字符串/字符,从pos开始

Pasted image 20251115210848.png

该函数返回了第一个找到的位置,如果没有找到就返回npos(一个极大值)

Pasted image 20251115211208.png

rfind:从pos位置开始往前找字符\字符串\对象

Pasted image 20251115211908.png

子串

substr:取字符串从pos开始长为len的子串

string substr (size_t pos = 0, size_t len = npos) const;

利用这个两个接口可以实现对文件类型的识别.

int main()
{
	string s1("string.cpp");
	string s2("string.c");
	string s3("string.txt");
	size_t pos1=s1.find('.');
	if (pos1 != string::npos)
	{
		cout << s1.substr(pos1);
	}
	return 0;
}

但是有的时候会出现有连续后缀的东西,比如
1.tar.zip,如果我想取最后一个后缀,可以使用refind
如果我想找到所有后缀,我们可以先找到第一个位置,然后再从找到的第一个位置开始往下找第二个.
一个网址由协议 域名 资源名称构成
\(\underset{协议}{https}://\underset{域名}{cplusplus.com}/\underset{资源名称}{reference/string/string/rfind}\)
我们进入一个网站,做的第一件事必然是将协议,域名和资源名称分离开.这就可以通过我们的string类实现.

int main()
{
	string url("https://cplusplus.com/reference/string/string/rfind/");
	size_t i1 = url.find(':');
	if (i1 != string::npos)
	{
		cout << "协议是:" << url.substr(0, i1)<<endl;
	}
	size_t i2 = url.find('/', i1+3);//跳过://
	if (i2 != string::npos)
	{
		cout << "域名是:" << url.substr(i1+3, i2-i1-3)<<endl;
	}
	cout << "资源名称是:" << url.substr(i2);
	return 0;
}

string类的模拟实现

在模拟实现string时,遇到的第一个问题就是string这个类名和库函数重复了,这个时候就可以使用C++入门.

namespace feng
{
	class string
	{
	public:
	private:
		char* str;
		int _size;
		int _capacity;
	};
}

构造函数

构造函数考虑无参和含参

string()
	:_str(nullptr)
{}
string(char* str)
	:_str(str)
{}

但是这样写实际上是不行的.我在调用构造函数时肯定是

string("hello");

但是会报错,原因是hello是常量字符串.传参的时候str是数组首元素地址,传入构造函数后str指向了”hello”的首元素.而”hello”作为常量字符串,是存储在代码段(常量区)的,因此无法被修改,也就是权限发生了扩大,因此会被编译器检查发生报错.
string在空间不够的时候还需要进行扩容后,所以需要动态开辟数组,那么这个数组就需要开到堆上内存管理.所以我们需要做的事情是把传进来的常量字符串拷贝到堆区.这样我们的构造函数就完成了

string()
	:_str(nullptr)
{}
string(const char* str)
	:_str(new char[strlen(str) + 1])//+1是为末尾的\0准备的
{
	strcpy(_str, str);
}

但是现在如果字符串是空字符串,我们一对它进行遍历就会崩溃,因为对象是个空指针.所以实际情况下,尽管是空字符串,它必须有一个\0

string()
	:_str(new char[1])
{
	_str[0] = '\0';
}
string(const char* str)
	:_str(new char[strlen(str) + 1])//+1是为末尾的\0准备的
{
	strcpy(_str, str);
}

为了编写的简便,我们可以合二为一写成全缺省形式

string(const char* str="")//缺省值没有任何有效字符,只有\0
	:_str(new char[strlen(str) + 1])
{
	strcpy(_str, str);
}

结合上我们的容量操作,最终构造函数变为

string(const char* str="")
{
	_size = strlen(str);
	_capacity = _size;
	_str = new char[_capacity + 1];//+1是为末尾的\0准备的
	strcpy(_str, str);
}

然后是拷贝构造,调用

string s2(s1);
cout << s1.c_str() << endl;
cout << s2.c_str() << endl;

发现正常打印了,但是程序却崩了.原因是我们并没有实现拷贝构造,所以这里调用的是而编译器自带的拷贝构造,而编译器自带的拷贝构造是浅拷贝类和对象,也就是说s2和s1指向了同一片空间,于是在程序结束后对同一片空间进行二次释放,程序就崩了.所以我们需要手动实现深拷贝,即自己开辟一块空间,然后指向这块空间.

string(const string& s)
{
	_size=strlen(s._str);
	_capacity=_size;
	_str=new char[_capacity + 1];
	strcpy(_str, s._str);
}

那么既然有拷贝构造,那么就要考虑赋值操作

string s3=s1

这样同样是浅拷贝,因此需要对等号进行重载

string operator=(const string& s)
{
	_capacity=strlen(s._str);
	_size=_capacity;
	_str=new char[_capacity + 1];
	strcpy(_str, s._str);
	return *this;
}

但是这样写是存在内存泄漏的.我们在调用

string s3=s1

时,首先是创建了s3,然后再把s1的值赋值给s3.在创建s3的时候s3已经指向了一块空间,而在代码中并没有对其进行释放,就导致了内存泄漏.

string& operator=(const string& s)
{
	_capacity=strlen(s._str);
	_size=_capacity;
	char* tmp= new char[_capacity + 1];
	strcpy(tmp, s._str);
	delete[] _str;
	_str = tmp;
	return *this;
}

为了防止自己给自己赋值,所以加一个判断

string& operator=(const string& s)
{
	if(this!=&s)
	{
		_capacity=strlen(s._str);
		_size=_capacity;
		char* tmp= new char[_capacity + 1];
		strcpy(tmp, s._str);
		delete[] _str;
		_str = tmp;
		return *this;
	}
}

析构函数

既然动态开辟了空间,析构函数就要对其进行释放

~string()
{
	delete[] _str;
	_str = nullptr;
	_size=_capacity=0;
}

容量操作

size(),返回字符串长度

size_t size() const
{
	return _size;
}

capacity():返回容量

size_t capacity() const
{
	return _capacity;
}

reserve(int n):增容到n

void reserve(int n)
{
	char* tmp = new char[n + 1];
	strcpy(tmp, _str);
	delete[] _str;
	_str = tmp;
	_capacity = n;
}

resize(int n,char c):把size变为n,这样就会有三种情况,假设size是5,capacity是10,那么第一种情况:resize(8),增加了size,但是没有超过容量;第二种是resize(18),增加了size,且超过了容量.两种增加size的时候填入字符c,默认为”\0″.如果n<size,那么就直接在n的位置填\0即可.

void resize(int n,char ch='\0')
{
	if (n < _size)
	{
		_str[n] = '\0';
		_size = n;
	}
	else
	{
		if (n > _capacity)
		{
			reserve(n);
		}
		
		for (int i = _size; i < n; i++)
		{
			_str[i] = ch;
		}
		_size = n;
		_str[_size] = '\0';
	}
}

访问操作

[]访问

char& operator[](size_t i)
{
	assert(i < _size);
	return _str[i];
}
const char& operator[](size_t i) const
{
	assert(i < _size);
	return _str[i];
}

输出重载

ostream& operator<<(ostream& out, const string& s)
{
	for (size_t i; i < s.size(); i++)
	{
		cout << s[i];
	}
}

由于传入的s是const对象,在调用size()方法时需要调用对应const类型,所以在写size方法时需要用const修饰
输入重载

istream& operator>>(istream& in,string& s)
{

}

迭代器:迭代器类似于指针,用于做遍历操作.

typedef char* iterator;
iterator begin()
{
	return _str;
}
iterator end()
{
	return _str + _size;
}

实现迭代器以后范围for就自动支持了,因为范围for是由迭代器实现的.也就是说

````col-md
```cpp
while (it2 != s2.end())
{
	cout << *it2 << " ";
	it2++;
}
````col-md
```cpp
for(auto e:s)
{
	cout<<s<<" "
}

后面这段代码会被替换为前面那一段

增删查改

尾插

void push_back(char ch);
void append(const char* ch);

要插入字符首先就需要考虑空间够不够,如果不够需要进行增容,当size=capacity时就说明需要增容

void push_back(char ch)
{
	//空间不足,进行扩容
	if (_size == _capacity)
	{
		size_t new_capacity = _capacity == 0 ? 2 : 2 * _capacity;
		char* tmp = new char[new_capacity + 1];
		strcpy(tmp, _str);
		delete[] _str;
		_str = tmp;
		_capacity = new_capacity;
	}	
	_str[_size] = ch;
	_size++;
	_str[_size] = '\0';//完成后要在最后面放\0
}
void append(const char* ch)
{
	size_t len = strlen(ch);
	//扩容
	if (_size + len > _capacity)
	{
		size_t new_capacity = _size + len;
		char* tmp = new char[new_capacity + 1];
		strcpy(tmp, _str);
		delete[] _str;
		_str = tmp;
		_capacity = new_capacity;
	}
	strcpy(_str + _size, ch);
	_size += len;
	_str[_size] = '\0';//完成后要在最后面放\0
}

反复增容比较麻烦,我们可以给他封装成一个函数,见String,并且

void push_back(char ch)
{
	//空间不足,进行扩容
	if (_size == _capacity)
	{
		size_t new_capacity = _capacity == 0 ? 2 : 2 * _capacity;
		reserve(new_capacity);
	}	
	_str[_size] = ch;
	_size++;
	_str[_size] = '\0';//完成后要在最后面放\0
}
void append(const char* ch)
{
	size_t len = strlen(ch);
	if (_size + len > _capacity)
	{
		size_t new_capacity = _size + len;
		reserve(new_capacity);
	}
	strcpy(_str + _size, ch);
	_size += len;
	_str[_size] = '\0';//完成后要在最后面放\0
}

然后是+=的重载,直接复用

string& operator+=(const char* ch)
{
	this->append(ch);
	return *this;
}
string& operator+=(char ch)
{
	this->push_back(ch);
	return *this;
}

插入,可以是字符,也可以是字符串

void insert(size_t pos,char ch)
{
	assert(pos < _size);
	if (_size == _capacity)
	{
		size_t newcapasity = _capacity == 0 ? 2 : 2 * _capacity;
		reserve(newcapasity);
	}
	for (int i = _size; i >= (int)pos; i--)
	{
		_str[i+1] = _str[i];
	}
	_str[pos] = ch;
	++_size;
}
void insert(size_t pos, const char* ch)
{
	assert(pos < _size);
	int len = strlen(ch);
	if (_size + len>=_capacity)
	{
		size_t newcapasity = _capacity = _size + len;
		reserve(newcapasity);
	}
	for (int i = _size; i >= (int)pos; i--)
	{
		_str[i + len] = _str[i];
	}
	memcpy(_str + pos, ch, len);
	_size+=len;
	_str[_size] = '\0';
}

为什么需要进行强转.原因是如果pos是0,那么当i减到-1的时候,由于pos是size_t类型,i会被隐式类型转换为size_t,那么-1对应的就是最大值,这样循环就永远都跳不出去了
完成插入的编写后,就可以复用到

void push_back(char ch)
{
	insert(_size,ch);
}
void append(const char* ch)
{
	_insert(_size,ch);
}

erase(int pos,int len=npos):删除pos后len个字符.那么有这几种情况,一个是正常删除,另一个是删的数量比pos后的数量大,最后一种是不传参,默认npos.如果超出数量,那就把后面删干净,在pos处填\0即可

void erase(int pos, int len = npos)
{
	assert(pos < _size);
	if (_size - pos <= len)
	{
		_size = pos;
		_str[pos] = '\0';
	}
	else
	{
		size_t i = pos + len;
		while (i <= _size)
		{
			_str[i - len] = _str[i];
			i++;
		}
		_size -= len;
		_str[_size] = '\0';
	}
}

find(char ch,size_t pos):从pos开始往后找ch

size_t find(char ch,int pos)
{
	for (int i = pos; i < _size; i++)
	{
		if (_str[i] == ch)
			return i;
	}
	return npos;
}
size_t find(const char* ch, int pos=0)
{
	char* p=strstr(_str + pos, ch);
	if (p == nullptr)
		return npos;
	else
		return p - _str;
}

其他接口

c_str:返回C类型的字符串

const char* c_str()
{
	return _str;
}

输入输出的重载

istream& operator>>(istream& in,string& s)
{
	while (1)
	{
		char ch;
		in >> ch;
		if (ch == ' ' || ch == '\n')
			break;
		else
			s += ch;
	}
	return in;
}
ostream& operator<<(ostream& out, const string& s)
{
	for (size_t i=0; i < s.size(); i++)
	{
		cout << s[i];
	}
	return out;
}

但是输入的重载有问题,in>>ch是由系统实现的,当输入换行的时候>>会认为已经输入结束了,导致换行或者空格永远无法被接收到,最终进入死循环.所以在这里不能调用

//in>>ch,改为in.get()
istream& operator>>(istream& in,string& s)
{
	while (1)
	{
		char ch;
		ch=in.get();
		if (ch == ' ' || ch == '\n')
			break;
		else
			s += ch;
	}
	return in;
}

getline():直接获取一行的输入,把空格判断删除就行

istream& getline(istream& in,string& s)
{
	while (1)
	{
		char ch;
		ch=in.get();
		if (ch == '\n')
			break;
		else
			s += ch;
	}
	return in;
}

代码汇总

using std::cout, std::cin, std::endl, std::ostream, std::istream;

namespace feng
{
	class string
	{
	public:
		typedef char* iterator;
		
		iterator begin()
		{
			return _str;
		}
		iterator end()
		{
			return _str + _size;
		}
		//构造函数
		string(const char* str="")
		{
			_size = strlen(str);
			_capacity = _size;
			_str = new char[_capacity + 1];//+1是为末尾的\0准备的
			strcpy(_str, str);
		}
		string(const string& s)
		{
			_size = strlen(s._str);
			_capacity = _size;
			_str = new char[_capacity + 1];
			strcpy(_str, s._str);
		}
		~string()
		{
			delete[] _str;
			_str = nullptr;
			_size = _capacity = 0;
		}
		string& operator=(const string& s)
		{
			if (this != &s)
			{
				_capacity = strlen(s._str);
				_size = _capacity;
				char* tmp = new char[_capacity + 1];
				strcpy(tmp, s._str);
				delete[] _str;
				_str = tmp;
			}
			return *this;
		}
		
		size_t size() const
		{
			return _size;
		}
		size_t capacity()
		{
			return _capacity;
		}
		void reserve(int n)
		{
			char* tmp = new char[n + 1];
			strcpy(tmp, _str);
			delete[] _str;
			_str = tmp;
			_capacity = n;
		}

		char& operator[](size_t i)
		{
			assert(i < _size);
			return _str[i];
		}
		const char& operator[](size_t i) const
		{
			assert(i < _size);
			return _str[i];
		}

		void push_back(char ch)
		{
			//空间不足,进行扩容
			if (_size == _capacity)
			{
				size_t new_capacity = _capacity == 0 ? 2 : 2 * _capacity;
				reserve(new_capacity);
			}	
			_str[_size] = ch;
			_size++;
			_str[_size] = '\0';
		}
		void append(const char* ch)
		{
			size_t len = strlen(ch);
			if (_size + len > _capacity)
			{
				size_t new_capacity = _size + len;
				reserve(new_capacity);
			}
			strcpy(_str + _size, ch);
			_size += len;
			_str[_size] = '\0';
		}
		string& operator+=(const char* ch)
		{
			this->append(ch);
			return *this;
		}
		string& operator+=(char ch)
		{
			this->push_back(ch);
			return *this;
		}
		void insert(size_t pos,char ch)
		{
			assert(pos <= _size);
			if (_size == _capacity)
			{
				size_t newcapasity = _capacity == 0 ? 2 : 2 * _capacity;
				reserve(newcapasity);
			}
			for (int i = _size; i >= (int)pos; i--)
			{
				_str[i+1] = _str[i];
			}
			_str[pos] = ch;
			++_size;
		}
		void erase(int pos, int len = npos)
		{
			assert(pos < _size);
			if (_size - pos <= len)
			{
				_size = pos;
				_str[pos] = '\0';
			}
			else
			{
				size_t i = pos + len;
				while (i <= _size)
				{
					_str[i - len] = _str[i];
					i++;
				}
				_size -= len;
				_str[_size] = '\0';
			}
		}
		void insert(int pos, const char* ch)
		{
			assert(pos <= _size);
			int len = strlen(ch);
			if (_size + len>=_capacity)
			{
				size_t newcapasity = _capacity = _size + len;
				reserve(newcapasity);
			}
			for (int i = _size; i >= (int)pos; i--)
			{
				_str[i + len] = _str[i];
			}
			memcpy(_str + pos, ch, len);
			_size+=len;
			_str[_size] = '\0';
		}
		void resize(int n,char ch='\0')
		{
			if (n < _size)
			{
				_str[n] = '\0';
				_size = n;
			}
			else
			{
				if (n > _capacity)
				{
					reserve(n);
				}
				
				for (int i = _size; i < n; i++)
				{
					_str[i] = ch;
				}
				_size = n;
				_str[_size] = '\0';
			}
		}
		size_t find(char ch,int pos)
		{
			for (int i = pos; i < _size; i++)
			{
				if (_str[i] == ch)
					return i;
			}
			return npos;
		}
		size_t find(const char* ch, int pos=0)
		{
			char* p=strstr(_str + pos, ch);
			if (p == nullptr)
				return npos;
			else
				return p - _str;
		}


		const char* c_str()
		{
			return _str;
		}
	private:
		char* _str;
		int _size;
		int _capacity;
		static size_t npos;
	};
	size_t string::npos = -1;
	ostream& operator<<(ostream& out, const string& s)
	{
		for (size_t i=0; i < s.size(); i++)
		{
			cout << s[i];
		}
		return out;
	}
	istream& operator>>(istream& in,string& s)
	{
		while (1)
		{
			char ch;
			ch = in.get();
			if (ch == ' ' || ch == '\n')
			{
				break;
			}
			else
			{
				s += ch;
			}
		}
		return in;
	}
	istream& getline(istream& in, string& s)
	{
		while (1)
		{
			char ch;
			ch = in.get();
			if (ch == '\n')
				break;
			else
				s += ch;
		}
		return in;
	}
}

深拷贝的现代写法

我们之前写的深拷贝是我开一个和对方一样大的空间,然后把对方的内容复制到我开辟的新空间

string(const char* str="")
	:_str(new char[strlen(str) + 1])//+1是为末尾的\0准备的
{
	strcpy(_str, str);
}
//拷贝构造深拷贝的传统写法
string(const string& s)
{
	_size=strlen(s._str);
	_capacity=_size;
	_str=new char[_capacity + 1];
	strcpy(_str, s._str);
}
//拷贝构造深拷贝的现代写法
string(const string& s)
	:_str(nullptr)
{
	string tmp(s._str);
	swap(_str,tmp._str);
}

它的思路是:创建一个tmp,将s._str传给tmp进行构造,然后用交换函数把tmp._str交换给_str.然后tmp是个临时变量,出作用域后就被释放.
这样的写法在拷贝构造上看不出多大区别,但是在赋值上就很方便

//传统写法
string& operator=(const string& s)
{
	if (this != &s)
	{
		_capacity = strlen(s._str);
		_size = _capacity;
		char* tmp = new char[_capacity + 1];
		strcpy(tmp, s._str);
		delete[] _str;
		_str = tmp;
	}
	return *this;
}
//现代写法
string& operator=(const string& s)
{
	if (this != &s)
	{
		string tmp(s);
		swap(_str,tmp._str);
	}
	return *this;
}
//简化:
string& operator=(string s)
{
	swap(_str,s._str);
	return *this;
}
//这里是传值调用,外界传进来一个string后,会调用构造函数构造临时变量s,s是外部传入字符串的深拷贝,然后将其数组和_str进行交换,出作用域后s被释放,这样就完成了赋值.

对于一个真实的string类,其成员还包含capacity和size,那么swap的时候这三个就要一起交换.

string(const string& s)
	:_str(nullptr),_size(0),_capacity(0)
{
	string tmp(s._str);
	this->swap(tmp);
}
void swap(const string& s)
{
	::swap(_str,s._str);
	::swap(_size,s._size);
	::swap(_capacity,s._capacity);
}

由于库函数内有swap,我自己也定义了swap,如果直接调用会优先调用我自己定义的swap,所以需要加上域限定符说明我是调用的库函数中全局的swap.

题目

翻转一个字符串

给你一个字符串,根据下述规则反转字符串:
所有非英文字母保留在原有位置。·所有英文字母(小写或大写)位置反转。返回反转后的 s。
输入: s = “ab-cd”
输出:“dc-ba”
思路:左右各走一个指针,如果两个指针都指向字符就交换,否则就分别往下走.这个思路和快排非常类似

class Solution {
public:
    bool isChar(char ch)
    {
        if((ch>='a'&& ch<='z')||(ch>='A'&&ch<='Z'))
            return true;
        else
            return false;
    }
    string reverseOnlyLetters(string s) {
        int begin=0;
        int end=s.size()-1;
        while(begin<end)
        {
            while(begin<end&&isChar(s[begin])==false)
            {
                begin++;
            }
            while(begin<end&&isChar(s[end])==false)
            {
                end--;
            }
            swap(s[begin],s[end]);//c++已经提供了swap函数,利用了模板进行实现
            begin++;
            end--;
            //交换完了要再移动一次,否则会陷入循环
        }
        return s;
    }
};

找单

给定一个字符串 s,找到它的第一个不重复的字符,并返回它的索引 。如果不存在,则返回 -1。
示例:
输入: s = “leetcode”
输出: 0
思路:
1.暴力搜索,锁定一个字符,去遍历字符串找有没有重复过,时间复杂度\(O(N^2)\)

class Solution {
public:
    int firstUniqChar(string s) {
        int ret=0;
        int isUnique=1;
        while(ret<s.size())
        {
            for(int i=0;i<s.size();i++)
            {
                isUnique=1;
                if(i==ret)
                {
                    continue;
                }
                if(s[ret]==s[i])
                {
                    isUnique=0;
                    ret++;
                    break;
                }
            }
            if(isUnique)
            {
                return ret;
            }
        }
        return -1;
    }
};

2.创建一个26长度的数组,遍历一遍字符串,让每个字符转为数字后对应数组的下标,然后在对应位置+1,(这样如果出现重复,对应位置大小大于1,如果只出现一次,值就是1).然后去找数组中首个值为1的位置.时间复杂度\(O(N)\)

class Solution {
public:
    int firstUniqChar(string s) {
        int count[26] = {0};
        for(char ch : s){
            count[ch - 'a']++;
        }
        for(int i = 0; i < s.size(); i++){
            if(count[s[i] - 'a'] == 1){
                return i;
            }
        }
        return -1;
    }
};

这种思想与计数排序类似,本质上是哈希的思想.

最后单词长度

对于给定的若干个单词组成的句子,每个单词均由大小写字母混合构成,单词间使用单个空格分隔。输出最后一个单词的长度。
思路:利用rfind()去找最后一个空格所在位置,然后用s.size()去减去找到的位置就可以算出最后那个单词的长度.

int main() {
    string s;
    while (cin >> s) { // 注意 while 处理多个 case
        size_t pos = s.rfind(' ');
        cout << s.size() - (pos+1)<<endl;
    }
}

但是输出并不对.

Pasted image 20260116143048.png

进入调试我们发现” T”消失了.

Pasted image 20260116143143.png

所以说:cin()天生要求接收的数据遇到空格或者换行就结束了.这种时候就不能用cin了,而是用getline

int main() {
    string s;
    while (getline(cin,s)) { // 注意 while 处理多个 case
        size_t pos = s.rfind(' ');
        cout << s.size() - (pos+1)<<endl;
    }
}

回文

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后,短语正着读和反着读都一样。则可以认为该短语是一个回文串 。
输入:s = “A man, a plan, a canal: Panama”
输出:true
解释:”amanaplanacanalpanama” 是回文串。
思路:先把字符串全部转为小写,然后再判断回文.

class Solution {
public:
	bool isCharOrNumber(char ch)
	{
		if((ch>='a' && ch<='z')||(ch>='0' && ch<='9'))
		{
			return true;
		}
		else
			return false;
	}
    bool isPalindrome(string s) {
        //全部转成小写
        for(auto &ch:s)//由于需要对字符串做修改,需要ch是s的引用
        {
	        if(ch>='A' && ch<='Z')
		        ch+=32;
        }
        int begin=0,end=s.size()-1;
        while(begin<end)
        {
	        while(begin<end&&!isCharOrNumber(s[begin]))
		        begin++;
		    while(begin<end&&!isCharOrNumber(s[end]))
		        end--;
		    //这里begin++和end--很有可能会溢出,所以要多个条件
		    
		    if(s[begin]!=s[end])
		    {
			    return false;
		    }
		    else
		    {
			    begin++;
			    end--;
		    }
        }
        return true;
    }
};

字符串相加

给定两个字符串形式的非负整数 num1 和num2 ,计算它们的和并同样以字符串形式返回。
你不能使用任何內建的用于处理大整数的库(比如 BigInteger), 也不能直接将输入的字符串转换为整数形式。
使用进位法进行相加.每一次相加的数据实际上是数据1+数据2+进位

class Solution {
public:
    string addStrings(string num1, string num2) {
        int end1 = num1.size() - 1, end2 = num2.size() - 1;
        int next = 0;//进位
        string retstr;
        while (end1 >= 0 || end2 >= 0)
        {
            int val1 = 0, val2 = 0;
            if (end1 >= 0)
                val1 = num1[end1]-'0';
            if (end2 >= 0)
                val2 = num2[end2]-'0';
            int ret = val1 + val2 + next;
            if (ret > 9)
            {
                ret -= 10;
                next = 1;
            }
            else
            {
                next = 0;
            }
            //retstr+=(ret+'0');//尾插需要进行逆置
            retstr.insert(retstr.begin(),ret + '0');
            end1--;
            end2--;
        }
        if (next == 1)
        {
            retstr.insert(retstr.begin(), '1');
        }
        return retstr;
    }
};

但是这样做效率极低,insert调用头插需要不断的移动数组的数据,位数越大移动越多,数量级是\(N^2\).另一种方法是就进行尾插,尾插完成后进行翻转,复杂度就是\(O(N)\)了

while (begin < end)
{
    swap(ret[begin], ret[end]);
    begin++;
    end--;
}
//或者
reverse(retstr.begin(), retstr.end());

字符串相乘

**给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。
注意:不能使用任何内置的 BigInteger 库或直接将输入转换为整数。**
思路:1234×567可以写为1234x(500+60+7).

class Solution {
public:
    string addStrings(string num1, string num2) {
        int end1 = num1.size() - 1, end2 = num2.size() - 1;
        int next = 0;//进位
        string retstr;
        while (end1 >= 0 || end2 >= 0)
        {
            int val1 = 0, val2 = 0;
            if (end1 >= 0)
                val1 = num1[end1] - '0';
            if (end2 >= 0)
                val2 = num2[end2] - '0';
            int ret = val1 + val2 + next;
            if (ret > 9)
            {
                ret -= 10;
                next = 1;
            }
            else
            {
                next = 0;
            }
            retstr+=(ret + '0');
            end1--;
            end2--;
        }
        if (next == 1)
        {
            retstr+='1';
        }
        reverse(retstr.begin(), retstr.end());
        return retstr;
    }
    string multiply(string num1, string num2) {
        int sz1 = num1.size();
        int sz2 = num2.size();
        int next = 0;
        string ret="0";
        for (int i = 0; i <sz1; i++)
        {
            string result;
            for (int j = sz2-1; j >= 0; j--)
            {
                int val1 = num1[i] - '0';
                int val2 = num2[j] - '0';
                int val = val1 * val2+next;
                if (val > 9)
                {
                    next = val / 10;
                    val %= 10;
                    result+=(val+'0');
                }
                else
                {
                    result+=(val+'0');
                    next = 0;
                }
            }
            if (next != 0)
            {
                result+=( next + '0');
                next = 0;
            }
            reverse(result.begin(), result.end());
            ret=addStrings(ret, result);
            if(i!=sz1-1)
             ret += '0';
        }
        while (ret[0] == '0'&& ret.size()>1)
        {
            ret.erase(0, 1);
        }
        return ret;
    }
};

而另一种思路是:1234×567可以视为1234+1234+…一直加567次

//另一种方式
string multiply(string num1, string num2) {
	string i("0");
	string one("1");
	string ret("0");
	while(i!=num1)
	{
		i=addStrings(i,one);
		ret=addStrings(ret,num2);
	}
}

思路很简单,但是由于频繁的拷贝,性能非常的差.可以想办法进行优化.

← 上一篇:
下一篇: →