~~~~ 串,也稱為字元串,在計算機上的非資料處理的對象基本都是字元串資料。
~~~~ 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。