C++初階（vector容器+模擬實現）
迭代器
四種迭代器
容器類名::iterator 迭代器名;//正向迭代器
容器類名::const_iterator 迭代器名;//常量正向迭代器，const修飾，只能用於讀取容器內的元素，不能改變其值
容器類名::reverse_iterator 迭代器名;//反向迭代器
容器類名::const_reverse_iterator 迭代器名;//常量反向迭代器，const修飾，只能用於讀取容器內的元素，不能改變其值
begin + end： 獲取第一個數據位置的iterator/const_iterator， 獲取最後一個數據的下一個位置
的iterator/const_iterator
rbegin + rend： 獲取最後一個數據位置的reverse_iterator，獲取第一個數據前一個位置的reverse_iterator
C++為每種容器類型定義了一種名為const_iterator的類型，該類型只能用於讀取容器內的元素，但不能改變其值。
對const_iterator類型解引用，得到的是一個指向const對象的引用。
for (vector<string>::const_iterator iter = text.begin(); iter != text.end(); ++ iter){
cout << *iter << endl; //ok: print each element in text
*iter = " "; // error: *iter is const
}
const_iterator可以用於const或者非const容器（因為不能修改對象的值），但是const的iterator只能用於非const容器（只能修改唯一指向的值）。
const vector<int> nines(10, 9); // cannot change elements in nines
// error: cit2 could change the element it refers to and nines is const
const vector<int>::iterator cit2 = nines.begin();
// ok: it can't change an element value, so it can be used with a const vector<int>
vector<int>::const_iterator it = nines.begin();
*it = 10; // error: *it is const
++it; // ok: it isn't const so we can change its value
通過迭代器可以讀取它指向的元素，迭代器名就表示迭代器指向的元素。通過非常量迭代器還能修改其指向的元素。
迭代器都可以進行++操作。反向迭代器和正向迭代器的區別在於：
- 對正向迭代器進行
++操作時，迭代器會指向容器中的後一個元素； - 而對反向迭代器進行
++操作時，迭代器會指向容器中的前一個元素。
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> v; //v是存放int類型變量的可變長數組，開始時沒有元素
for (int n = 0; n<5; ++n)
v.push_back(n); //push_back成員函數在vector容器尾部添加一個元素
vector<int>::iterator i; //定義正向迭代器
for (i = v.begin(); i != v.end(); ++i) { //用迭代器遍歷容器
cout << *i << " "; //*i 就是迭代器i指向的元素
*i *= 2; //每個元素變為原來的2倍
}
cout << endl;
//用反向迭代器遍歷容器
for (vector<int>::reverse_iterator j = v.rbegin(); j != v.rend(); ++j)
cout << *j << " ";
return 0;
}
begin 成員函數返回指向容器中第一個元素的迭代器iterator
end 成員函數返回的不是指向最後一個元素的迭代器，而是指向最後一個元素後面的位置的迭代器
rbegin 成員函數返回指向容器中最後一個元素的迭代器reverse_iterator
rend 成員函數返回指向容器中第一個元素前面的位置的迭代器
vector介紹
vector的本質其實是一個順序表的結構，也可以說是數組存儲，與順序表的結構很相似，vector的接口更為完善。
vector容器是一個單口的容器，從頭部或者中間插入元素需要向後移動大量元素，是不是和棧很相似啊。
概述
vector容器
- 數據結構：連續存儲空間
- 迭代器：隨機迭代器，提供讀寫操作，並能在數據中隨機移
- vector容器動態增長原理：
- 當存儲空間不夠的時候，會另外開闢一塊更大的空間，把數據拷貝過去，然後銷毀原來的空間
- 申請的空間，會比用戶需求大一點
- 重新分配空間，那麼原來的迭代器就會失效（★）
- 常用的API
- 構造和析構
- 賦值操作
- 容器大小操作
- 數據存取
- 插入和刪除
- 常用API中的注意事項
- resize開闢空間，並初始化。reserve開闢空間，但不初始化，沒有初始化的空間不能訪問
- reserve：如果容器要存儲大量數據的時候，要先開闢空間，避免多次申請空間
- swap：縮小容器的容量
vector中常用的接口
vector的構造和析構函數
vector<T> v;//採用模板類實現，默認構造函數，無參構造的話，容器一開始是空的
vector(size_type n, const value_type& val = value_type())//有參構造用n個val構造並初始化容器
vector(const vector& vec);//拷貝構造函數
vector (v.begin(), v.end());//使用迭代器初始化，將v[begin(),end()]迭代器區間中的元素拷貝給本身
void TestVector()
{
vector<int> v1;// 無參構造
vector<int> v2(4, 100);// 有參構造
vector<int> v3(v2); // 拷貝構造
vector<int> v4(v3.begin(), v3.end());// 使用迭代器進行初始化
}
vector三種遍歷方式
- for+operator[]訪問遍歷（在vector模板類中重寫了[]）
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
// 三種遍歷方式
// 1.通過[]的方式遍歷
for (size_t i = 0; i < v.size(); ++i)
{
cout << v[i] << " ";
}
cout << endl;
2.迭代器
// 2.迭代器方式遍歷
// 和string類一樣，有四種迭代器
// iterator const_iterator reverse_iterator const_reverse_iterator
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
//正向迭代器iterator,指向容器中的第一個元素
vector<int>::iterator it = v.begin();
while (it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
//反向迭代器reverse_iterator，指向容器中的最後一個元素
vector<int>::reverse_iterator rit = v.rbegin();
while (rit != v.rend())
{
cout << *rit << " ";
++rit;
}
cout << endl;
3.範圍for
//3.範圍for 會被編譯器替換成迭代器的方式遍歷
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
vector賦值操作
assign(beg, end);//將[beg, end)區間中的數據拷貝賦值給本身。
assign(n, elem);//將n個elem拷貝賦值給本身。
vector&operator=(const vector&vec)//重載等號操作符
swap(vec);// 將vec與本身的元素互換。
vector<int> v;
v.assign(10, 6);
vector<int> v2;
v2.push_back(1);
v2.push_back(2);
v2.push_back(3);
printVector(v);
printVector(v2);
cout << "-----------------------------" << endl;
v.swap(v2);//交換v和v2的數據
vector增刪改查
insert(const_iterator pos, int count,ele);//迭代器指向位置pos插入count個元素ele
push_back(ele);//尾部插入元素ele
pop_back();//刪除最後一個元素
erase(const_iterator start, const_iterator end);//刪除迭代器從start到end之間的元素
erase(const_iterator pos);//刪除迭代器指向的元素
clear();//刪除容器中所有元素
vector<int> v;
for (int i = 0; i < 5; i++)
{
v.push_back(i);
}
printVector(v);
v.insert(v.begin() + 1, 100);
v.pop_back();
v.erase(v. begin());
v.erase(v.begin() + 1, v.end() - 1);
v.clear();
vecto容器大小操作
size();//返回容器中元素的個數
empty();//判斷容器是否為空
resize(int num);//重新指定容器的長度為num，若容器變長，則以默認值填充新位置。如果容器變短，則末尾超出容器長度的元素被刪除。
resize(int num, elem);//重新指定容器的長度為num，若容器變長，則以elem值填充新位置。如果容器變短，則末尾超出容器長度的元素被刪除。
capacity();//容器的容量
reserve(int len);//容器預留len個元素長度，預留位置不初始化，元素不可訪問。
//resize(int num)開闢空間並且初始化空間裏面的值
//reserve(int len)開闢空間但是不會初始化空間內的值
vector<int> v;
vector<int> v2;
v2.push_back(1);
v2.push_back(2);
v2.push_back(3);
cout << v2.size() << endl;
v2.resize(5);//多餘的位置初始化為0
v2.resize(2);//多餘的元素被刪除
v2.reserve(20);//開闢了20個空間，但是不會初始化，沒初始化的空間不能被訪問
v2.push_back(20);
//reserve的作用，當vector需要大量的空間的時候，需要用到reserve
//預開闢空間
void test0()
{
vector<int> v;
v.reserve(10000000);
int* p = NULL;
int num = 0;
//當vector容器的容量不夠的時候，vector會自動的開闢更大的空間
for (int i = 0; i < 10000000; i++)
{
v.push_back(i);
if (p != &v[0])
{
//統計開闢空間的次數
p = &v[0];
num++;
}
}
cout << num << endl;
}
vector迭代器失效的原因
迭代器的主要作用就是讓算法能夠不用關心底層數據結構，其底層實際就是一個指針，或者是對指針進行了封裝，比如：vector的迭代器就是原生態指針T*。因此迭代器失效，實際就是迭代器底層對應指針所指向的空間被銷毀了，而使用一塊已經被釋放的空間，造成的後果是程序崩潰(即如果繼續使用已經失效的迭代器，程序可能會崩潰)
兩種情況：
1.空間擴容
void TestVector6()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
vector<int>::iterator it = v.begin();
v.push_back(6);
v.push_back(7); // 迭代器失效，底層就是一個指針，尾插如數據是，因為擴容會導致空間會發生變化，指針指向的舊空間會被銷毀，所以迭代器失效
while (it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
擴容導致空間發生了變化，但是指針的指向沒有改變，如果我們此時再去訪問就相當於野指針的解引用了，編譯器會報錯。所以要及時更新迭代器的值就好了。
2.erase
void TestVector6()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
vector<int>::iterator it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
v.erase(it);// 迭代器失效，因為刪除會導致後面的數據往前挪動，此時迭代器會錯過一個數據，編譯器檢測就會報錯
++it;
}
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
程序崩了，刪除會導致後面的數據往前挪動，理論上不會失效，但是編譯器檢測就會報錯，這裡的失效是指迭代器的位置不對了。
如何修改呢？
void TestVector6()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
vector<int>::iterator it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
it = v.erase(it);// 給迭代器重新賦值
else
++it;
}
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
運行結果如下:
總結： 使用迭代器前記得對迭代器賦值，可以避免迭代器失效的問題產生。
vector模擬實現
vector框架
template<class T>
class vector
{
public:
private:
iterator start;// 起始位置的指針
iterator finish;// start+size
iterator endofstorage;// start+capacity
};
構造函數和析構函數
先實現一個無參構造，對三個成員進行初始化
vector():start(nullptr),finish(nullptr),endofstorage(nullptr)
{}
實現一個析構函數，釋放堆區空間，指針置空
~vector()
{
delete[] start;
start = nullptr;
finish = nullptr;
endofstorage = nullptr;
}
迭代器和operator[]實現
我們首先要定義迭代器的類型，在vector中，迭代器其實就是一個原生指針T*。所以我們這樣定義：
typedef T* iterator;
typedef const T* const_iterator;
下面是STL中vector的源碼定義：
1.普通迭代器 iterator
//begin()
iterator begin()
{
return start;
}
//end()
iterator end()
{
return finish;
}
2.const迭代器 const_iterator
//const迭代器
const_iterator begin()
{
return start;
}
const_iterator end()
{
return finish;
}
T& operator[](const size_t i) const
{
return start[i];
}
3.operator[]
T& operator[](const size_t i) const
{
return start[i];
}
vector中的增刪改查
1.reserve 預留空間，要考慮增容問題(拷貝數據不用memcpy，因為memcpy進行的是淺拷貝，對自定義類型處理會有問題，後面還會詳細介紹)
void reserve(size_t n)
{
int sz = size();
if (n > capacity())
{
T* tmp = new T[n];
if (start)
{
//memcpy(tmp, _start, sizeof(T) * sz);// 淺拷貝，對於自定義類型會出錯，string類
//賦值，對於string類就是賦值重載，也就是深拷貝
for (size_t i = 0; i < size(); i++)
{
tmp[i] = this->start[i];
}
}
delete[] this->start;
this->start = tmp;
this->finish = start + sz;
this->endofstorage = start + n;
}
}
2.push_back 尾插要考慮增容，增容都可以復用reserve函數
void push_back(T x)
{
if (finish == endofstorage)
{
size_t newcapacity = capacity() == 0 ? 2 : 2 * capacity();
reserve(newcapacity);
}
*finish = x;
++finish;
}
3.尾刪 注意要加一個assert(_finish > _start);確保不刪空
void pop_back()
{
assert(finish > start);
--finish;
}
4.insert 在pos位置插入一個元素
void insert(iterator pos, const T& x)
{
assert(pos <= end());
if (finish == endofstorage)
{
//算出原先差距，以免迭代器失效帶來一些問題
int gap = end() - pos;
size_t newcapacity = capacity() == 0 ? 2 : 2 * capacity();
reserve(newcapacity);
pos = end() + gap;
}
//所有元素後移
iterator end = finish;
while (pos < end)
{
*end = *(end - 1);
--end;
}
*pos = x;
++finish;
}
5.erase 刪除pos位置的元素
iterator erase(iterator pos)
{
assert(pos < finish && pos >= start);
iterator _start = pos;
while (_start + 1 < finish)
{
//所有元素前移
*_start = *(_start + 1);
++_start;
}
--finish;
return pos;
}
總結： 這裡要注意的是插入數據要考慮增容問題，增容我們可以封裝為一個reserve這個函數處理。
vector的容量問題
1.size
size_t size()const
{
return finish - start;
}
2.capacity
size_t capacity()const
{
return endofstorage + start;
}
3.empty
bool empty()
{
return size() == 0;
}
4.resize 改變size的大小，缺省值給T()，這個是根據不同類型給缺省值
//默認參數， T()是T類型的缺省值，具體是什麼也不清楚
void resize(size_t n, const T& val = T())
{
size_t sz = size();
if (n < sz)
{
finish = start + n;
}
else
{
if (n > capacity())
{
reserve(n);
}
iterator end = finish;
while (end < start + n)
{
*end = val;
++end;
}
finish = start + n;
}
}
vector的拷貝構造函數和operator=
1.swap 加一個域限定符::表示調用std裏面的swap函數
void swap(vector<T>& v)
{
::swap(start, v.start);
::swap(finish, v.finish);
::swap(endofstorage, v.endofstorage);
}
2.拷貝構造函數
寫法1：
vector(const vector<T>& v)
:start(nullptr)
,finish(nullptr)
,endofstorage(nullptr)
{
reserve(v.capacity());
for (auto e : v)
push_back(e);
}
寫法2：
vector(const vector<T>& v)
{
start = new T[v.capacity()];
finish = start + v.size();
endofstorage = start + v.capacity();
//memcpy(start, v._start, sizeof(T) * v.size());
for (size_t i = 0; i < size(); ++i)
{
start[i] =v. start[i];
}
}
3.operator= 復用swap函數，代碼更簡潔
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
memcpy拷貝問題
- memcpy是內存的二進制格式拷貝，將一段內存空間中內容原封不動的拷貝到另外一段內存空間中
- 如果拷貝的是內置類型的元素，memcpy既高效又不會出錯，但如果拷貝的是自定義類型元素，並且自定義類型元素中涉及到資源管理時，就會出錯，因為memcpy的拷貝實際是淺拷貝。
總結： 想什麼的拷貝構造函數和reserve函數裏面都不要使用memcpy進行拷貝，因為這些都是位元組序的拷貝，是淺拷貝，對於內置類型不會出問題，但是對於自定義類型會出現問題。
