C++模擬實(shí)現(xiàn)vector的示例代碼

更新時(shí)間：2022年08月19日 15:59:45 作者：安河橋畔

Vector是一個(gè)能夠存放任意類(lèi)型的動(dòng)態(tài)數(shù)組，有點(diǎn)類(lèi)似數(shù)組，是一個(gè)連續(xù)地址空間。本文將用C++模擬實(shí)現(xiàn)vector，感興趣的小伙伴可以了解一下

一、迭代器

定義

vector類(lèi)型的迭代器就是原生態(tài)的指針，對(duì)T*進(jìn)行重命名即可

typedef T* iterator;
typedef const T* const_iterator;

普通迭代器

iterator begin()
{
    return start;
}
iterator end()
{
    return finish;
}

const類(lèi)型迭代器

const類(lèi)型迭代器可以訪問(wèn)const成員變量

const iterator cbegin()const
{
    return start;
}
const iterator cend()const
{
    return finish;
}

二、構(gòu)造類(lèi)

構(gòu)造函數(shù)

構(gòu)造空對(duì)象

在初始化列表中對(duì)三個(gè)成員變量進(jìn)行初始化

vector()
    :start(nullptr)
    , finish(nullptr)
    , endOfStorage(nullptr)
{}

n個(gè)T類(lèi)型

開(kāi)辟空間以后，對(duì)finish進(jìn)行自增，在空間填充元素

vector(size_t n, const T& value = T())
    :start(new T[n])
    , finish(start)
    , endOfStorage(start + n)
{
    for (int i = 0; i < n; i++)
    {
        *finish++ = value;
    }
}

重載前一個(gè)構(gòu)造函數(shù)，將第一個(gè)參數(shù)設(shè)置為int類(lèi)型

vector(int n, const T& value = T())
    :start(new T[n])
    , finish(start)
    , endOfStorage(start + n)
{
    for (int i = 0; i < n; i++)
    {
        *finish++ = value;
    }
}

之所以要對(duì)這種類(lèi)型的構(gòu)造函數(shù)進(jìn)行重載，是因?yàn)樵谡{(diào)用構(gòu)造函數(shù)時(shí)，如果實(shí)參傳兩個(gè)整型數(shù)字，編譯器會(huì)默認(rèn)為int類(lèi)型數(shù)據(jù)，進(jìn)行推演之后與前面的size_t類(lèi)型不匹配，則會(huì)調(diào)用下面的區(qū)間構(gòu)造的方法，導(dǎo)致程序報(bào)錯(cuò)，如圖：

迭代器構(gòu)造

將構(gòu)造方法中迭代器的類(lèi)型寫(xiě)成模板類(lèi)型，這樣便可以接收其它類(lèi)型的迭代器，如：T類(lèi)型為char，Iterator迭代器為string類(lèi)型，便可以從字符串中截取字符，構(gòu)造vector<char>類(lèi)型的對(duì)象。

//寫(xiě)成函數(shù)模板，可以接受任意類(lèi)型的迭代器
template<typename Iterator>
vector(Iterator first, Iterator last)
{
    size_t n = ZH::distance(first, last);//獲取長(zhǎng)度
    start = new T[n];
    finish = start;
    endOfStorage = start + n;
    while (first != last){
        *finish = *first;
        first++;
        finish++;//完成賦值的同時(shí)也移動(dòng)了finish的位置
    }
}

將distance方法寫(xiě)到另一個(gè).hpp頭文件中

template<typename Iterator>
//此處的Iterator是模板參數(shù)，表示可以傳任意類(lèi)型的迭代器
size_t distance(Iterator first, Iterator last)
{
    //獲取元素個(gè)數(shù)，暫時(shí)只考慮底層空間連續(xù)的情況
    int count = 0;
    while (first != last)
    {
        first++;
        count++;
    }
    return count;
}

拷貝構(gòu)造函數(shù)

拷貝構(gòu)造函數(shù)的形參必須是const類(lèi)對(duì)象的引用，必須使用const類(lèi)型的迭代器才能訪問(wèn)，復(fù)用迭代器構(gòu)造的方法定義一個(gè)臨時(shí)變量temp，交換temp與當(dāng)前對(duì)象

//此處拷貝構(gòu)造函數(shù)的形參是const類(lèi)型
vector(const vector<T>& v)
    :start(nullptr)
    , finish(nullptr)
    , endOfStorage(nullptr)
{
    //▲用const類(lèi)型的迭代器訪問(wèn)const變量
    vector<T> temp(v.cbegin(), v.cend());
    this->swap(temp);
}

賦值運(yùn)算符重載

形參設(shè)置為類(lèi)類(lèi)型對(duì)象，調(diào)用賦值運(yùn)算符重載函數(shù)時(shí)，形參會(huì)拷貝實(shí)參，交換當(dāng)前對(duì)象與形參的值。

vector<T>& operator=(const vector<T> v)
{
    this->swap(v);
    return *this;
}

析構(gòu)函數(shù)

釋放空間，將三個(gè)迭代器賦值為空

~vector()
{
    delete[]start;
    start = nullptr;
    finish = nullptr;
    endOfStorage = nullptr;
}

三、容量相關(guān)操作

size、capacity

size_t size()
{
    return finish - start;
}
size_t capacity()
{
    return endOfStorage - start;
}

empty

判斷fiinsh與start是否相等即可，相等則為空

size_t empty()
{
    return finish == start;
}

resize

定義一個(gè)變量保存舊的size的值‘判斷是減小還是增加size；判斷是否需要擴(kuò)容，需要?jiǎng)t調(diào)用reserve函數(shù)，從舊空間的結(jié)束位置開(kāi)始，給新增加的空間填充元素；最后改變finish的值。

void resize(size_t newsize, const T& value = T())
{
    size_t oldsize = size();
    if (newsize > oldsize){
        if (newsize > capacity()){
            reserve(newsize);
        }
        for (size_t i = oldsize; i < newsize; i++)
        {
            start[i] = value;
        }
    }
    finish = start + newsize;//不用考慮增加或減小
}

reserve

reserve的步驟：申請(qǐng)新空間，拷貝舊空間的元素，釋放舊的空間。

void reserve(size_t newcapacity)
{
	size_t oldcapacity = capacity();
	if (newcapacity > oldcapacity)
	{
		size_t n = size();//保存size()的值
		T* temp = new T[newcapacity];
		//start不為空時(shí)才進(jìn)行拷貝舊空間元素和釋放的操作
		if (start)
		{
			//memcpy淺拷貝，當(dāng)vector中存放的對(duì)象內(nèi)部設(shè)計(jì)資源管理
			// 會(huì)有內(nèi)存泄漏和野指針問(wèn)題
			//memcpy(temp, start, sizeof(T) * n);

			for (size_t i = 0; i < n; i++)
			{
				temp[i] = start[i];//調(diào)用賦值運(yùn)算符重載
			}
			delete[] start;
		}
		start = temp;
		//▲此處不能用satart+size(),因?yàn)閟ize方法中有finish-start,而start值已經(jīng)改變
		finish = start + n;
		endOfStorage = start + newcapacity;
	}
}

易錯(cuò)點(diǎn)：

判斷start的值是否為空，如果原來(lái)的start為空，則不需要再拷貝元素和釋放

淺拷貝問(wèn)題

finish更新問(wèn)題

size()的方法內(nèi)部finish-start，而此時(shí)start已經(jīng)發(fā)生改變，finish還是舊的，所以要提前定義一個(gè)臨時(shí)變量保存size()的值

三、元素訪問(wèn)

[ ]重載

重載成普通類(lèi)型和const類(lèi)型，const類(lèi)型可以訪問(wèn)const成員

T& operator[](size_t index)
{
	assert(index < size());
	return start[index];
}

const T& operator[](size_t index)const
{
	assert(index < size());
	return start[index];
}

front

返回動(dòng)態(tài)數(shù)組第一個(gè)元素

T& front()
{
    return start[0];
}
const T& front()const
{
    return start[0];
}

back

返回最后一個(gè)位置前一個(gè)元素

T& back()
{
    return *(finish - 1);
}
const T& back()const
{
    return *(finish - 1);
}

四、修改類(lèi)接口

push_back

插入前先判斷空間是否已滿，空間若滿則進(jìn)行擴(kuò)容，擴(kuò)容時(shí)，要原來(lái)的空間容量為0的情況；將value放置到末尾位置，并將finish向后移動(dòng)一個(gè)單位

void push_back(const T& value)
{
    if (finish == endOfStorage)
    {
        //因?yàn)樵瓉?lái)的capacity可能為0,所以要+3
        reserve(capacity() * 2 + 3);
    }
    *finish++ = value;
}

pop_back

尾刪，先判斷對(duì)象是否為空，若不為空則將finish位置前移一個(gè)單位

void pop_back()
{
    if (empty())
    {
        return;
    }
    finish--;
}

insert

任意位置插入，insert的返回值為新插入的第一個(gè)元素位置的迭代器；因?yàn)椴迦肟赡軙?huì)進(jìn)行擴(kuò)容，導(dǎo)致start的值改變，所以先定義一個(gè)變量保存pos與start的相對(duì)位置；判斷是否需要擴(kuò)容；從插入位置開(kāi)始，將所有元素向后搬移一個(gè)位置；將pos位置的值置為要插入的值；更新finish的值。

//第二個(gè)參數(shù)用const修飾，常量引用
//不用const修飾則為非常量引用
iterator insert(iterator pos, const T& value)
{
    int index = pos - start;
    assert(pos >= start && pos < finish);
    //判斷空間是否足夠
    if (finish == endOfStorage)
    {
        reserve(capacity() * 2);
    }
    pos = start + index;
    for (auto it = finish; it > pos; it--)
    {
        *it = *(it - 1);
    }
    *pos = value;
    finish++;
    return pos;
}

erase

判斷下標(biāo)合法性；從pos位置下一個(gè)位置開(kāi)始，將所有元素向前搬移一個(gè)位置；更新finish的值

iterator erase(iterator pos)
{
	assert(pos >= start && pos < finish);

	auto it = pos;
	while (it < finish - 1)
	{
		*it = *(it + 1);
		it++;
	}
	finish--;
	return pos;
}

clear

清空所有元素，令finish=start即可

void clear()
{
    finish = start;
}

swap

vector內(nèi)置的swap函數(shù)，調(diào)用標(biāo)準(zhǔn)庫(kù)中的swap交換vector的三個(gè)成員變量的值

void swap(vector<T>& v)
{
    std::swap(start, v.start);
    std::swap(finish, v.finish);
    std::swap(endOfStorage, v.endOfStorage);
}

五、成員變量

private:
    iterator start;
    iterator finish;
    iterator endOfStorage;

vector內(nèi)部有三個(gè)成員變量，start表示起始位置，finish表示有效元素的末尾位置，endOfStorage表示空間的末尾位置；通過(guò)這三個(gè)成員變量可以得到size和capacity等值，如圖：

以上就是C++模擬實(shí)現(xiàn)vector的示例代碼的詳細(xì)內(nèi)容，更多關(guān)于C++ vector的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章:

C++
vector