~~~~ 串，也稱為字元串，在計算機上的非資料處理的對象基本都是字元串資料。

~~~~ stl是标準模闆庫，是标準庫的子集。std是命名空間。

介紹

~~~~ 字元串（String），是由零個或多個字元組成的有限序列。一般記為 s = a 1 a 2 … a n s = a 1 a 2 … a n （ 0 ≤ n ⪇ ∞ 0 ≤ n ⪇ ∞ ） { s=a_{1}a_{2}\dots a_{n}} s=a_{1}a_{2}\dots a_{n}（ {0\leq n\lneq \infty } 0\leq n\lneq \infty ） s=a1a2…ans=a1a2…an（0≤n⪇∞0≤n⪇∞）。它是程式設計語言中表示文本的資料類型。在程式設計中，字元串（string）為符号或數值的一個連續序列，如符号串（一串字元）或二進制數字串（一串二進制數字）。

~~~~ 字元串中任意個連續字元組成的子序列稱為該串的子串。包含子串的串相應地稱為主串。通常稱字元在序列中的序号為改字元在字元串中的位置。

操作

~~~~ 字元串基本操作不同的語言有所不同，我們這裡定義6種操作，包括：複制、附加、擷取長度，比較、查找、指派等，當然C語言對應的函數肯定不止6種，我們這裡就對這六種進行簡單的學習。代碼會在後面實作。

字元編碼

~~~~ 說到字元串，我們就必須說一下字元編碼，很多人在剛剛進入程式員這個行業的時候，遇到字元串多會碰到中文亂碼問題，這個就是字元編碼不一緻導緻的。

~~~~ 字元編碼（英語：Character encoding）、字集碼是把字元集中的字元編碼為指定集合中某一對象（例如：比特模式、自然數序列、8位組或者電脈沖），以便文本在計算機中存儲和通過通信網絡的傳遞。常見的例子包括将拉丁字母表編碼成摩斯電碼和ASCII。其中，ASCII将字母、數字和其它符号編号，并用7比特的二進制來表示這個整數。通常會額外使用一個擴充的比特，以便于以1個位元組的方式存儲。

~~~~ 在計算機技術發展的早期，如ASCII（1963年）和EBCDIC（1964年）這樣的字元集逐漸成為标準。但這些字元集的局限很快就變得明顯，于是人們開發了許多方法來擴充它們。對于支援包括東亞CJK字元家族在内的寫作系統的要求能支援更大量的字元，并且需要一種系統而不是臨時的方法實作這些字元的編碼。

~~~~ 很多時候我們的系統使用的都是utf-8，這也是大多數人的選擇，但是在中國，就會接觸到國标（政府相關的項目），我們就需要了解gb2312了，還有一個比較常用的就是unicode，這就不詳說，大家可以去了解一下。

實作

~~~~ 我去看過一些語言的字元串的實作，像進階語言，多是靜态申請，每次用多少，申請多少，每次都不同，如果從一個開發人員的角度考慮，我們是希望空間和時間最佳利用才是最好的，下面我實作了一個string類，采用的是eager-copy。

#ifndef MYSTRING_PTR_INCLUDE
#define MYSTRING_PTR_INCLUDE


#include <stdio.h>
#include <iostream>

class MyString_ptr
{
public:
	//構造函數
	MyString_ptr();//
	MyString_ptr(const MyString_ptr &);
	MyString_ptr(const char *);
	MyString_ptr(const size_t, const char *);
	//析構函數
	~MyString_ptr();

	// 字元串長度
	size_t length();
	// 判斷是否為空
	bool isEmpty();
	// 傳回c風格的trr的指針
	const char* c_str();

	// 重載運算符
	friend MyString_ptr operator+(const MyString_ptr&, const MyString_ptr&);
	friend bool operator==(const MyString_ptr&, const MyString_ptr&);
	// 擷取對應位置的字元
	char& operator[](const size_t);
	const char& operator[](const size_t)const;
	MyString_ptr& operator=(const MyString_ptr&);
	MyString_ptr& operator+=(const MyString_ptr&);

	// 比較函數
	int compare(const MyString_ptr& val);

	// 成員操作函數
	// 擷取從offset位置開始len長度的字元串
	MyString_ptr substr(size_t offset, const size_t len);
	// 附加字元串到末尾
	MyString_ptr& append(const MyString_ptr& val);
	// 插入字元串 在offset位置
	MyString_ptr& insert(size_t offset, const MyString_ptr& val);
	// 替換字元串
	MyString_ptr& assign(MyString_ptr&, size_t offset, size_t len);
	// 删除從offset位置開始len長度的字元串
	MyString_ptr& erase(size_t offset, size_t len);

	//find_first_of 查找某一個字元 size_t 是非符号數的,重載
	// 查找在字元串中第一個與str中的某個字元比對的字元，傳回它的位置。
	//搜尋從index開始，如果沒找到就傳回npos
	int find_first_of(const char* str, size_t index = 0);
	int find_first_of(const char ch, size_t index = 0);
	int find_first_of(const MyString_ptr &, size_t index = 0);

	// 在字元串中查找第一個與str中的字元都不比對的字元，傳回它的位置。搜尋從index開始。如果沒找到就傳回nops
	int find_first_not_of(const char* str, size_t index = 0);
	int find_first_not_of(const char ch, size_t index = 0);
	int find_first_not_of(const MyString_ptr&, size_t index = 0);

	/*
	一般來說，swap操作将容器内容交換不會導緻容器的指針、引用、疊代器失效。

	但當容器類型為array和string時除外。

	原因在于：SSO  (Short String Optimization 指C++針對短字元串的優化。)

　　預設情況下，C++的std::string都是存儲在heap中，導緻通路std::string需要經過一次尋址過程，速度較慢，并且這種實作的空間局部性不好，對cache的利用較低。

　　很多string的字元串長度很小，這個時候，我們可以把字元串存儲到棧上，進而不需要進行記憶體配置設定，優化建立速度，并且通路棧上資料的局部性很好，速度比較快。

	即C++會自動把較短的字元串放到對象内部，較長的字元串放到動态記憶體。
	假如 std::string 用 SSO 實作，而待交換的兩個對象中的字元串恰好一長一短，則原先指向短字元串中的疊代器會全部失效。
	*/
	// 交換
	void swap(MyString_ptr& val);

	// 字元替換
	MyString_ptr& replace_all(const char oldc, const char newc = 0);

	//查找
	int find(const char* str, size_t index = 0);


	static constexpr auto npos{ static_cast<size_t>(-1) };
private:
	char *p_str;
	size_t strLength;
};


size_t _strlen(const char *_dest);

char * _strcpy(char* _dest, const char* _src, int _src_len);

char * _strcpy(char* _dest, const char* _src);


#endif // !MYSTRING_PTR_INCLUDE

源檔案

#include "MyString_ptr.h"
#include <stdio.h>
#include <assert.h>
using namespace std;

size_t _strlen(const char *_dest) {
	size_t len = 0;
	if (!_dest) {
		return len;
	}
	//計算
	while (*_dest++) {
		len++;
	}
	return len;
}

char * _strcpy(char* _dest, const char* _src, int _src_len) {
	char * _pDest = _dest;
	assert(_dest && _src);//斷言，調試使用
	while (_src_len--) {
		*_dest++ = *_src++;
	}
	return _pDest;
}

char * _strcpy(char* _dest, const char* _src) {
	char * _pDest = _dest;
	assert(_dest && _src);
	while (*_src) {
		*_dest++ = *_src++;
	}
	return _pDest;
}

int _strcmp(const char* val1, const char* val2, int len){
	int cmp = 0;
	if(!val1 && !val2){
		return 0;
	}
	if(!val1) return -1;
	if(!val2) return 1;
	for(int i = 0; i < len; i++){
		cmp = val1[i] - val2[i];
		if(cmp != 0){
			return cmp;
		}
	}
	return cmp;
}

//構造函數
MyString_ptr::MyString_ptr() :p_str(NULL), strLength(0) {}

MyString_ptr::MyString_ptr(const MyString_ptr &val) : p_str(NULL), strLength(0) {
	//第一件事就是判斷是否為空
	assert(val.length > 0 && val.p_str);
	strLength = val.strLength;
	//申請空間
	p_str = new char[strLength];
	size_t i = strLength;
	//拷貝
	_strcpy(p_str, val.p_str, strLength);
}

MyString_ptr::MyString_ptr(const char *_src) : p_str(NULL), strLength(0) {
	if (!_src) {
		return;
	}
	strLength = _strlen(_src);
	//申請空間
	p_str = new char[strLength];
	//拷貝
	_strcpy(p_str, _src);
}

MyString_ptr::MyString_ptr(const size_t len, const char *_src) : p_str(NULL), strLength(0) {
	char* _p_src = NULL;
	size_t i = 0;
	if (!_src || !len) {
		return;
	}
	//申請空間
	p_str = new char[len];
	strLength = len;

	i = len;
	_p_src = p_str;
	//指派
	while (i--) {
		*_p_src++ = *_src++;
	}
	_p_src = NULL;
}

//析構函數
MyString_ptr::~MyString_ptr() {
	if (p_str) {
		delete p_str;
		strLength = 0;
	}
}

// 字元串長度
size_t MyString_ptr::length() {
	return strLength;
}

//判斷是否為空
bool MyString_ptr::isEmpty() {
	return strLength ? false : true;
}

//傳回c風格的trr的指針
const char* MyString_ptr::c_str() {
	return (const char*)p_str;
}

//重載運算符  a = b + c
MyString_ptr operator+(const MyString_ptr& val1, const MyString_ptr& val2) {
	//先判斷長度是否正常
	if (!val2.p_str || !val2.strLength) {
		return val1;
	}
	if (!val1.p_str || !val1.strLength) {
		return val2;
	}
	MyString_ptr ret;
	char *pStr = NULL;
	ret.strLength = val1.strLength + val2.strLength;
	ret.p_str = new char[ret.strLength];
    pStr = ret.p_str;
	_strcpy(pStr, val1.p_str, val1.strLength);
	pStr += val1.strLength;
	_strcpy(pStr, val2.p_str, val2.strLength);
	pStr = NULL;
	return ret;
}

bool operator==(const MyString_ptr& val1, const MyString_ptr& val2) {
	if(val1.strLength != val2.strLength){
		return false;
	}
	if(_strcmp(val1.p_str, val2.p_str, val1.strLength) == 0){
		return true;
	}
	return false;
} 

//擷取對應位置的字元
char& MyString_ptr::operator[](const size_t val) {
	return p_str[val];
}

const char& MyString_ptr::operator[](const size_t val)const {
	return (const char&)p_str[val];
}

MyString_ptr& MyString_ptr::operator=(const MyString_ptr& val) {
	if(strLength != val.strLength){
		if(p_str){
			delete p_str;
			p_str = NULL;
			strLength = 0;
		}
		if(!val.strLength){
			return *this;
		}
		strLength = val.strLength;
		p_str = new char[strLength];
		_strcpy(p_str, val.p_str, strLength);
		return *this;
	}
	if(!val.strLength){
		return *this;
	}
	_strcpy(p_str, val.p_str, strLength);
	return *this;
}

MyString_ptr& MyString_ptr::operator+=(const MyString_ptr& val) {
	if (!val.p_str || !val.strLength) {
		return *this;
	}
	char *pStr = NULL;
	int len = strLength + val.strLength;
	pStr = new char[len];
	_strcpy(pStr, p_str, strLength);
	if(p_str){
		delete p_str;
		p_str = NULL;
	}
	p_str = pStr;
	pStr += strLength;
	_strcpy(pStr, val.p_str, val.strLength);
	pStr = NULL;
	strLength = len;
	return *this;
}

//比較函數
int MyString_ptr::compare(const MyString_ptr& val){
	if(strLength > val.strLength){
		return 1;
	}
	if(strLength < val.strLength){
		return -1;
	}
	return _strcmp(p_str, val.p_str, strLength);
}

// 成員操作函數
// 擷取從offset位置開始len長度的字元串
MyString_ptr MyString_ptr::substr(size_t offset, const size_t len) {
	return MyString_ptr(len, p_str + offset);
}

// 附加字元串到末尾
MyString_ptr& MyString_ptr::append(const MyString_ptr& val) {
	if(!val.strLength){
		return *this;
	}
	char * pStr = NULL;
	int len = strLength + val.strLength;
    pStr = new char[len];
	_strcpy(pStr, p_str, strLength);
	if(p_str){
		delete p_str;
		p_str = NULL;
	}
	p_str = pStr;
	_strcpy(pStr + strLength, val.p_str, val.strLength);
	strLength = len;
	return *this;
}

// 插入字元串 在offset位置
MyString_ptr& MyString_ptr::insert(size_t offset, const MyString_ptr& val) {
	if(!val.strLength){
		return *this;
	}
	if(strLength < offset || !strLength){
		return this->append(val);
	}
	char * pStr = NULL;
	int len = strLength + val.strLength;
    pStr = new char[len];
	_strcpy(pStr, p_str, offset);
	_strcpy(pStr + offset, val.p_str, val.strLength);
	_strcpy(pStr + offset + val.strLength, p_str + offset, strLength - offset);
	if(p_str){
		delete p_str;
		p_str = NULL;
	}
	p_str = pStr;
	pStr = NULL;
	strLength = len;
	return *this;
}

// 替換字元串
MyString_ptr& MyString_ptr::assign(MyString_ptr& val, size_t offset, size_t len) {
	if(!len || offset > strLength || offset < 0){
		return *this;
	}
	int newlen = len + strLength;
	char *pnewStr = new char[newlen];
	
	_strcpy(pnewStr, p_str, offset);
	_strcpy(pnewStr + offset, val.p_str, len);
	_strcpy(pnewStr + offset + len, p_str + offset, strLength - offset);

	if(p_str){
		delete p_str;
		p_str = NULL;
	}
	p_str = pnewStr;
	pnewStr = NULL;

	strLength = newlen;
	return *this;
}

// 删除從offset位置開始len長度的字元串
MyString_ptr& MyString_ptr::erase(size_t offset, size_t len) {
	if(!len || offset < 0 || offset > strLength || offset + len > strLength){
		return *this;
	}
	int newlen = strLength - len;
	char* pnewStr = new char[newlen];

	_strcpy(pnewStr, p_str, offset);
	_strcpy(pnewStr, p_str + offset + len, strLength - len - offset);
	if(p_str){
		delete p_str;
		p_str = NULL;
	}
	p_str = pnewStr;
	pnewStr = NULL;
	strLength = newlen;
	return *this; 
}

//find_first_of 查找某一個字元 size_t 是非符号數的,重載
// 查找在字元串中第一個與str中的某個字元比對的字元，傳回它的位置。
//搜尋從index開始，如果沒找到就傳回npos
int MyString_ptr::find_first_of(const char* str, size_t index = 0) {
	if(!p_str || !str || index > strLength){
		return -1;
	}
	int len_str = _strlen(str);
	if(!len_str || len_str > strLength || len_str + index > strLength){
		return -1;
	}
	int j = 0;
	for(int i = index; i < strLength; i++){
		for(j = 0; p_str[i + j] == str[j] && j < len_str; j++);
		if(j == len_str){
			return i;
		}
	}
	return npos;
}
int MyString_ptr::find_first_of(const char ch, size_t index = 0) {
	if(!p_str || index > strLength){
		return -1;
	}

	for(int i = 0; i < strLength; i++){
		if(*p_str == ch){
			return i;
		}
	}
	return -1;
}
int MyString_ptr::find_first_of(const MyString_ptr &val, size_t index = 0) {
	if(!p_str || !val.strLength || index > strLength || val.strLength > strLength
	    || val.strLength + index > strLength){
		return -1;
	}
	int j = 0;
	for(int i = index; i < strLength; i++){
		for(j = 0; p_str[i + j] == val.p_str[j] && j < val.strLength; j++);
		if(j == val.strLength){
			return i;
		}
	}
	return -1;
}
// 在字元串中查找第一個與str中的字元都不比對的字元，傳回它的位置。搜尋從index開始。如果沒找到就傳回nops
int MyString_ptr::find_first_not_of(const char* str, size_t index = 0) {
	if(!str || strLength == 0 || index < strLength){
		return npos;
	}
	const char* p = str;
	bool isSuccess = false;
	for(int i = index; i < strLength; i++){
		p = str;
		isSuccess = false;
		while(*p){
			if(p_str[i] == *p){
				isSuccess = true;
				break;
			}
			p++;
		}
		if(!isSuccess){
			return i;
		}
	}
	return npos;
}
int MyString_ptr::find_first_not_of(const char ch, size_t index = 0) {
	if(strLength == 0 || index < strLength){
		return npos;
	}
	for(int i = index; i < strLength; i++){
		if(p_str[i] != ch){
			return i;
		}
	}
	return npos;
}
int MyString_ptr::find_first_not_of(const MyString_ptr& val, size_t index = 0) {
	if(val.strLength == 0 || strLength == 0 || index < strLength){
		return npos;
	}
	bool isSuccess = false;
	for(int i = index; i < strLength; i++){
		isSuccess = false;
		for(int j = 0; j < val.strLength; j++){
			if(val.p_str[j] == p_str[i]){
				isSuccess = true;
				break;
			}
		}
		if(!isSuccess){
			return i;
		}
	}
	return npos;	
}
// 交換
void MyString_ptr::swap(MyString_ptr& val) {
	val.strLength ^= strLength;
	strLength ^= val.strLength;
	val.strLength ^= strLength;

	char* p = p_str;
	p_str = val.p_str;
	val.p_str = p_str;
}
// 字元替換
MyString_ptr& MyString_ptr::replace_all(const char oldc, const char newc) {
	for(int i =0; i< strLength; i++){
		if(p_str[i] == oldc){
			p_str[i] = newc;
		}
	}
}
//查找
int MyString_ptr::find(const char* str, size_t index) {
	if(!str || strLength == 0 || index > strLength){
		return npos;
	}
	int _len = _strlen(str);
	if(index + _len > strLength){
		return npos;
	}
	int j = 0;
	for(int i = index; i < strLength; i++){
		for(j = 0; p_str[i + j] == str[j] && j < _len; j++);
		if(j == _len)return i;
	}
	return npos;
}

（上面的類，沒有做過多的測試，有問題可以找到我，-_-）

研究過的人就應該知道，string的主要優化方案還有cow（早期）和sso，對于這兩個的差別我們很多時候還是需要了解一下的。

同時在實作string類的時候，就考慮了一下c如何和sso，這應該是現在主要的對string類拷貝的優化方法了，這裡我就記錄一下對于cow和sso的了解，上面第一篇string的實作可以發現，使用的直接就是深拷貝，就是無論如果都是重新new一個對象直接複制資料

對于cow和sso，我寫了一個例子，大家可以自己運作看一下，在gcc5.0一起，個之後看結果如果：

#include <iostream>
#include <deque>
#include <string>

int main(){
    std::string str1 = "hello world!";
    std::string str2 = str1;
    if(str1.c_str() == str2.c_str()){
        std::cout << "true" << std::endl;
    }
    else{
        std::cout << "false" << std::endl;
    }
    std::string str3 = str2;
    str2 = "";
    if(str3.c_str() == str1.c_str()){
        std::cout << "true" << std::endl;
    }
    else{
        std::cout << "false" << std::endl;
    }
    str1 = "";
    if(str1.c_str() == str2.c_str()){
        std::cout << "true" << std::endl;
    }
    else{
        std::cout << "false" << std::endl;
    }
    return 1;
}

在兩個版本的gcc編譯的結果是不同的，一個true，true，true；一個是false，false，false，而這就是兩個不同的對于string的優化，也就是我們這裡要學習的cow和sso優化。

cow(copy or write)，字面意思了解就是複制或者寫，就是當我們平時使用拷貝的時候，或者是需要拷貝的時候，如果兩個字元串是一樣的，我們隻會進行位址的複制，而不是申請新的記憶體，進行拷貝；

而隻有當兩個字元串内容不一樣的時候，才會重新申請記憶體進行複制，這就會導緻某些時候資源占用會比較高，這有優點，也有缺點。當然缺點更大，在我們平時使用多線程的時候，就會有安全問題。

sso(short string optimization)

SSO政策中，拷貝均使用立即複制記憶體的方法，也就是深拷貝的基本定義，其優化在于，當字元串較短時，直接将其資料存在棧中，而不去堆中動态申請空間，這就避免了申請堆空間所需的開銷。

使用以下代碼來驗證一下：

int main() {
    string a = "aaaa";
    string b = "bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb";

    printf("%p ------- %p\n", &a, a.c_str());
    printf("%p ------- %p\n", &b, b.c_str());

    return 0;
}

某次運作的輸出結果為：

1
2
0136F7D0 ------- 0136F7D4
0136F7AC ------- 016F67F0

可以看到，a.c_str()的位址與a、b本身的位址較為接近，他們都位于函數的棧空間中，而b.c_str()則離得較遠，其位于堆中。

SSO是目前STL庫的實作方式，其優點就在于，對程式中經常用到的短字元串來說，運作效率較高。

下面我們就可以檢視一下stl中的string的實作

_GLIBCXX_BEGIN_NAMESPACE_CXX11

  template<typename _CharT, typename _Traits = char_traits<_CharT>,
           typename _Alloc = allocator<_CharT> >
    class basic_string;

  /// A string of @c char
  typedef basic_string<char>    string;   

#ifdef _GLIBCXX_USE_WCHAR_T
  /// A string of @c wchar_t
  typedef basic_string<wchar_t> wstring;   
#endif

#if ((__cplusplus >= 201103L) \
     && defined(_GLIBCXX_USE_C99_STDINT_TR1))
  /// A string of @c char16_t
  typedef basic_string<char16_t> u16string; 

  /// A string of @c char32_t
  typedef basic_string<char32_t> u32string; 
#endif

先看上面我們可以發現，string的基本長度不隻是char（一個位元組），也可以是兩個或者三個到四個，而不同長度的位元組，都可以使用basic_string，我們下面就是看basic_string類的實作。

代碼過多，我就不複制了，主要看它的存儲的方式：

template<typename _CharT, typename _Traits, typename _Alloc>
    class basic_string
...
      typedef typename _Alloc_traits::pointer		pointer;
...
      struct __sv_wrapper
      {
	explicit __sv_wrapper(__sv_type __sv) noexcept : _M_sv(__sv) { }
	__sv_type _M_sv;
      };
#endif

      // Use empty-base optimization: http://www.cantrip.org/emptyopt.html
      struct _Alloc_hider : allocator_type // TODO check __is_final
      {
#if __cplusplus < 201103L
	_Alloc_hider(pointer __dat, const _Alloc& __a = _Alloc())
	: allocator_type(__a), _M_p(__dat) { }
#else
	_Alloc_hider(pointer __dat, const _Alloc& __a)
	: allocator_type(__a), _M_p(__dat) { }

	_Alloc_hider(pointer __dat, _Alloc&& __a = _Alloc())
	: allocator_type(std::move(__a)), _M_p(__dat) { }
#endif

	pointer _M_p; // The actual data.
      };


      _Alloc_hider	_M_dataplus;
      size_type		_M_string_length;

      enum { _S_local_capacity = 15 / sizeof(_CharT) };

      union
      {
	_CharT           _M_local_buf[_S_local_capacity + 1];
	size_type        _M_allocated_capacity;
      };

看上面我們就發現了，它有一個16個位元組的字元數組，這就是之前說的sso，然後當我們使用字元串較短的時候，就會直接使用者個聯合體，而上面同樣有一個指針類型，用于字元串過長的時候，去堆中申請空間。

本文資料第三方資料主要來自維基百科。

找時間重寫一個sso的string類，到時候加到後面吧！如果想學sso，可以直接看std::string。

C++ 字元串 string介紹操作字元編碼實作

介紹

操作

字元編碼

實作

繼續閱讀

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

C#多線程——前台線程和背景線程

QName是什麼

成員函數初始化清單

2021-08-13c++——類之操作符重載

swmm與lisflood-fp源碼如何一起編譯 CMake指令

Windows下VS開發環境環境安裝工程項目設定關于Debug和Release的提示

一文看懂字元串的加減乘除

Android – ListView 中添加按鈕，動态删除添加ItemView的操作

C++ 第十五周報告1--《冒泡法排序》

C++實作簡單順序表

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

線性表之順序表的實作

GridView終極用法(一)

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述