目錄
1、認識string類
2、標準庫中的string類
2.1、string類的常見接口
2.1.1、構造與賦值重載
2.1.2、迭代器
2.1.3、容量
2.1.4、訪問
2.1.5、修改
2.1.6、字符串操作
2.1.7、成員常量
2.1.8、非成員函數
2.1.9、轉換函數
2.2、vs和g++下的string
2.2.1、vs下的string
2.2.2、g++下的string
3、OJ題
3.1、僅僅反轉字母
3.2、第一個出現一次的字符
3.3、最后一個單詞的長度
3.4、字符串是否回文
3.5、字符串相加
4、模擬實現
5、補充
1、認識string類
C語言中,字符串是以'\0'結尾的一些字符的集合,為了操作方便,C標準庫中提供了一系列字符串的庫函數, 但是這些庫函數與字符串是分離開的,不太符合面向對象的思想,而且底層空間需要用戶自己管理,稍不留神可能還會越界訪問。
在OJ題中,有關字符串的題目基本以string類的形式出現,而且在常規工作中,為了簡單、方便、快捷,基本都使用string類,很少有人去使用C庫中的字符串操作函數。
2、標準庫中的string類
string類是basic_string模板類的一個實例,它使用char來實例化basic_string模板類。這個類獨立于所使用的編碼來處理字節,string 類可以存儲多字節或變長字符序列,但在操作時是基于字節而非字符的。
string類的文件介紹
2.1、string類的常見接口
只講解最常用的接口,對其他的接口感興趣的可以點擊string類文件的介紹查看。
2.1.1、構造與賦值重載
string(); // 構造空的string類對象,即空字符串
string (const string& str); // 用string對象構造string對象
string (const char* s); // 用C式字符串構造string對象
string (size_t n, char c); // 用n個c構造string對象
string& operator= (const string& str); // 賦值重載
string& operator= (const char* s);
string& operator= (char c);
2.1.2、迭代器
// 正向迭代器
iterator begin(); // 返回第一個位置
iterator end(); // 返回第一個位置的下一個位置const_iterator begin() const;
const_iterator end() const; // 反向迭代器
reverse_iterator rbegin(); // 返回最后一個位置
reverse_iterator rend(); // 返回最后一個位置的上一個位置const_reverse_iterator rbegin() const;
const_reverse_iterator rend() const;
注:關于迭代器的原理,可以看看下面的string的模擬實現。
例如:
int main()
{string s1;string::iterator t1 = s1.begin();while (t1 != s1.end()){cout << *t1;++t1;}cout << endl;string s2("hello world");string::iterator t2 = s2.begin();while (t2 != s2.end()){cout << *t2;++t2;}cout << endl;string s3(s2);string::iterator t3 = s3.begin();while (t3 != s3.end()){cout << *t3;++t3;}cout << endl;string s4(10, 'a'); string::iterator t4 = s4.begin();while (t4 != s4.end()){cout << *t4;*t4 += 1;++t4;}cout << endl;const string s5(s2);string::const_reverse_iterator t5 = s5.rbegin();while (t5 != s5.rend()){cout << *t5;++t5;}cout << endl;string s6;s6 = s4;string::const_iterator t6 = s6.begin();while (t6 != s6.end()){cout << *t6;++t6;}cout << endl;return 0;
}
2.1.3、容量
size_t size() const; // 返回有效字符長度
size_t length() const; // 返回有效字符長度
void resize (size_t n); // 將有效字符的個數改為n個
void resize (size_t n, char c); // 將有效字符的個數改成n個,多出的空間用字符c填充
size_t capacity() const; // 返回空間的總大小
void reserve (size_t n = 0); // 預留空間
void clear(); // 清空字符串
bool empty() const; // 判斷是否為空,是返回true,否返回false
注意:
1、size()與length()方法底層實現原理完全相同,引入size()的原因是為了與其他容器的接口保持一 致,一般情況下基本都是用size()。
2、clear()只是將string中有效字符清空,不改變底層空間大小。?
3、resize(size_t n) 與 resize(size_t n, char c)都是將字符串中有效字符個數改變到n個,不同的是當字符個數增多時,resize(n)用0來填充多出的元素空間,resize(size_t n, char c)用字符c來填充多出的元素空間。
注意:resize在改變元素個數時,如果是將元素個數增多,可能會改變底層容量的大小,如果是將元素個數減少,底層空間總大小不變。
4、reserve(size_t n=0):為string預留空間,不改變有效元素個數,當reserve的參數小于string的底層空間總大小時,reserver不會改變容量大小。
例如:
int main()
{string s1("hello world");cout << s1.size() << endl;cout << s1.length() << endl;cout << s1.capacity() << endl;s1.clear();cout << s1.size() << endl;cout << s1.length() << endl;cout << s1.capacity() << endl;cout << s1.empty() << endl;s1 = "i am a student";cout << s1.size() << endl;cout << s1.length() << endl;cout << s1.capacity() << endl;s1.reserve(100);cout << s1.size() << endl;cout << s1.length() << endl;cout << s1.capacity() << endl;s1.resize(50, 'o');cout << s1.size() << endl;cout << s1.length() << endl;cout << s1.capacity() << endl;string::iterator t1 = s1.begin();while (t1 != s1.end()){cout << *t1;++t1;}cout << endl;return 0;
}
2.1.4、訪問
char& operator[] (size_t pos); // 返回pos位置的字符
const char& operator[] (size_t pos) const;
char& back(); // 返回最后一個元素
const char& back() const;
char& front(); // 第一個元素
const char& front() const;
// 范圍for
例如:
int main()
{string s1("i love you");for (int i = 0; i < s1.size(); i++){cout << s1[i];}cout << endl;cout << s1.front() << endl;cout << s1.back() << endl;string s2("aaaaaaaaaaaa");for (auto& e : s2) // 在底層實際上用的還是迭代器{cout << e;e += 1;}cout << endl;for (auto e : s2){cout << e;}return 0;
}
2.1.5、修改
string& operator+= (const string& str); // 追加字符串
string& operator+= (const char* s); // 重載
string& operator+= (char c); // 重載
string& append (const string& str); // 追加字符串
string& append (const char* s); // 重載
string& append (size_t n, char c) // 重載
void push_back (char c); // 尾插字符
string& insert (size_t pos, const char* s); // pos位置前插入字符串
注意:在string尾部追加字符時,s.push_back(c)和s.append(1, c)以及s += 'c'三種的實現方式差不多,一般情況下string類的+=操作用的比較多,+=操作不僅可以連接單個字符,還可以連接字符串。
例如:
int main()
{string s1("i am");s1 += " student";for (char s : s1){cout << s;}cout << endl;s1.push_back('!');s1.append("do you like me?");for (auto s : s1){cout << s;}cout << endl;s1.insert(13, " ");for (auto s : s1){cout << s;}return 0;
}
2.1.6、字符串操作
const char* c_str() const; // 返回C式字符串
size_t find (const char* s, size_t pos = 0) const; // 從pos位置向后開始查找字符串
size_t find (char c, size_t pos = 0) const;
size_t rfind (const char* s, size_t pos = npos) const; // 從pos位置向前查找字符串
size_t rfind (char c, size_t pos = npos) const;
string substr (size_t pos = 0, size_t len = npos) const; // 從pos位置開始截len個長度的字符串構造對象
例如:?
int main()
{string s1("i am");const char* s2 = s1.c_str();s1 += " student! do you like me?";size_t n = s1.find("like me", 0);string s3 = s1.substr(n, 7);for (auto e : s3){cout << e;}cout << endl;return 0;
}
2.1.7、成員常量
static const size_t npos = -1; // size_t類型的最大值
2.1.8、非成員函數
string operator+ (const string& lhs, const string& rhs); // 運算符重載
istream& operator>> (istream& is, string& str); // 流提取
ostream& operator<< (ostream& os, const string& str); // 流插入
istream& getline (istream& is, string& str); // 獲取一行字符串,默認遇換行結束
istream& getline (istream& is, string& str, char delim); // 可以指定遇到delim結束
bool operator== (const string& lhs, const string& rhs); // 等于
bool operator!= (const string& lhs, const string& rhs); // 不等于
bool operator< (const string& lhs, const string& rhs); // 小于
bool operator<= (const string& lhs, const string& rhs); // 小于等于
bool operator> (const string& lhs, const string& rhs); // 大于
bool operator>= (const string& lhs, const string& rhs); // 大于等于
例如:?
int main()
{string s1("100");s1 = s1 + "100";cout << s1 << endl;string s2;getline(cin, s2);cout << s2 << endl;cout << (s1 == s2) << endl;string s3;cin >> s3;cout << s3 << endl;cout << string::npos << endl;return 0;
}
2.1.9、轉換函數
int stoi (const string& str, size_t* idx = 0, int base = 10); // 轉換為整數
string to_string (int val); // 轉換為string類型
例如:
int main()
{string s1("100");int n = stoi(s1);n += 50;string s2 = to_string(n);for (auto e : s2){cout << e;}cout << endl;return 0;
}
上面的幾個接口了解一下,下面的OJ題目中會有一些體現他們的使用,此外還可以看string的模擬實現,來理解string類的使用。string類中還有一些其他的操作,這里不一一列舉,大家在需要用到時不明白了查文檔即可。?
2.2、vs和g++下的string
注意:下述結構是在32位平臺下進行驗證,32位平臺下指針占4個字節。
2.2.1、vs下的string
string總共占28個字節,內部結構稍微復雜一點,先是有一個聯合體,聯合體用來定義string中字 符串的存儲空間: 當字符串長度小于16時,使用內部固定的字符數組來存放當字符串長度大于等于16時,從堆上開辟空間。
2.2.2、g++下的string
G++下,string是通過寫時拷貝實現的,string對象總共占4個字節,內部只包含了一個指針,該指 針將來指向一塊堆空間,內部包含了如下字段: 空間總大小、字符串有效長度、引用計數。
寫時拷貝是寫時再進行深拷貝,是通過“淺拷貝”和引用計數機制,以及“延遲復制”策略來實現的。當創建對象或賦值時,多個對象可以共享同一份數據(不立即復制),只有當其中某個對象需要修改這份共享數據時,才會為它創建一份獨立的拷貝(即“寫”操作觸發復制)。
引用計數:用來記錄資源使用者的個數。在構造時,將資源的計數給成1,每增加一個對象使用該資源,就給計數增加1,當某個對象被銷毀時,先給該計數減1,然后再檢查是否需要釋放資源,如果計數為0,說明該對象為資源的最后一個使用者,將該資源釋放;否則就不能釋放,因為還有其他對象在使用該資源。
3、OJ題
3.1、僅僅反轉字母
僅僅反轉字母
參考:
3.2、第一個出現一次的字符
第一個出現一次的字符
參考:
3.3、最后一個單詞的長度
最后一個單詞的長度
參考:
注意:無論是scanf還是cin都有一個特點就是遇到空格或者換行就會結束。
3.4、字符串是否回文
驗證回文串
參考:
3.5、字符串相加
字符串相加
參考:
上面的這個題時間復雜度比較高,我們可以進行優化一下:
4、模擬實現
我們只實現string類的主要的功能。
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('\0')),_size(0),_capacity(0){}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);}/*String(const String& s)//傳統寫法的構造函數{_str = new char[s.capacity()+1];strcpy(_str, s._str);_size = s.size();_capacity = s.capacity();}*/void swap(String& s){std::swap(_str, s._str);std::swap(_size, s._size);std::swap(_capacity, s._capacity);//這個是算法庫里面的函數。}String(const String& s)//現代寫法的構造函數/*:_str(nullptr) //不寫這個在vs不報錯,但是在其他編譯器上不寫這個可能會出現錯誤。一般情況下,編譯器不會對自定義類型處理, _size(0) //但在vs上,編譯器把_str處理為nullptr,_size和_capacity處理為0。不處理的情況下,默認為隨機值,等到出作用域銷毀的, _capacity(0)*/ //時候,也就是delete的時候就會出現錯誤。{String tmp(s._str);swap(tmp);}~String(){delete[] _str;_str = nullptr;_size = _capacity = 0;}//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;//}//String& operator=(const String& s)//現代寫法//{// if (this != &s)// {// String tmp(s);// swap(tmp);// }// return *this;//}String& operator=(String s)//極致的現代寫法{swap(s);return *this;}// /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////普通的成員函數char& operator[](size_t pos){assert(pos < _size);return _str[pos];}const char& operator[](size_t pos) const//為const對象提供的重載形式{assert(pos < _size);return _str[pos];}const char* c_str() const{return _str;}void reserve(size_t n){if (n>_capacity){char* tmp = new char[n + 1];strcpy(tmp, _str);delete[] _str;_str = tmp;_capacity = n;}}void resize(size_t n, char c = '\0'){if (n <= _size){_str[n] = '\0';_size = n;}else{reserve(n);while (_size < n){_str[_size] = c;++_size;}_str[_size] = '\0';}}size_t find(char ch, size_t pos = 0){for (size_t i = pos; i < _size; i++){if (ch == _str[i]){return i;}}return npos;}String substr(size_t pos, size_t len = npos){String s;size_t end = pos + len;if (len == npos || len + pos >= _size){len = _size - pos;end = _size;}s.reserve(len);for (size_t i = pos; i < end; i++){s += _str[i];}return s;}size_t find(const char* sub, size_t pos = 0){const char* tmp = strstr(_str + pos, sub);if (tmp){return tmp - _str;}elsereturn npos;}void push_back(const char ch){if (_capacity == _size){reserve(_capacity == 0 ? 4 : _capacity * 2);}_str[_size] = ch;++_size;_str[_size] = '\0';}void append(const char* str){size_t len = strlen(str);if (len + _size > _capacity){reserve(len + _size);}strcpy(_str + _size, str);_size += len;}String& operator+=(char ch){push_back(ch);return *this;}String& operator+=(const char* str){append(str);return *this;}String& operator+=(const String& s){append(s._str);return *this;}void insert(size_t pos,char ch){assert(pos <= _size);if (_capacity == _size){reserve(_capacity == 0 ? 4 : _capacity * 2);}size_t end = _size+1;while (end > pos){_str[end] = _str[end - 1];--end;}_str[pos] = ch;++_size;}void insert(size_t pos, const char* str){assert(pos <= _size);size_t len = strlen(str);if (len + _size > _capacity){reserve(len + _size);}size_t end = _size+1;while (end > pos){_str[end+len-1] = _str[end-1];--end;}strncpy(_str + pos, str, len);_size += len;}void erase(size_t pos = 0, size_t len = npos){assert(pos < _size);if (len == npos || len + pos > _size){_str[pos] = '\0';_size = pos;}else{size_t begin = pos + len;while (begin <= _size){_str[begin - len] = _str[begin];++begin;}_size -= len;}}void clear(){_str[0] = '\0';_size = 0;}/*size_t size(){return _size;}size_t capacity(){return _capacity;}*/size_t size() const//其實寫了下面的兩個const修飾的成員函數就沒必要寫上面的兩個成員函數了。{return _size;}size_t capacity() const{return _capacity;}// ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////bool operator==(const String& s) const{return strcmp(_str, s._str) == 0;}bool operator<(const String& s) const{return strcmp(_str, s._str) < 0;}bool operator>(const String& s) const{return !(*this <= s);}bool operator<=(const String& s) const{return *this == s || *this < s;}bool operator>=(const String& s) const{return !(*this < s);}bool operator!=(const String& s) const{return !(*this == s);}// //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
private:char* _str;size_t _size;size_t _capacity;public:const static size_t npos;//為了在類外也能訪問,所以公開了。};const size_t String::npos = -1;// ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////*istream& operator>>(istream& in, String& s)
{s.clear();char ch = in.get();while (ch != ' ' && ch != '\n'){s += ch;ch = in.get();}return in;
}*/istream& operator>>(istream& in, String& s)//上面的優化版本
{s.clear();char buff[129];size_t i = 0;char ch; //流提取默認遇到空格或者換行結束//in >> ch; //這種寫法是不行的,因為流提取沒法提取空格或者換行。ch = in.get();//這里的get函數是庫里面的函數,這個函數是可以拿到空格和換行的。while (ch != ' ' && ch != '\n'){buff[i++] = ch;if (i == 128){buff[i] = '\0';s += buff;i = 0;}ch = in.get();}if (i != 0){buff[i] = '\0';s += buff;}return in;
}ostream& operator<<(ostream& out, const String& s)
{/*for (size_t i = 0; i < s.size(); i++){out << s[i];}*/for (auto ch : s)//范圍for也是可以的。out << ch;return out;
}
5、補充
編碼表:值和符號一一映射的關系。
ASCII表被制作時僅僅考慮到了英文,為了讓電腦能呈現其他國家的語言,所以就制作了Unicode統一碼,也叫萬國碼。Unicode又可以分為UTF-8、UTF-16、UTF-32。UTF-8是兼容ASCII表的,對于常見的漢字,用UTF-8編碼占兩個字節,越是不常用的漢字占的字節數越多,但不超過4個字節。
GBK全稱《漢字內碼擴展規范》,之所以會有GBK的存在是因為有些生僻字或者古漢字用Unicode不能很好的兼容,因而制作出了更符合中國的GBK編碼,使用了雙字節的編碼方案。?
Windows上一般使用GBK,Linux上一般用UTF-8。
亂碼一般是指存儲方式和解釋方式不同而導致的解析出的一些沒有規律的字符或者數字等。