Vector
0. vector 的介绍
Vectors are sequence containers representing arrays that can change in size.vector 是用数组实现的、可变长度的顺序容器。
template <
class T, //元素类型
class Alloc = allocator //空间配置器类型
>
class vector;
//类模板的声明
从 vector 的声明可以看出，vector 其实就是一种类模板。
vector 的大小可以动态变化，它的大小会被容器自动处理。vector 的内部是用动态开辟的数组实现的，所以在插入元素时可能需要增容，也就是重新开辟一块空间并拷贝原空间的内容，而深拷贝消耗比较大。
和顺序表类似，vector 存在容量的概念，不会每次插入新元素都增容，而是按照一定规律来进行增容。因此，vector 与单纯的数组相比会占用更多的内存，能够换来更好的管理方式。
学习 string 的时候花了很长时间，但 vector 和 string 类似，所以完全可以将两者类比学习。vector 是适用于任意类型，string 是专门针对字符串设计的类，相当于 vector 的特殊化。虽然两者都是依托数组实现的，但仍不能相互替代。1. vector 的使用
1.1 vector 的默认成员函数
文章图片
| 接口声明 | 解释 |
|---|---|
vector() |
默认构造（无参构造） |
vecotr(size_type n, const_value_type& val=value_type()) |
填充构造，构造对象含有 n 个指定的元素 val |
vector(InputIterator first, InputIterator last) |
范围构造，以迭代器的方式取某个对象的部分[ f i r s t , l a s t ) [first,last) [first,last) 构造对象 |
vector(const vector& v) |
拷贝构造 |
template //迭代器模板
vector (InputIterator first, InputIterator last);
文章图片
析构函数通常不用手动调用。赋值重载的使用也很简单。1.2 vector 的容量操作
文章图片
| 接口声明 | 解释 |
|---|---|
size_type size() |
返回对象的有效元素个数 |
size_type capacity() |
返回对象的容量大小 |
size_type max_size() |
返回 vector 对象最大能存储的元素个数（无意义） |
void reserve (size_type n);
|
增加容量大小，不影响有效个数 |
void resize (size_type n, value_type val = value_type());
|
增加/减小有效元素个数，可指定初始值 |
vector v;
v.size();
v.capacity();
v1.reserve(100);
//扩容到100
v1.resize(100,1);
//有效元素个数变为100,新增元素初始化为1
v1.resize(10);
//有效元素个数变为10
文章图片
由图可知，Windows 下 vector 增容按1.5倍增。
1.3 vector 的访问操作
文章图片
| 接口声明 | 解释 |
|---|---|
reference operator[](size_type n) |
重载操作符[]，返回对应下标位置元素的引用 |
reference at(size_type n);
|
返回对象中指定下标位置的引用。 |
[]重载和at的区别是[]越界会断言报错，at是抛异常。1.4 vector 的迭代器操作
文章图片
有
[]的重载我们就已经能方便快捷的访问操作 vector 的元素，但并不意味着就要放弃使用迭代器。因为容器的定义要保证规范性和统一性，大部分容器都支持迭代器访问，且迭代器使用简单统一。STL 标准库中的任意容器针对迭代器操作的区间都是采用[ f i r s t , l a s t ) [first,last) [first,last) 左开右闭的方式。
/* vector三种遍历方式 */
//[]
for (size_t i = 0;
i < v1.size();
i++) {
v1[i] += 1;
cout << v1[i] << " ";
}
cout << endl;
//iterator
vector::iterator it = v1.begin();
while (it != v1.end()) {
cout << *it << " ";
it++;
}
cout << endl;
//for-loop
for (auto e : v1) {
cout << e << " ";
}
cout << endl;
1.5 vector 的修改操作
文章图片
| 接口声明 | 解释 |
|---|---|
push_back |
尾插一个元素 |
pop_back |
尾删一个元素 |
assign |
类似构造函数中的范围构造和填充构造，使用利用迭代器取对象的部分或指定个元素来填充对象。覆盖性的分配内容。 |
insert |
指定迭代器位置插入一个值，指定迭代器位置插入多个值，指定迭代器位置插入迭代器区间 |
erase |
删除指定迭代器位置的值，删除指定迭代器区间的值 |
/* assign */
template
void assign (InputIterator first, InputIterator last);
// range (1)
void assign (size_type n, const value_type& val);
// fill (2)
/* insert */
iterator insert (iterator position, const value_type& val);
// single element (1)
void insert (iterator position, size_type n, const value_type& val);
// fill (2)
template
void insert (iterator position, InputIterator first, InputIterator last);
// range (3)
/* erase */
iterator erase (iterator position);
iterator erase (iterator first, iterator last);
v.insert(ret, 30);
v.insert(ret, 2, 30);
v.insert(ret, v2.begin(), v2.end());
v1.erase(pos);
v1.erase(v1.begin(), v1.end());
1.6 vector 的其他操作 查找接口 find vector 库中没有像 string 库一样提供成员函数
find接口。因为 vector 作为数组本身的查找需求比较简单，直接使用算法库中的find即可，而 string 对象需要实现正向反向查找字符或子串，才单独实现在类中。#include
template
InputIterator find (InputIterator first, InputIterator last, const T& val) {
while (first != last) {
if (*first == val) {
return first;
}
++first;
}
return last;
}
遍历对象寻找是否有和 val 相等的迭代器位置元素，有则返回迭代器位置，无则返回最后一个迭代器位置
end()。2. vector 的模拟实现
文章图片
2.1 类的定义
template
class vector {
public:
typedef T* iterator;
// ...
private:
iterator start;
iterator finish;
iterator end_of_storage;
}
这个结构和我们之前实现的顺序表结构形式稍有不同，但本质是一样的。只是将表示容量和元素个数的变量用指向对应位置的迭代器代替。
class Seqlist {
T* _a;
/* start */
size_t _size;
/* finish - start */
size_t _capacity;
/* end_of_storage - start */
}
2.2 默认成员函数是空间配置器（内存池）相关的东西，学习 vector 阶段不必过多了解。
//default constructor
vector()
: _start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{}
//fill constructor
vector(size_t n, const T& val = T())
: _start(new T[n])
, _finish(_start + n)
, _end_of_storage(_finish)
{
memset(_start, val, sizeof(T) * n);
}
//copy constructor
vector(const vector& v)
: _start(new T[v.capacity()])
, _finish(_start + v.size())
, _end_of_storage(_start + v.capacity())
{
memcpy(_start, v._start, sizeof(T) * v.size());
}
- 默认构造、填充构造、拷贝构造三种构造函数的默认传统写法。都很类似地开空间再拷贝数据。
//range constructor
template
vector(InputIterator first, InputIterator last)
: _start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
while (first != last)
{
push_back(*first++);
}
}
//copy constructor
vector(const vector& v)
: _start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
vector tmp(v.begin(), v.end());
swap(tmp);
}
从范围构造可以看出类模板中的函数也可以是函数模板。迭代器的分类 函数模板的模板参数要传迭代器区间时，命名是有规定的，范围构造中的
InputIterator就是一种指定的迭代器类型。因容器的结构各有不同，迭代器分为五种类型：| 迭代器类型 | 名称 | 解释 | 适用容器 |
|---|---|---|---|
| input / output_iterator | 输入/输出迭代器 | 只读迭代器只能读取，只写迭代器可以写入该位置的值 | 无实际容器 |
| forward_iterator | 向前迭代器 | 只能向前移动（++），允许在迭代器位置进行读写 | forward_list |
| bidirectional_iterator | 双向迭代器 | 可以双向移动（++,–），允许在迭代器位置进行读写 | list, map, set |
| random_access_iterator | 随机迭代器 | 支持指针运算，可移动（++,–）任意跳转（+,-）读写(*) | deque,vector,string |
文章图片
之所以划分出不同的迭代器类型，是为了限制传入的迭代器的类型，因为其必须满足指定的需求才能完成接下来的函数。
例如范围构造的参数指明迭代器类型为
InputIterator，意思是满足输入迭代器的要求的迭代器都可以作此参数。故此处我们可以传入任意的迭代器。一般像底层是数组连续空间实现的容器，例如 vector, string 等的迭代器类型都是随机迭代器。像双向链表这样的非连续空间的容器的迭代器类型是双向迭代器。
- 通过复用构造函数的范围构造重载版本可以实现拷贝构造的现代写法。记得要初始化一下指针不然构造出来的随机值会影响之后的释放。
//overload operator=
vector& operator=(vector v)/* pass by value */
{
swap(v);
return *this;
}
//destructor
~vector() {
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
- 赋值重载的现代写法都是这么写的，只要实现了拷贝构造就可以。
//overload operator []
T& operator[] (size_t pos) {
return *(_start + pos);
}
const T& operator[](size_t pos) const {
return *(_start + pos);
}
//iterator
typedef T* iterator;
typedef const T* const_iterator;
iterator begin() {
return _start;
}
iterator end() {
return _finish;
}
const_iterator begin() const {
return _start;
}
const_iterator end() const {
return _finish;
}
反向迭代器的设计较为复杂，要单独设计类去封装，该类封装正向迭代器，然后重载其operator++，学到 list 会能更好的理解迭代器。2.3 容量接口
void resize(size_t n, const T& val = T()) {
if (n > size()) {
if (n > capacity()) {
reserve(n);
}
while (_finish != _start + n)
{
*_finish = val;
_finish++;
}
}
//_finish = _start + n;
//迭代器的遍历以达到更新_finish位置的效果。
}
- 缺省值采用
T()的形式，即用 T 类型的匿名对象作val的缺省值。T()是调用默认构造函数的初始化出的对象，得到的是 T 类型的空值。
模板泛型编程兴起时，C++ 为了让模板参数适用于所有类型，对内置类型也优化出了构造函数。
void reserve(size_t n)
{
if (n > capacity()) {
size_t oldSize = size();
//增容
T* tmp = new T[n];
if (_start) {
memcpy(tmp, _start, size() * sizeof(T));
delete[] _start;
}
// 更新迭代器位置
_start = tmp;
_finish = _start + oldSize;
_end_of_storage = _start + n;
}
}
- 在
_start更新前计算出有效元素个数oldSize，用于更新增容后的_finish的地址，等到_start被修改后才计算就无法得到正确的结果。
vector> v;
v.push_back("1111111");
v.push_back("1111111");
v.push_back("1111111");
v.push_back("1111111");
v.push_back("1111111");
//增容浅拷贝
假如用 vector 数组存储 string 对象，四次尾插元素都没问题，当第五次尾插元素时出现了内存问题。其实，第五次尾插出现问题，是因为第五次时正好数组已满需要增容。而模拟实现的
reserve函数使用memcpy将原空间的内容按字节拷贝至新空间。- 若 vector 存储的是内置类型的数据，则浅拷贝至新空间没有问题。
- 若 vector 存储的是自定义类型的数据，由于浅拷贝粗暴地复制变量后再释放原空间，使得新变量指向已释放的空间。
文章图片
如图所示，将对象中的原变量浅拷贝一份，再释放原空间，导致拷贝来的新变量指向了已释放的空间。故应该改为深拷贝。深拷贝需要调用自定义类型的拷贝构造或者赋值重载。
模拟实现的 reserve 是从堆上直接用 new 开辟一块空间，顺带初始化该段空间，所以深拷贝调用赋值重载即可。库中的容器都是从内存池上开辟空间，则需要调用定位 new 初始化空间再调用拷贝构造去拷贝数据。
void reserve(size_t n)
{
if (n > capacity()) {
size_t oldSize = size();
T* tmp = new T[n];
if (_start) {
//memcpy(tmp, _start, size() * sizeof(T));
for (int i = 0;
i < size();
i++) {
tmp[i] = _start[i];
//_start指向的空间存任意类型都能完成深拷贝
}
delete[] _sta rt;
}
_start = tmp;
_finish = _start + oldSize;
_end_of_storage = _start + n;
}
}
size_t size() const {
return _finish - _start;
}
size_t capacity() const {
return _end_of_storage - _start;
}
bool empty() const {
return _start == _finish;
}
2.4 修改接口
void swap(vector v) {
std::swap(start, x.start);
std::swap(finish, x.finish);
std::swap(end_of_storage, x.end_of_storage);
}
void assign(size_t n, const T& val) {
resize(n);
memset(_start, val, sizeof(T) * n);
//出其他值Error
}
void clear() {
_finish = _start;
}
void push_back(const T& x) {
if (_finish == _end_of_storage) {
//增容
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = x;
++_finish;
}
void pop_back() {
assert(_finish > _start);
--_finish;
}
上述接口没什么难度。
iterator insert(iterator pos, const T& val)
{
assert(_start <= pos && pos <= _finish);
//检查pos位置是否合法
// 增容
if (_finish == _end_of_storage) {
size_t sz = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
//增容会导致迭代器失效，迭代器位置陈旧
pos = _start + sz;
//增容后更新pos
}
// 后移 [pos,_finish)
iterator end = _finish;
while (end != pos) {
*end = *(end - 1);
--end;
}
// 插入
*pos = val;
++_finish;
return pos;
//返回迭代器最新位置
}
- 插入元素必然考虑增容，增容后
_start指向新空间，但迭代器位置pos并没有改变仍然指向原空间的某个位置，也就是迭代器失效。所以要在增容前计算pos相对_start的位置，待增容后更新pos使之指向对应的位置即可。 insert函数内迭代器失效的问题解决了，但函数外的pos实参并没有改变仍然指向陈旧的错误位置，故将更新的pos迭代器作返回值返回。
vector::iterator pos = find(v.begin(), v.end(), 2); if (pos != v.end()) { pos = v.insert(pos, 20); // 更新 pos 实参 }
只能采用返回值的形式，不可以通过传引用解决，因为可能会传入临时对象等。
iterator erase(iterator pos)
{
assert(_start <= pos && pos < _finish);
/*iterator begin = pos;
while (begin != _finish) {
*begin = *(begin + 1);
// 越界访问 -> begin=_finish-1时，begin+1 == _finish
begin++;
}*/
iterator begin = pos + 1;
while (begin != _finish)
{
*(begin - 1) = *begin;
begin++;
}
_finish--;
return pos;
//返回迭代器最新位置
}
- 遍历循环的临界条件是下标
!=尾元素的后一个位置（不可访问），则下标最终会遍历到尾元素，即访问范围已足够，因此不可在循环内使下标加值如：*(begin+1)。
vector::iterator pos = v1.begin();
while (pos != v1.end()) {
//删除所有偶数
if (*pos % 2 == 0) {
pos = v1.erase(pos);
//删除后pos复位
}
else {
++pos;
//不符合删除条件的才进位
}
}
文章图片
erase同样有迭代器失效的问题，删除后 pos 就已经指向了下一个元素，再直接++pos会跳过该元素。须不符合删除条件时再 ++。pos=erase(pos)保证删除后 pos 的位置依然正确，避免有些少见的 STL 版本可能会缩容导致pos为野指针。
漏掉元素是 erase 删除元素出现的所有问题的根源。迭代器失效的问题只有在连续使用迭代器时才会出现。不光 vector 会迭代器失效，只要能够使用迭代器访问的容器，都可能发生迭代器失效的问题。2.5 其他接口
bool operator==(vector v) {
if (&x != this) {
for (size_t i = 0;
i < size();
i++) {
if ((*this)[i] != v[i]) {
return false;
}
}
}
return true;
}
bool operator!=(vector v) {
return !(*this == v);
}
bool operator< (vector v) {
for (size_t i = 0;
i < size();
i++) {
if ((*this)[i] >= v[i]) {
return false;
}
}
return true;
}
bool operator<=(vector v) {
return *this < v || *this == v;
}
bool operator> (vector v) {
return !(*this <= v);
}
bool operator>=(vector v) {
return !(*this < v);
}
【C++编程学习指导|vector类的使用介绍及模拟实现】复用==,<逻辑即可完成对象的所有比较运算符的重载。
推荐阅读
- C++编程学习指导|C++初阶（String类续）
- C++编程学习指导|C++初阶（String类）
- C语言|手把手教如何搭建Linux环境（搭建云服务器） (Linux基础篇p1)
- C++|C++(八股文) —— 指针和引用的区别
- 算法|ACC Acwing4376. 数圈圈
- c语言|数据结构3--深入了解单向链表的实现
- 【LeetCode热题100道】7. 整数反转
- 音视频|【音频】削波失真（爆音）问题定位与解决
- C++基础|C++基础（三） 格式控制 setf、setiosflags等详解及避坑