C++中vector類(lèi)的一些簡(jiǎn)單實(shí)現(xiàn)
更新時(shí)間：2023年08月27日 10:24:41 作者：limou3434
C++中的std::vector是一個(gè)動(dòng)態(tài)數(shù)組（也被稱(chēng)為可變大小數(shù)組）的容器類(lèi),它是C++標(biāo)準(zhǔn)庫(kù)提供的其中一種容器類(lèi),提供了方便的操作和管理動(dòng)態(tài)數(shù)組的功能,本文就給大家介紹了C++中vector類(lèi)的簡(jiǎn)單實(shí)現(xiàn)代碼,需要的朋友可以參考下
下面代碼是有關(guān)于vector的一些基礎(chǔ)實(shí)現(xiàn)，和庫(kù)里的函數(shù)可能有較大的不同，但是基本可以實(shí)現(xiàn)vector的很多功能。
#include <iostream>
#include <cassert>
#include <string>
/*
看源代碼不要上來(lái)就一行一行看，先看文檔再進(jìn)行使用，再整理框架（梳理類(lèi)、變量、接口），然后“連蒙帶猜”驗(yàn)證細(xì)節(jié)
*/
namespace limou
{
template <typename T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
public:
//1.Menber function
vector()
: _start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{}
template <typename InputIterator>//這里之所以又嵌套一個(gè)類(lèi)模板的原因是：能夠使用多種種類(lèi)的迭代器，而不當(dāng)當(dāng)是T類(lèi)型的迭代器
vector(InputIterator first, InputIterator last)
: _start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
while (first != last)
{
push_back(*first);
++first;
}
}
vector(const vector<T>& v)
: _start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
reserve(v.capacity());
for (auto& e : v)
{
push_back(e);
}
}
vector(size_t n, const T& val = T())//構(gòu)造一個(gè)匿名對(duì)象，并且自動(dòng)初始化
{
reserve(n);
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}
vector(int n, const T& val = T())//這個(gè)函數(shù)是專(zhuān)門(mén)給部分類(lèi)型準(zhǔn)備的（比如int）不重載就會(huì)調(diào)用成迭代器初始化
{
reserve(n);
for (int i = 0; i < n; i++)
{
push_back(val);
}
}
vector<T>& operator=(vector tmp)//先拷貝一份，另外這里提一嘴，在類(lèi)里面寫(xiě)成vector和vector<T>是一樣的，當(dāng)然我們建議寫(xiě)全
{
swap(tmp);
return *this;
}
~vector()
{
delete[] _start;
}
//2.Iterator
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
//3.Capacity
size_t size()
{
return _finish - _start;
}
size_t capacity() const
{
return _end_of_storage - _start;
}
//3.1.使用memcpy()會(huì)引發(fā)深淺拷貝的問(wèn)題，因此不可以使用這個(gè)函數(shù)
//void reserve(size_t n)
//{
// if (n > capacity())//如果指定的數(shù)字大于現(xiàn)有容量就擴(kuò)容
// {
// T* tmp = new T[n];
// size_t sz = size();
// if (_start)//如果不是空容器
// {
// memcpy(tmp, _start, sizeof(T) * sz);
// delete[] _start;//這里有可能因?yàn)闇\拷貝而出事
// }
// _start = tmp;//由于這里更換成了tmp
// _finish = tmp + sz;//而這里原本的_finish是指向別的空間指針，所以必須要修改
// _end_of_storage = tmp + n;//同理這里也做修改
// }
//}
//3.2.拷貝數(shù)據(jù)如果使用拷貝構(gòu)造
void reserve(size_t n)
{
if (n > capacity())//如果指定的數(shù)字大于現(xiàn)有容量就擴(kuò)容
{
T* tmp = new T[n];
size_t sz = size();
if (_start)//如果不是空容器
{
//memcpy(tmp, _start, sizeof(T) * sz);
for (size_t i = 0; i < sz; i++)
{
tmp[i] = _start[i];
//這樣子做可以自動(dòng)調(diào)用不同類(lèi)型的深拷貝（賦值運(yùn)算重載），
//這個(gè)深拷貝有可能是我們寫(xiě)的也有可能是庫(kù)里的……
}
delete[] _start;
}
_start = tmp;//由于這里更換成了tmp
_finish = _start + sz;//而這里原本的_finish是指向別的空間指針，所以必須要修改
_end_of_storage = _start + n;//同理這里也做修改
}
}
//3.3.當(dāng)然，還有一種方法是使用引用計(jì)數(shù)，不過(guò)這個(gè)方法我們暫時(shí)不講（這個(gè)地方如果是類(lèi)似string類(lèi)型使用引用計(jì)數(shù)效率就會(huì)有很大的提高）
//3.4.另外，庫(kù)中的實(shí)現(xiàn)使用了拷貝構(gòu)造，因?yàn)槿思沂褂玫氖嵌ㄎ籲ew，因此可以調(diào)用，而我們自己是直接使用new的，已經(jīng)存在兩個(gè)對(duì)象了，只能使用賦值重載
void resize(size_t n, const T& val = T())
//這里給了默認(rèn)匿名參數(shù)T()，
//注意匿名對(duì)象具有常屬性，
//這也是為什么在C++之后支持“int i = int(3);”
//這種語(yǔ)法就是因?yàn)椋?
//在類(lèi)模板出現(xiàn)后沒(méi)有辦法確認(rèn)是內(nèi)置類(lèi)型，還是自定義類(lèi)型
//并且還會(huì)給與自定義類(lèi)型默認(rèn)值
{
if (n <= size())
{
_finish = _start + n;
return;
}
reserve(n);
while (_finish < _start + n)
{
*_finish = val;
_finish++;
}
}
//4.Element access
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos) const
{
assert(pos < size());
return _start[pos];
}
//5.Modifiers
//注意insert()和erase()在使用過(guò)后迭代器都會(huì)失效，在庫(kù)中就可以利用返回值來(lái)解決這個(gè)問(wèn)題，我們自己實(shí)現(xiàn)的就沒(méi)有實(shí)現(xiàn)insert()的返回值
void push_back(const T& x)
{
//if (_finish == _end_of_storage)//如果容量不足
//{
// reserve(capacity() == 0 ? 4 : capacity() * 2);//2倍容量
//}
//*_finish = x;
//_finish++;
insert(end(), x);
}
void insert(iterator pos, const T& x)
{
//檢驗(yàn)是否合法
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _end_of_storage)//如果容量不足
{
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);//2倍容量
pos = _start + len;
//上面這里還解決了迭代器失效的問(wèn)題。
//由于擴(kuò)容導(dǎo)致的問(wèn)題，pos指向舊空間的某個(gè)位置時(shí)，
//舊空間沒(méi)了，沒(méi)能指向新空間，因此這里必須進(jìn)行更新。
//但是由于這里沒(méi)有辦法使用引用（傳過(guò)來(lái)的pos迭代器是一個(gè)值），
//因此本函數(shù)insert()使用過(guò)后迭代器就會(huì)失效，只能保證在本函數(shù)內(nèi)有效。
}
iterator end = _finish - 1;
//1,2,3,4,5
//^ ^
while (end >= pos)
{
*(end + 1) = *end;
end--;
}
*pos = x;
_finish++;
}
//1.第一種erase的書(shū)寫(xiě)解決不了迭代器失效的問(wèn)題
//void erase(iterator pos)
//{
// //檢驗(yàn)是否合法
// assert(pos >= _start);
// assert(pos <= _finish);
// //{1,2,3,4,5}
// //pos->3,it->4,{1,2,4,5}
// //{1},pos->1,it=_finish
// iterator it = pos + 1;
// while (it < _finish)
// {
// *(it - 1) = *it;
// it++;
// }
// --_finish;
//}
//2.第二種可以解決迭代器失效的問(wèn)題，返回的是原pos的后一個(gè)數(shù)據(jù)的迭代器，也就是刪除后pos的位置
iterator erase(iterator pos)
{
//檢驗(yàn)是否合法
assert(pos >= _start);
assert(pos <= _finish);
//{1,2,3,4,5}
//pos->3,it->4,{1,2,4,5}
//{1},pos->1,it=_finish
iterator it = pos + 1;
while (it < _finish)
{
*(it - 1) = *it;
it++;
}
--_finish;
return pos;
}
//6.other
void swap(vector<int>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
private:
//三個(gè)迭代器成員變量
iterator _start;//指向“存儲(chǔ)空間”或者“存儲(chǔ)”開(kāi)始的位置
iterator _finish;//指向“存儲(chǔ)”結(jié)束的位置
iterator _end_of_storage;//指向“存儲(chǔ)空間”結(jié)束的位置
};
void test_1()
{
vector<int> v1;
for (int i = 0; i < 10; i++)
{
v1.push_back(i);
std::cout << v1[i]++ << " ";
}
std::cout << std::endl;
vector<int>::iterator it = v1.begin();
while (it != v1.end())
{
std::cout << (*it++)++ << " ";
}
std::cout << std::endl;
for (auto in : v1)
{
std::cout << in << " ";
}
const vector<float> v2;
//for (int i = 0; i < 10; i++)
//{
// v2.push_back((float)i + 0.1);
// std::cout << v2[i]++ << " ";
//}
}
void test_2()
{
vector<int> v1;
v1.resize(5);
for (auto in : v1)
{
std::cout << in << " ";
}std::cout << std::endl;
vector<int*> v2;
v2.resize(5);
for (auto p : v2)
{
std::cout << (void*)p << " ";
}std::cout << std::endl;
vector<std::string> v3;
v3.resize(5);
for (auto str3 : v3)
{
std::cout << "空字符=[" << str3 << "]" << " ";
}std::cout << std::endl;
vector<std::string> v4;
v4.resize(5, "abcd");
for (auto str4 : v4)
{
std::cout << "字符=[" << str4 << "]" << " ";
}std::cout << std::endl;
}
void test_3()
{
vector<int> v1;
v1.insert(v1.begin(), 1);
v1.insert(v1.begin() + 1, 2);
v1.insert(v1.begin() + 2, 3);
for (auto in : v1)
{
std::cout << in << " ";
}
std::cout << std::endl;
}
void test_4()
{
vector<int> v1;
v1.push_back(1);//內(nèi)部使用了一次insert()因此迭代器失效
std::cout << v1[v1.size() - 1] << " ";
v1.push_back(2);//但是又重新使用insert()的時(shí)候重新計(jì)算了迭代器，使用后迭代器又失效了
std::cout << v1[v1.size() - 1] << " ";
v1.push_back(3);
std::cout << v1[v1.size() - 1] << " ";
std::cout << std::endl;
vector<int> v2;
v2.insert(v2.begin(), 1);//內(nèi)部使用了一次insert()因此迭代器失效
std::cout << v2[v2.size() - 1] << " ";
v2.insert(v2.begin(), 2);//但是又重新使用insert()的時(shí)候重新計(jì)算了迭代器，使用后迭代器又失效了
std::cout << v2[v2.size() - 2] << " ";
v2.insert(v2.begin(), 3);
std::cout << v2[v2.size() - 3] << " ";
std::cout << std::endl;
//錯(cuò)誤示例（因?yàn)榈魇В?
vector<int> v3;
v3.insert(v3.begin(), 4);
v3.insert(v3.begin(), 3);
v3.insert(v3.begin(), 2);
vector<int>::iterator it = v3.begin();
v3.insert(it, 1);//這個(gè)語(yǔ)句過(guò)后迭代器失效了
v3.insert(it, 0);
v3.insert(it, 0);
for (int i = 0; i < 7; i++)
{
std::cout << v3[i] << " ";
}std::cout << std::endl;
}
void test_5()
{
1.使用erase()的時(shí)候一般不會(huì)出現(xiàn)迭代器失效的問(wèn)題
//vector<int> v;
//v.push_back(0);
//std::cout << v[0] << std::endl;
//v.erase(v.begin());
//v.push_back(1);
//v.push_back(2);
//v.push_back(3);
//v.push_back(4);
//vector<int>::iterator it = v.begin();
//while (it != v.end())
//{
// std::cout << *it << " ";
// it++;
//}
//2.但是有一種情況會(huì)很危險(xiǎn)
//假設(shè)我們要?jiǎng)h除一組數(shù)據(jù)中的偶數(shù)
//可以試一下數(shù)據(jù)
//{1,2,3,4,5}正常
//{1,2,3,4,5,6}奔潰
//{2,2,3,4,5}結(jié)果不對(duì)
vector<int> vbug;
vbug.push_back(1);
vbug.push_back(2);
vbug.push_back(3);
vbug.push_back(4);
vbug.push_back(5);
vbug.push_back(6);
vbug.push_back(7);
vbug.push_back(8);
vbug.push_back(9);
vbug.push_back(10);
auto it = vbug.begin();
//1.錯(cuò)誤使用
//while (it != vbug.end())
//{
// if (*it % 2 == 0)
// {
// vbug.erase(it);
// }
// //對(duì)于{1,2,3,4,5,6,7,8,9,10}
// //當(dāng)最后一步只剩下{1,3,5,7,9,10}的時(shí)候
// //it->10,_finish->10后面的空間，因此在erase的時(shí)候，刪除10的步驟就是_finish--
// //但是循環(huán)條件處的end()指向的位置還是原本的_finish位置
// it++;
// //而上面的一步又使得it++,it->舊的_finish
// //而回到循環(huán)條件的時(shí)候end()重新進(jìn)行了計(jì)算（更新為新的_finish--）
// //此時(shí)it和end()錯(cuò)位，*it訪(fǎng)問(wèn)了野指針
// //導(dǎo)致迭代器失效
//}
//for (auto e : vbug)
//{
// std::cout << e << " ";
//}
//std::cout << std::endl;
//2.debug后
while (it != vbug.end())
{
if (*it % 2 == 0)
{
vbug.erase(it);
}
if (it == vbug.end())
break;
it++;
}
for (auto e : vbug)
{
std::cout << e << " ";
}
std::cout << std::endl;
//3.使用總結(jié)
//但是實(shí)際上如果數(shù)據(jù)存在連續(xù)的偶數(shù)，即使是debug后的版本也會(huì)出現(xiàn)問(wèn)題（上面代碼能過(guò)只是巧合）
//因此在后期就會(huì)引入一些智能指針的解決方案
//因此我們認(rèn)為使用erase()后會(huì)導(dǎo)致之前的迭代器失效
}
//關(guān)于迭代器失效的其中一個(gè)解決方案就是修改返回值的類(lèi)型
void test_6()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v.push_back(6);
v.push_back(6);
vector<int>::iterator it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
it = v.erase(it);
}
else
{
it++;
}
}
for (int i = 0; i < v.size(); i++)
{
std::cout << v[i] << " ";
}
}
void test_7()
{
vector<std::string> v1;
v1.push_back("1111111111111111111111");
v1.push_back("1111111111111111111111");
v1.push_back("1111111111111111111111");
v1.push_back("1111111111111111111111");
v1.push_back("1111111111111111111111");
for (auto e : v1)
{
std::cout << e << " ";
}
std::cout << std::endl;
}
void test_8()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
vector<int> v2(v1);
for (auto& e : v1)
{
std::cout << e << " ";
}
std::cout << std::endl;
for (auto& e : v2)
{
std::cout << e << " ";
}
std::cout << std::endl;
vector<int> v3;
v3 = v2;
for (auto& e : v3)
{
std::cout << e << " ";
}
std::cout << std::endl;
}
void test_9()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
std::string str("abcdef");
vector<int> v2(v1.begin(), v1.end());
for (int i = 0; i < v2.size(); i++)
{
std::cout << v2[i] << " ";
}std::cout << std::endl;
vector<int> v3(str.begin() + 1, str.end() - 1);
for (int j = 0; j < v3.size(); j++)
{
std::cout << v3[j] << " ";
}std::cout << std::endl;
}
void test_10()
{
vector<int> v1(10, 1);
vector<std::string> v2(5, "xxxx");
for (int i = 0; i < v1.size(); i++)
{
std::cout << v1[i] << " ";
}
std::cout << std::endl;
for (int j = 0; j < v2.size(); j++)
{
std::cout << v2[j] << " ";
}
std::cout << std::endl;
}
}
/*
vector沒(méi)有流重載，因?yàn)楹芷婀郑鸁o(wú)法知道按照什么樣的格式進(jìn)行輸出和輸入
*/到此這篇關(guān)于C++中vector類(lèi)的簡(jiǎn)單實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)C++ vector類(lèi)實(shí)現(xiàn)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
利用C語(yǔ)言玩轉(zhuǎn)魔方陣實(shí)例教程
這篇文章主要給大家介紹了關(guān)于利用C語(yǔ)言玩轉(zhuǎn)魔方陣的相關(guān)資料,文中詳細(xì)介紹了關(guān)于奇數(shù)魔方陣和4N 魔方陣的實(shí)現(xiàn)方法，通過(guò)示例代碼讓大家更好的參考學(xué)習(xí)，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧。2017-11-11
本文介紹了如何運(yùn)用面向?qū)ο笏枷脒M(jìn)行五子棋游戲的設(shè)計(jì)與開(kāi)發(fā)，與面向過(guò)程程序設(shè)計(jì)比較,面向?qū)ο蟪绦蛟O(shè)計(jì)更易于實(shí)現(xiàn)對(duì)現(xiàn)實(shí)世界的描述,提高軟件的擴(kuò)展性和可維護(hù)性。附上最終的程序源碼，推薦給大家，有需要的小伙伴可以參考下。2015-03-03
Linux線(xiàn)程管理必備:解析互斥量與條件變量的詳解
本篇文章是對(duì)互斥量與條件變量的應(yīng)用進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下
2013-05-05 
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)俄羅斯方塊源碼完整版，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2021-06-06 
C語(yǔ)言中獲取進(jìn)程識(shí)別碼的相關(guān)函數(shù)
這篇文章主要介紹了C語(yǔ)言中獲取進(jìn)程識(shí)別碼的相關(guān)函數(shù),分別為getpid()函數(shù)和getppid()函數(shù)的使用,需要的朋友可以參考下
2015-08-08 
這篇文章主要為大家總結(jié)了C++中輸入輸出流及文件流操作,具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2016-10-10 
這篇文章主要為大家詳細(xì)介紹了MFC實(shí)現(xiàn)滾動(dòng)字幕，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2020-05-05 
c語(yǔ)言如何實(shí)現(xiàn)兩數(shù)之和
這篇文章主要介紹了c語(yǔ)言如何實(shí)現(xiàn)兩數(shù)之和，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教
2022-07-07 
C++實(shí)現(xiàn)浮點(diǎn)數(shù)精確加法
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)浮點(diǎn)數(shù)精確加法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2020-05-05