【C++初阶】一篇手撕vector类

vector类

- 一，vector的介绍
- 二，vector的使用
- - 2.1 vector的定义
  - 2.2 vector iterator
  - 2.3 vector空间增长问题
  - 2.4 vector增删查改
  - 2.5 vector<char> 可以替代 string 嘛？

一，vector的介绍

vector 是表示可变大小数组序列容器。
就像数组一样，vector 也采用连续的存储空间来存储元素。也就意味着可以采用小标对 vector 的元素进行访问，和数组处理一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
本质讲，vector 使用动态分配数组来存储它的元素。当新元素插入时，为了增加存储空间，这个数组需要被重新分配大小。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价较高的任务，因为每当一个新的元素加入到容器的时候，vector 并不会每次都重新分配大小。
vector 分配空间策略：vector 会分配一些额外的空间以适应可能的增长，因此存储空间（容量）比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候实在常数时间复杂度完成的。
因此，vector 占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长
与其它的动态序列容器相比（如：deque、list、forward_list），vector 在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率会比较低。

二，vector的使用

vector 学习时一定要学会查看文档：vector的文档介绍，vector 在实际中非常重要，在实际中我们熟悉常用的接口就可以，下面列出了需要我们重点掌握的接口。

2.1 vector的定义

在这里插入图片描述
小Tips：size_type 表示一个无符号整数类型，value_type 是第一个模板参数，也就是要存储的数据类型。使用迭代器区间的构造函数是函数模板，只要是满足 Input 类型的迭代器都可以使用该构造函数。

int TestVector1()
{vector<int> first;                                vector<int> second(4, 100);                       vector<int> third(second.begin(), second.end());  vector<int> fourth(third);                       int myints[] = { 16,2,77,29 };vector<int> fifth(myints, myints + sizeof(myints) / sizeof(int));cout << "The contents of fifth are:";for (vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it)cout << ' ' << *it;cout << '\n';return 0;
}

2.2 vector iterator

在这里插入图片描述

int main()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);vector<int>::iterator it1 = v.begin();while (it1 != v.end()){cout << *it1 << " ";++it1;}cout << endl;
}

在这里插入图片描述

void PrintVector(const vector<int>& v)
{// const对象使用const迭代器进行遍历打印vector<int>::const_iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;
}

2.3 vector空间增长问题

在这里插入图片描述

vs 和 g++ 的扩容机制有所不同，vs 下 capacity 是按照 1.5 倍增长的，g++ 是按照 2 倍增长的。vs 是 PJ 版本 STL，g++ 是 SGI 版本 STL。
reserve 只负责开辟空间，如果确定知道需要多少空间，reserve 可以缓解 vector 增容的代价缺陷问题。
resize 在开空间的同时还会进行初始化，影响成员变量 _size。

void TestVectorExpand()
{size_t sz;vector<int> v;sz = v.capacity();cout << "making v grow:\n";for (int i = 0; i < 100; ++i){v.push_back(i);if (sz != v.capacity()){sz = v.capacity();cout << "capacity changed: " << sz << '\n';}}
}

vs下的结果：
在这里插入图片描述

Linux下的结果：
在这里插入图片描述
小Tips：如果已经确定 vector 中要存储元素的大概个数，可以提前将空间设置足够，就可以避免边插入边扩容导致效率低下的问题。

void TestVectorExpandOP()
{vector<int> v;size_t sz = v.capacity();v.reserve(100); // 提前将容量设置好，可以避免一遍插入一遍扩容cout << "making bar grow:\n";for (int i = 0; i < 100; ++i){v.push_back(i);if (sz != v.capacity()){sz = v.capacity();cout << "capacity changed: " << sz << '\n';}}
}

2.4 vector增删查改

在这里插入图片描述

//经典的错误
void Testerro()
{vector<int> v1;v1.reserve(10);for (size_t i = 0; i < 10; i++){v1[i] = i;}
}

注意：上面的代码虽然给 v1 提前开了 10 个空间，但是 v1 中的有效元素个数还是 0，即 v1.size() 的返回值是0，这样一来我们就不能直接通过下标去访问 vector 对象中的每一个元素，因为 operator[ ] 实现中的第一步就是检查下标的合理性，防止越界访问，执行 assert(pos < _size)，而此时 _size 是 0，就会出错。上面的代码只需要把 reserve 改成 resize 就可以正常运行，因为 resize 会改变 _size 的大小。如果硬要使用 reserve 提前开空间，那么接下来要使用 push_back 来插入数据。