C++模擬實(shí)現(xiàn)STL容器vector的示例代碼
更新時(shí)間：2022年11月24日 08:32:23 作者：蔣靈瑜的筆記本
這篇文章主要為大家詳細(xì)介紹了C++如何模擬實(shí)現(xiàn)STL容器vector的相關(guān)資料，文中的示例代碼講解詳細(xì)，對(duì)我們學(xué)習(xí)C++有一定幫助，需要的可以參考一下
一、vector迭代器失效問題
1、Visual Studio和g++對(duì)迭代器失效問題的表現(xiàn)
int main(){
std::vector<int>v{1,2,3,4};
std::vector<int>::iterator it = std::find(v.begin(), v.end(), 2);
if(it != v.end())
{
v.erase(it);
it++;//調(diào)用erase()后，it已經(jīng)失效了，運(yùn)行后迭代器引發(fā)異常
}
return 0;
}在Visual Studio2022中，調(diào)用vector的insert()和erase()接口后，it迭代器（包括it之后的自定義迭代器）將會(huì)失效，如果仍操作這些已經(jīng)失效的迭代器，編譯器將會(huì)引發(fā)異常。
博主嘗試在Linux的g++編譯器（4.8.5版本）下運(yùn)行相同debug版本的程序（編譯時(shí)帶上-g選項(xiàng)），發(fā)現(xiàn)g++中調(diào)用完insert()和erase()接口后，it迭代器并未失效，甚至可以操縱it讀寫_end_of_storage-_finish這部分空間，這是不安全的。
所以，后續(xù)調(diào)用完insert()和erase()接口后，我們一律認(rèn)為當(dāng)前迭代器失效！
2、解決迭代器失效的方法
int main(
std::vector<int> v{1,2,3,4};
std::vector<int>::iterator it = std: :find(v.begin(), v. end(),2);
if(it != v.end())
{
it=v.erase(it);//讓當(dāng)前迭代器接收erase的返回值，更新迭代器
it++;
}
return 0;
}使用時(shí)讓當(dāng)前迭代器接收insert()和erase()的返回值，更新迭代器即可。
二、模擬實(shí)現(xiàn)構(gòu)造函數(shù)調(diào)用不明確
1、問題描述
vector(size_t n, const T& val = T())//這里的形參用size_t就會(huì)引發(fā)這兩個(gè)構(gòu)造函數(shù)調(diào)用問題
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
reserve(n);
for (size_t i = 0; i < n; ++i)
{
push_back(val);
}
}
template <class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
while (first != last)
{
push_back(*first++);
}
}
本意是想使用第一種構(gòu)造方式，用3個(gè)6進(jìn)行構(gòu)造。編譯器會(huì)根據(jù)形參調(diào)用最匹配的函數(shù)重載。
第一個(gè)構(gòu)造函數(shù)的第一個(gè)形參是size_t，形參去匹配的話需要發(fā)生隱式類型轉(zhuǎn)換。
但是這兩個(gè)參數(shù)更匹配第二個(gè)構(gòu)造函數(shù)（因?yàn)榈诙€(gè)模板可以為int，完全匹配），一旦走第二個(gè)構(gòu)造函數(shù)，該構(gòu)造函數(shù)內(nèi)部是要對(duì)first進(jìn)行解引用操作，所以編譯器會(huì)報(bào)非法的間接尋址（解引用）錯(cuò)誤。
2、解決調(diào)用不明確的方法
針對(duì)構(gòu)造函數(shù)vector(size_t n, const T& val = T())，我們多重載一個(gè)vector(int n, const T& val = T())版本的構(gòu)造函數(shù)即可解決該問題。
三、reserve中的深淺拷貝問題
1、reserve中淺拷貝發(fā)生原因
這句memcpy表面上把原來的數(shù)據(jù)全部拷貝到tmp里面了，但是，這只是按字節(jié)的拷貝，如果當(dāng)前類型為vector<vector<int>>等非內(nèi)置類型，將會(huì)發(fā)生淺拷貝。
2、淺拷貝發(fā)生的圖解
memcpy會(huì)把vector<vector<int>>,從_start位置開始，按字節(jié)進(jìn)行拷貝。如圖所示，拷貝的對(duì)象是4個(gè)vector<int>,這是是一種淺拷貝！
3、解決方法
void reserve(size_t n)
{
//擴(kuò)容
if (n > capacity())
{
size_t oldSize = size();//先記錄下size,后續(xù)解決finish失效
T* tmp = new T[n];
if (_start != nullptr)
{
//memcpy(tmp, _start, sizeof(T) * oldSize);//淺拷貝
for (size_t i = 0; i < oldSize; ++i)
{
tmp[i] = _start[i];//調(diào)用賦值運(yùn)算符重載完成深拷貝
}
delete[] _start;
}
_start = tmp;
_finish = _start + oldSize;//異地?cái)U(kuò)容后_finish失效，需重新設(shè)定_finish
_end_of_storage = _start + n;
}
}借助賦值運(yùn)算符重載，完成深拷貝。
四、模擬實(shí)現(xiàn)vector整體代碼
#pragma once
#include <iostream>
#include <assert.h>
using std::cout;
using std::cin;
using std::endl;
namespace jly
{
template <class T>
class vector
{
public:
//構(gòu)造函數(shù)
vector()
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{}
vector(size_t n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
reserve(n);
for (size_t i = 0; i < n; ++i)
{
push_back(val);
}
}
vector(int n, const T& val = T())//多重載一個(gè)int版本的構(gòu)造，解決調(diào)函數(shù)不明確的問題
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
reserve(n);
for (int i = 0; i < n; ++i)
{
push_back(val);
}
}
template <class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
while (first != last)
{
push_back(*first++);
}
}
//拷貝構(gòu)造
void swap(vector<T>& v)//一定要加引用，不然拷貝構(gòu)造函數(shù)調(diào)用swap會(huì)引發(fā)無限拷貝
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
vector(const vector<T>& v)
: _start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
vector<T> tmp(v.begin(), v.end());
swap(tmp);
}
//vector(const vector<T>& v)//寫法二
// : _start(nullptr)
// , _finish(nullptr)
// , _end_of_storage(nullptr)
//{
// reserve(v.capacity());
// for (const auto& e : v)
// {
// push_back(e);
// }
//}
//賦值運(yùn)算符重載
vector<T>& operator=(vector<T> v)//能解決自己給自己賦值的問題
{
swap(v);
return *this;
}
//析構(gòu)函數(shù)
~vector()
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
//迭代器
typedef T* iterator;
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const iterator begin()const
{
return _start;
}
const iterator end()const
{
return _finish;
}
T& operator[](size_t pos)
{
return _start[pos];
}
const T& operator[](size_t pos)const
{
return _start[pos];
}
//reserve接口
void reserve(size_t n)
{
//擴(kuò)容
if (n > capacity())
{
size_t oldSize = size();//先記錄下size,后續(xù)解決finish失效
T* tmp = new T[n];
if (_start != nullptr)
{
//memcpy(tmp, _start, sizeof(T) * oldSize);//淺拷貝
for (size_t i = 0; i < oldSize; ++i)
{
tmp[i] = _start[i];//調(diào)用賦值運(yùn)算符重載完成深拷貝
}
delete[] _start;
}
_start = tmp;
_finish = _start + oldSize;//異地?cái)U(kuò)容后_finish失效，需重新設(shè)定_finish
_end_of_storage = _start + n;
}
}
//resize接口
void resize(size_t n, T val = T())//val給T類型的缺省值
{
if (n > capacity())//n大于capacity，要擴(kuò)容
{
reserve(n);
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
else if (n > size())//n小于capacity但大于原size
{
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
else//縮size的情況
{
_finish = _start + n;
}
}
//push_back/pop_back接口
void push_back(const T& val)
{
if (_finish == _end_of_storage)
{
size_t newCapacity = capacity() == 0 ? 4 : 2 * capacity();
reserve(newCapacity);
}
*_finish = val;
++_finish;
}
void pop_back()
{
assert(!empty());
--_finish;
}
//insert和erase接口
iterator insert(iterator pos, const T& val)
{
assert(pos >= _start && pos <= _finish);
//判斷擴(kuò)容
if (_finish == _end_of_storage)
{
size_t len = pos - _start;//需要處理pos迭代器失效問題，記錄len
size_t newCapacity = capacity() == 0 ? 4 : 2 * capacity();
reserve(newCapacity);//擴(kuò)容后pos迭代器失效
pos = _start + len;//重新設(shè)定pos
}
//挪動(dòng)數(shù)據(jù)
for (iterator i = _finish; i > pos; --i)
{
*i = *(i - 1);
}
//填入數(shù)據(jù)
*pos = val;
++_finish;
return pos;
}
iterator erase(iterator pos)
{
assert(pos >= _start && pos <= _finish);
for (iterator i = pos; i < _finish - 1; ++i)
{
*pos = *(pos + 1);
}
--_finish;
return pos;
}
//小接口
size_t size()const
{
return _finish - _start;
}
size_t capacity()const
{
return _end_of_storage - _start;
}
bool empty()const
{
return _start == _finish;
}
void clear()
{
_finish = _start;
}
private:
iterator _start;
iterator _finish;
iterator _end_of_storage;
};
/測(cè)試部分
void test()
{
vector<int> v(1, 5);
vector<int> v1(v);
for (auto e : v1)
{
cout << e << " ";
}
}
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> vv;
vv.resize(numRows);
for (size_t i = 0; i < vv.size(); ++i)
{
vv[i].resize(i + 1, 0);
vv[i][0] = vv[i][vv[i].size() - 1] = 1;
}
for (size_t i = 0; i < vv.size(); ++i)
{
for (size_t j = 0; j < vv[i].size(); ++j)
{
if (vv[i][j] == 0)
{
vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
}
}
}
for (size_t i = 0; i < vv.size(); ++i)
{
for (size_t j = 0; j < vv[i].size(); ++j)
{
cout << vv[i][j] << " ";
}
cout << endl;
}
return vv;
}
};
void test_vector()
{
vector<vector<int>> vv;
vector<int> v(5, 1);
vv.push_back(v);
vv.push_back(v);
vv.push_back(v);
vv.push_back(v);
vv.push_back(v);
for (size_t i = 0; i < vv.size(); ++i)
{
for (size_t j = 0; j < vv[i].size(); ++j)
{
cout << vv[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
}到此這篇關(guān)于C++模擬實(shí)現(xiàn)STL容器vector的示例代碼的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)STL容器vector內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要為大家詳細(xì)介紹了QT實(shí)現(xiàn)簡(jiǎn)單打地鼠游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-12-12
C語言實(shí)現(xiàn)掃雷小游戲（適合初學(xué)者）
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)掃雷小游戲，適合初學(xué)者練習(xí)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-03-03
C++11的for循環(huán),以及范圍Range類的簡(jiǎn)單實(shí)現(xiàn)
下面小編就為大家?guī)硪黄狢++11的for循環(huán),以及范圍Range類的簡(jiǎn)單實(shí)現(xiàn)。小編覺得挺不錯(cuò)的， 現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2016-06-06
C++ std::unique_lock 用法實(shí)例詳解
std::unique_lock 是 C++11 提供的一個(gè)用于管理互斥鎖的類,它提供了更靈活的鎖管理功能,適用于各種多線程場(chǎng)景,這篇文章給大家介紹了C++ std::unique_lock 用法,感興趣的朋友跟隨小編一起看看吧2023-09-09
C語言 function recursion函數(shù)遞歸詳解
遞歸指的是在函數(shù)的定義中使用函數(shù)自身的方法，舉個(gè)例子： 從前有座山，山里有座廟，廟里有個(gè)老和尚，正在給小和尚講故事呢！故事是什么呢？"從前有座山，山里有座廟，廟里有個(gè)老和尚，正在給小和尚講故事呢！故事是什么呢？"從前有座山，山里有座廟，循環(huán)下去2021-10-10
詳解C++編程中的主表達(dá)式與后綴表達(dá)式編寫基礎(chǔ)
這篇文章主要介紹了C++編程中的主表達(dá)式與后綴表達(dá)式編寫基礎(chǔ),是C++入門學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下2016-01-01
C++?Boost?CircularBuffer算法超詳細(xì)精講
Boost是為C++語言標(biāo)準(zhǔn)庫提供擴(kuò)展的一些C++程序庫的總稱。Boost庫是一個(gè)可移植、提供源代碼的C++庫，作為標(biāo)準(zhǔn)庫的后備，是C++標(biāo)準(zhǔn)化進(jìn)程的開發(fā)引擎之一，是為C++語言標(biāo)準(zhǔn)庫提供擴(kuò)展的一些C++程序庫的總稱2022-11-11
在我們學(xué)習(xí) C 語言的基本構(gòu)建塊之前，讓我們先來看看一個(gè)最小的 C 程序結(jié)構(gòu)，在接下來的章節(jié)中可以以此作為參考2021-06-06
C語言strlen,strcpy,strcmp,strcat,strstr字符串操作函數(shù)實(shí)現(xiàn)
這篇文章主要介紹了C語言strlen,strcpy,strcmp,strcat,strstr字符串操作函數(shù)實(shí)現(xiàn),,文章圍繞主題展開詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，需要的朋友可以參考一下2022-09-09
c++實(shí)現(xiàn)簡(jiǎn)單隨機(jī)數(shù)的代碼
在本篇文章里小編給大家整理的是一篇關(guān)于c++實(shí)現(xiàn)簡(jiǎn)單隨機(jī)數(shù)的代碼內(nèi)容，有需要的朋友們可以跟著學(xué)習(xí)下。2021-05-05