C++中vector的模擬實現實例詳解
vector接口總覽
namespace nzb
{
//模擬實現vector
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
//默認成員函數
vector(); //構造函數
vector(size_t n, const T& val); //構造函數
template<class InputIterator>
vector(InputIterator first, InputIterator last); //構造函數
vector(const vector<T>& v); //拷貝構造函數
vector<T>& operator=(const vector<T>& v); //賦值重載
~vector(); //析構函數
//迭代器相關函數
iterator begin();
iterator end();
const_iterator begin()const;
const_iterator end()const;
//容量相關函數
size_t size()const;
size_t capacity()const;
void reserve(size_t n);
void resize(size_t n, const T& val = T());
bool empty()const;
//修改容器相關函數
void push_back(const T& x);
void pop_back();
void insert(iterator pos, const T& x);
iterator erase(iterator pos);
void swap(vector<T>& v);
//訪問容器相關函數
T& operator[](size_t i);
const T& operator[](size_t i)const;
private:
iterator _start; //指向容器的頭
iterator _finish; //指向有效數據的尾
iterator _endofstorage; //指向容器的尾
};
}
默認成員函數
構造函數
1、無參構造，將所有成員變量初始化為空指針即可
vector()
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{}
2、構造一個含有n個值為val的vector容器。
先將容器容量擴大到n，再尾插val
vector(size_t n, const T& val)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
reserve(n); //擴容
for (size_t i = 0; i < n; i++) //尾插
{
push_back(val);
}
}
3、利用迭代器區間進行構造
因為迭代器區間可以是其他迭代器區間，所以我們要重新定義一塊模板，再將迭代器中的數據尾插
template <class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
while (first != last)
{
push_back(*first);
first++;
}
}
拷貝構造
傳統寫法
先將容器容量擴大到n，再尾插原vector類中的數據（這裡擴容和尾插調整瞭容器尾指針和數據尾指針，我們不必再次調整）
vector(const vector<T>& v)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
reserve(v.capacity());
for (const auto& e : v)
{
push_back(e);
}
}
現代寫法
利用迭代器構造一份vector類，再交換該類和拷貝構造的類
vector(const vector<T>& v)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
vector<T> tmp(v.begin(), v.end());
swap(tmp);
}
賦值重載
傳統寫法
先初始化原來vector類的空間，再將數據拷貝過來
vector<T>& operator=(const vector<T>& v)
{
if (this != &v)
{
delete[] _start;
_start = _finish = _endofstorage = nullptr;
reserve(v.capacity());
for (const auto& e : v)
{
push_back(e);
}
}
return *this;
}
現代寫法
現代寫法極為巧妙，利用傳值的特性（出瞭函數立即銷毀）傳入vector類，再交換該類和拷貝構造的類達到賦值的效果
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
析構函數
釋放開辟存儲數據的空間，再將容器的各個成員變量置為空
~vector()
{
delete[] _start;
_start = _finish = _endofstorage = nullptr;
}
迭代器相關函數
vector當中的迭代器實際上就是容器當中所存儲數據類型的指針。
typedef T* iterator; typedef const T* const_iterator;
begin和end
vector當中的begin函數返回容器的首地址，end函數返回容器當中有效數據的下一個數據的地址。
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
我們還需寫一份const版本，const版本隻能讀不能寫，防止vector中數據被修改
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
容量相關函數
size和capacity
size表示vector容器中已存儲有效數據個數而capacity表示vector容器的最大容量，那如何得出該組數據呢？
我們知道vector成員函數_start,_finish,_endofstorage是指針，而指針減指針得到兩個指針間的數據個數，我們可以用_finish-_start得到size,用_endofstorage-_start得到capacity
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _endofstorage - _start;
}
reserve
當n大於當前的capacity時，將capacity擴大到n或大於n。
當n小於當前capacity時什麼也不做。
void reserve(size_t n)
{
if (n > capacity())
{
size_t sz = size(); // 記錄原容器中數據個數
T* tmp = new T[n]; // 開辟一塊容量為n的空間
if (_start) //判空
{
for (size_t i = 0; i < sz; i++) // 拷貝數據
{
tmp[i] = _start[i];
}
delete[] _start; // 釋放原容器中的數據
}
_start = tmp; // 調整指針
_finish = _start + sz;
_endofstorage = _start + n;
}
}
註意：這裡拷貝數據不能用memcpy。當我們拷貝的是一些簡單的常量時是沒有問題的，但是當我們拷貝的是另一個類，如string類時，拷貝的string還是指向原來string類指向的空間。當原來string被釋放時，原string類指向的空間也被釋放，此時拷貝的string類指向的是一塊已被釋放的空間，程序結束時它將再次被釋放，釋放一塊已被釋放的空間程序報錯。
resize
當n大於當前的size時，將size擴大到n，擴大的數據為val，若val未給出，則默認為容器所存儲類型的默認構造函數所構造出來的值。
當n小於當前的size時，將size縮小到n。
void resize(size_t n, const T& val = T())
{
if (n <= size())// 當n小於當前的size時
{
_finish = n + _start;// 將size縮小到n
}
else // 當n大於當前的size時
{
if (n > capacity())// 當n大於容量時，擴容
{
reserve(n);
}
while (_finish < _start + n)// 給size到容器結尾賦值
{
*_finish = val;
_finish++;
}
}
}
這裡用瞭匿名對象T（）來作為缺省參數
empty
通過比較_start和_finish指針來判斷容器是否為空
bool empty()const
{
return _start == _finish;
}
修改容器相關函數
push_back
先判斷容器是否已滿，如果滿瞭先擴容再尾插，如果沒滿，直接尾插
void push_back(const T& x)
{
if (_finish == _endofstorage)// 判斷是否需要擴容
{
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
// 尾插數據
*_finish = x;
_finish++;
}
pop_back
先判空處理，再–_finish
void pop_back()
{
assert(!empty());// 判空
--_finish;
}
insert
功能：利用迭代器再指定位置插入數據。
實現方式：插入前判斷是否需要擴容，再將指定位置後的數據往後挪動一位，把數據插入指定位置。
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start&&pos <= _finish);// 判斷傳入數據的合法性
if (_finish == _endofstorage)// 擴容
{
size_t len = pos - _start;// 記錄pos的位置
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
pos = _start + len;
}
iterator end = _finish - 1;
while (end >= pos)// 挪動數據
{
*(end + 1) = *end;
--end;
}
*pos = x;// 插入數據
_finish++;
return pos;
}
註意:擴容時要記錄pos和_start的相對位置，避免擴容後迭代器失效問題
erase
功能：刪除指定位置數據。
實現方式：先判斷傳入數據的合法性，在將pos位置後的數據全部往前挪動一位，覆蓋掉原pos位置的數據
iterator erase(iterator pos)
{
assert(pos >= _start&&pos < _finish);// 判斷傳入數據的合法性
iterator it = pos + 1;// 利用迭代器記錄pos的後一位
while (it != _finish)// 將pos後的數據往前挪動一位
{
*(it - 1) = *it;
it++;
}
_finish--;
return pos;
}
swap
功能：交換兩個vector中的數據
實現方式：利用庫函數中的swap進行交換
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
}
訪問容器相關函數
operator[ ]
為瞭方便訪問數據vector中也加入瞭“下標+[ ]”操作
T& operator[](size_t i)// 可讀可寫
{
assert(i < size());
return _start[i];
}
const T& operator[](size_t i) const// 隻能讀
{
assert(i<size());
return _start[i];
}
總結
到此這篇關於C++中vector的模擬實現的文章就介紹到這瞭,更多相關C++ vector模擬實現內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！
推薦閱讀：
- C++超詳細講解模擬實現vector
- C++ STL _ Vector使用及模擬實現
- C++ vector類的模擬實現方法
- C++Vector容器常用函數接口詳解
- C++中vector迭代器失效與深淺拷貝問題詳析