C++中vector類的一些簡(jiǎn)單實(shí)現(xiàn)
更新時(shí)間:2023年08月27日 10:24:41 作者:limou3434
C++中的std::vector是一個(gè)動(dòng)態(tài)數(shù)組(也被稱為可變大小數(shù)組)的容器類,它是C++標(biāo)準(zhǔn)庫(kù)提供的其中一種容器類,提供了方便的操作和管理動(dòng)態(tài)數(shù)組的功能,本文就給大家介紹了C++中vector類的簡(jiǎn)單實(shí)現(xiàn)代碼,需要的朋友可以參考下
下面代碼是有關(guān)于vector
的一些基礎(chǔ)實(shí)現(xiàn),和庫(kù)里的函數(shù)可能有較大的不同,但是基本可以實(shí)現(xiàn)vector
的很多功能。
#include <iostream> #include <cassert> #include <string> /* 看源代碼不要上來就一行一行看,先看文檔再進(jìn)行使用,再整理框架(梳理類、變量、接口),然后“連蒙帶猜”驗(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è)類模板的原因是:能夠使用多種種類的迭代器,而不當(dāng)當(dāng)是T類型的迭代器 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ù)是專門給部分類型準(zhǔn)備的(比如int)不重載就會(huì)調(diào)用成迭代器初始化 { reserve(n); for (int i = 0; i < n; i++) { push_back(val); } } vector<T>& operator=(vector tmp)//先拷貝一份,另外這里提一嘴,在類里面寫成vector和vector<T>是一樣的,當(dāng)然我們建議寫全 { 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ā)深淺拷貝的問題,因此不可以使用這個(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)用不同類型的深拷貝(賦值運(yùn)算重載), //這個(gè)深拷貝有可能是我們寫的也有可能是庫(kù)里的…… } delete[] _start; } _start = tmp;//由于這里更換成了tmp _finish = _start + sz;//而這里原本的_finish是指向別的空間指針,所以必須要修改 _end_of_storage = _start + n;//同理這里也做修改 } } //3.3.當(dāng)然,還有一種方法是使用引用計(jì)數(shù),不過這個(gè)方法我們暫時(shí)不講(這個(gè)地方如果是類似string類型使用引用計(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àn)椋? //在類模板出現(xiàn)后沒有辦法確認(rèn)是內(nèi)置類型,還是自定義類型 //并且還會(huì)給與自定義類型默認(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()在使用過后迭代器都會(huì)失效,在庫(kù)中就可以利用返回值來解決這個(gè)問題,我們自己實(shí)現(xiàn)的就沒有實(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; //上面這里還解決了迭代器失效的問題。 //由于擴(kuò)容導(dǎo)致的問題,pos指向舊空間的某個(gè)位置時(shí), //舊空間沒了,沒能指向新空間,因此這里必須進(jìn)行更新。 //但是由于這里沒有辦法使用引用(傳過來的pos迭代器是一個(gè)值), //因此本函數(shù)insert()使用過后迭代器就會(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的書寫解決不了迭代器失效的問題 //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.第二種可以解決迭代器失效的問題,返回的是原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ǔ)”開始的位置 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è)語句過后迭代器失效了 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)迭代器失效的問題 //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訪問了野指針 // //導(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)問題(上面代碼能過只是巧合) //因此在后期就會(huì)引入一些智能指針的解決方案 //因此我們認(rèn)為使用erase()后會(huì)導(dǎo)致之前的迭代器失效 } //關(guān)于迭代器失效的其中一個(gè)解決方案就是修改返回值的類型 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沒有流重載,因?yàn)楹芷婀?,您無法知道按照什么樣的格式進(jìn)行輸出和輸入 */
到此這篇關(guān)于C++中vector類的簡(jiǎn)單實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)C++ vector類實(shí)現(xiàn)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章

C語言中獲取進(jìn)程識(shí)別碼的相關(guān)函數(shù)
這篇文章主要介紹了C語言中獲取進(jìn)程識(shí)別碼的相關(guān)函數(shù),分別為getpid()函數(shù)和getppid()函數(shù)的使用,需要的朋友可以參考下
2015-08-08 
C++實(shí)現(xiàn)浮點(diǎn)數(shù)精確加法
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)浮點(diǎn)數(shù)精確加法,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
2020-05-05