目錄
一.模板
1.1函式模板
1.1.1模板呼叫程序
1.1.2模板的呼叫原理
1.1.3模板引數的匹配原則
1.2類模板
1.2.1類模板的定義
1.2.2類模板的實體化
二.STL
2.1STL的概念
2.2STL的六大組件
2.3常用容器1--string
2.3.1string的基本概念
2.3.2string的迭代器
2.3.3string方法
2.3.4深拷貝實作
2.3.5string類的實作
2.4常用容器2--Vector
2.4.1Vector基本概念
2.4.2Vector方法
2.4.3Vector模擬實作
2.4.4Vecotr迭代器失效
2.5常用容器3--list
2.5.1list容器的概念
2.5.2list常用介面方法
2.5.3list迭代器失效
2.5.4list容器的模擬實作
一.模板
1.1函式模板
函式模板是通用型別的代碼，是通用的函式描述，也就是說他們用泛型(泛型可具體指型別 )來定義函式，
舉個栗子：
//并不是一個真正的函式，他只是一個模板
template<typename T> //模板引數串列--告訴編譯器T是一種型別
T Add(T left,T right){//引數串列
cout<<typeid(T).name()<<endl; //查看型別
reutrn left+right;
}建立一個模板并將模板命名成T，關鍵字template和typename是必須的(在c++98添加temp那么之前，一直使用class理創建模板，)模板并不創建任何函式，只是告訴編譯器如何定義函式，
在撰寫模板的程序中，撰寫的模板可能無法處理某些型別，因此就要為特定型別提供具體化的模板定義，
1.1.1模板呼叫程序
模板被呼叫的程序就是實體化的程序，分為隱式實體化和顯示實體化，
- 隱式實體化:代碼在運行之前，現需要編譯，在編譯階段，對模板如果是隱式實體化編譯器會對傳遞的實參的型別進行推演，然后確定模板引數串列中T的實際型別，確定出來后，然后再根據確定的型別生成實際型別的代碼，
- 顯示實體化:在函式名后的<>中指定模板引數的實際型別稱之為顯示轉換，會直接指定模板引數串列中T的型別，編譯器在編譯代碼期間，可以直接根據用戶所提供的T型別生成處理具體型別，并且且生成代碼后，可能回對用戶傳遞的實參進行隱式轉化，
//隱式轉換與顯示轉轉換
template<class T>
T Add(const T& left, const T& right)
{
return left + right;
}
Add(1,2.0);//隱式轉換，編譯器會報錯
//因為在編譯期間，當編譯器看到該實體化時，需要推演其實參型別
//通過第一個將T推演為int，通過第二個實參將T推演為double型別，但模板引數串列中只有一個T，
//編譯器無法確定此處到底該將T確定為int 或者 double型別而報錯
//改變的方式：
//1.強轉
//2.可以在模板引數串列再加上一種型別,(在使用typename和class其實兩個都可以)
template<typename T,typename S>
//3.對函式模板進行顯示實體化，對其直接指明是什么型別
Add<int>(1,2.0);//顯示轉換如果型別不匹配，編譯器會嘗試進行隱式型別轉換，如果無法轉換成功，編譯器會報錯，
1.1.2模板的呼叫原理
函式模板是一個藍圖，它本身并不是函式，是編譯器使用方式產生特定具體型別函式的模具，所以其實模板就是將本來應該我們做的重復的事情交給了編譯器，在編譯器編譯階段，對于函式模板的使用，編譯器需要根據傳入的實參型別來推演生成對應型別的函數以供呼叫，
1.1.3模板引數的匹配原則
- 一個非模板函式可以和一個同名的函式模板同時存在，而且該函式模板還可以被實體化為這個非模板函式
- 對于非模板函式和同名函式模板，如果其他條件都相同，在調動時會優先呼叫非模板函式而不會從該模板產生出一個實體，如果模板可以產生一個具有更好匹配的函式，那么將選擇模板
- 模板函式不允許自動型別轉換，但普通函式可以進行自動型別轉換
1.2類模板
我們在之前寫代碼的時候，會使用typedef處理各種需求，然而之中方法有兩個缺點：首先是每次修改型別時都需要編輯頭檔案，其次實在每個程式中只能使用這種技術生成一種堆疊，既不能讓typedef同時代表兩種不同的型別，因此C++類模板為生成通用類宣告提供了好的方法，他不是具體的類，是編譯器根據實體化結果生成具體類的模板，
1.2.1類模板的定義
//定義格式
template<class T1, class T2, ...., class Tn>
class 類模板名
{
//類內成員定義
};舉個栗子：動態順序表，在這里我們要注意，vector不是具體的類，而是編譯器根據被實體化的型別生成具體類的模具，
template<class T>
class Vector
{
public:
Vector(size_t capaticy = 10)
:_pData(new T[capacity])
,_size(0)
,_capacity(capacity)
{}
//使用解構式演示：在類中宣告，在類外定義，
~Vector();
void PushBack(const T& data);
void PopBack();
//...
size_t Size() {
return _size;
}
T& operator[](size_t pos){
assert(pos < _size);
return _Pdata[pos];
}
private:
T* _pData;
size_t _size;
size_t _capacity;
};//注意：類模板中函式放在類外進行定義的時候，需要加上模板引數串列
template <class T>
Vector<T>::~Vector(){
if(_pDate)
delate[] _pData;
_size = _capacity = 0;
}1.2.2類模板的實體化
模板的具體實作被稱之為實體化或者具體化，不能將模板成員函式放在對立的實作檔案當中，模板不是函式，不能單獨編譯，必須將模板與其特定的模板實體化請求一起使用，類模板實體化與函式模板實體化不同，類模板實體化需要在類模板明知后面跟上<>,然后將實體化的型別放在<>中即可，類模板名字不是真正的類，而實體化的結果才是真正的類，
僅在程式包含模板是不能生成模板類，而必須請求實體化，為此，需要宣告一個型別為模板類的物件，方法是使用所需的具體型別替換泛型名，
//Vector列明，Vector<int>才是型別
Vector<int> s1;
Vector<double> s2;二.STL
2.1STL的概念
STL(standard template libaray-標準模板庫)：是C++標準庫的重要組成部分，不僅是一個可復用的組件庫，而且 是一個包羅資料結構與演算法的軟體框架，通俗的說，就是將常見的資料結構以模板的方式進行封裝，還增加了一些通用的靈活的演算法，(通用的體現：模板，與型別無關；find，任意型別資料結構組織資料都可以查找，與具體型別無關)（靈活地體現：讓用戶選擇定制演算法的功能）STL的一個重要特點是資料結構和演算法分離，另一個重要特點是他不是面向物件的，STL的核心思想在于將容器和演算法分開，彼此獨立設計，最后再重新組合在一起，
2.2STL的六大組件
STL中有六大組件，我們可以理解為有六個模塊，這六個模塊不是相互獨立的，
- 容器：容器是一種資料結構，是用來管理資料的，就是對常見資料結構進行封裝，常用的資料結構：陣列，鏈表，樹，堆疊，佇列，集合，映射表，（a.序列式容器：每個元素都有固定的位置，取決于插入的時機和地點，和元素無關；b.關聯式容器元素位置取決于特定的排序準則，和插入順序無關）
容器種類 序列式容器 Vector 將元素置于一個動態陣列中加以管理，可以隨機存取元素(用索引直接存取)，設計組的頭部和尾部添加或者移除元素都十分快速，但是在中部或者頭部插入元素十分費時， string 是動態型別順序表，字串是表示字符序列的類，標準的字串類提供了對此類物件的支持，其介面類似于標準字符容器的介面，但添加了專門用于操作 單位元組字符字串的設計特性，string類是使用char(即作為它的字符型別，使用它的默認char_traits和分配器型別， Deque 是“double-ended queue”的縮寫，可以隨機存取元素（用索引直接存取），陣列頭部和尾部添加或移除元素都非常快速，但是在中部或頭部安插元素比較費時， List 雙向鏈表，不提供隨機存取，在任何位置上執行插入和洗掉動作都十分迅速，內部只需調整一下指標， 關聯式容器 Set/Multiset 內部的元素依據其值自動排序，Set內的相同數值的元素只能出現一次，Multisets內可包含多個數值相同的元素，內部由二叉樹實作，便于查找， Map/Multimap Map的元素是成對的鍵值/實值，內部的元素依據其值自動排序，Map內的相同數值的元素只能出現一次，Multimaps內可包含多個數值相同的元素，內部由二叉樹實作，便于查找， - 迭代器：它是一種抽象的概念，提供了訪問容器種物件的方法，是只能夠依序尋訪某個容器所含的各個元素，而又無需暴露該容器的內部表示方式，
迭代器的種類 迭代器 功能 描述 輸入迭代器 提供對資料的只讀訪問 只讀，支持++，++，!= 輸出迭代器 提供對資料的只寫訪問 只寫，支持++ 前向迭代器 提供讀寫操作，并能向前推進迭代器 讀寫，支持++，++，!= 雙向迭代器 提供讀寫操作，并能向前和向后操作 讀寫，支持++，- 隨機訪問迭代器 提供讀寫操作，并能以跳躍的方式訪問容器的任意資料，是功能最強的迭代器 讀寫，支持++，-，[n]，-n，<，<=，>，>= - 演算法：是用來操作容器中的資料的模板函式，函式本身與他們操作的資料的結構和型別無關，因此他們可以再從簡單陣列到高度復雜容器的任何資料結構上使用，
- 配接器：標準庫提供了三種順序容器配接器：queue(FIFO佇列)、priority_queue(優先級佇列)、stack(堆疊)
- 仿函式(函式物件)，用來設計演算法的功能，讓演算法變得更加靈活，
- 空間配置器：在STL底層用來管理空間的申請，釋放， `
2.3常用容器1--string
2.3.1string的基本概念
- string是表示字串的字串類，，char*是一個指標，string是一個類，string封裝了char*，管理這個字串面試一個char*型的容器，
- 該類的介面與常規容器的介面基本相同，再添加了一些專門用來操作string的常規操作，
- string在底層實際是：basic_string模板類的別名，typedef basic_string string，
- 不能操作多位元組或者變長字符的序列，
2.3.2string的迭代器
迭代器主要是用來遍歷容器的，一般情況下遍歷string是直接使用for下或者范圍for，現在我們可以使用以下的函式進行操作：
| begin+end | begin獲取一個字符的迭代器 + end獲取最后一個字符下一個位置的迭 代器 |
| rbegin+rend | begin獲取一個字符的迭代器 + end獲取最后一個字符下一個位置的迭 代器 |
具體操作如下：
void test(){
string s("hello");
//使用正向迭代器來進行遍歷
string::iterator it = s.begin();
while(it != s.end()){
cout<< *it;
++it;
}
cout<<endl;
//使用反向迭代器
string::reverse_iterator rit = s.rbegin();
while(rit !=rend()){
cout<<*rit;
++rit;//此時指標向前走
}
cout<<endl;
}2.3.3string方法
1.string構造方式與遍歷方式，如下：
//構造
string s1("hello world");
string s2(10,'a');
string s3(s2);//拷貝構造
char* p = "ellow world";
string s5(p,p+5);//區間的方式進行構造
2.string類物件的容量操作：
| 函式名稱 | 功能說明 |
| size | 回傳字串有效字符長度 |
| length | 回傳字串有效字符長度 |
| capacity | 回傳空間總大小 |
| empty | 檢測字串釋放為空串，是回傳true，否則回傳false |
| clear | 清空有效字符 |
| reserve | 為字串預留空間 |
| resize | 將有效字符的個數該成n個，多出的空間用字符c填充 |
- 檢測size(),capacity(),clear(),empty()，length函式
注意：size()與length()方法底層實作原理完全相同，引入size()的原因是為了與其他容器的介面保持一致，一般情況下基本使用size()，clear()只是將string中有效字符清空，不改變底層空間大小，void test(){ string s("hello"); //查看有效元素的個數 cout << s.size() << endl; //底層空間最大存放對少 cout << s.capacity() << endl; //輸出字串的有效長度長度 cout << s.length() << endl; //判斷是否為空 if(s.empty()){ cout << "true:空!" << endl; }else{ cout << "false:不空！" << endl; } //清空 s.clear(); } - rsize()函式
在這里我們要注意，元素增多時可能會擴容，將元素個數減少時，容量是不改變的，當n>old_capacity，此時進行擴容，開辟新空間，拷貝元素，釋放就空間；n<old_capacity，此時進行容量減少，當n>15時，不會將容量縮小，n<=15時，將空間釋放掉，直接使用內部固定大小(在VS2013下進行的檢測)void test(){ string s("hello"); //擴容 or 減少 resize(size_t n, char ch);//將有效元素增加到n個，對出的空間，用ch補充 resize(size_t n);//將有效空間增加到n,多出的空間用默認值0補充 } - reverse()函式
注意，當引數大于底層空間的時候會發生擴容，在擴容的時候有有效元素的個數不會發生改變，縮小的時候以15為分界線，在大于15的時候，reverse在將容量縮小的時候，底層的容量不會發生變化，當小于等于15的時候，reverse才會真正將空間總的容量進行修改，(是15的原因：因為在VS2013環境下，內部還會有固定的長度為char型別的陣列：char xxx[16]；當其修改時小于15的時候，就會將原有的空間釋放掉，然后利用他本身固有的陣列)void test(){ string s("hello"); s.reserve(10);//將空間進行擴容到10 } - at()函式 :at函式檢測是否有越界
void test(){ string s("hello"); s.reserve(10);//將空間進行擴容到10 cout << s.at(100) << endl; //此時會報出例外 }
3.string的訪問及遍歷方法：
| 函式名稱 | 功能說明 |
| operator | 回傳pos位置的字符，const string類物件呼叫 |
| begin+end | begin獲取一個字符的迭代器 + end獲取最后一個字符下一個位置的迭 代器 |
| rbegin+rend | begin獲取一個字符的迭代器 + end獲取最后一個字符下一個位置的迭 代器 |
| 范圍for | C++11支持更簡潔的范圍for的新遍歷方式 |
代碼展示：
void Test()
{
string s("hello");
// 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();
while(rit != s.rend())
cout<<*rit<<endl;
// 3.范圍for
for(auto ch : s)
cout<<ch<<endl;
}4.string類物件的修改操作：
| 函式名稱 | 功能 |
| push_back | 在字串后尾插字符c |
| append | 在字串后追加一個字串 |
| operator+= | 在字串后追加字串str |
| insert | 在任意位置進行插入字串 |
| c_str | 回傳C格式字串 |
| erase | 任意位置字串的洗掉操作 |
| find+npos | 從字串pos位置開始往后找字符c，回傳該字符在字串中的位置 |
| rfind | 從字串pos位置開始往前找字符c，回傳該字符在字串中的位置 |
| substr | 在str中從pos位置開始，截取n個字符，然后將其回傳 |
代碼展示：
//追加操作，插入操作，洗掉操作
void test(){
string s;
s += "hello";
s += " ";
string s1 = ("lllll");
s = s.append(3,'!');//可以在s后面追加n個字符!
s = s.append(s1, 1, 2);//可以給s字串之后追加s1的1下標位置之后的2個字串
//在起始位置插入字串
s.insert(0, "abc ");
//在某個位置插入字符
s.insert(2,4,'a');//在2下標后的位置插入4個a
//在任意位置進行和洗掉
s.erase(0, 5);//在起始位開始向后置洗掉5個字符
//也可以通過迭代器的方式給出位置
s.erase(s.begin());//洗掉起始位置的字符
s.erase(s.begin(),s.end());//從開始洗掉到末尾
}//特殊操作
void test(){
//將string型別的字串轉成char*型別
string s("12345");
atoi(s.c_str());//先將s轉化成char*型別；在利用atoi()將其轉化成整形
//獲取檔案的后綴
string file("string.cpp");
string postFix = file.substr(file.find('.')+1);//先獲取字符.后面的字符位置，在獲取這個位置之后的字串
//獲取檔案的名字
string file2("F:\\work\\string.cpp");
string name = file2.substr(file2.rfind('\\')+1,file2.rfind('.')-(file2.rfind('\\')+1));
//從file2的末尾位置開始查找,找到'\\'后面的位置，
//再找到所找位置到'.'的字符數，進行輸出
}string在自動插入的時候會有自己的擴容機制，再VS下，擴容是按照1.5倍進行擴容，再linux下是按照2倍進行擴容，
2.3.4深拷貝實作
在這里我們發現了一個問題：如果一個類中沒有顯示提供拷貝建構式，則編譯器會生成一份默認的拷貝函式，拷貝方式是將一個物件中的內容原封不動的拷貝到另一個物件中，這是淺拷貝，但是因為String中涉及到了資源管理，如果使用編譯器生成默認拷貝建構式，最后就會導致多個物件在底層使用同一份資源，導致的結果就是多個物件在銷毀時，會將同一份資源釋放多次而導致代碼崩潰，
1.普通寫法：
class String{
public:
String(const char* str = ""){//建構式
if(nullptr == str){//先檢測用戶給出的字串是否為空
str = "";
//這樣無論如何str都有一個合法的指標--str一定是一個合法的字串
}
//開辟空間
_str = new char[strlen(str)+1];
//將str里的字串往當前物件里面進行拷貝
//strcpy(_str, str);淺拷貝相當于拷貝的是物件本身的內容
}
//解決淺拷貝的方式是使用深拷貝，深拷貝拷貝的是物件中管理資源中縮放的資料
//如果一個類中涉及到資源管理時，需要用戶顯示提供拷貝構造
//深拷貝方式：拷貝構造
String(const String& s):_str(new char[strlen(s._str)+1]){
//給新物件重新開辟空間
strcpy(_str,s._str);
}
//如果沒有顯式實作賦值運算子多載，會造成記憶體泄漏而且會在銷毀時因為資源釋放多次而造成代碼崩潰
String& operator=(const String& s){
if (this != &s){
delete[] _str;//將當前的空間釋放掉
_str = new char[strlen(s._str) + 1];//重新開辟一個空間，空間大小為s字串長度+1
strcpy(_str, s._str);//然后將s中的字串往當前空間進行拷貝
/*另一種方法，兩個效果一樣
char* temp = new char[strlen(s._str) + 1];
strcpy(temp, s._str);
delete[] _str;
_str = temp;
*/
}
return *this;
}
~String(){//因為物件里面管理了資源，所以一定要提供解構式
if (_str){
delete[] _str;
_str = nullptr;
}
}
private：
char* _str;
};
2.簡潔寫法：
class String{
public:
String(const char* str = ""){
if (nullptr == str)
{
str = "";
}
// 無論如何str都有一個合法的指標--str肯定是一個合法的字串
_str = new char[strlen(str) + 1];
strcpy(_str, str);
}
// 深拷貝方式：拷貝構造
String(const String& s)
: _str(nullptr){//此時如果沒有給其賦值=空，那么就是隨機值，
//那么在將臨時物件中指標與當前物件中指標進行交換后，temp._str中存放的是隨機值
//在建構式結束之前要進行銷毀,就必須釋放掉空間，當試圖去釋放時就會崩潰
String temp(s._str);//創建1個臨時物件，需要呼叫建構式來進行構造
swap(_str, temp._str);//將當前物件與temp的底層空間進行交換，此時相當于temp._str為空，他就不需要釋放空間
}
String& operator=(String s){
swap(_str, s._str);
return *this;
}
~String(){
if (_str)
{
delete[] _str;
_str = nullptr;
}
}
private:
char* _str;
};
2.3.5string類的實作
class string{
public:
//迭代器相關的
typedef char* iterator;
public:
//構造相關的
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;
}
string(size_t n,char ch):_str(new char[n+1])
,_capacity(n)
,_size(n){//用n個字符ch的方法來進行構造
memset(_str,ch,n);
_str[_size] = '\0';
}
string& operator=(const string& s){//賦值運算子多載
if(this != &s){
char* temp = new char[strlen(s._str)+1];
strcpy(temp, s_str);
delete[] _str;
_str = temp;
_size = s._size;
_capacity = s._capacity;
}
}
~string(){
if(_str){
delete[] _str;
_str = nullptr;
_capaticy = 0;
_size = 0;
}
}
public:
//迭代器
iterator begin(){
return _str;
}
iterator end(){
return _str + _size;
}
public:
//容量相關的
size_t size()const{
return _size;
}
size_t capacity()const{
return _capacity;
}
bool empty()const{
return 0 == _size;
}
void reverse(size_t newcapacity){
size_t oldcapacity = capacity();
if(_capacity() > oldcapacity){
//說明底層空間增加了
//開辟新空間
char* str = new char[newcapacity+1];
//拷貝元素
strcpy(str,_str);
//釋放舊的空間
delete[] _str;
//使用新得空間
_str = str;
_capacity = newcapacity;
}
}
void resize(size_t newsize,char ch){//將物件中的元素個數進行修改，多出的個數用ch填充
size_t oldsize = size();
if(nesize() <= oldsize){
//說明減少了
_size = newsize;
}else{
size_t cap = _capacity();
if(newsize > cap){//如果增加的size大于底層開辟的空間，那么就需要對底層空間增加
reverse(newsize * 2);
}
memset(_str + _size, ch, newsize-oldsize);
}
_str[_size] = '\0';
_size = newsize;
}
//元素訪問
char& operator[](size_t index){
assert(index < _size);
return _str[index];
}
public:
//modigy
void push_back(char ch){
*this += ch;
}
void append(char ch){
push_back(ch);
}
void append(string s){
*this += s;
}
string& operator+=(char ch){
//先考慮空間的大小
if(_size == _capacity){
//此時，size=capacity的時候，在進行添加，需要擴容
reverse(2 * _capacity);
}
//進行添加
_str[_size] = ch;
_str[_size+1] = '\0'
size += 1;
return *this;
}
string& operator+=(string s){
size_t newsize = s._size + _size;
if(newsize > _capacity){
reverse(2 * newsize);
}
strcat(_str+_size, s._str);
_size = newsize;
_str[_size] = '\0';
return *this;
}
void swap(string& s){
std::swap(_str,s._str);
std::swap(_size,s._size);
std::swap(_capacity,s._capacity);
}
void clear(){
_size = 0;
_str[_size] = '\0';
}
//其他操作
const char* c_str()const{
return _str;
}
size_t find(char ch,size_t pos = 0){
if(pos >= _size){
return npos;
}
for(size_t i = pos; i< _size; i++){
if(_str[i] == ch){
return i;
}
}
return npos;
}
size_t rfind(char ch,sizr_t pos = npos){//給成默認值
if(pos >= _size){
return npos;
}
for(size_t i = pos; i >=0; --i){
if(_str[i] == ch){
return i;
}
}
return npos;
}
string substr(size_t pos = 0, size_t n = npos){
assert(pos < _size);
size_t len = strlen(_str + pos);
n = min(len , n);//取最小的，因為若是超過了len會造成越界，因此取最小
string temp;
temp.rsize(n+1,0);
strncpy(temp._str,_str+pos,n);
return temp;
}
friend ostream& opsrator<<(ostream& _cout,const string& s){
_cout << s._str;
return _cout;
}
private:
char* _str;
size_t _size;
size_t _capacity;
statoc size_t npos;
};
size_t string::npos = -1;
2.4常用容器2--Vector
2.4.1Vector基本概念
vector是表示可變大小陣列的序列容器， 就像陣列一樣，vector也采用的連續存盤空間來存盤元素，也就是意味著可以采用下標對vector的元素進行訪問，和陣列一樣高效，但是又不像陣列，它的大小是可以動態改變的，而且它的大小會被容器自動處理， 本質講，vector使用動態分配陣列來存盤它的元素，當新元素插入時候，這個陣列需要被重新分配大小為了增加存盤空間，其做法是，分配一個新的陣列，然后將全部元素移到這個陣列，就時間而言，這是 一個相對代價高的任務，因為每當一個新的元素加入到容器的時候，vector并不會每次都重新分配大小，vector分配空間策略：vector會分配一些額外的空間以適應可能的增長，因為存盤空間比實際需要的存 儲空間更大，不同的庫采用不同的策略權衡空間的使用和重新分配，但是無論如何，重新分配都應該是 對數增長的間隔大小，以至于在末尾插入一個元素的時候是在常數時間的復雜度完成的，因此，vector占用了更多的存盤空間，為了獲得管理存盤空間的能力，并且以一種有效的方式動態增長，
2.4.2Vector方法
1.Vecotr定義
| 建構式說明 | 介面說明 |
| vector() | 無參構造 |
| vector（size_type n, const value_type& val = value_type()） | 構造并初始化n個val |
| vector (const vector& x); | 拷貝構造 |
| vector (InputIterator first, InputIterator last); | 使用迭代器進行初始化構造 |
#include<vector>
void test(){
vecotr<int> v1;
vector<int> v2(10,5);
int array[] = {1,2,3,4};
//區間構造
vector<int> v3(array,array + sizeof(array)/sizeof(array[0]));
//拷貝構造
vector<int> v4(v3);
vector<int> v5{1,2,3,4};
//使用迭代器
int myints[] = {16,2,77,29};
vector<int> fifth (myints, myints + sizeof(myints) / sizeof(int) );
for(vector<int>::iterator it = fifth.begin();it!=fifth.end();++it){
cout<<' '<<*it;
cout<<'\n';
}
}2.Vecotr迭代器的使用
| iterator的使用 | 介面說明 |
| begin+end | 獲取第一個資料位置的iterator/const_iterator， 獲取最后一個資料的下一個位置 的iterator/const_iterator |
| rbegin+ rend | 獲取最后一個資料位置的reverse_iterator，獲取第一個資料前一個位置的 reverse_iterator |
//迭代器進行列印
void test(){
vecotr<int>::iterator it = v.begin();
//1.
while(it != v.end()){
cout<<*it<<" ";
++it;
}
//2.
auto it = v.begin();
while(it != v.end()){
cout<<*it<<" ";
++it;
}
}3.Vecotr空間
| 容量空間 | 介面說明 |
| size | 獲取資料個數 |
| capacity | 獲取容量大小 |
| empty | 判斷是否為空 |
| resize | 改變vector的size |
| reserve | 改變vector放入capacity |
//空間容量操作
void test(){
vector<int> a(5,5);
size_t cap = a.capacity();//獲取容量大小
size_t size = a.size();//獲取資料個數
//reserve
a.reverse(20);//將空間容量增大到20
a.resize(2);//改變a的size的值，如果小于，則將多出的直接銷毀
a.rseize(10,6);//如果大于原來的size，則將其對出的個數用6進行填補，如果沒有給出val值，則將使用默認值填充
if(a.empty() == 0){
cout<<"此時是空的"<<endl;
}
}4.Vecotr增刪改查操作
| vector增刪改查操作 | 介面說明 |
| push_back | 尾插 |
| pop_back | 尾刪 |
| find | 查找 |
| insert | 在position之前插入val |
| erase | 洗掉position位置的資料 |
| swap | 交換兩個vector的資料空間 |
| operator[](size_t index) | 像陣列一樣訪問(注意：如果index越界，assert觸發) |
//insert在所給位置之前插入給定的值
iterator insert(iterator pos, const T& x);//在這個位置上插入x，回傳值是一個迭代器
void insert(iterator pos,size_t n,const T& x);//給n個x插入到pos位置之前
void insert(iterator pos,iterator first,iterator last);//[first,last)將一個區間進行插入，所以必須使用迭代器
iterator erase(iterator pos) ;//回傳的含義：將pos位置的元素洗掉后，讓pos后一個元素位置回傳來
iterator erase(iterator first,iterator last);//[first,last)//operator[]+index 和vector中新式for+auto的遍歷
void test(){
int a[] = {1,2,3,4};
vector<int> v(a,a+sizeof(a)/sizeof(a[0]));
//通過[]遍歷
for(size_t i = 0;i < v.size(); ++i){
cout<< v[i] <<endl;
}
//通過新式范圍for遍歷；注意，index越界，會拋出例外，out_of_range
for(auto e : v)
cout<< e <<" ";
cout<<endl;
//尾插和尾刪
v.push_back(5);//在v后面插入5
v.pop_back();//洗掉v的最后一個元素
//在pos之前位置上進行插入
veoctor<int>::inerator pos = fins(v.begin(),v.end(),3);//使用find查找3所在的位置的iterator
v.insert(pos, 5);//在pos位置插入5
//在pos位置進行洗掉
v.erase(pos);
//單個元素洗掉
veoctor<int>::iterator it = v.begin();
//auto it = v.begin();
while(it !=v.end()){
v.erase(it);
++it;
}
}5.創建二維陣列
void test(){
vector<vector<int>> vv;
vv.resize(5);
//方式1
for(size_t i = 0;i < 5; ++i){
vv[i].resize(6);
for(size_t j = 0; j < 6; j++){
vv[i][j] = j+1;
}
}
//方式2
vv.resize(5,vector<int>{1,2,3,4,5,6});
//方式3
vector<vector<int>> vv(5,vector<int>{1,2,3,4,5,6});
//遍歷
for(size_t i = 0; i < vv.size();++i){
for(sizt_t j = 0; j < vv[i].siez(); ++j){
cout<< vv[i][j]<<" ";
}
cout << endl;
}
}2.4.3Vector模擬實作
vector就是動態型別的順序表，
#include <iostream>
#include <assert.h>
using namespace std;
template<class T>
class vector{
public:
// vector的迭代器實際就是：原生態的指標
typedef T* iterator;
public:
vector()
: start(nullptr)
, finish(nullptr)
, endofstorage(nullptr){}
vector(int n, const T& data = T())
: start(new T[n])
, finish(start + n)
, endofstorage(finish){
for (int i = 0; i < n; ++i){
start[i] = data;
}
}
// 區間構造
// vector<int> v2(10, 5); // int int
template<class Iterator>
vector(Iterator first, Iterator last){//區間構造
size_t n = 0;
auto it = first;
while (it != last){
n++;
++it;
}
start = new T[n];
finish = start + n;
endofstorage = finish;
for (size_t i = 0; i < n; ++i){
start[i] = first[i];
}
}
vector(const vector<T>& v) :start(new T[v.size()]){//拷貝構造
for (int i = 0; i< v.size(); i++){
start[i] = v[i];
}
}
vector<T>& operator=(const vector<T>& v){
if(this !=v){
delete[] start;
start = new T[v.size()];
for (int i = 0; i< v.size(); i++){
start[i] = v[i];
}
}
}
~vector(){
if (start)
{
delete[] start;
start = finish = endofstorage = nullptr;
}
}
public:
//與迭代器相關的操作
iterator begin()
{
return start;
}
iterator end()
{
return finish;
}
//與容量相關的操作
size_t size()const{
return finish - start;
}
size_t capacity()const{
return endofstorage - start;
}
bool empty()const{
return start == finish;
}
void resize(size_t newsize,const T& data = T()){
size_t oldsize = size();
// 將有效元素個數減少到newsize個
if (newsize > oldsize){
// 將有效元素個數增加到newsize個
// 1. 考慮是否需要擴容
if (newsize > capacity())
reserve(newsize);
for (size_t i = size(); i < newsize; ++i){
start[i] = data;
}
}
finish = start + newsize;
}
void reserve(size_t newcapcity){
size_t oldcapacity = capacity();
if (newcapcity > oldcapacity){//新空間增大，進行擴容
size_t oldsize = size();
// 1. 開辟新空間
T* temp = new T[newcapcity];
// 2. 拷貝元素--->有些情況下可以，有些情況下不行
//memcpy(temp, start, oldsize*sizeof(T));
for (size_t i = 0; i < oldsize; ++i){
temp[i] = start[i];
}
// 3. 釋放舊空間
delete[] start;
// 4. 使用新空間
start = temp;
// 如果此時我們使用的是finish = start + size();有問題
//因為size()實作中是finish-start，連個指標相加，兩個指標所指向的空間應該相同，但是此時不相同
finish = start + oldsize;
endofstorage = start + newcapcity;
}
}
//元素訪問
T& operator[](size_t index){//訪問任意位置元素
assert(index < size());
return start[index];
}
const T& operator[](size_t index)const{
assert(index < size());
return start[index];
}
T& front(){//訪問首地址元素
return start[0];
}
const T& front()const{
return start[0];
}
T& back(){//范文末尾元素
return *(finish - 1);
}
const T& back()const{
return *(finish - 1);
}
//修改
void push_back(const T& data){
if (size() == capacity()){//檢測是否需要擴容
reserve(capacity() * 2 + 3);
}
*finish = data;
finish++;
}
void pop_back(){//尾刪
if (empty())
return;
--finish;
}
iterator insert(iterator pos, const T& data){
if (size() == capacity()){//任意位置插入
reserve(capacity() * 2 + 3);
}
// 需要將pos位置及其后續所有的元素整體往后搬移
iterator it = finish; // it元素要搬移到的位置
while (it != pos)
{
*it = *(it - 1);
--it;
}
*pos = data;
++finish;
return pos;
}
iterator erase(iterator pos){//洗掉任意位置元素
if (pos == end())
return pos;
iterator it = pos; // 元素要搬移到的位置
while (it != finish){
*it = *(it + 1);
++it;
}
--finish;
return pos;
}
void clear(){
// 有問題：存的是物件
finish = start;
// erase(start, last);
}
void swap(vector<T>& v){
std::swap(start, v.start);
std::swap(finish, v.finish);
std::swap(endofstorage, v.endofstorage);
}
private:
iterator start; //利用迭代器型別，相當于int*，指向陣列的起始位置
iterator finish;//執行陣列元素的末尾位置
iterator endofstorage;
};
2.4.4Vecotr迭代器失效
a.什么是迭代器失效
迭代器我們可以分成兩種，一種他就是指標，另一種實際上就是將指標重新封裝了一種新的型別iterator，迭代器的本質就是指標，迭代器失效實際上就是指標失效，指標失效指的是指標指向的空間不存在了，指標成了野指標，現在使用迭代器就相當于使用一個野指標，因此迭代器失效造成的后果就是程式崩潰，
b.vector在什么情況下失效
- 所有插入操作都有可能會引起迭代器失效
//情況1：所有插入方式都有可能會引起迭代器失效 void test(){ vector<int> v{1,2,3,4,5,6}; v.revere(8); auto it = v.begin(); v.push_back(7); v.push_back(8); v.push_back(9);//在插入9時需要擴容，此時迭代器會失效 //因為在進行擴容時會開辟新的空間，將就空間的資料復制到新空間 //并且將就空間進行釋放，而it依舊指向就空間，因此就是指向已經釋放的空間，因此會造成代碼崩潰 //push_back();insert();rserve();rsize();assgin();=等方法都會引起迭代器失效 while(it != v.end()){ cout<< *it <<" "; ++it; } cout<<endl; } - erase(iterator pos)：洗掉pos位置上的元素，洗掉成功后pos迭代器就失效了，
//情況2指定位置元素的洗掉操作erase() void(){ vector<int> v{1,2,3,4,5,6}; //使用find查找3的位置 vector<int>::iterator pos = find(v.begin(),v.end(),3); //洗掉pos位置上的資料會導致pos迭代器失效 v.erase(pos); cout<< *pos <<end;//此時會導致非法訪問 //erase洗掉pos位置元素后，pos位置之后的元素會往前搬移，沒有導致底層空間的改變，理論上講迭代器不應該會失效， //但是：如果pos剛好是最后一個元素，刪完之后pos剛好是end的位置，而end位置是沒有元素的 //那么pos就失效了，因此洗掉vector中任意位置上元素時，vs就認為該位置迭代器失效 了， } - swap()也會產生得帶起失效
void test(){
vector<int> v1{1,2,3,4,5};
auto it1 = v1.begin();
vector<int> v2{6,7,8,9,0};
auto it2 = v2.begin();
v1.swap(v2);
while(it1 != v1.end()){
cout<< *it1 <<" ";
++it1;
}
//因為v1和v2底層結構都是順序表，進行交換就是將底層空間進行交換
//然而此時it1是指向原v1的空間，但是此時v1已經與v2進行了交換，此時指向的是v2的空間
}c. 解決迭代器失效
在b中1情況下，上述操作完成后，如果想要繼續通過迭代器操作vector中的元素，只需要給it重新賦值就行，在b中2的情況下，也是直接用it給其重新賦值，
//情況1：所有插入方式都有可能會引起迭代器失效
void test(){
vector<int> v{1,2,3,4,5,6};
v.revere(8);
auto it = v.begin();
v.push_back(7);
v.push_back(8);
v.push_back(9);
it = v.begin();
while(it != v.end()){
cout<< *it <<" ";
++it;
}
cout<<endl;
}
//情況2指定位置元素的洗掉操作erase()
void(){
vector<int> v{1,2,3,4,5,6};
vector<int>::iterator pos = find(v.begin(),v.end(),3);
pos = v.erase(pos);
cout<< *pos <<end;//此時會導致非法訪問
}2.5常用容器3--list
2.5.1list容器的概念
list是序列容器的一種,序列式是指我們所學的線性資料結構，list的底層是帶頭結點的雙向鏈表結構，雙向鏈表中每個元素存盤在互不相關的獨立節點中，在節點中通過指標指向其前一個元素和后一個元素，list是可以在常數范圍內在任意位置進行插入和洗掉的序列式容器，并且該容器可以前后雙向迭代，list容器的方法list與forward_list非常相似：最主要的不同在于forward_list是單鏈表，只能朝前迭代，已讓其更簡單高效，與其他的序列式容器相比(array，vector，deque)，list通常在任意位置進行插入、移除元素的執行效率更好，與其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的隨機訪問，
2.5.2list常用介面方法
1.list的構造方法
| 建構式 | 介面說明 |
| list() | 構造空的list |
| list (size_type n, const value_type& val = value_type()) | 構造list中包含n個值為val的元素 |
| list (const list<T>& x) | 構造拷貝函式 |
| list (InputIterator first, InputIterator last) | 用區間進行構造，區間在(first,last)之間 |
//構造
void test(){
list<int> L1; // 頭結點，空的
list<int> L2(10, 5);
vector<int> v{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> L3(v.begin(), v.end());//區間構造
list<int> L4(L3);//拷貝構造
list<int> L5{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
L1 = L5;
}2.list迭代器的使用
| 函式宣告 | 介面說明 |
| end+begin | 回傳第一個元素的迭代器+回傳最后一個元素下一個位置的迭代器 |
| rend+rbegin | 回傳第一個元素的reverse_iterator,即end位置，回傳最后一個元素下一個位置的 reverse_iterator,即begin位置 |
- begin與end為正向迭代器，對迭代器執行++操作，迭代器向后移動
- rbegin(end)與rend(begin)為反向迭代器，對迭代器執行++操作，迭代器向前移動
void test(){
list<int> L1;
list<int> L5{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
L1 = L5;
auto it = L5.begin();//利用迭代器進行遍歷
while (it != L5.end()){
cout << *it << " ";
++it;
}
cout << endl;
// e實際就是L1鏈表中每個節點值域的一份拷貝
for (auto e : L1)
cout << e << " ";
cout << endl;
auto rit = L5.rbegin();
while (rit != L5.rend()){
cout << *rit << " ";
rit++;
}
}3.list增刪改查訪問等操作
| 函式宣告 | 介面說明 |
| empty | 檢測list是否為空，是回傳true，否則回傳false |
| size | list的有效節點 |
| resize | 增加list中的值，并且值為val |
| front | 回傳一個結點中的值得參考 |
| back | 回傳最后一個結點的值得參考 |
| push_front | 在list首元素之前加入val值 |
| pop_front | 洗掉list首元素 |
| push_back | 在list末尾插入val |
| pop_back | 洗掉尾元素 |
| insert | 在任意位置插入元素 |
| erase | 在任意位置洗掉元素 |
| swap | 交換兩個list中的元素 |
| clear | 清空list中的所有元素 |
| unique | 洗掉重復值(這組資料必須是有序的) |
| remove | 將所有值為val的元素全部進行洗掉 |
void test(){
list<int> L1;
if (L1.empty()){//檢測list中的元素是否為空
cout << "list is empty!!!" << endl;
}
else{
cout << "list is not empty!!!" << endl;
}
list<string> S1;
cout << s.size() << endl;//查看list中的有效結點
S.resize(5，"hello");//將list中的有效結點擴大到5個，并且用hello進行填充
L1.push_front(2);//在L1的首元素位置插入2
L1.push_front(1);//在L1的首元素位置插入1
L1.push_front(0);//在L1的首元素位置插入0
L1.push_back(3);//在L1的尾部位置插入3
L1.push_back(4);//在L1的尾部位置插入4
L1.pop_front();//洗掉首元素
L1.pop_back();//尾刪
L1.front() = 0;//將首元素修改成0，一般情況下不這樣進行使用
//在任意位置進行插入
auto it = find(L1.begin(), L1.end(), 2);
if(it != L1.end()){//進行插入
//插入單個元素，在元素2的位置插入元素0
L1.insert(it,0);//在it位置進行插入0
PrintList(L1);//再將結果進行列印
//在任意位置插入一段區間
int array[3] = {4,5,6};
L1.insert(L.end(),array,array+sizeof(array)/sizeof(array[0]));
PrintList(L1);//再將結果進行列印
}
//任意位置的洗掉,洗掉單個元素，再洗掉元素的時候，有可能會造成迭代器失效
L1.erase(it);//it位置的洗掉
//++it;這一步代碼會崩潰
//洗掉一段區間
L1.erase(L1.begin(),L1.end());//相當于clear
list<int> L2 = {1,3,6,9,2,4,6,8,1,3,6,9};
L2.sort();//對L2進行排序
L2.unique();//洗掉L2中的重復值
L2.reverse();//對L2進行逆置
list<int> L3 = {1,1,1,2,3,4,5,6,7};
L3.remove(1);//將值為1的資料全部進行洗掉
//他的是現實將L3拿到的值傳遞給fun這個方法，然后判斷是否需要洗掉
L3.remove_if(fun);//fun是傳進的函式，函式實作了你所想洗掉的什么資料的方法
}2.5.3list迭代器失效
失效的情況是指向的節點的無效，即該節點被洗掉了，因為list的底層結構為帶頭結點的雙向回圈鏈表，因此在list中進行插入時是不會導致list的迭代 器失效的，只有在洗掉時才會失效，并且失效的只是指向被洗掉節點的迭代器，其他迭代器不會受到影響，
void test(){
list<int> L{1,2,3,4,5};
//情況1
auto it = L.begin();
L.erase(it);
++it;
//情況2
L.assign(10,5);//將L中的10個有效元素用5填充
it++;
//情況3
list<int> L1 = {9,8,7,6,5,4};
L.swap(L1);//交換L與L1的有效元素
while(it != L.emd()){
cout<< *it << endl;
++it;
}
}2.5.4list容器的模擬實作
//模擬實作
template<class T>
struct ListNode{//節點的定義
ListNode(const T& x = T())
: next(nullptr)
, prev(nullptr)
, data(x){}
ListNode<T>* next;
ListNode<T>* prev;
T data;
};
template<class T>
struct ListIterator{
typedef ListNode<T> Node;
typedef ListIterator<T> Self;
public:
// 0. 構造
ListIterator(Node* n)
: node(n){}
// 1. 迭代器要能夠移動 ++、--
Self& operator++(){
node = node->next;
return *this;
}
Self operator++(int){
Self temp(*this);
node = node->next;
return temp;
}
Self& operator--(){
node = node->prev;
return *this;
}
Self operator--(int){
Self temp(*this);
node = node->prev;
return temp;
}
// 2. 能夠解參考
T& operator*(){
return node->data;
}
T* operator->(){
return &(node->data);
}
// 3. 迭代器要能夠比較
bool operator!=(const Self& s){
return node != s.node;
}
bool operator==(const Self& s){
return node == s.node;
}
Node* node;
};
template<class T>
class list{
typedef ListNode<T> Node;
public:
typedef ListIterator<T> iterator;
private:
void CreadHead(){//創建頭指標
head = new Node;
head->next = head;
head->prev = head;
}
public:
list(){//構造空的list
CreadHead();
}
list(int n, const T& data){//n個值為data，進行構造
CreadHead();//先創建空鏈表
for (int i = 0; i < n; ++i)
push_back(data);//插入
}
template<class Iterator>//告訴編譯器他是一個模板型別
list(Iterator first, Iterator last){
CreadHead();
while (first != last){
push_back(*first);
++first;
}
}
list(const list<T>& L){//拷貝構造
CreadHead();
auto it = L.begin();
while (it != L.end()){
push_back(*it);
++it;
}
}
~list(){//解構式
clear();
delete head;
head = nullptr;
}
//迭代器的操作
iterator begin(){
return iterator(head->next);
}
iterator end(){
return iterator(head);
}
//容量相關的
size_t size()const{
size_t count = 0;
Node* cur = head->next;
while (cur != head){//在雙向回圈鏈表中沒有空指標，因此當回圈一次結束后再一次指向head是就結束
++count;
cur = cur->next;
}
return count;
}
bool empty()const{
return head->next == head;
}
void resize(size_t newsize, const T& data = T()){//T()是如果沒有提供，給出默認值，寫成T()，如果T是內置型別這樣寫直接數他的型別，如果T是自定義型別，那么就相當于創建了一個匿名物件，是呼叫類里面的無參建構式，如果類里面沒有午餐的建構式就會進行報錯
size_t oldsize = size();
if (newsize >= oldsize){// 增多
for (size_t i = oldsize; i < newsize; ++i)
push_back(data);
}
else{// 減少
for (size_t i = newsize; i < oldsize; ++i)
pop_back();
}
}
T& front(){
return head->next->data;
}
const T& front()const{//因為const物件不能訪問普通的成員函式，因此還需要定義const型別的成員函式
return head->next->data;
}
T& back(){
return head->prev->data;
}
const T& back()const{
return head->prev->data;
}
//增刪改查操作
void push_back(const T& data){//尾插
insert(end(), data);
}
void pop_back(){//尾刪
auto it = head->prev;
erase(it);
}
void push_front(const T& data){//頭插
insert(begin(), data);
}
void pop_front(){//頭刪
erase(begin());
}
iterator insert(iterator pos, const T& data){//任意位置進行插入
Node* newnode = new Node(data);
Node* cur = pos.node;
newnode->next = cur;
newnode->prev = cur->prev;
newnode->prev->next = newnode;
cur->prev = newnode;
return iterator(newnode);
}
iterator erase(iterator pos){//任意位置進行洗掉
if (pos == end())
return pos;
Node* cur = pos.node;
Node* retnode = cur->next;
cur->prev->next = cur->next;
cur->next->prev = cur->prev;
delete cur;
// 洗掉
return iterator(retnode);
}
void swap(list<T>& L){//交換
std::swap(head, L.head);//直接講兩個鏈表的頭結點進行交換
}
void clear(){//將有效結點清空
Node* cur = head->next;
while (cur != head){
head->next = cur->next;
delete cur;
cur = head->next;
}
head->next = head;
head->prev = head;
}
private:
Node* head;
};轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/294210.html
標籤：其他