文章目錄
- 前言
- 一、vector的介紹
- 二、vector的使用
- 1.建構式
- 2.遍歷
- 3.資料的插入與洗掉
- 3.resize和reserve
- 三、vector的模擬實作
- 1.成員變數
- 2.建構式
- (1)默認建構式
- (2)拷貝構造
- (3)構造含有n個val的vector
- 3.解構式
- 4.賦值運算子多載
- 5.一些簡單的函式
- 6.reserve和resize
- (1)reserve
- (2)resize
- 7.資料的增刪查改
- (1)push_back
- (2)pop_back
- (3)insert
- (4)erase
- 四、迭代器失效問題
- 1.引起其底層空間改變的操作
- 2.指定位置元素的erase操作
- 感謝閱讀,如有錯誤請批評指正
前言
vector和string一樣,都是最簡單的容器,邏輯和實作上都非常類似,所以本篇內容很多需要注意的地方在【C++】STL:string的模擬實作和【C++】STL:string的使用中都已提到過,讀者如有問題可閱讀這兩篇文章對應位置,
一、vector的介紹
vector是表示可變大小陣列的序列容器,采用連續的存盤空間來存盤元素,也就是意味著可以采用下標對vector的元素進行訪問,和陣列一樣高效,但是又不像陣列,它的大小是可以動態改變的,而且它的大小會被容器自動處理,包含在< vector >頭檔案下,
二、vector的使用
STL之所以好用,不僅是因為它提供了常見的資料結構容器及操作,更是因為對容器的操作大部分相似,學習成本很低,
在【C++】STL:string的使用中已經介紹了string的操作,而vector的操作也大同小異,所以下面只給出vector使用的例子,而不再系統地講解每個操作函式的功能,
1.建構式
常用的構造一個vector有如下五種方法,通過除錯可以看到它們具體的內容,

還有一種特殊的結構vector<vector< int >>,如果是第一次見到可能不容易理解,其實這就是一個二維陣列,

2.遍歷
這里的遍歷仍有三種方法,迭代器是STL中所有容器都支持的遍歷方式;范圍for是一種簡便寫法,實質仍是迭代器,也是所有容器都可用;下標+[]是string和vector才能用的,因為它們的地址空間是連續的,同時這三種方法均是可讀、可寫,
代碼如下:
int main()
{
vector<double> v = { 1.1, 2.2, 3.14, 6.66 };
//1.迭代器
vector<double>::iterator it = v.begin();
while (it != v.end())
{
cout << *it << " ";
it++;
}
cout << endl;
//2.范圍for
for (double e : v)
cout << e << " ";
cout << endl;
//3.下標+[]
for (size_t i = 0; i < v.size(); i++)
cout << v[i] << " ";
cout << endl;
return 0;
}
運行結果如下:

3.資料的插入與洗掉
針對資料的操作有如下四種,如果對STL熟悉的話只看函式名應該就可以知道這個函式的功能,

代碼如下:
//一個列印v中資料的函式
template<class T>
void print(const vector<T>& v)
{
//傳的v是const修飾的,所以這里要用const迭代器
vector<T>::const_iterator it = v.begin();
while (it != v.end())
{
cout << *it << " ";
it++;
}
cout << endl;
}
int main()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(30);
v.push_back(4);
v.push_back(6);
print(v);
v.pop_back();
print(v);
//find為C++演算法庫中的查找函式
//給出迭代器區間和要查找的資料即可查找
vector<int>::iterator it = find(v.begin(), v.end(), 30);
if (it != v.end())//找到了
{
//在30之前插入-20
v.insert(it, -20);//insert的第一個引數要用迭代器
}
print(v);
//洗掉it前面的資料
v.erase(it);
print(v);
return 0;
}
運行結果如下:

3.resize和reserve
對于一個順序表v,size是當前v中的資料個數,capacity是v中能存盤的最大資料個數,
代碼如下:
int main()
{
vector<int> v;
//size:當前v中的資料個數
//capacity:v中能存盤的最大資料個數
cout << "size:" << v.size() << endl;
cout << "capacity:" << v.capacity() << endl << endl;
v.resize(30);
cout << "size:" << v.size() << endl;
cout << "capacity:" << v.capacity() << endl << endl;
v.reserve(50);
cout << "size:" << v.size() << endl;
cout << "capacity:" << v.capacity() << endl << endl;
return 0;
}
運行結果如下:

三、vector的模擬實作
1.成員變數
在資料結構(一):順序表中實作順序表時,使用的結構是一個動態開辟的陣列+size+capacity,而STL底層實作vector時使用三個指標完成的,這里模仿它來完成,
代碼如下:
template<class T>
class Vector
{
public:
//...
private:
T* _start;
T* _finish;
T* _endOfStorage
};
_start指向這段資料的開始,_finish指向有效資料的末尾的下一個位置,_endOfStorage指向_start開辟的整個空間的末尾,具體如下,

由上圖很容易看出,size = _finish - _start,capacity = _endOfStorage - _start,
由于vector存放資料時地址是連續的,所以迭代器也是原生指標,所以可將上面的代碼封裝如下:
template<class T>
class Vector
{
public:
typedef T* Iterator;
private:
Iterator _start;
Iterator _finish;
Iterator _endOfStorage;
};
2.建構式
這里實作多個建構式多載,
在建構式這里使用了一些下面會實作的函式,如果對這些函式不是很明白,可以先往下看,明白這些函式的底層實作后再回來看這里,
(1)默認建構式
一個幾乎什么都沒做的默認建構式,
代碼如下:
template<class T>
class Vector
{
public:
typedef T* Iterator;
//把新構造的vector的三個指標全置空
Vector()
:_start(nullptr)
, _finish(nullptr)
, _endOfStorage(nullptr)
{}
private:
Iterator _start;
Iterator _finish;
Iterator _endOfStorage;
};
(2)拷貝構造
即用一個已經實體化的vector物件v構造一個新的vector物件this,先給this開辟v的大小的空間(reserve函式),再依次把v的資料插入到*this內(這里用push_back),
代碼如下:
template<class T>
class Vector
{
public:
Vector(const Vector<T>& v)
:_start(nullptr)
, _finish(nullptr)
, _endOfStorage(nullptr)
{
this->reserve(v.capacity());
for (auto e : v)
this->push_back(e);
}
private:
Iterator _start;
Iterator _finish;
Iterator _endOfStorage;
};
(3)構造含有n個val的vector
先用resize函式開辟n個空間,再依次把其值修改為val,或者可以借用上面的思路:先用reserve函式將vector的最大資料個數修改為n,進行n次this->push_back(val),
代碼如下:
template<class T>
class Vector
{
public:
Vector(size_t n, T val)
:_start(nullptr)
, _finish(nullptr)
, _endOfStorage(nullptr)
{
resize(n);
Iterator it = _start;
while (it != _finish)
{
*it = val;
it++;
}
}
private:
Iterator _start;
Iterator _finish;
Iterator _endOfStorage;
};
3.解構式
vector的析構比較簡單,只需要釋放空間并把三個指標置空即可,
代碼如下:
template<class T>
class Vector
{
public:
~Vector()
{
//釋放空間
if (_start != nullptr)
delete[] _start;
//把三個指標置空
_start = nullptr;
_finish = nullptr;
_endOfStorage = nullptr;
}
private:
Iterator _start;
Iterator _finish;
Iterator _endOfStorage;
};
4.賦值運算子多載
寫法1:處理空間,處理指標,填充資料,
代碼如下:
template<class T>
class Vector
{
public:
//注意這里傳const+參考,也就是說這個v就是函式外部的v,這里不能被修改
//要與下面第2種寫法區分
Vector& operator=(const Vector<T>& v)
{
//防止自己給自己賦值
if (this != &v)
{
//處理空間
delete[] _start;
_start = new T[v.capacity()];
//處理指標
_endOfStorage = _start + v.capacity();
//填充資料
//注意這里temp遍歷v的空間,_finish遍歷*this的空間
Iterator temp = v._start;
for (_finish = _start; temp < v._finish; _finish++, temp++)
*_finish = *temp;
}
return *this;
}
private:
Iterator _start;
Iterator _finish;
Iterator _endOfStorage;
};
寫法2:用一個臨時產生的物件來與*this的內容交換,具體可看代碼中的注釋,
代碼如下:
template<class T>
class Vector
{
public:
//多載一個這里需要的swap函式
void swap(Vector<T> v)
{
//加::表示下面的swap函式時全域域內的
::swap(_start, v._start);
::swap(_finish, v._finish);
::swap(_endOfStorage, v._endOfStorage);
}
//以v2 = v1為例
//這里傳參的v本身就是外部函式呼叫時v1的一個臨時(深)拷貝,生命周期僅在這一函式內
//由于v是v1的深拷貝,直接交換v與*this(也即v2)的內容即可
Vector& operator=(Vector<T> v)
{
//將三個指標全部交換,*this內的內容就和
this->swap(v);
//*this原來的內容現在在v內,函式結束呼叫后v自動呼叫解構式清理掉這些內容
return *this;
}
private:
Iterator _start;
Iterator _finish;
Iterator _endOfStorage;
};
5.一些簡單的函式
這里實作一些邏輯簡單的函式,如判空(empty),迭代器(begin,end)和const迭代器,size和capacity,operate[]等函式,
代碼如下:
template<class T>
class Vector
{
public:
typedef T* Iterator;
typedef const T* const_Iterator;
bool empty() const
{
return _start == _finish;
}
Iterator begin()
{
return _start;
}
Iterator end()
{
return _finish;
}
const_Iterator begin() const
{
return _start;
}
const_Iterator end() const
{
return _finish;
}
size_t capacity()
{
return _endOfStorage - _start;
}
size_t capacity() const
{
return _endOfStorage - _start;
}
size_t size()
{
return _finish - _start;
}
size_t size() const
{
return _finish - _start;
}
//注意operator[]可讀可寫,所以回傳值要加參考
T& operator[](size_t i)
{
assert(i < size());
return _start[i];
}
private:
Iterator _start;
Iterator _finish;
Iterator _endOfStorage;
};
6.reserve和resize
(1)reserve
reserve函式即預留出一定的空間存放資料,其中要注意一個細節,
代碼如下:
template<class T>
class Vector
{
public:
void reserve(size_t n)
{
if (n > capacity())
{
T* tmp = new T[n];
size_t sz = size();//注意:sz要提前拿到
if (_start != nullptr)
{
//拷貝資料
for (size_t i = 0; i < sz; i++)
tmp[i] = _start[i];
delete[] _start;//釋放舊空間
}
//修改指標
_start = tmp;
_finish = _start + sz;
_endOfStorage = _start + n;
}
}
private:
Iterator _start;
Iterator _finish;
Iterator _endOfStorage;
};
注意:sz要在if判斷前拿到,if判斷結束后,原來的空間被釋放,_start也隨之被修改,而_finish和_endOfStorage沒變,相減得到的size和capacity都是不對的,

(2)resize
resize與string的resize類似,且這里不需要處理\0,可類比實作,這里不多贅述,
代碼如下:
template<class T>
class Vector
{
public:
// 給預設值,T為int時為0,為double時為0.0,為string時為"",其它型別也可類比
void resize(size_t n, const T& val = T())
{
if (n < size())
_finish = _start + n;
else
{
if (n > capacity())
reserve(n);
while (_finish < _start + n)
{
*_finish = val;
_finish++;
}
}
}
private:
Iterator _start;
Iterator _finish;
Iterator _endOfStorage;
};
7.資料的增刪查改
順序表資料的增刪查改的細節在資料結構(一):順序表中已經介紹的很詳細,且在資料結構中多次處理,對于之前提到的細節這里不多贅述,
(1)push_back
代碼如下:
template<class T>
class Vector
{
public:
void push_back(const T& x = T())
{
//順序表已滿,需擴容
if (_finish == _endOfStorage)
{
//這里以每次2倍擴容為例
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
*_finish = x;
_finish++;
}
private:
Iterator _start;
Iterator _finish;
Iterator _endOfStorage;
};
(2)pop_back
代碼如下:
template<class T>
class Vector
{
public:
void pop_back()
{
assert(!empty());
_finish--;
}
private:
Iterator _start;
Iterator _finish;
Iterator _endOfStorage;
};
這里要提一下,STL中對于vector只有push_back和pop_back,而沒有push_front和pop_front,因為這兩個函式實作時需要挪動資料,導致O(N)的時間復雜度,效率太極,所以不提供,如果真的需要使用,可以呼叫insert和erase,
(3)insert
在某一位置前插入元素,注意位置要傳迭代器作為引數,
代碼如下:
template<class T>
class Vector
{
public:
//在pos位置前插入x
void insert(Iterator pos, const T& x)
{
size_t len = pos - _start;//pos之后元素個數
if (_finish == _endOfStorage)//需要擴容
{
size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
reserve(newcapacity);
pos = len + _start;
}
//挪動資料
Iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
end--;
}
*pos = x;
_finish++;
}
private:
Iterator _start;
Iterator _finish;
Iterator _endOfStorage;
};
(4)erase
代碼如下:
template<class T>
class Vector
{
public:
Iterator erase(Iterator pos)
{
//從pos位置開始用后面的資料覆寫前面的資料
Iterator it = pos;
for (; it < _finish - 1; it++)
*it = *(it + 1);
_finish--;
//注意回傳pos,這個在后面會用到
return pos;
}
private:
Iterator _start;
Iterator _finish;
Iterator _endOfStorage;
};
四、迭代器失效問題
迭代器的主要作用就是讓演算法能夠不用關心底層資料結構,其底層就是一個指標或是對指標進行了封裝,比如:vector的迭代器就是原生指標T*,
因此迭代器失效,實際就是迭代器底層對應指標所指向的空間被銷毀了卻繼續對其訪問,而使用一塊已經被釋放的空間,造成的后果是程式可能會崩潰(即如果繼續使用已經失效的迭代器,程式可能會崩潰),
1.引起其底層空間改變的操作
引起其底層空間改變的操作,都有可能是迭代器失效,比如:resize、reserve、insert、push_back等,因為這些函式在實作時會涉及擴容的問題,可能會引起底層空間改變,
這里以resize為例解釋,
代碼如下:

下圖中it原來指向v.begin(),但resize后v的空間修改了,it已經不等于修改后的v.begin()了,而原來it指向的空間已經被釋放,再次訪問就會造成崩潰,
圖解如下:

解決方法就是在空間被修改后把指向原來地址的變數都更新(這里只需要更新it),這樣即可正常運行,

2.指定位置元素的erase操作
下面一段代碼希望通過迭代器來洗掉順序表中的偶數元素,但是是有問題的,
代碼如下:
int main()
{
vector<int> v = { 1, 2, 3, 4 };
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
v.erase(it);
it++;
}
print(v);
return 0;
}
程式崩潰

圖解如下:

如下修改后可正常運行:
代碼如下:
int main()
{
vector<int> v = { 1, 2, 3, 4 };
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)//是偶數就洗掉并更新it
it = v.erase(it);//更新it,這也是為什么erase的回傳值是迭代器
else//是奇數就往后遍歷
it++;
}
print(v);
return 0;
}
運行如下:

感謝閱讀,如有錯誤請批評指正
轉載請註明出處,本文鏈接:https://www.uj5u.com/qita/301761.html
標籤:其他
