??C++學(xué)習(xí)歷程：STL——string學(xué)習(xí)

---

• 博客主頁：一起去看日落嗎
• 持續(xù)分享博主的C++學(xué)習(xí)歷程
• 博主的能力有限，出現(xiàn)錯誤希望大家不吝賜教
• 分享給大家一句我很喜歡的話： 也許你現(xiàn)在做的事情，暫時看不到成果，但不要忘記，樹??成長之前也要扎根，也要在漫長的時光??中沉淀養(yǎng)分。靜下來想一想，哪有這么多的天賦異稟，那些讓你羨慕的優(yōu)秀的人也都曾默默地翻山越嶺??。

---

?? ?? ?? ??

??1. 為什么要學(xué)習(xí)string類？

??1.1 C語言中的字符串

C語言中，字符串是以’\0’結(jié)尾的一些字符的集合，為了操作方便，C標(biāo)準(zhǔn)庫中提供了一些str系列的庫函數(shù)，但是這些庫函數(shù)與字符串是分離開的，不太符合OOP的思想，而且底層空間需要用戶自己管理，稍不留神可能還會越界訪問。

??1.2 兩個面試題（暫不做講解）

字符串轉(zhuǎn)整形數(shù)字

字符串相加

在OJ中，有關(guān)字符串的題目基本以string類的形式出現(xiàn)，而且在常規(guī)工作中，為了簡單、方便、快捷，基本都使用string類，很少有人去使用C庫中的字符串操作函數(shù)。

??2. 標(biāo)準(zhǔn)庫中的string類

??2.1 string類(了解)

string類的文檔介紹

• 字符串是表示字符序列的類。
• 標(biāo)準(zhǔn)的字符串類提供了對此類對象的支持，其接口類似于標(biāo)準(zhǔn)字符容器的接口，但添加了專門用于操作單字節(jié)字符字符串的設(shè)計特性。
• string 類是使用 char(即作為它的字符類型，使用它的默認(rèn) char_traits 和分配器類型 (關(guān)于模板的更多信息，請參閱 basic_string)。
• string 類是 basic_string 模板類的一個實(shí)例，它使用 char 來實(shí)例化 basic_string 模板類，并用 char_traits 和 allocator 作為 basic_string 的默認(rèn)參數(shù)(根于更多的模板信息請參考 basic_string)。
• 注意，這個類獨(dú)立于所使用的編碼來處理字節(jié):如果用來處理多字節(jié)或變長字符(如 UTF-8) 的序列，這個類的所有成員(如長度或大小)以及它的迭代器，將仍然按照字節(jié)(而不是實(shí)際編碼的字符)來操作。

總結(jié)：

• string 是表示字符串的字符串類。
• 該類的接口與常規(guī)容器的接口基本相同，再添加了一些專門用來操作 string 的常規(guī)操作。
• string 在底層實(shí)際是：basic_string 模板類的別名，typedef basic_string<char, char_traits, allocator> string;。
• 不能操作多字節(jié)或者變長字符的序列。

在使用 string 類時，必須包含 string 頭文件以及 using namespace std;

#include<string>
#include<iostream>
using namespace std;
int main()
{
	cout << sizeof(char) << endl;
	cout << sizeof(wchar_t) << endl;

	char arr1[] = "hello bit";
	char arr2[] = "byih";
	return 0;
}

??2.1 string類的常用接口說明（只講解最常用的接口）

??2.1.1 string類對象的常見構(gòu)造

#include<string>
#include<iostream>
using namespace std;   
//大概原理
template<class T>
class basic_string
{
	T* _arr;
	int _size;
	int _capacity;
};
//typedef basic_string<char> string;
int main()
{
	string s1;
	string s2("hello");  
	string s3("byih");
	string s4(10, 'a');
	string s5(s2);
	//對于string它重載了流提取和流插入等，這里就可以直接用
	cout << s1 << endl;
	cout << s2 << endl;
	cout << s3 << endl;
	cout << s4 << endl;
	cout << s5 << endl;
	
	//賦值 ———— 深拷貝
	s1 = s5;
	cout << s1 << endl;
}

s1雖然是無參的，但是他的第一個位置會有一個\0

??2.1.2 string類對象的容量操作造

#include<string>
#include<iostream>
using namespace std;
void test_string1()
{
	//1、size | length
	string s1("hello world");
	cout << s1.size() << endl;
	cout << s1.length() << endl;
	cout << "----------cut----------" << endl;
	//2、max_size
	string s2;
	cout << s1.max_size() << endl;
	cout << s2.max_size() << endl;	
	cout << "----------cut----------" << endl;
	//3、capacity
	cout << s1.capacity() << endl;
	cout << "----------cut----------" << endl;
	//4、resize
	string s3("hello world");
	cout << s3.size() << endl;
	cout << s3 << endl;
	//s3.resize(20);//n大于當(dāng)前的字符串的長度且沒有指定c，所以hello world\0\0\0\0...   
	//s3.resize(5);//n小于當(dāng)前的字符串的長度， 它會刪除掉從n開始的這些字符
	s3.resize(20, 'x');//n大于當(dāng)前的字符串的長度且指定c，所以hello worldxxxx...
	cout << s3.size() << endl;
	cout << s3 << endl;
	cout << "----------cut----------" << endl;
	//5、reserve
	string s4("hello world");
	s4.reserve(20);
	cout << s4 << endl;
	cout << s4.size() << endl;
	cout << s4.capacity() << endl;
	s4.reserve(10);
	cout << s4 << endl;
	cout << s4.size() << endl;
	cout << s4.capacity() << endl;
	cout << "----------cut----------" << endl;
	//6、clear | empty
	string s5("hello world");
	cout << s5 << endl;
	cout << s5.empty() << endl;;
	s5.clear();
	cout << s5 << endl;
	cout << s5.empty() << endl;
	cout << "----------cut----------" << endl;
	//7、shrink_to_fit 暫且不演示
}   
void test_string2()
{
	string s;
	size_t sz = s.capacity();
	cout << "making s grow:\n" << sz << endl;
	for(int i = 0; i < 500; ++i)
	{
		s.push_back('c');
		if(sz != s.capacity())
		{
			sz = s.capacity();
			cout << "capacity changed:" << sz << '\n';
		}
	}
	cout << "----------cut----------" << endl;
}
int main()
{
	test_string1();
	test_string2();

	return 0;
}

注意：

1. size()與length()方法底層實(shí)現(xiàn)原理完全相同，引入size()的原因是為了與其他容器的接口保持一致，一般情況下基本都是用size()。
2. clear()只是將string中有效字符清空，不改變底層空間大小。
3. resize(size_t n) 與 resize(size_t n, char c)都是將字符串中有效字符個數(shù)改變到n個，不同的是當(dāng)字符個數(shù)增多時：resize(n)用0來填充多出的元素空間，resize(size_t n, char c)用字符c來填充多出的元素空間。注意：resize在改變元素個數(shù)時，如果是將元素個數(shù)增多，可能會改變底層容量的大小，如果是將元素個數(shù)減少，底層空間總大小不變。
4. reserve(size_t res_arg=0)：為string預(yù)留空間，不改變有效元素個數(shù)，當(dāng)reserve的參數(shù)小于string的底層空間總大小時，reserver不會改變?nèi)萘看笮　?/li>

??2.1.3 string類對象的訪問及遍歷操作

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
using namespace std;

#include <string>


// 測試string容量相關(guān)的接口
// size/clear/resize
void Teststring1()
{
	// 注意：string類對象支持直接用cin和cout進(jìn)行輸入和輸出
	string s("hello, bit!!!");
	cout << s.size() << endl;
	cout << s.length() << endl;
	cout << s.capacity() << endl;
	cout << s << endl;

	// 將s中的字符串清空，注意清空時只是將size清0，不改變底層空間的大小
	s.clear();
	cout << s.size() << endl;
	cout << s.capacity() << endl;

	// 將s中有效字符個數(shù)增加到10個，多出位置用'a'進(jìn)行填充
	// “aaaaaaaaaa”
	s.resize(10, 'a');
	cout << s.size() << endl;
	cout << s.capacity() << endl;

	// 將s中有效字符個數(shù)增加到15個，多出位置用缺省值'\0'進(jìn)行填充
	// "aaaaaaaaaa\0\0\0\0\0"
	// 注意此時s中有效字符個數(shù)已經(jīng)增加到15個
	s.resize(15);
	cout << s.size() << endl;
	cout << s.capacity() << endl;
	cout << s << endl;

	// 將s中有效字符個數(shù)縮小到5個
	s.resize(5);
	cout << s.size() << endl;
	cout << s.capacity() << endl;
	cout << s << endl;
}

//====================================================================================
void Teststring2()
{
	string s;
	// 測試reserve是否會改變string中有效元素個數(shù)
	s.reserve(100);
	cout << s.size() << endl;
	cout << s.capacity() << endl;

	// 測試reserve參數(shù)小于string的底層空間大小時，是否會將空間縮小
	s.reserve(50);
	cout << s.size() << endl;
	cout << s.capacity() << endl;
}

// 利用reserve提高插入數(shù)據(jù)的效率，避免增容帶來的開銷
//====================================================================================
void TestPushBack()
{
	string s;
	size_t sz = s.capacity();
	cout << "making s grow:\n";
	for (int i = 0; i < 100; ++i)
	{
		s.push_back('c');
		if (sz != s.capacity())
		{
			sz = s.capacity();
			cout << "capacity changed: " << sz << '\n';
		}
	}
}

// 構(gòu)建vector時，如果提前已經(jīng)知道string中大概要放多少個元素，可以提前將string中空間設(shè)置好
void TestPushBackReserve()
{
	string s;
	s.reserve(100);
	size_t sz = s.capacity();

	cout << "making s grow:\n";
	for (int i = 0; i < 100; ++i)
	{
		s.push_back('c');
		if (sz != s.capacity())
		{
			sz = s.capacity();
			cout << "capacity changed: " << sz << '\n';
		}
	}
}



// string的遍歷
// begin()+end()   for+[]  范圍for
// 注意：string遍歷時使用最多的還是for+下標(biāo) 或者 范圍for(C++11后才支持)
// begin()+end()大多數(shù)使用在需要使用STL提供的算法操作string時，比如：采用reverse逆置string
void Teststring3()
{
	string s1("hello Bit");
	const string s2("Hello Bit");
	cout << s1 << " " << s2 << endl;
	cout << s1[0] << " " << s2[0] << endl;

	s1[0] = 'H';
	cout << s1 << endl;

	// s2[0] = 'h';   代碼編譯失敗，因為const類型對象不能修改
}

void Teststring4()
{
	string s("hello Bit");
	// 3種遍歷方式：
	// 需要注意的以下三種方式除了遍歷string對象，還可以遍歷是修改string中的字符，
	// 另外以下三種方式對于string而言，第一種使用最多
	// 1. for+operator[]
	for (size_t i = 0; i < s.size(); ++i)
		cout << s[i] << endl;

	// 2.迭代器
	string::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it << endl;
		++it;
	}

	// string::reverse_iterator rit = s.rbegin();
	// C++11之后，直接使用auto定義迭代器，讓編譯器推到迭代器的類型
	auto rit = s.rbegin();
	while (rit != s.rend())
		cout << *rit << endl;

	// 3.范圍for
	for (auto ch : s)
		cout << ch << endl;
}


//
// 測試string：
// 1. 插入(拼接)方式：push_back  append  operator+= 
// 2. 正向和反向查找：find() + rfind()
// 3. 截取子串：substr()
// 4. 刪除：erase
void Teststring5()
{
	string str;
	str.push_back(' ');   // 在str后插入空格
	str.append("hello");  // 在str后追加一個字符"hello"
	str += 'b';           // 在str后追加一個字符'b'   
	str += "it";          // 在str后追加一個字符串"it"
	cout << str << endl;
	cout << str.c_str() << endl;   // 以C語言的方式打印字符串

	// 獲取file的后綴
	string file("string.cpp");
	size_t pos = file.rfind('.');
	string suffix(file.substr(pos, file.size() - pos));
	cout << suffix << endl;

	// npos是string里面的一個靜態(tài)成員變量
	// static const size_t npos = -1;

	// 取出url中的域名
	string url("http://www.cplusplus.com/reference/string/string/find/");
	cout << url << endl;
	size_t start = url.find("://");
	if (start == string::npos)
	{
		cout << "invalid url" << endl;
		return;
	}
	start += 3;
	size_t finish = url.find('/', start);
	string address = url.substr(start, finish - start);
	cout << address << endl;

	// 刪除url的協(xié)議前綴
	pos = url.find("://");
	url.erase(0, pos + 3);
	cout << url << endl;
}

int main()
{
	return 0;
}

??2.1.4 string類對象的修改操作

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
using namespace std;

#include <string>


// 測試string容量相關(guān)的接口
// size/clear/resize
void Teststring1()
{
	// 注意：string類對象支持直接用cin和cout進(jìn)行輸入和輸出
	string s("hello, bit!!!");
	cout << s.size() << endl;
	cout << s.length() << endl;
	cout << s.capacity() << endl;
	cout << s << endl;

	// 將s中的字符串清空，注意清空時只是將size清0，不改變底層空間的大小
	s.clear();
	cout << s.size() << endl;
	cout << s.capacity() << endl;

	// 將s中有效字符個數(shù)增加到10個，多出位置用'a'進(jìn)行填充
	// “aaaaaaaaaa”
	s.resize(10, 'a');
	cout << s.size() << endl;
	cout << s.capacity() << endl;

	// 將s中有效字符個數(shù)增加到15個，多出位置用缺省值'\0'進(jìn)行填充
	// "aaaaaaaaaa\0\0\0\0\0"
	// 注意此時s中有效字符個數(shù)已經(jīng)增加到15個
	s.resize(15);
	cout << s.size() << endl;
	cout << s.capacity() << endl;
	cout << s << endl;

	// 將s中有效字符個數(shù)縮小到5個
	s.resize(5);
	cout << s.size() << endl;
	cout << s.capacity() << endl;
	cout << s << endl;
}

//====================================================================================
void Teststring2()
{
	string s;
	// 測試reserve是否會改變string中有效元素個數(shù)
	s.reserve(100);
	cout << s.size() << endl;
	cout << s.capacity() << endl;

	// 測試reserve參數(shù)小于string的底層空間大小時，是否會將空間縮小
	s.reserve(50);
	cout << s.size() << endl;
	cout << s.capacity() << endl;
}

// 利用reserve提高插入數(shù)據(jù)的效率，避免增容帶來的開銷
//====================================================================================
void TestPushBack()
{
	string s;
	size_t sz = s.capacity();
	cout << "making s grow:\n";
	for (int i = 0; i < 100; ++i)
	{
		s.push_back('c');
		if (sz != s.capacity())
		{
			sz = s.capacity();
			cout << "capacity changed: " << sz << '\n';
		}
	}
}

// 構(gòu)建vector時，如果提前已經(jīng)知道string中大概要放多少個元素，可以提前將string中空間設(shè)置好
void TestPushBackReserve()
{
	string s;
	s.reserve(100);
	size_t sz = s.capacity();

	cout << "making s grow:\n";
	for (int i = 0; i < 100; ++i)
	{
		s.push_back('c');
		if (sz != s.capacity())
		{
			sz = s.capacity();
			cout << "capacity changed: " << sz << '\n';
		}
	}
}



// string的遍歷
// begin()+end()   for+[]  范圍for
// 注意：string遍歷時使用最多的還是for+下標(biāo) 或者 范圍for(C++11后才支持)
// begin()+end()大多數(shù)使用在需要使用STL提供的算法操作string時，比如：采用reverse逆置string
void Teststring3()
{
	string s1("hello Bit");
	const string s2("Hello Bit");
	cout << s1 << " " << s2 << endl;
	cout << s1[0] << " " << s2[0] << endl;

	s1[0] = 'H';
	cout << s1 << endl;

	// s2[0] = 'h';   代碼編譯失敗，因為const類型對象不能修改
}

void Teststring4()
{
	string s("hello Bit");
	// 3種遍歷方式：
	// 需要注意的以下三種方式除了遍歷string對象，還可以遍歷是修改string中的字符，
	// 另外以下三種方式對于string而言，第一種使用最多
	// 1. for+operator[]
	for (size_t i = 0; i < s.size(); ++i)
		cout << s[i] << endl;

	// 2.迭代器
	string::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it << endl;
		++it;
	}

	// string::reverse_iterator rit = s.rbegin();
	// C++11之后，直接使用auto定義迭代器，讓編譯器推到迭代器的類型
	auto rit = s.rbegin();
	while (rit != s.rend())
		cout << *rit << endl;

	// 3.范圍for
	for (auto ch : s)
		cout << ch << endl;
}


//
// 測試string：
// 1. 插入(拼接)方式：push_back  append  operator+= 
// 2. 正向和反向查找：find() + rfind()
// 3. 截取子串：substr()
// 4. 刪除：erase
void Teststring5()
{
	string str;
	str.push_back(' ');   // 在str后插入空格
	str.append("hello");  // 在str后追加一個字符"hello"
	str += 'b';           // 在str后追加一個字符'b'   
	str += "it";          // 在str后追加一個字符串"it"
	cout << str << endl;
	cout << str.c_str() << endl;   // 以C語言的方式打印字符串

	// 獲取file的后綴
	string file("string.cpp");
	size_t pos = file.rfind('.');
	string suffix(file.substr(pos, file.size() - pos));
	cout << suffix << endl;

	// npos是string里面的一個靜態(tài)成員變量
	// static const size_t npos = -1;

	// 取出url中的域名
	string url("http://www.cplusplus.com/reference/string/string/find/");
	cout << url << endl;
	size_t start = url.find("://");
	if (start == string::npos)
	{
		cout << "invalid url" << endl;
		return;
	}
	start += 3;
	size_t finish = url.find('/', start);
	string address = url.substr(start, finish - start);
	cout << address << endl;

	// 刪除url的協(xié)議前綴
	pos = url.find("://");
	url.erase(0, pos + 3);
	cout << url << endl;
}

int main()
{
	return 0;
}

注意：

1. 在string尾部追加字符時，s.push_back? / s.append(1, c) / s += 'c’三種的實(shí)現(xiàn)方式差不多，一般情況下string類的+=操作用的比較多，+=操作不僅可以連接單個字符，還可以連接字符串。
2. 對string操作時，如果能夠大概預(yù)估到放多少字符，可以先通過reserve把空間預(yù)留好。

??2.1.5 string類非成員函數(shù)

上面的幾個接口大家了解一下，下面的OJ題目中會有一些體現(xiàn)他們的使用。string類中還有一些其他的操作，這里不一一列舉，大家在需要用到時不明白了查文檔即可。

??2.1.6 vs和g++下string結(jié)構(gòu)的說明

注意：下述結(jié)構(gòu)是在32位平臺下進(jìn)行驗證，32位平臺下指針占4個字節(jié)。

• vs下string的結(jié)構(gòu)
  string總共占28個字節(jié)，內(nèi)部結(jié)構(gòu)稍微復(fù)雜一點(diǎn)，先是有一個聯(lián)合體，聯(lián)合體用來定義string中字符串的存儲空間：
  — 當(dāng)字符串長度小于16時，使用內(nèi)部固定的字符數(shù)組來存放
  — 當(dāng)字符串長度大于等于16時，從堆上開辟空間

union _Bxty
{ 	// storage for small buffer or pointer to larger one
	value_type _Buf[_BUF_SIZE];
	pointer _Ptr;
	char _Alias[_BUF_SIZE]; // to permit aliasing
} _Bx;

這種設(shè)計也是有一定道理的，大多數(shù)情況下字符串的長度都小于16，那string對象創(chuàng)建好之后，內(nèi)部已經(jīng)有了16個字符數(shù)組的固定空間，不需要通過堆創(chuàng)建，效率高。
其次：還有一個size_t字段保存字符串長度，一個size_t字段保存從堆上開辟空間總的容量
最后：還有一個指針做一些其他事情。
故總共占16+4+4+4=28個字節(jié)。

• g++下string的結(jié)構(gòu)
  G++下，string是通過寫時拷貝實(shí)現(xiàn)的，string對象總共占4個字節(jié)，內(nèi)部只包含了一個指針，該指針將來指向一塊堆空間，內(nèi)部包含了如下字段：
  — 空間總大小
  — 字符串有效長度
  — 引用計數(shù)

struct _Rep_base
{
	size_type _M_length;
	size_type _M_capacity;
	_Atomic_word _M_refcount;
};

— 指向堆空間的指針，用來存儲字符串。

??小試牛刀（做題訓(xùn)練）

??第一題

僅僅反轉(zhuǎn)字母

給你一個字符串 s ，根據(jù)下述規(guī)則反轉(zhuǎn)字符串：

• 所有非英文字母保留在原有位置。
• 所有英文字母（小寫或大寫）位置反轉(zhuǎn)。

返回反轉(zhuǎn)后的 s 。

示例 1：

輸入：s = “ab-cd”
輸出：“dc-ba”

示例 2：

輸入：s = “a-bC-dEf-ghIj”
輸出：“j-Ih-gfE-dCba”

示例 3：

輸入：s = “Test1ng-Leet=code-Q!”
輸出：“Qedo1ct-eeLg=ntse-T!”

提示:

• 1 <= s.length <= 100
• s 僅由 ASCII 值在范圍 [33, 122] 的字符組成
• s 不含 ‘"’ 或 ‘\’

題解思路：

我們使用 begin 指針從左邊開始掃描字符串 s，end 指針從右邊開始掃描字符串 s。如果兩個指針都掃描到字母，且begin < end，那么交換 s[begin]和 s[end]，然后繼續(xù)進(jìn)行掃描；否則表明反轉(zhuǎn)過程結(jié)束，返回處理后的字符串。

代碼實(shí)現(xiàn)：

class Solution 
{
public:
    bool isLetter(char ch)//判斷是否為字母，如果是返回treu，否則返回false
    {
        if(ch >= 'a' && ch <= 'z')
            return true;
        if(ch >= 'A' && ch <= 'Z')
            return true;
        return false;
    }
    string reverseOnlyLetters(string s) 
    {
        auto begin = s.begin();
        auto end = s.end() - 1;
        while(begin < end)
        {
            while(begin < end && !isLetter(*begin))//非英文字母，且保證最后begin和end重合
            {
                ++begin;
            }
            while(begin < end && !isLetter(*end))//非英文字母，且保證最后begin和end重合
            {
                --end;
            }
            swap(*begin, *end);//交換
            //交換后還要調(diào)整
            ++begin;
            --end;
        }
        return s;
    }
};

??第二題

字符串中第一個唯一字符

題述：給定一個字符串 s ，找到它的第一個不重復(fù)的字符，并返回它的索引 。如果不存在，則返回 -1 。

示例1：

輸入：s = “l(fā)eetcode”
輸出：0

示例2：

輸入: s = “l(fā)oveleetcode”
輸出: 2

示例3：

輸入: s = “aabb”
輸出: -1

提示:

• 1 <= s.length <= 105
• s 只包含小寫字母

解題思路：

首先遍歷一遍字符串，然后把每個字母的出現(xiàn)次數(shù)計算出來。

之后再遍歷一遍字符串。遍歷過程中，如果遇到了一個值出現(xiàn)過一次的字母，就返回這個字母的下標(biāo)。

代碼實(shí)現(xiàn)：

class Solution 
{
public:
    int firstUniqChar(string s) 
    {
        int count[26] = {0};
        //統(tǒng)計每個字符出現(xiàn)的次數(shù)
        for(auto ch:s)
        {
           count[ch - 'a']++;
        }
        //找出字符串中第一個不重復(fù)的字符
        for(int i = 0; i < s.size(); ++i)
        {
            if(count[s[i] - 'a'] == 1)
            {
				return i;
            }
        }
        return -1;
    }
};

??第三題

字符串最后一個單詞的長度

• 解題思路

注意這里讀區(qū)字符串不能直接cin，因為cin遇到空格就會終止，要用getline

• 代碼實(shí)現(xiàn)

#include<string>
#include<iostream>
using namespace std;
int main()
{
    string s;
    //cin >> s;
    getline(cin, s);
    size_t pos = s.rfind(' ');
    if(pos != string::npos)//多個單詞
    {
        cout << s.size() - (pos + 1) << endl;
    }
    else//一個單詞
    {
        cout << s.size() << endl;
    }
    return 0;
}

??第四題

驗證回文串

• 解題思路

使用雙指針。初始時，左右指針分別指向 sgood\textit{sgood}sgood 的兩側(cè)，隨后我們不斷地將這兩個指針相向移動，每次移動一步，并判斷這兩個指針指向的字符是否相同。當(dāng)這兩個指針相遇時，就說明 sgood\textit{sgood}sgood 時回文串。

• 代碼演示

class Solution {
public:
    bool IsLetterOrNun(char ch)
    {
        if((ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9'))
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    bool isPalindrome(string s) {
        int begin = 0, end = s.size() - 1;
        while(begin < end)
        {
            while(begin < end && !IsLetterOrNun(s[begin]))//跳過非字母數(shù)字
            {
                ++begin;
            }
            while(begin < end && !IsLetterOrNun(s[end]))//跳過非字母數(shù)字
            {
                --end;
            }
            if(s[begin] != s[end])
            {
                //有一個是數(shù)字，就不存在大小寫比較問題
                if(s[begin] < 'A' || s[end] < 'A')
                {
                    return false;
                }
                else if(s[begin] < s[end] && s[begin] + 32 == s[end])
                {
                    ++begin;
                    --end;
                }
                else if(s[end] < s[begin] && s[end] + 32 == s[begin])
                {
                    ++begin;
                    --end;
                }
                else
                {
                    return false;
                }
            }
            else
            {
                ++begin;
                --end;
            }
        }
        return true;
    }
};

//改進(jìn)代碼


class Solution {
public:
    bool isPalindrome(string s) {
        string sgood;
        for (char ch: s) {
            if (isalnum(ch)) {
                sgood += tolower(ch);
            }
        }
        int n = sgood.size();
        int left = 0, right = n - 1;
        while (left < right) {
           if (sgood[left] != sgood[right]) {
                return false;
            }
            ++left;
            --right;
        }
        return true;
    }
};

??第五題

字符串相加

• 解題思路

本題我們只需要對兩個大整數(shù)模擬「豎式加法」的過程。豎式加法就是我們平常學(xué)習(xí)生活中常用的對兩個整數(shù)相加的方法，回想一下我們在紙上對兩個整數(shù)相加的操作，是不是如下圖將相同數(shù)位對齊，從低到高逐位相加，如果當(dāng)前位和超過 101010，

• 代碼演示

class Solution {
public:
    string addStrings(string num1, string num2) {
        string retStr;
        int end1 = num1.size() - 1;
        int end2 = num2.size() - 1;
        int carry = 0;
        while(end1 >= 0 || end2 >= 0)//只要還有一位那么就繼續(xù)
        {
            int val1 = 0, val2 = 0;
            if(end1 >= 0)
            {
                val1 = num1[end1] - '0';
                --end1;
            }
            if(end2 >= 0)
            {
                val2 = num2[end2] - '0';
                --end2;
            }
            int ret = val1 + val2 + carry;
            if(ret > 9)//進(jìn)位
            {
                ret -= 10;
                carry = 1;
            }
            else
            {
                carry = 0;
            }
            //頭插
            retStr.insert(0, 1, '0' + ret);
            //retStr.insert(retStr.begin(), '0' + ret);//同上
        } 
        if(carry == 1)//還有一位的情況："1","9"
        {
           retStr.insert(retStr.begin(), '1');
        }
        return retStr;
    }
};

??3. string類的模擬實(shí)現(xiàn)

??3.1 經(jīng)典的string類問題

上面已經(jīng)對string類進(jìn)行了簡單的介紹，大家只要能夠正常使用即可。在面試中，面試官總喜歡讓學(xué)生自己來模擬實(shí)現(xiàn)string類，最主要是實(shí)現(xiàn)string類的構(gòu)造、拷貝構(gòu)造、賦值運(yùn)算符重載以及析構(gòu)函數(shù)。大家看下以下string類的實(shí)現(xiàn)是否有問題？

string.h

// 為了和標(biāo)準(zhǔn)庫區(qū)分，此處使用String
class String
{
public:
	/*String()
	:_str(new char[1])
	{*_str = '\0';}
	*/
	//String(const char* str = "\0") 錯誤示范
	//String(const char* str = nullptr) 錯誤示范
	String(const char* str = "")
	{
	// 構(gòu)造String類對象時，如果傳遞nullptr指針，可以認(rèn)為程序非
		if (nullptr == str)
		{
			assert(false);
		return;
		}
		_str = new char[strlen(str) + 1];
		strcpy(_str, str);
	}
	~String()
	{
		if (_str)
		{
			delete[] _str;
			_str = nullptr;
		}
	}
private:
	char* _str;
};
// 測試
void TestString()
{
	String s1("hello bit!!!");
	String s2(s1);
}

string.cpp

#include"string.h"
int main()
{
	TestString();
	return 0;
}

說明：上述String類沒有顯式定義其拷貝構(gòu)造函數(shù)與賦值運(yùn)算符重載，此時編譯器會合成默認(rèn)的，當(dāng)用s1構(gòu)造s2時，編譯器會調(diào)用默認(rèn)的拷貝構(gòu)造。最終導(dǎo)致的問題是，s1、s2共用同一塊內(nèi)存空間，在釋放時同一塊空間被釋放多次而引起程序崩潰，這種拷貝方式，稱為淺拷貝。

??3.2 淺拷貝

由如上代碼我們了解了淺拷貝會帶來兩個問題：

• 析構(gòu)兩次空間
• 其中一個去修改，會影響另一個

淺拷貝：也稱位拷貝，編譯器只是將對象中的值拷貝過來。如果對象中管理資源，最后就會導(dǎo)致多個對象共享同一份資源，當(dāng)一個對象銷毀時就會將該資源釋放掉，而此時另一些對象不知道該資源已經(jīng)被釋放，以為還有效，所以當(dāng)繼續(xù)對資源進(jìn)項操作時，就會發(fā)生發(fā)生了訪問違規(guī)。

就像一個家庭中有兩個孩子，但父母只買了一份玩具，兩個孩子愿意一塊玩，則萬事大吉，萬一不想分享就你爭我奪，玩具損壞。

可以采用深拷貝解決淺拷貝問題，即：每個對象都有一份獨(dú)立的資源，不要和其他對象共享。父母給每個孩子都買一份玩具，各自玩各自的就不會有問題了。

??3.3 深拷貝

如果一個類中涉及到資源的管理，其拷貝構(gòu)造函數(shù)、賦值運(yùn)算符重載以及析構(gòu)函數(shù)必須要顯式給出。一般情況都是按照深拷貝方式提供。

深拷貝會新開辟一塊與原對象一樣大的空間，再把原對象空間上的值拷貝過來。

3.3.1 ??深拷貝的傳統(tǒng)版寫法的string類

string.h

#pragma once
namespace bit
{
	class string
	{
	public:
		string(char* str)
			:_str(new char[strlen(str) + 1]
		{
			strcpy(_str, str);
		}
		//s2(s1)
		string(const string& s)
			:_str(new char[strlen(s.str) + 1])
		{
			strcpy(_str, s._str);
		}
		//s1 = s3
		string operator=(const string& s)
		{
			if(this != &s)//防止自己賦值
			{
				/*delete[] _str;//this->_str
				_str = new char[strlen(s._str) + 1];*/
				char* tmp = new char[strlen(s._str) + 1];
				delete[] _str;
				_str = tmp;
				strcpy(_str, s._str);
			}
			return *this;
		}
		~string()
		{
			delete[] _str;
			_str = nullptr;
		}
		char& operator[](size_t pos)
		{
			return _str[pos];
		}
	private:
		char* _str;
	};
	void f1(string s)
	{}
	void f2(const string& s)
	{}
	template<class T>
	void f3(T x)
	{}
	void f3(const T& x)
	{}
	void test_string1()
	{
		string s1("hello");
		s1[0] = 'x';

		string s2(s1);
		s2[0] = 'y';
		
		string s3("hello bit");
		s1 = s3;
	
		f1(s1);
		f2(s2);
	}
}

string.cpp

#include"string.h"
int main()
{
	try
	{
		bit::test_string1();	
	}
	catch(exception& e)
	{
		cout << e.what() << endl;	
	}
	return 0;
}

3.3.2 ??深拷貝的現(xiàn)代版寫法的String類

class String
{
public:
	String(const char* str = "")
	{
		if (nullptr == str)
		{
			assert(false);
			return;
		}
		_str = new char[strlen(str) + 1];
		strcpy(_str, str);
	}
	String(const String& s)
		: _str(nullptr)
	{
		String strTmp(s._str);
		swap(_str, strTmp._str);
	}
	// 對比下和上面的賦值那個實(shí)現(xiàn)比較好？
	String& operator=(String s)
	{
		swap(_str, s._str);
		return *this;
	}
	/*
	String& operator=(const String& s)
	{
		if(this != &s)
		{
			String strTmp(s);
			swap(_str, strTmp._str);
		}
		return *this;
	}
	*/
	~String()
	{
		if (_str)
		{
			delete[] _str;
			_str = nullptr;
		}
	}
private:
	char* _str;
};

它們倆的效率是一樣的，但兩者都各有千秋

• 傳統(tǒng)寫法，可讀性高，便于理解，但操作性較低
• 現(xiàn)代寫法，代碼更加簡潔高效，但是邏輯更加復(fù)雜

??3.4 寫時拷貝(了解)

寫時拷貝就是一種拖延癥，是在淺拷貝的基礎(chǔ)之上增加了引用計數(shù)的方式來實(shí)現(xiàn)的。

引用計數(shù)：用來記錄資源使用者的個數(shù)。在構(gòu)造時，將資源的計數(shù)給成1，每增加一個對象使用該資源，就給計數(shù)增加1，當(dāng)某個對象被銷毀時，先給該計數(shù)減1，然后再檢查是否需要釋放資源，如果計數(shù)為1，說明該對象時資源的最后一個使用者，將該資源釋放；否則就不能釋放，因為還有其他對象在使用該資源。

早期 Linux 選擇了寫時拷貝的技術(shù)，而 VS 下選擇了直接深拷貝的技術(shù)。它們本質(zhì)都是深拷貝，只是說 Linux 下先做淺拷貝，如果不寫就不做深拷貝，寫了再去做深拷貝，并且是誰寫誰做。

寫時拷貝

寫時拷貝在讀取時的缺陷

??3.5 string類的模擬實(shí)現(xiàn)

#pragma once

namespace bit
{
	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;
		}

		/*string()
			:_str(new char[1])
			, _size(0)
			, _capacity(0)
		{
			_str[0] = '\0';
		}*/

		// 不能這么初始化空對象
		/*string()
			:_str(nullptr)
			, _size(0)
			, _capacity(0)
			{}*/

		//string(const char* str = "\0")
		/*string(const char* str = "")
			:_str(new char[strlen(str)+1])
			, _size(strlen(str))
			, _capacity(strlen(str))
		{
			strcpy(_str, str);
		}*/

	/*	string(const char* str = "")
			: _size(strlen(str))
			, _capacity(_size)
			, _str(new char[_capacity + 1])
		{
			strcpy(_str, str);
		}*/

		string(const char* str = "")
		{
			_size = strlen(str);
			_capacity = _size;
			_str = new char[_capacity + 1];

			strcpy(_str, str);
		}

		// 傳統(tǒng)寫法
		// s2(s1)
		//string(const string& s)
		//	:_str(new char[s._capacity+1])
		//	, _size(s._size)
		//	, _capacity(s._capacity)
		//{
		//	strcpy(_str, s._str);
		//}

		 s1 = s3
		 s1 = s1
		//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;
		//}

		// 現(xiàn)代寫法 -- 資本主義/老板思維
		// s2(s1)
		void swap(string& tmp)
		{
			::swap(_str, tmp._str);
			::swap(_size, tmp._size);
			::swap(_capacity, tmp._capacity);
		}

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

		// s1 = s3
		//string& operator=(const string& s)
		//{
		//	if (this != &s)
		//	{
		//		//string tmp(s._str);
		//		string tmp(s);
		//		swap(tmp); // this->swap(tmp);
		//	}

		//	return *this;
		//}

		// s1 = s3
		// s頂替tmp做打工人
		string& operator=(string s)
		{
			swap(s);
			return *this;
		}

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

		const char* c_str() const
		{
			return _str;
		}

		size_t size() const
		{
			return _size;
		}

		size_t capacity() const
		{
			return _capacity;
		}

		const char& operator[](size_t pos) const
		{
			assert(pos < _size);

			return _str[pos];
		}

		char& operator[](size_t pos)
		{
			assert(pos < _size);

			return _str[pos];
		}

		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(char ch)
		{
			// 滿了就擴(kuò)容
			/*if (_size == _capacity)
			{
				reserve(_capacity == 0 ? 4 : _capacity * 2);
			}

			_str[_size] = ch;
			++_size;
			_str[_size] = '\0';*/
			insert(_size, ch);
		}

		void append(const char* str)
		{
			//size_t len = strlen(str);

			 滿了就擴(kuò)容
			 _size + len  8  18  10  
			//if (_size + len > _capacity)
			//{
			//	reserve(_size+len);
			//}

			//strcpy(_str + _size, str);
			strcat(_str, str); 需要找\0，效率低
			//_size += len;
			insert(_size, str);
		}

		/*void append(const string& s)
		{
		append(s._str);
		}

		void append(size_t n, char ch)
		{
		reserve(_size + n);
		for (size_t i = 0; i < n; ++i)
		{
		push_back(ch);
		}
		}*/

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

		string& operator+=(const char* str)
		{
			append(str);
			return *this;
		}

		string& insert(size_t pos, char ch)
		{
			assert(pos <= _size);

			// 滿了就擴(kuò)容
			if (_size == _capacity)
			{
				reserve(_capacity == 0 ? 4 : _capacity * 2);
			}

			 挪動數(shù)據(jù)
			//int end = _size;
			//while (end >= (int)pos)
			//{
			//	_str[end + 1] = _str[end];
			//	--end;
			//}
			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);
			}

			// 挪動數(shù)據(jù)
			size_t end = _size + len;
			while (end >= pos+len)
			{
				_str[end] = _str[end - len];
				--end;
			}

			strncpy(_str + pos, str, len);
			_size += len;

			return *this;
		}

		void erase(size_t pos, size_t len = npos)
		{
			assert(pos < _size);

			if (len == npos || pos + len >= _size)
			{
				_str[pos] = '\0';
				_size = pos;
			}
			else
			{
				strcpy(_str + pos, _str + pos + len);
				_size -= len;
			}
		}

		size_t find(char ch, size_t pos = 0) const;
		size_t find(const char* sub, size_t pos = 0) const;
		bool operator>(const string& s) const;
		bool operator==(const string& s) const;
		bool operator>=(const string& s) const;
		bool operator<=(const string& s) const;
		bool operator<(const string& s) const;
		bool operator!=(const string& s) const;
	private:
		size_t _capacity;
		size_t _size;
		char* _str;

		// const static 語法特殊處理
		// 直接可以當(dāng)成定義初始化
		const static size_t npos = -1;
	};

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

		return out;
	}

	istream& operator>>(istream& in, string& s)
	{
		// 輸入字符串很長，不斷+=，頻繁擴(kuò)容，效率很低，大家可以想法優(yōu)化一下 
		char ch;
		//in >> ch;
		ch = in.get();
		while (ch != ' ' && ch != '\n')
		{
			s += ch;
			ch = in.get();
		}

		return in;
	}

	//size_t string::npos = -1;

	void test_string1()
	{
	    /*std::string s1("hello world");
		std::string s2;*/
		string s1("hello world");
		string s2;

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

		for (size_t i = 0; i < s1.size(); ++i)
		{
			cout << s1[i] << " ";
		}
		cout << endl;

		for (size_t i = 0; i < s1.size(); ++i)
		{
			s1[i]++;
		}

		for (size_t i = 0; i < s1.size(); ++i)
		{
			cout << s1[i] << " ";
		}
		cout << endl;
	}

	void test_string2()
	{
		string s1("hello world");
		string::iterator it = s1.begin();
		while (it != s1.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;

		it = s1.begin();
		while (it != s1.end())
		{
			*it += 1;
			++it;
		}
		cout << endl;

		for (auto ch : s1)
		{
			cout << ch << " ";
		}
		cout << endl;
	}

	void test_string3()
	{
		string s1("hello world");
		string s2(s1);
		cout << s1.c_str() << endl;
		cout << s2.c_str() << endl;

		s2[0] = 'x';
		cout << s1.c_str() << endl;
		cout << s2.c_str() << endl;

		string s3("111111111111111111111111111111");
		s1 = s3;
		cout << s1.c_str() << endl;
		cout << s3.c_str() << endl;

		s1 = s1;

		cout << s1.c_str() << endl;
		cout << s3.c_str() << endl;
	}

	void test_string4()
	{
		string s1("hello world");
		string s2("xxxxxxx");

		s1.swap(s2);
		swap(s1, s2);
	}

	void test_string5()
	{
		string s1("hello");
		cout << s1.c_str() << endl;
		s1.push_back('x');
		cout << s1.c_str() << endl;
		cout << s1.capacity() << endl;

		s1 += 'y';
		s1 += 'z';
		s1 += 'z';
		s1 += 'z';
		s1 += 'z';
		s1 += 'z';
		s1 += 'z';
		cout << s1.c_str() << endl;
		cout << s1.capacity() << endl;
	}

	void test_string6()
	{
		string s1("hello");
		cout << s1.c_str() << endl;
		s1 += ' ';
		s1.append("world");
		s1 += "bit hello";
		cout << s1.c_str() << endl;

		s1.insert(5, '#');
		cout << s1.c_str() << endl;

		s1.insert(0, '#');
		cout << s1.c_str() << endl;
	}

	void test_string7()
	{
		string s1("hello");
		cout << s1.c_str() << endl;

		s1.insert(2, "world");
		cout << s1.c_str() << endl;

		s1.insert(0, "world ");
		cout << s1.c_str() << endl;
	}

	void test_string8()
	{
		string s1("hello");
		s1.erase(1, 10);
		cout << s1.c_str() << endl;


		string s2("hello");
		s2.erase(1);
		cout << s2.c_str() << endl;

		string s3("hello");
		s3.erase(1, 2);
		cout << s3.c_str() << endl;
	}

	void test_string9()
	{
	/*	string s1;
		cin >> s1;
		cout << s1 << endl;*/

		string s1("hello");
		cout << s1 << endl;
		cout << s1.c_str() << endl;
		s1 += '\0';
		s1 += "world";
		cout << s1 << endl;
		cout << s1.c_str() << endl;

		string s3, s4;
		cin >> s3 >> s4;
		cout << s3<< s4 << endl;
	}
}

??4. 拓展閱讀

面試中string的一種正確寫法

STL中的string類怎么了文章來源地址http://www.zghlxwxcb.cn/news/detail-822149.html

到了這里，關(guān)于【C++】STL——string（兩萬字詳解）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！