關于string的‘\0‘與string，vector構造特點，反迭代器與迭代器類等的討論

問題一：關于string的''\0''問題討論

問題二：C++標準庫中的string內存是分配在堆上面嗎？

問題三：string與vector的capacity大小設計的特點

問題四：string的流提取問題

問題五：迭代器失效

?問題六：Vector 最大最小值索引位置

問題7：反迭代器的實現（包含迭代器類的介紹）

前言：

前幾篇文章我們已經介紹完了string，vector，list的使用與string的使用原理，但是僅僅知道這些對于我們日常使用來說已經夠了，但是在我們日常使用的時候，不免會有報錯與相關的疑惑，那么這里我介紹幾個我認為有問題的地方，后續有問題的話，還會繼續補充。

問題一：關于string的''\0''問題討論

之前在某篇文章中看到，C語言字符串是以'\0'結尾的，但是C++string類型的字符串并不是以'\0'結尾。話不多說，直接放代碼（vsX86環境）：
#include<iostream>
#include<string>
using namespace std;
int main()
{string b("abc");cout << b.capacity() << endl;cout << b.size() << endl;if (b[3] == '\0')cout << "yes" << endl;elsecout << "no" << endl;return 0;
}
運行結果：

.

可以看到我們創建的這個string，他的容器大小為15，這個string存儲大小為3，但是我們卻可以通過越界訪問? b[3]? ?，并且通過驗證字符串的結尾就是'\0'。此時我的內心是疑惑的，心想"abc"是C語言風格的字符串給b構造，肯定會把"abc"后面影藏的'\0'給構造進去，如果不會這樣就會在迭代器里面不會遇見結束表示符。那么至于這里的結尾的最后一個'\0'，從結果來說是大小size不計算的，所以大小size是3。

但是我們又嘗試別的構造的話又會嘗試別的疑惑，比如這個代碼：

#include<iostream>
#include<string>
using namespace std;
int main()
{string b("abcd",3);//這種構造方法是通過字符串abcd，然后只取前3個字符進行構造string//但是這個字符串存放的其實是 abcd\0cout << b.capacity() << endl;cout << b.size() << endl;if (b[3] == '\0')cout << "yes" << endl;elsecout << "no" << endl;return 0;
}

結果跟上面一模一樣。此刻我又想，構造函數會在末尾自動添加一個'\0'，并且size和capacity函數都不計算'\0'的。

但是我們一開始是假設他跟c語言的風格相似的會把abc后面的'\0'會自動添加上，但是我們這個代碼是只取了abcd\0這個字符串的前三個，沒有'\0'啊~！

所以此刻，我肯定是矛盾的！！因為最開始說string字符串是不以'\0'結尾的，但是測試下來，確實是以'\0'結尾的。

哎呀~為什么呢？經過查閱資料后，才得知了其中的奧妙，奧妙如下：

std::string：標準中未明確規定需要\0作為字符串結尾。編譯器在實現時既可以在結尾加\0，也可以不加。（因編譯器不同，就比如vs就不用）

但是，當通過c_str()或data()（二者在 C++11 及以后是等價的）來把std::string轉換為const char *時，會發現最后一個字符是\0。但是C++11，string字符串都是以'\0'結尾（這也是c++祖師爺為以前的自己的規定的優化）。

為什么C語言風格的字符串要以'\0'結尾，C++可以不要？

c語言用char*指針作為字符串時，在讀取字符串時需要一個特殊字符0來標記指針的結束位置，也就是通常認為的字符串結束標記。而c++語言則是面向對象的，長度信息直接被存儲在了對象的成員中，讀取字符串可以直接根據這個長度來讀取，所以就沒必要需要結束標記了。而且結束標記也不利于讀取字符串中夾雜0字符的字符串。

這里我們深入一下string的構造時的細節：

#include<iostream>
#include<string>
using namespace std;
int main()
{int aa = 0;printf("棧區的地址：%p\n", &aa);int* pl = new int;printf("堆區的地址：%p\n", pl);string a("abcddddddddddddddddddddddddd", 20);printf("a的地址:    %p\n", &a);printf("a[0]的地址: %p\n", &a[0]);a[1] = 'X';cout << a << endl;printf("a的地址:    %p\n", &a);printf("a[0]的地址: %p\n", &a[0]);string b("abc");printf("b的地址:    %p\n", &b);printf("b[0]的地址: %p\n", &b[0]);return 0;
}

然后通過運行的知，

用紅色標注出來的是在棧上存儲的，藍色標注的時在堆上存儲的，然而a，b就與指針類似，他們指向一片空間，空間內存儲的對象信息，?對象地址分別是006FF6AC與006FF688,他倆的地址跟棧區地址最為接近所以該對象存儲在棧區上。同理a[0]是堆區上，但是b[0]按道理也應該是在堆區上，但是為什么會是是在棧區上呢？其實這是c++的一個特殊處理，這里留下一個小疑問，（下一個問題進行解答，這里先給出為什么的答案：當string內存存儲的個數在16以內（包括'\0'）（后面解釋為什么是16）在棧上，超過以后在堆上。）

所以，string在構造函數的時候，會在堆上開辟一塊內存存放字符串，并且指向這塊字符串。

（這里給大家提問一個小問題：就是為什么a先定義的，但是a對象地址為什么比b的大？）

解答：a、b是兩個局部對象變量，棧是向下增長的，所以先入棧的變量地址高，即&a > &b，

問題二：C++標準庫中的string內存是分配在堆上面嗎？

例如我聲明一個string變量。
string str;
一直不停的str.append("xxxxx");時，str會不停的增長。

我想問的是這個內存的增長，標準庫中的string會把內存放置到堆上嗎？

另外STL中的其他容器是否遵循相同的規則。

首先我們給出結論：16以內在棧上，超過以后在堆上。(這句話的答案省略上面的問題的前提條件：【在棧上構造的 string 對象】，如果string 是 new 出來的即在堆上構造的，當然內部的緩沖區總是在堆上的）。(vector也是如此，但是細節上略有不同）

為什么要這樣做呢？

如果以動態增長來解釋就是：

因為棧通常是一種具有固定大小的數據結構，如數組實現的棧在創建時會指定一個固定的容量。因此，一般情況下，棧是不支持動態增長的。?

所以是存儲在堆上的。

其實還有另一個原因，那么下一個問題給出解答；

問題三：string與vector的capacity大小設計的特點

在我們設計string與vector的時候，你是否觀察過他的capacity的大小呢？就比如vs里面為什么會讓string與vector在其存儲的內存個數小于16時會將數據存儲在棧上，大于16存儲在堆上呢？

這是因為string與vector第一次會在棧上開辟空間，直接開辟16個單位空間，然后挨個進行流提取，這樣的話就會方便很多?，就算要再添加數據，也不需要進行動態增長，然后這個16個單位空間就是string與vector的capacity。這里的證明可以通過調試自己查看他的capacity，當然編譯器不同，可能這個首次開辟空間大小略有不同，但是不影響。

總的來說這兩種解釋都是解決的次要問題，他這樣設計主要為了解決內存碎片的問題；如果存儲的內容大小小于16，他就會先存在棧上的數組里面，當大于16，就會進行拷貝到堆上，然后棧上的數組就會進行浪費，這樣達到了利用空間換時間的效果

問題四：string的流提取問題

首先如果我們自己實現string的流提取，我們會下意識認為會挨個提取輸入的字符，然后挨個與s進行對接，代碼試下如下：?（這個代碼實現的流提取是完全沒有問題的）

istream& operator>>(istream& in, string& s)
{s.clear();char ch;ch = in.get();while (ch != ' ' && ch != '\n'){s += ch;ch = in.get();}return in;
}

但是這樣寫會有一個弊端，就是會多次進行擴容，俗話常說：擴容本身就是一件麻煩的時，淺拷貝就不多說了，深拷貝就更麻煩了；

所以后來就進行了優化，會先開辟一個數組，然后將流提取的字符挨個放到數組里面，當數組滿的時候（或者流提取的字符提取完了）我們當讓s+=數組；這樣既保證了存儲的數據在堆上，也避免了多次進行擴容；（需要注意的是我們要自己添加 '\0' 在string的末尾）

	istream& operator>>(istream& in, string& s){s.clear();char buff[129];size_t i = 0;char ch;//in >> ch;ch = in.get();s.reserve(128);while (ch != ' ' && ch != '\n'){buff[i++] = ch;if (i == 128){buff[i] = '\0';s += buff;i = 0;}//in >> ch;ch = in.get();}if (i != 0){buff[i] = '\0';s += buff;}return in;}

當然這上面的兩個問題都是存在于string于vector上的，因為他們存儲的數據是連續的，二list作為鏈表就不存在這樣的問題。?

問題五：迭代器失效

然而迭代器失效就不一樣了，string，vector，list都存在。

在我們使用迭代器進行遍歷的時候，不免會出現不正當的使用而使其迭代器失效；

失效的主要原因就是：迭代器對應的指針所指向的空間已經被銷毀了，而使用一塊已經被釋放的空間的時候，就會造成程序崩潰(即如果繼續使用已經失效的迭代器，程序可能會崩潰)。俗話來說就是野指針了。

前面我們都在用string來進行解釋，這里我們使用vector來解釋，

1

就比如下面這個代碼：

include<iostream>
#include<vector>
using namespace std;int main()
{vector<int> v(10, 1);auto it = v.begin();v.insert(it, 0);(*it)++;return 0;
}

看起來沒有問題，但是我們是先給迭代器賦值，然后進行插入，但是有一點問題就是如果插入時恰好進行擴容，并且時異地擴容，那么這個it就會變為野指針。從而達到迭代器失效的問題。

2

同樣插入存在異地擴容，當然刪除也存在著迭代器失效的問題；

#include<iostream>
#include<vector>
using namespace std;int main()
{vector<int> v(10, 1);auto it = v.end() - 1;v.erase(it);(*it)++;return 0;
}

這時候如果再進行使用it，那么就會報錯。

注意：

vs 對于迭代器失效檢查很嚴格，如使用了 erase 之后，之前的迭代器就不允許使用，只有重新給迭代器賦值，才可以繼續使用
Linux下，g++編譯器對迭代器失效的檢測并不是非常嚴格，處理也沒有vs下極端。

?問題六：Vector 最大最小值索引位置

#include<iostream>
#include<vector>
using namespace std;int main()
{vector<double> v{ 1.0, 2.0, 3.0, 4.0, 5.0, 1.0, 2.0, 3.0, 4.0, 5.0 };vector<double>::iterator biggest = max_element(begin(v), end(v));cout << "Max element is " << *biggest << " at position " << distance(begin(v), biggest) << endl;auto smallest = min_element(begin(v), end(v));cout << "min element is " << *smallest << " at position " << distance(begin(v), smallest) << endl;return 0;
}

運行結果：

問題7：反迭代器的實現

在上一篇文章中的list的迭代器是沒有進行實現的，關于list的迭代器他的實現還是有點特殊的地方；?

迭代器類存在的意義

之前模擬實現string和vector時都沒有說要實現一個迭代器類，為什么實現list的時候就需要實現一個迭代器類了呢？

因為string和vector對象都將其數據存儲在了一塊連續的內存空間，我們通過指針進行自增、自減以及解引用等操作，就可以對相應位置的數據進行一系列操作，因此string和vector當中的迭代器就是原生指針。

然而對于list的來說，他的每個結點的存儲都不是連續的，是隨機的，不可以像string，vector那樣僅僅通過與簡單的自增，自減以及進行解引用等操作對相應的結點做操作。?

而迭代器的意義就是，讓使用者可以不必關心容器的底層實現，可以用簡單統一的方式對容器內的數據進行訪問。

既然list的結點指針的行為不滿足迭代器定義，那么我們可以對這個結點指針進行封裝，對結點指針的各種運算符操作進行重載，使得我們可以用和string和vector當中的迭代器一樣的方式使用list當中的迭代器。就比如，當你使用list當中的迭代器進行自增操作時，實際上執行了p = p->next語句，只是你不知道而已，這一步迭代器替你進行了復雜的操作，這樣就可以在各種操作上進行了統一。

總結： list迭代器類，實際上就是對結點指針進行了封裝，對其各種運算符進行了重載，使得結點指針的各種行為看起來和普通指針一樣。（例如，對結點指針自增就能指向下一個結點）

迭代器類的模板參數說明?

查閱相關std源文件庫里面的設計，發現迭代器類的模板參數的設計為3個。

template<class T, class Ref, class Ptr>

這里就引發出來思考為什么要這樣設計呢？

在list的模擬實現當中，我們typedef了兩個迭代器類型，普通迭代器和const迭代器。

typedef _list_iterator<T, T&, T*> iterator;
typedef _list_iterator<T, const T&, const T*> const_iterator;

?這里我們就可以看出，迭代器類的模板參數列表當中的Ref和Ptr分別代表的是引用類型和指針類型

?當我們使用普通迭代器時，編譯器就會實例化出一個普通迭代器對象；當我們使用const迭代器時，編譯器就會實例化出一個const迭代器對象。

若該迭代器類不設計三個模板參數，那么就不能很好的區分普通迭代器和const迭代器。（換句話來說，按照與string與vector的思路來寫list的const與非const迭代器再使用的時候會報錯，編譯器不知道走那個迭代器）

那么就再前面文章的基礎上加上迭代器類吧。

template <class T>
struct list_node
{T _data;list_node<T>* _prev;list_node<T>* _next;list_node(const T& x = T()):_data(x), _prev(nullptr), _next(nullptr){}
};
template<class T, class Ref, class Ptr>
struct __list_iterator 
{typedef list_node<T> Node;typedef __list_iterator<T, Ref, Ptr> self;Node* _node;		__list_iterator(Node* node):_node(node){}
}
class list
{typedef list_node<T> Node;
public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T,const T&,const T*> const_iterator;const_iterator begin() const{return const_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}iterator begin(){return _head->_next;}iterator end(){return _head;}
private:Node* _head;size_t _size;
};

?我們們迭代器類的構造函數就是用我們傳的結點參數來進行初始化。

?運算符重載需要注意要返回self就行

self是當前迭代器對象的類型：

介紹完迭代器類，下面就介紹反迭代器是怎么實現的吧；

同樣反迭代器我們也需要設計一個反迭代器類；

但是反迭代器的實現由于正向迭代器實現的思路又有所不一樣

其中他的成員變量是正向迭代器

大致如圖所示：

template<class Iterator, class Ref, class Ptr>
class Reserve_iterator
{typedef Reserve_iterator<Iterator, Ref, Ptr> Self;public:Reserve_iterator(Iterator it):_it(it){}
private:Iterator _it;
};

?同樣他與正向迭代器一樣，為了方便會進行typedef

rbegin與rend?

rbegin是其實是返回的end，rend其實是返回的begin，弄清楚這一點就比較好說了，只需要將begin傳到反迭代器類的rendend傳到反迭代器類的rbegin就可以了；

reserve_iterator rbegin()
{return reserve_iterator(end());
}
reserve_iterator rend()
{return reserve_iterator(begin());
}
const_reserve_iterator rbegin() const
{return const_reserve_iterator(end());
}
const_reserve_iterator rend() const
{return const_reserve_iterator(begin());
}

?operator++

對于反迭代器的++其實對應的就是正向迭代器的--

所以在實現的時候只需要進行減減就可以

	Self& operator++(){--_it;return *this;}

?這里返回的是引用其實很好理解，因為這里的++產生的效果是前置++，所以直接在原來的基礎上進行操作就可以，返回進行返回引用；

?operator--

同樣還有--，對應的也是正向迭代器的++，還是返回引用就可以

	Self& operator--(){++_it;return *this;}

這里就不一樣了，一個是返回的ref一個是ptr，這是因為我們在開始的情況下?，就將ref為引用，ptr為解引用。

到這里就完了，寫作不易還請點贊；