vector模擬實現與核心機制詳情 - 初始化,迭代器,構造函數,數據倉庫,大數據,yyds乾貨盤點阿森CTO 博客

@TOC

📝基本框架

我們先定義自己的命名空間倆封裝自定義的vector類，這樣可以避免與標準庫中的 vector 發生命名衝突。隨即，我們定義模版類vector，三個成員變量都是迭代器，而vector迭代器又是原生指針，所以我們將指針取別名為iterator

框架代碼：

namespace self
{
	template<class T>
	class vector
	{
	public:
		// 定義類型別名 iterator 和 const_iterator，用於表示指向元素的指針類型
		typedef T* iterator;
		typedef const T* const_iterator;

	private:
	private:
		iterator _start;            // 指向動態數組的起始位置
		iterator _finish;           // 指向當前數組中最後一個元素的下一個位置
		iterator _end_of_storage;   // 指向已分配內存的末尾（容量的終點）

	};
}

vector模擬實現與核心機制_構造函數

理解代碼並添加註釋如下：

namespace self
{
    template<class T>
    class vector
    {
    public:
        // 定義迭代器類型
        typedef T* iterator;
        typedef const T* const_iterator;

    private:
        // 數據成員
        iterator _start; // 指向容器中第一個元素的指針
        iterator _finish; // 指向容器中最後一個元素之後的位置
        iterator _end_of_storage; // 指向容器所分配的存儲空間的尾部

        // 在這裏添加其他成員函數和成員變量
    };
}

成員變量的的私有數據成員：

iterator _start;: 這個成員變量保存了一個指向容器中第一個元素的指針。
iterator _finish;: 這個成員變量保存了一個指向容器中最後一個元素之後的位置的指針。
iterator _end_of_storage;: 這個成員變量保存了一個指向容器所分配的存儲空間的尾部的指針。

🌠 構造和銷燬

🌉vector()

vector模擬實現與核心機制_初始化_02

完全空值初始化：

vector()
	: _start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{}

缺省值初始化

vector() {};

private:
	iterator _start = nullptr;            // 指向動態數組的起始位置
	iterator _finish = nullptr;           // 指向當前數組中最後一個元素的下一個位置
	iterator _end_of_storage = nullptr;   // 指向已分配內存的末尾（容量的終點）

3.或者我們也可以偷個懶，讓編譯器自己生成

//強制編譯器生成默認構造函數
vector() = default;

🌉vector(const vector& v)

這個構造函數是 vector 類的拷貝構造函數，用於創建一個新的 vector 對象，它是現有 vector 對象的拷貝。

vector(const vector<T>& v)
{
    reserve(v.size());
    for (auto e : v)
    {
        push_back(e);
    }
}

這是一個拷貝構造函數，它接受一個 const 引用類型的 vector 對象 v 作為參數。這個函數的目的是創建一個新的 vector 對象，並將傳入的 vector 對象 v 的內容拷貝到這個新的 vector 對象中。

這個拷貝構造函數的實現邏輯：

預留空間：首先調用 reserve() 函數為目標 vector 預留足夠的空間來存儲源 vector 的所有元素。這樣可以避免在元素插入過程中多次分配內存，提高性能。
拷貝元素：通過範圍基於 for 循環遍歷源 vector 中的每個元素，並使用 push_back() 將這些元素逐個添加到目標 vector 中。 push_back和reserve()下文會有講解。

🌉vector(size_t n, const T& value = T())

重載構造函數，用於創建一個 vector 對象，並將其初始化為 n 個指定值 value。

vector(size_t n, const T& value = T())
{
    for (size_t i = 0; i < n; ++i)
    {
        push_back(value);
    }
}

這是一個帶有兩個參數的構造函數：

n：表示 vector 中元素的數量。
value：表示每個元素的初始值，默認值為 T()，即 T 類型的默認構造值。

這個構造函數用於創建一個 vector 對象，並將其初始化為 n 個相同的元素，每個元素的值為 value。
const T& 表示一個對 T 類型的常量引用。使用常量引用可以避免在函數內部修改傳入的值，並且通常比傳值的方式更加高效，因為避免了不必要的複製操作。
value 是參數的名字，它代表了要初始化 vector 中每個元素的值。
T() 是 T 類型的默認構造函數的調用。它創建了一個 T 類型的對象，並使用默認構造函數來初始化它。
T() 表示調用 T 類型的默認構造函數，生成一個 T 類型的臨時對象。對於內置類型（如 int, double），這通常是將其初始化為零；對於用户定義的類型（類或結構體），則會調用該類型的默認構造函數。

默認參數的作用:當構造函數被調用而未提供 value 參數時，value 會被初始化為 T()，即一個 T 類型的默認值。

如果提供了 value 參數，那麼構造函數會使用提供的值，而不是默認值。

假設 T 是一個簡單的類或結構體：

class Example {
public:
    int data;
    Example() : data(0) {}  // 默認構造函數，將 data 初始化為 0
    Example(int val) : data(val) {}
};

在 vector 的構造函數中：

vector(size_t n, const T& value = T())
{
    for (size_t i = 0; i < n; ++i)
    {
        push_back(value);
    }
}

當你調用 vector(5)，value 會被初始化為 T()，即 Example()，因此所有元素將會使用 Example 的默認構造值（data 為 0）。
當你調用 vector(5, Example(10))，value 被初始化為 Example(10)，所有元素的 data 將會是 10。

總結: T() 在 const T& value = T() 中的作用是提供一個默認值用於初始化 value 參數。這個默認值是通過調用 T 類型的默認構造函數得到的。這樣，構造函數在沒有提供具體值的情況下，也能正確地初始化 vector 對象中的元素。

🌉賦值拷貝構造：vector& operator=(vector v)

//v3 = v2
vector<T>& operator=(vector<T> v)
{
	swap(v);
	return *this;
}

void swap(const vector<T>& v)
{
	std::swap(_start, v._start);
	std::swap(_finish, v._finish);
	std::swap(_end_of_storage, v._end_of_storage);
}

賦值運算符重載 (operator=)

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

這裏分為三部： 1.1. 參數 vector<T> v

這個賦值運算符重載接受一個 vector<T> 對象 v 作為參數。這裏的 v 是按值傳遞的，這意味着傳遞的是 v 的一個副本。
傳遞副本而不是引用，有助於實現 強異常安全保證。如果在賦值過程中出現異常，原來的 vector 不會被影響。

1.2. swap(v)

swap(v) 是核心操作，它交換當前對象 (*this) 與傳入的 v 對象的數據成員。
這個操作通過交換指針來交換兩個 vector 對象的內部數據（如起始位置 _start、結束位置 _finish、存儲容量邊界 _end_of_storage），而無需進行逐個元素的複製。
交換後，傳入的副本 v 原來持有的資源會被銷燬，而當前對象將接管這些資源。

1.3. return *this

最後返回當前對象的引用 *this，允許鏈式賦值操作，如 v1 = v2 = v3;。

總結: 這種實現方式通過參數按值傳遞的副本，再通過交換數據來實現賦值運算，避免了臨時資源分配失敗導致的資源泄漏，並且非常高效，因為只交換指針，不進行實際數據複製。

swap 函數

void swap(const vector<T>& v)
{
    std::swap(_start, v._start);
    std::swap(_finish, v._finish);
    std::swap(_end_of_storage, v._end_of_storage);
}

const vector<T>& v這裏是引用：

swap 函數接受一個 const vector<T>& v 作為參數。因為這個函數只是交換內部指針，v 被聲明為 const 是為了表明不會修改 v 的邏輯內容（但實際上會修改 v 的內部指針）。 std::swap 是標準庫中的模板函數，交換兩個變量的值。這裏通過交換 _start、_finish 和 _end_of_storage 三個指針，實現了兩個 vector 對象之間的數據交換。 函數效果：交換完成後，原對象和傳入的對象交換了內部數據指針，但沒有改變實際存儲的數據。這種方式避免了內存分配和數據複製操作的開銷，提高了效率。

🌉模版函數實現區間初始化 vector(InputIterator first, InputIterator last)

這個構造函數是一個模板函數，目的是讓 vector 類支持任意類型的迭代器區間初始化。通過這個構造函數，你可以使用兩個迭代器來初始化一個 vector 對象，將迭代器區間 [first, last) 中的所有元素插入到 vector 中。讓我們逐步分析這段代碼：

//類模版中也可以使用函數模版
//函數模版 --- 目的支持任意容易得迭代器區間初始化
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
	while (first != last)
	{
		push_back(*first);
		++first;
	}
}

🌉函數模板的定義 InputIterator

template<class InputIterator>
vector(InputIterator first, InputIterator last)

這是一個函數模板，用於在 vector 類中定義一個構造函數。InputIterator 是模板參數，表示輸入迭代器的類型。由於這是一個模板函數，所以它可以接受任意類型的迭代器。
first 和 last 是兩個迭代器，定義了一個半開區間 [first, last)。這個區間的所有元素將被複制到新的 vector 中。

循環遍歷迭代器區間

while (first != last)
{
    push_back(*first);
    ++first;
}

while (first != last)：這個 while 循環用於遍歷迭代器區間 [first, last)。只要 first 不等於 last，就會繼續循環。

push_back(*first)：

*first 是解引用操作，獲取當前 first 所指向的元素值。
push_back(*first) 將這個值添加到 vector 的末尾。
push_back() 函數會處理必要的內存擴展，因此即使 vector 當前容量不足，它也能動態擴展存儲空間，以容納新元素。

函數的功能和用途：

功能：這個模板構造函數允許你用任意的迭代器區間來初始化一個 vector。這個區間可以是數組、std::list、std::set、std::deque 等容器的迭代器區間，甚至是原始指針。
用途：這種靈活性使得 vector 可以從幾乎任何標準容器或數組中初始化。例如，如果你有一個數組 int arr[] = {1, 2, 3, 4};，可以使用這個構造函數將 arr 的內容複製到 vector 中：

vector<int> vec(arr, arr + 4);

🌉列表初始化區間vector(initializer_list il)

vector(initializer_list<T> il)
{
	reserve(il.size());
	for (auto e : il)
	{
		push_back(e);
	}

}

這段代碼是 vector 類的一個構造函數，它接受一個 initializer_list<T> 類型的參數來初始化 vector。initializer_list 是 C++11 引入的一個特性，允許以列表的形式直接初始化容器。下面詳細分析這段代碼的每一部分：

vector(initializer_list<T> il)

initializer_list<T> 是 C++11 中引入的標準庫類型，表示一個初始化列表，它是一個常量迭代器區間，支持對 T 類型的元素進行初始化。
il 是構造函數的參數，代表一個初始化列表，其中包含了要插入到 vector 中的元素。

reserve(il.size());

reserve() 是 vector 類的一個成員函數，用於預先分配一定的內存空間，以避免在添加元素時頻繁重新分配內存。
il.size() 返回初始化列表中元素的數量。調用 reserve(il.size()) 可以確保 vector 在添加所有元素之前有足夠的空間，從而提高性能。

for (auto e : il)
{
    push_back(e);
}

範圍基於 for 循環 (for (auto e : il)) 遍歷初始化列表 il 中的每一個元素。

auto 關鍵字讓編譯器自動推斷 e 的類型，這裏 e 是 T 類型。
il 是一個 initializer_list<T>，它提供了迭代器接口，因此可以用這種方式進行遍歷。

push_back(e) 將當前元素 e 插入到 vector 的末尾。

push_back() 方法會將元素 e 添加到 vector 中。如果 vector 的當前容量不足以容納新的元素，它會自動擴展容量。

優點和使用場景

易用性：支持直接使用花括號初始化列表，例如：

self::vector<int> v = {1, 2, 3, 4, 5};

示例

假設我們有一個 vector<int>，我們可以使用這個構造函數初始化 vector：

self::vector<int> v = {1, 2, 3, 4, 5};

這個語句會創建一個 vector<int> 對象 v，並將初始化列表 {1, 2, 3, 4, 5} 中的元素依次插入到 vector 中。

🌉~vector()

析構函數，我們只需要釋放空間並置指針指向空：

~vector()
{
	if (_start)
	{
		delete[] _start;
		_start = _finish = _end_of_storage = nullptr;				
	}
}

🌠begin與end

迭代器開始與結束：

iterator begin()
{
	return _start;
}

iterator end()
{
	return _finish;
}

iterator begin() const
{
	return _start;
}

iterator end() const
{
	return _finish;
}

const_iterator cbegin() const
{
	return _start;
}

const_iterator cend() const
{
	return _finish;
}

獲取容量大小與有效元素個數，只需要進行對應指針相減

size_t size() const 
{
	return _finish - _start;
}

size_t capacity() const
{
	return _end_of_storage - _start;
}

🌉reserve

void reserve(size_t n)
{
	if (n > capacity())
	{
		size_t old_size = size();//記錄原size()的大小
		T* tmp = new T[n];

		if (_start)
		{
			memcpy(tmp, _start, sizeof(T) * size());
			delete[] _start;
		}

		_start = tmp;
		_finish = _start + old_size;//避免使用原來finish指針與更新後的start指針相減得到錯誤的size()
		_end_of_storage = _start + n;
	}

}

vector模擬實現與核心機制_迭代器_03

這個 reserve 函數用於在 vector 類中預留一定的內存，以便容納 n 個元素。這個方法的主要目的是擴展 vector 的容量，確保它能夠容納更多的元素，同時管理內部內存的重新分配。下面詳細分析這段代碼：

函數實現

void reserve(size_t n)
{
    if (n > capacity())
    {
        size_t old_size = size(); // 記錄原 size() 的大小
        T* tmp = new T[n]; // 分配新的內存空間

        if (_start)
        {
            memcpy(tmp, _start, sizeof(T) * size()); // 複製原有元素
            delete[] _start; // 釋放原內存
        }

        _start = tmp; // 更新 start 指針
        _finish = _start + old_size; // 更新 finish 指針
        _end_of_storage = _start + n; // 更新 end_of_storage 指針
    }
}

記錄原大小

size_t old_size = size();

size() 返回 vector 中當前元素的數量。
old_size 用於記錄當前 vector 中的元素數量，以便在內存擴展後，能夠正確地設置 _finish 指針。因為不記錄，等delete了_start，到這兩部_start = tmp; // 更新 start 指針，_finish = _start + size(); 再用舊的減去一個釋放的_start，就會有問題。

這裏我們執行深拷貝，通過memcpy將舊數組的元素複製到新數組。需要注意的是，memcpy是基於字節的淺拷貝，如果vector實例化為string類，淺拷貝可能導致二次釋放等問題。

vector模擬實現與核心機制_迭代器_04

雖然我的_start指向新空間並進行了深拷貝，但string類卻進行了淺拷貝，仍然指向原始空間。為了解決這個問題，我們不能使用memcpy，而是需要通過賦值操作進行二次深拷貝。

void reserve(size_t n)
{
	if (n > capacity())
	{
		T* tmp = new T[n];
		size_t old_size = size();
		//memcpy(tmp, _start, size() * sizeof(T));
		for (size_t i = 0; i < old_size; i++)
		{
			tmp[i] = _start[i];
		}
		delete[] _start;

		_start = tmp;
		_finish = tmp + old_size;
		_endofstorage = tmp + n;
	}
}

🌉resize

void resize(size_t n, const T& x = T())
{
	if (n < size()) // 如果新的大小小於當前大小
	{
		_finish = _start + n; // 將_finish指針移動到新大小的位置
	}
	else if (n > size()) // 如果新的大小大於當前大小
	{
		size_t oldSize = size();
		reserve(n); // 確保有足夠的容量來存儲新大小的元素

		for (size_t i = oldSize; i < n; ++i)
		{
			push_back(x); // 用默認值x填充新的元素
		}
	}
	// 如果 n 等於當前大小，不需要進行任何操作
}

如果新大小小於當前大小,則截斷容器中多餘的元素;如果新大小大於當前大小,則使用給定的填充值來填充新的元素。

🌉insert與erase

vector模擬實現與核心機制_迭代器_05

iterator insert(iterator pos, const T& x)
{
	assert(pos >= _start);
	assert(pos <= _finish);

	if (_finish == _end_of_storage)
	{
		size_t len = pos - _start;
		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 在 vector 當前元素的範圍內，即在有效的 [start, finish] 區間內。 內存擴展

if (_finish == _end_of_storage)
{
    size_t len = pos - _start;
    size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
    reserve(newcapacity);

    pos = _start + len;
}

如果 vector 當前容量已滿（_finish == _end_of_storage），則需要擴展容量。
計算插入位置在原始 vector 中的索引 len，並使用 reserve(newcapacity) 擴展容量。
擴展容量後，更新 pos 的位置，使其指向新的內存區域中插入的目標位置。這裏 pos = _start + len 是為了確保擴展後的 pos 位置正確。這裏的len記錄原來位置是防止迭代器失效問題：因為我們使用了reserve，開了新空間，如果未保存，使用新的地址，那將會有風險。

返回值

return pos;

返回新插入元素的位置 pos，使得插入操作可以鏈式使用，更新迭代器。

在 C++ 中，std::vector 是一個動態數組，它會根據需要擴展其內部存儲的容量。由於這種擴展和其他操作，vector 中的迭代器可能會失效。以下是 vector 中迭代器失效的主要條件：

內存重新分配

vector 會在需要時擴展其內存容量。當 vector 的容量不足以容納新元素時，它會重新分配內存。這通常發生在以下操作時：

插入元素：當 vector 的容量滿時，使用 push_back、insert 等方法插入新元素可能會觸發內存重新分配。
擴展容量：使用 reserve 增加 vector 的容量，如果 reserve 請求的容量大於當前容量，vector 可能會重新分配內存。

影響：

內存重新分配會導致所有原有的指針和迭代器失效，因為 vector 內部的元素被移動到新的內存位置。
在內存重新分配後，原來的迭代器和指針將不再有效，因為它們指向的是舊的內存區域。

刪除元素

刪除元素通常不會導致內存重新分配，但會影響迭代器的有效性：

erase：調用 erase 方法刪除元素會使指向被刪除元素的迭代器失效。
範圍刪除：erase 刪除一段範圍內的元素時，範圍內的所有迭代器會失效，此外，所有指向被刪除元素之後的迭代器也會失效，因為元素的後續位置發生了改變。

影響：

erase 操作可能導致指向被刪除元素的迭代器失效。
被刪除元素之後的所有迭代器也會失效，因為刪除操作可能會導致元素的重新排列。

在對 vector 進行賦值或移動操作時，雖然這些操作不會直接影響單個迭代器，但會對迭代器的使用產生影響：

賦值操作：將一個 vector 賦值給另一個 vector，會涉及到內存重新分配和元素複製，這可能會使原有的迭代器失效。
移動操作：使用移動構造函數或移動賦值操作時，也可能導致內部數據的重新分配和元素的重新排列，從而使迭代器失效。

為了避免迭代器失效的影響，在進行可能導致失效的操作後，應當重新獲取迭代器或使用容器提供的穩定操作。例如，可以使用 vector 提供的 begin() 和 end() 重新獲取迭代器。在設計使用迭代器的代碼時，應考慮這些因素，以確保代碼的正確性和可靠性。

vector模擬實現與核心機制_迭代器_06

iterator erase(iterator pos)
{
	assert(pos >= _start);
	assert(pos < _finish);

	iterator end = pos + 1;
	while (end <= _finish)
	{
		*(end - 1) = *end;
		++end;
	}

	--_finish;
	return pos;
}

迭代器失效：刪除操作會使指向被刪除元素的迭代器失效。刪除一個元素，迭代器還指向原位置，但元素被移動了，也就是原位置的後一個元素來到原位置，因此注意 erase 後，pos 之後的迭代器要更新指向新位置。

🌉push_back與pop_back

push_back函數可以複用，也可以使用insert的方法構造：

void push_back(const T& x)
{
	//if (_finish == _end_of_storage)
	//{
	//	size_t newcapacity = capacity() == 0 ? 4 : sizeof(T) * 2;
	//	reserve(newcapacity);
	//}
	//*_finish = x;
	//_finish++;

	insert(end(), x);
}

void pop_back()
{
	assert(size() > 0);
	--_finish;

}

🌠訪問元素

訪問元素operator[]需要注意的就是，要判斷是否pos訪問的位置合法：

T& operator[](size_t pos)
{
	assert(pos < size());

	return  _start[pos];
}

const T& operator[](size_t pos) const
{
	assert(pos < size());

	return _start[pos];
}

🌠全代碼

代碼中有豐富的測試用例來驗證vector的實現是否有問題：

🌉test.cpp

# define _CRT_SECURE_NO_WARNINGS 1
#include "vector.h"

int main()
{
	//self::test_vector01();
	//self::test_vector02();
	//self::test_vector03();
	//self::test_vector04();
	//self::test_vector05();
	//self::test_vector06();
	//self::test_vector07();
	self::test_vector08();

	return 0;
}

🌉vector.h

#pragma once
#include <iostream>
#include <list>
#include <assert.h>
using namespace std;

namespace self
{
	template<class T>
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;

		iterator begin()
		{
			return _start;
		}

		iterator end()
		{
			return _finish;
		}

		iterator begin() const
		{
			return _start;
		}

		iterator end() const
		{
			return _finish;
		}

		const_iterator cbegin() const
		{
			return _start;
		}

		const_iterator cend() const
		{
			return _finish;
		}

		//強制編譯器生成默認構造函數
		vector() = default;

		//s2(s1)
		vector(const vector<T>& v)
		{
			reserve(v.size());
			for (auto e : v)
			{
				push_back(e);
			}

		}

		vector(size_t n, const T& value = T())
		{
			for (size_t i = 0; i < n; ++i)
			{
				push_back(value);
			}
		}

		//v3 = v2
		vector<T>& operator=(vector<T> v)
		{
			swap(v);
			return *this;
		}

		void swap(const vector<T>& v)
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_end_of_storage, v._end_of_storage);
		}

		//類模版中也可以使用函數模版
		//函數模版 --- 目的支持任意容易得迭代器區間初始化
		template<class InputIterator>
		vector(InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

		vector(initializer_list<T> il)
		{
			reserve(il.size());
			for (auto e : il)
			{
				push_back(e);
			}

		}

		~vector()
		{
			if (_start)
			{
				delete[] _start;
				_start = _finish = _end_of_storage = nullptr;				
			}
		}
		
		size_t size()
		{
			return _finish - _start;
		}

		size_t capacity()
		{
			return _end_of_storage - _start;
		}

		size_t size() const 
		{
			return _finish - _start;
		}

		size_t capacity() const
		{
			return _end_of_storage - _start;
		}

		void reserve(size_t n)
		{
			if (n > capacity())
			{
				size_t old_size = size();//記錄原size()的大小
				T* tmp = new T[n];

				//if (_start)
				//{
				//	memcpy(tmp, _start, sizeof(T) * size());
				//	delete[] _start;
				//}

				for (size_t i = 0; i < old_size; i++)
				{
					tmp[i] = _start[i];
				}
				delete[] _start;

				_start = tmp;
				_finish = _start + old_size;//避免使用原來finish指針與更新後的start指針相減得到錯誤的size()
				_end_of_storage = _start + n;
			}

		}

		void resize(size_t n, const T& x = T())
		{
			if (n < size()) // 如果新的大小小於當前大小
			{
				_finish = _start + n; // 將_finish指針移動到新大小的位置
			}
			else if (n > size()) // 如果新的大小大於當前大小
			{
				size_t oldSize = size();
				reserve(n); // 確保有足夠的容量來存儲新大小的元素

				for (size_t i = oldSize; i < n; ++i)
				{
					push_back(x); // 用默認值x填充新的元素
				}
			}
			// 如果 n 等於當前大小，不需要進行任何操作
		}

		void push_back(const T& x)
		{
			//if (_finish == _end_of_storage)
			//{
			//	size_t newcapacity = capacity() == 0 ? 4 : sizeof(T) * 2;
			//	reserve(newcapacity);
			//}
			//*_finish = x;
			//_finish++;

			insert(end(), x);
		}

		void pop_back()
		{
			assert(size() > 0);
			--_finish;

		}

		T& operator[](size_t pos)
		{
			assert(pos < size());

			return  _start[pos];
		}

		const T& operator[](size_t pos) const
		{
			assert(pos < size());

			return _start[pos];
		}

		iterator insert(iterator pos, const T& x)
		{
			assert(pos >= _start);
			assert(pos <= _finish);

			if (_finish == _end_of_storage)
			{
				size_t len = pos - _start;
				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;
		}

		iterator erase(iterator pos)
		{
			assert(pos >= _start);
			assert(pos < _finish);

			iterator end = pos + 1;
			while (end <= _finish)
			{
				*(end - 1) = *end;
				++end;
			}

			--_finish;
			return pos;
		}
	private:
		iterator _start;
		iterator _finish;
		iterator _end_of_storage;

	};

	void test_vector01()
	{
		self::vector<int> v1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);
		v1.push_back(5);
		v1.push_back(5);
		v1.push_back(4);

		for (size_t i = 0; i < v1.size(); i++)
		{
			cout << v1[i];
		}
		cout << endl;

		self::vector<int>::iterator it = v1.begin();
		while (it != v1.end())
		{
			cout << *it << " ";
			it++;
		}
		cout << endl;

		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;

		v1.pop_back();
		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	void test_vector02()
	{
		self::vector<int> v1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);

		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;



		size_t x = 0;
		cin >> x;
		self::vector<int>::iterator it = find(v1.begin(), v1.end(), x);
		if (it != v1.begin())
		{
			it = v1.insert(it, 100);
			cout << *it << endl;
		}
		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;

	}

	void test_vector03()
	{
		self::vector<int> v1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);

		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;

		size_t x = 0;
		cin >> x;
		self::vector<int>::iterator it = find(v1.begin(), v1.end(), x);
		if (it != v1.end())
		{
			it = v1.erase(it);

			if (it != v1.end())
				cout << *it << endl;
		}

		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;

		cout << typeid(it).name() << endl;
	}

	void test_vector04()
	{
		vector<int> v3;
		v3.push_back(1);
		v3.push_back(2);
		v3.push_back(3);
		v3.push_back(4);
		vector<int>::iterator it = v3.begin();
		while (it != v3.end())
		{
			if (*it % 2 == 0)
			{
				v3.erase(it);
			}
			else
			{
				++it;
			}
		}

		for (auto e : v3)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	void test_vector05()
	{
		vector<int> v6;
		v6.push_back(1);
		v6.push_back(1);
		v6.push_back(1);
		for (auto e : v6)
		{
			cout << e << " ";
		}
		cout << endl;

		vector<int> v7(v6);
		for (auto e : v7)
		{
			cout << e << " ";
		}
		cout << endl;

		vector<int> v8 = v6;
		for (auto e : v8)
		{
			cout << e << " ";
		}
		cout << endl;

	}

	void test_vector06()
	{
		int i = 0;
		int j(1);
		int k = int();
		int x = int(2);
		vector<string> v8(4, "xxxxx");
		for (auto e : v8)
		{
			cout << e << " ";
		}
		cout << endl;


		vector<int> v9(4u, 104);
		for (auto e : v9)
		{
			cout << e << " ";
		}
		cout << endl;


		vector<int> v10(v9.begin(), v9.end());
		for (auto e : v9)
		{
			cout << e << " ";
		}
		cout << endl;


	}

	void test_vector07()
	{
		vector<string> v8(4, "xxxxx");
		for (auto e : v8)
		{
			cout << e << " ";
		}
		cout << endl;


		list<int> It;
		It.push_back(100);
		It.push_back(100);
		It.push_back(100);
		It.push_back(100);

		list<int> v3(It.begin(), It.end());
		for (auto e : v3)
		{
			cout << e << " ";
		}
		cout << endl;


	}

	class A
	{
	public:
		A(int a = 0)
			:_a1(a)
			, _a2(0)
		{

		}

		A(int a1, int a2)
			:_a1(a1)
			, _a2(a2)
		{

		}
	private:
		int _a1;
		int _a2;
	};

	void test_vector08()
	{
		A aa1(1);
		A aa2(2, 2);
		const A& aa3 = { 1, 2 };

		A aa4 = 1;
		A aa5 = { 1,3 };

		vector<int> v1({ 1,2,3,4,5,6 });
		vector<int> v2 = { 1,2,3,4,5,8 };
		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;
		for (auto e : v2)
		{
			cout << e << " ";
		}
		cout << endl;

		auto il1 = { 1,2,3,4 };
		initializer_list<int> il2 = { 1,3,4 };
		cout << typeid(il1).name() << endl;
		cout << sizeof(il2) << endl;
		for (auto e : il2)
		{
			cout << e << " ";
		}
		cout << endl;

	}
}

阿森CTO 博客

阿森CTO 博客

博客 / 詳情