探索C嘎嘎的奇妙世界:第十七关---STL(vector的模拟实现)

        vector是一种动态数组，可以动态调整大小并按照索引访问元素。由于很多接口在string中都有所重复，所以这次来讲一些有所区别的接口

1. 迭代器

        Vector中的迭代器是一种用于遍历vector中元素的对象。迭代器提供了一种访问vector中元素的统一方式，使得可以通过一种通用的语法来遍历和访问容器中的元素。在C++中，vector的迭代器是一个类对象，它包含了指向vector中元素的指针，并提供了一系列操作符和方法来访问和操作元素。通过使用迭代器，可以方便地遍历vector中的元素，进行查找、插入、删除等操作。同时，迭代器也提供了一种与算法和其他容器进行交互的统一接口，使得代码更加灵活和可扩展。请看示例代码：

    	typedef T* iterator;
		typedef const T* const_iterator;

		const_iterator begin() const
		{
			return _start;
		}

		const_iterator end() const
		{
			return _finish;
		}

		iterator begin()
		{
			return _start;
		}

		iterator end()
		{
			return _finish;
		}

        上述我们实现了两种迭代器，一种是const的一种是非const，用来适应不同的场景，让我们一起来解析一下上述代码吧：

        首先，通过typedef关键字将T类型定义为iterator类型，将const T类型定义为const_iterator类型。这样可以方便地使用iterator和const_iterator来声明并操作迭代器。

        接着，定义了begin()和end()方法，其中const_iterator版本是用于const对象的，iterator版本是用于非const对象的。

        在const_iterator版本的begin()方法中，直接返回指向vector第一个元素的指针_start。

        在const_iterator版本的end()方法中，直接返回指向vector最后一个元素后面一个位置的指针_finish。

        在iterator版本的begin()方法中，同样返回指向vector第一个元素的指针_start，不同的是这是一个非const版本的指针，可以用于修改vector中的元素。

        在iterator版本的end()方法中，同样返回指向vector最后一个元素后面一个位置的指针_finish，也是一个非const版本的指针。

        通过实现这些方法，可以实现在vector对象上使用迭代器进行遍历和访问元素的功能。同时，const_iterator版本的方法可以保证在const对象上也可以使用迭代器进行遍历，但不能对元素进行修改。而iterator版本的方法可以方便地在非const对象上进行修改操作。

2. 拷贝构造函数、赋值构造函数以及析构函数

        对于这些函数，想必我们轻车熟路了吧，那就不过多介绍了，请看示例代码：

		template <class InputIterator>
		vector(InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

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

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

		vector(int n, const T& val = T())
		{
			reserve(n);
			for (int i = 0; i < n; i++)
			{
				push_back(val);
			}
		}

		// 强制编译器生成默认的
		vector() = default;

		// v2(v1)
		vector(const vector<T>& v)
		{
			reserve(v.capacity());
			for (auto e : v)
			{
				push_back(e);
			}
		}

让我们来分析一下：

        1. 参数为两个迭代器first和last的构造函数：使用了模板技术，接收一个表示范围的[first, last)迭代器，并通过循环将范围内的元素逐个调用push_back()函数插入到vector中。

        2. 参数为元素个数n和初始值val的构造函数：通过reserve()函数预留空间，然后使用循环调用push_back()函数将n个val元素插入到vector中。

        3. 使用initializer_list<T>参数的构造函数：通过reserve()函数预留空间，然后使用循环遍历initializer_list并调用push_back()函数将其中的元素插入到vector中。

        4. 参数为整数n和初始值val的构造函数：与第2个构造函数类似，通过reserve()函数预留空间，然后使用循环调用push_back()函数将n个val元素插入到vector中。

        5. 默认构造函数：使用了默认的函数定义，没有做任何处理。

        6. 拷贝构造函数：接收一个vector对象v作为参数，通过reserve()函数预留空间，然后使用循环遍历v并调用push_back()函数将其中的元素逐个插入到新的vector中。

        通过这些构造函数的实现，可以实现多种不同的初始化vector的方式，例如可以从迭代器范围、指定元素个数和初始值、initializer_list等不同的数据源构造vector对象。

3. swap、capacity、size以及operator[ ]的重载

请看示例代码：

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

size_t capacity()
{
	return _end_of_storage - _start;
}

size_t size()
{
	return _finish - _start;
}

T& operator[](size_t i)
{
	assert(i >= 0 && i < size());
	return *(_start + i);
}

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

	return _start[i];
}

上述代码是vector类中的一些成员函数的实现。

        1. swap函数：用于交换两个vector对象的数据。通过调用std::swap()函数，分别交换_start、_finish和_end_of_storage这三个成员变量的值。

        2. capacity函数：返回vector当前能够容纳的元素个数，即_end_of_storage减去_start的值。

        3. size函数：返回vector当前实际存储的元素个数，即_finish减去_start的值。

        4. operator[]函数：重载了下标运算符，通过下标i来访问vector中的元素。在operator[]函数中使用了断言判断下标是否合法，然后使用指针算术运算来找到指定位置的元素并返回。其中，非const版本返回的是引用，可以进行修改；const版本返回的是常量引用，只能进行读取操作。

        这些函数的实现为vector类提供了一些常用的功能，如交换两个vector对象、获取当前容量和大小、以及通过下标访问元素等。

4. reserve、push_back以及pop_back

请看示例代码：

		void reserve(size_t n)
		{
			if (n > capacity())
			{
				size_t oldsize = size();
				iterator tmp = new T[n];
				if (_start)
				{
					//memcpy(tmp, _start, sizeof(T) * size());//浅拷贝
					for (size_t i = 0; i < size(); i++)
					{
						tmp[i] = _start[i];
					}
					delete[] _start;
				}
				_start = tmp;
				_finish = _start + oldsize;
				_end_of_storage = _start + n;
			}
		}

		void push_back(const T& x)
		{
			if (_finish == _end_of_storage)
			{
				size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
				reserve(newcapacity);
			}
			*_finish = x;
			_finish++;
		}
		void pop_back()
		{
			assert(size() > 0);
			_finish--;
		}

上述代码是vector类中的reserve、push_back和pop_back函数的实现。

        1. reserve函数：用于预分配内存空间以容纳至少n个元素。首先判断n是否大于当前的容量，如果是，则需要重新分配内存。首先保存当前的大小为oldsize，然后创建一个临时指针tmp，分配大小为n的新的内存空间。如果_start指针不为空，则将原始元素逐个复制到新的内存空间中，注意这里是深拷贝。然后释放原始内存空间，并更新_start、_finish和_end_of_storage的值。

        2. push_back函数：用于在vector尾部添加一个元素x。如果当前的空间不够容纳新的元素，则调用reserve函数进行内存扩容。然后将新元素x赋值给_finish指向的位置，并将_finish指针向后移动一位。

        3. pop_back函数：用于删除vector尾部的一个元素。该函数首先使用断言判断vector是否为空，然后将_finish指针向前移动一位，即将最后一个元素的位置腾空。

        这些函数实现了向vector中添加和删除元素的功能，以及在需要时进行内存扩容，保证了vector的动态增长性能。

5. insert以及erase

请看示例代码：

		void insert(iterator pos, const T& x)
		{
			assert(pos >= _start && 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 it = _finish-1;
			while (it >= pos)
			{
				*(it + 1) = *it;
				it--;
			}
			*pos = x;
			_finish++;
		}
		void erase(iterator pos)
		{
			assert(pos >= _start && pos <= _finish);
			iterator it1 = pos + 1;
			while (it1 < _finish)
			{
				*(it1 - 1) = *it1;
				it1++;
			}
			_finish--;
		}

上述代码是vector类中的insert和erase函数的实现。

        1. insert函数：用于在指定的位置pos插入一个元素x。首先使用断言判断pos的合法性，即pos必须在_start和_finish之间。然后判断当前的空间是否足够容纳新的元素，如果不够，则调用reserve函数进行内存扩容，并更新pos的位置。然后将pos之后的元素逐个向后移动一位，给新元素腾出位置。最后将新元素x赋值给pos指向的位置，并将_finish指针向后移动一位。

        2. erase函数：用于删除指定位置pos的元素。首先使用断言判断pos的合法性，即pos必须在_start和_finish之间。然后将pos之后的元素逐个向前移动一位，覆盖掉pos指向的元素。最后将_finish指针向前移动一位，即删除了pos位置的元素。

        这些函数实现了在vector中插入和删除元素的功能，通过移动和覆盖元素的方式实现了元素的插入和删除操作。

         到此我们只是简单的模拟实现了一下STL中vector的相关接口~,后续我们会一一展开学习的,希望这篇博客能给您带来一些启发和思考!那我们下次再一起探险喽,欢迎在评论区进行讨论~~~