C++：STL中vector的使用和模拟实现

在上一篇中讲到了string类，string并不属于STL中因为string出现的比STL早，但是在使用方法上两者有相似之处，学习完string后再来看vector会容易的多，接着往下阅读，一定会有收获滴！

目录

vector的介绍

vector的使用

 vector的构造函数

 vector的拷贝构造

 vector iterator 的使用

 vector的空间

vector增删改 

vector的介绍

1.string是存储字符串的类，vector是表示可变大小数组的序列容器。

2. 就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素 进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自 动处理。

3. 本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小 为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是 一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大 小。

4. vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存 储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是 对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。

5. 因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增 长。

6. 与其它动态序列容器相比（deque, list and forward_list）， vector在访问元素的时候更加高效，在末 尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起list和forward_list 统一的迭代器和引用更好。

vector的使用

对于vector的接口有很多，想要更仔细的看这里：https://legacy.cplusplus.com/reference/vector/vector/?kw=vector

 vector的构造函数

vector的构造函数重载了好几种，所以初始化的方法也有多种。

vector() //无参构造

vector(size_t n,const value_type& val = value_type()) //构造并初始化n个val

vector(InputIterator first, InputIterator last) //使用迭代器来初始化

 对于第二种的构造函数中value_type()会去调用该类型的构造函数，第三种使用迭代器来构造，对于vector的迭代器就是原生指针，区间是左闭右开。

示例：

int a[5] = { 1,2,3,4,5 };
	vector<int> v(a, a + 4);


	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	vector<int>::iterator it = v.begin();
	vector<int> v1(v.begin(), v.end());

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

运行结果：

模拟实现：
成员变量：

typedef T* iterator;
typedef const T* const_iterator;

iterator _start = nullptr;// 指向数据块的开始
iterator _finish = nullptr;// 指向有效数据的尾
iterator _end_Of_Storage = nullptr;// 指向存储容量的尾

        vector()
        {}

		vector(size_t n, const T& value = T())
		{
			resize(n,value);
		}

		vector(int n, const T& value = T())
		{
			resize(n, value);
		}

		template<class InputIterator>

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

 vector的拷贝构造

vector的拷贝构造是指创建一个新的vector对象，其内容与原vector对象完全相同。

vector (const vector& x);

 模拟实现：

vector(const vector<T>& v)
		{
			_start = new T[v.capacity()];

			for (size_t i = 0; i < v.size(); i++)
			{
				_start[i] = v. _start[i];
			}
			_finish = _start + v.size();
			_end_Of_Storage = _start + v.capacity();
		}

在模拟实现时需要注意，拷贝分为浅拷贝和深拷贝，如果在vector的实现中使用浅拷贝就会出问题，会出现析构两次以及野指针的问题，所以需要深拷贝。 

 vector iterator 的使用

查看vector文档可以看到vector的迭代器

 begin()和end()：获取第一个数据位置的iterator/const_iterator，获取最后一个数据的下一个位置的iterator/const_iterator。

模拟实现：

iterator begin()
		{
			return _start;
		}

		iterator end() {
			return _finish;
		}

		const_iterator begin() const
		{
			return _start;
		}

		const_iterator end() const{
			return _finish;
		}

 vector的空间

size() 返回 vector 当前存储的元素数量，是实际已使用的空间大小。
示例：

std::vector<int> vec = {1, 2, 3};
std::cout << vec.size(); // 输出 3

capacity() 返回 vector 当前分配的存储空间大小（以元素数量计），可能大于或等于 size()。
示例：

std::vector<int> vec;
vec.reserve(10);
std::cout << vec.capacity(); // 输出 10（size 仍为 0）

resize(n) 调整 vector 的 size 为 n：

• 若 n < size()，多余元素被删除。
• 若 n > size()，新增元素默认初始化（或通过第二个参数指定值）。
  示例：

std::vector<int> vec = {1, 2, 3};
vec.resize(5);      // 变为 {1, 2, 3, 0, 0}
vec.resize(2);       // 变为 {1, 2}

reserve(n) 预分配至少容纳 n 个元素的内存空间，避免多次动态扩容（仅影响 capacity，不改变 size）。
示例：

std::vector<int> vec;
vec.reserve(100);    // 提前分配空间
vec.push_back(1);    // 不会触发扩容

区别： 

• size 是实际元素数量，capacity 是当前分配的内存容量。
• resize 修改 size 并可能初始化/删除元素，reserve 仅调整 capacity 不改变 size。
• 频繁插入数据时，reserve 可减少重新分配开销。

capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。 这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义 的。vs是PJ版本STL，g++是SGI版本STL。 reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问 题。 resize在开空间的同时还会进行初始化，影响size。

 模拟实现：

          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 oldsz = size();
				T* tmp = new T[n];
				/*memcpy(tmp, _start, n * sizeof(T));*/
				for (size_t i = 0; i < oldsz; i++)
				{
					tmp[i] = _start[i];
				}
				delete[] _start;
				_start = tmp;
				_finish = tmp + oldsz;
				_end_Of_Storage = _start + n;
			}
		}

    void resize(size_t n, const T& value = T())
		{
			if (n < size())
			{
				_finish = _start + n;
			}
			else
			{
				reserve(n);
				
				while (_finish != _start + n)
				{
					*_finish = value;
					_finish++;
				}
			}
		}

vector增删改 

尾插：push_back() 在 vector 末尾添加元素：

vector<int> vec = {1, 2, 3};
vec.push_back(4); // vec: {1, 2, 3, 4}
 

模拟实现：

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

			insert(end(), x);
		}

如果不用insert函数就使用注释那一段代码来实现尾插，效果是一样的，只不过先实现insert函数的话写尾插会更方便一点。

insert（）在指定位置插入元素：

vec.insert(vec.begin() + 1, 5); // vec: {1, 5, 2, 3, 4}
 

模拟实现：

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

			if (size() == capacity())
			{
				size_t len = pos - _start;
				size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
				reserve(newcapacity);
				pos = _start + len;
			}
			iterator end = _finish - 1;
			while (pos <= end)
			{
				*(end+1) = *end;
				end--;
			}

			*pos = x;
			++_finish;
			return pos;
		}

erase()删除指定位置的元素： 

vec.erase(vec.begin() + 2); // 删除第3个元素，vec: {1, 5, 3, 4}
vec.erase(vec.begin(), vec.begin() + 2); // 删除前2个元素，vec: {3, 4}
 

在使用erase需要注意迭代器失效的问题， 直接删除当前迭代器指向的元素会导致该迭代器失效。

例如：

std::vector<int> vec = {1, 2, 3, 4};
auto it = vec.begin() + 1;
vec.erase(it); // it失效
// 此时访问*it是未定义行为
 

以及循环删除多个元素：

std::vector<int> vec = {1, 2, 3, 4};
for (auto it = vec.begin(); it != vec.end(); ++it) {
    if (*it % 2 == 0) {
        vec.erase(it); // it失效后，++it行为未定义
    }
}
 

对于这些我们需要重新来定义迭代器it，erase会返回指向被删除下一位置的迭代器，所以我们需要重新接收更新迭代器，正确处理方法：

std::vector<int> vec = {1, 2, 3, 4};
for (auto it = vec.begin(); it != vec.end(); ) {
    if (*it % 2 == 0) {
        it = vec.erase(it); // 更新迭代器
    } else {
        ++it;
    }
}
 

模拟实现：

iterator erase(iterator pos)
		{
			assert(pos >= _start && pos < _finish);
			auto it = pos + 1;
			while (it != end())
			{
				*(it - 1) = *it;
				it++;
			}
			_finish--;
			return pos;
		}

对于erase删除数据在vector中就是需要挪动数据，直接将需要删除的数据覆盖，将后面的数据往前挪，最后返回被删除元素的位置。在进行删除动作之前需要进行断言，不可越界访问。

尾删：pop_back()：删除最后一个元素

vec.pop_back(); // vec: {1, 5, 2, 3, 4}
 

模拟实现：

如果先实现好erase函数，pop_back函数就很好写了。

void pop_back()
		{
			/*if(_finish != _start)
			--_finish;*/

			erase(end());
		}

vector的使用就介绍到这里啦，这也是常用的函数，需要了解更多可以查看vector文档来学习，如果你已经了解string类，想必vector也手到擒来，string类和STL的用法相似，学会其中一种，再去学习其它STL就比较容易。