【C++初阶】vector
🥕个人主页：开敲🍉
🔥所属专栏：C++🥭
🌼文章目录🌼
1. vector的介绍及使用
1.1 vector介绍
1.2 vector的使用
1.2.1 vector的定义
1.2.2vector iterator的使用（迭代器）：
1.2.3 vector空间增长问题
1.2.4 vector的增删查改
1.2.5 迭代器失效问题
2. vector的模拟实现
1. vector的介绍及使用
1.1 vector介绍
vector - C++ Reference (cplusplus.com)
前面讲过使用STL的三个境界是：会使用，能明理，能扩展。学习vector我们也是按照这个标准来进行学习的。
1.2 vector的使用
学习vector的时候一定要学会多看资料和文档：vector - C++ Reference (cplusplus.com)，vector在实际中也非常常用，我们学习时只需要熟悉常用的接口即可，下面列出vector的常用接口：
1.2.1 vector的定义
Construct(构造函数声明)：
vector()（重点）：无参构造
vector(size_t n,const value_type& val = value_type())：构造并初始化n个val
vector(const vector& x)（重点）：拷贝构造
template<class InputIterator,class InputIterator>
vector(InputIterator first,InputIterator last)：迭代器构造 (迭代器构造可以使得我们能用不同的类去相互构造)
1.2.2vector iterator的使用（迭代器）：
begin+end（重点）：获取第一个位置数据的iterator或const_iterator + 获取最后一个数据下一个位置的iterator或const_iterator
rbegin+rend：获取最后一个位置数据的reverse_iterator + 获取第一个位置前一个位置的reverse_iterator
1.2.3 vector空间增长问题
size：获取有效数据个数
capacity：获取容量大小
empty：判断是否为空（判断是否有数据存储）
rsize（重点）：改变有效数据个数
reserve（重点）：改变容量大小
注：
① capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2
倍增长的。这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是
根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。
② reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代
价缺陷问题。
③ resize在开空间的同时还会进行初始化，影响size。
1.2.4 vector的增删查改
push_back（重点）：尾插数据
pop_back（重点）：尾删数据
insert：指定位置插入数据
erase：指定位置删除数据
swap：交换两个vector的数据空间
operator[]（重点）：模拟数据访问
1.2.5 迭代器失效问题
迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对
指针进行了封装，比如：vector的迭代器就是原生态指针T* 。因此迭代器失效，实际就是迭代器
底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即
如果继续使用已经失效的迭代器，程序可能会崩溃)。
对于vector可能会导致其迭代器失效的操作有：
① 会引起迭代器指向内容改变的操作，如：insert、resize、erase等
这里我们调用insert接口在it这个位置插入数据，但是后序我们想要将it这个位置数据改变时编译器报错了，这就是因为迭代器失效。
这里的迭代器失效是因为，it指向的已经不是insert前的位置的数据了，画图理解：
② 会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、
assign、push_back等
这里我们只是将v的空间增大了而已啊，it指向的位置没有改变，为啥还会出错呢。这就是增容的问题。
vector的增容是开辟一块更大的空间，将原先空间里的数据全部拷贝到新空间中，而当我们vector中的数据搬迁到新空间时，it指向的还是原来的空间，而原来的空间已经释放，因此这里编译器同样会报错。
③ 与vector类似，string也会存在与vector相同的迭代器失效问题
2. vector的模拟实现
//vector.h 文件
#pragma once
#include <iostream>
#include <assert.h>
using namespace std;namespace gjk
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;//无参构造
vector()
{}//构造并初始化n个val
vector(int n, const T& val = T())
{
_begin = new T[n + 1];
for (size_t i = 0; i < n; i++)
{
_begin[i] = val;
}
_finish = _begin + n;
_end_of_storage = _finish;
}//使用一个vector初始化另一个vector
vector(const vector<T>& data)
{
_begin = new T[data.capacity() + 1];
for (size_t i = 0; i < data.size(); i++)
{
_begin[i] = data._begin[i];
}
_finish = _begin + data.size();
_end_of_storage = _begin + data.capacity();
}//迭代器构造
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
first++;
}
}//析构
~vector()
{
delete[] _begin;
_begin = _finish = _end_of_storage = nullptr;
}//获取有效数据个数
size_t size()
{
return _finish - _begin;
}//获取容量大小
size_t capacity()
{
return _end_of_storage - _begin;
}const size_t size() const
{
return _finish - _begin;
}const size_t capacity() const
{
return _end_of_storage - _begin;
}//模拟数据下标访问
T& operator[](size_t pos)
{
return _begin + pos;
}const T& operator[](size_t pos) const
{
return _begin + pos;
}//返回第一个数据的iterator
iterator begin()
{
return _begin;
}//返回最后一个数据的下一个位置的iterator
iterator end()
{
return _finish;
}const_iterator begin() const
{
return _begin;
}const_iterator end() const
{
return _finish;
}//预留开辟空间/增容
void reserve(size_t n)
{
if (n > capacity())
{
size_t old_size = size();
T* tmp = new T[n + 1]{ 0 };
if (size())
{
for (size_t i = 0; i < n; i++)
{
tmp[i] = _begin[i];
}
}delete[] _begin;
_begin = tmp;
_finish = _begin + old_size;
_end_of_storage = _begin + n;
}
}//改变有效数据个数
void rsize(size_t n, const T& val = T())
{
if (n < size())
_finish = _begin + n;
else
{
reserve(n + 1);
iterator it = _finish;
while (it != _begin+n)
{
*it = val;
it++;
}
}
}//打印模板
template<class Container>
void printf_container(const Container& con)
{
for (auto e : con)
{
cout << e << " ";
}
cout << endl;
}//尾插数据
void push_back(const T& data)
{
if (_finish == _end_of_storage)
reserve(capacity() == 0 ? 4 : 2 * capacity());
(*_finish) = data;
_finish++;
}//尾删数据
void pop_back()
{
if (_finish != _begin)
_finish--;
}//交换两个vector的数据
void swap(vector<T>& data)
{
size_t old_size = size();
size_t old_capacity = capacity();
T* tmp = new T[capacity() + 1];
for (size_t i = 0; i < size(); i++)
{
tmp[i] = _begin[i];
}
_begin = data._begin;
_finish = data._finish;
_end_of_storage = data._end_of_storage;
data._begin = tmp;
data._finish = data._begin + old_size;
data._end_of_storage = data._begin + old_capacity;
}//指定位置插入数据
iterator insert(iterator pos, const T& data)
{
size_t tmp = pos - _begin;
if (_finish == _end_of_storage)
{
reserve(capacity() == 0 ? 4 : 2 * capacity());
pos = _begin + tmp;
}iterator end = _finish + 1;
while (end - 1 >= pos)
{
*end = *(end - 1);
end--;
}
*pos = data;
_finish++;
return pos + 1;
}//指定位置删除数据
iterator erase(iterator pos)
{
iterator end = pos + 1;
while (end <= _finish)
{
*(end - 1) = *end;
end++;
}
_finish--;
return pos - 1;
}//赋值运算符重载
vector<int>& operator=(vector<int> data)
{
swap(data);
return *this;
}
private:
iterator _begin = nullptr;
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
};
}//test.cpp 文件 （测试功能）
#define _CRT_SECURE_NO_WARNINGS 1
#include "vector.h"
namespace gjk
{
void vector_test1()
{
vector<int> v(10, 1);
v.reserve(100);
v.rsize(10);
cout << v.size() << endl;
cout << v.capacity() << endl;
for (int i = 0; i < 30; i++)
{
v.push_back(20 + i);
cout << v.capacity() << endl;
}
v.pop_back();
v.printf_container(v);
}void vector_test2()
{
vector<int> v1(10, 1);
vector<int> v2(10, 2);v1.swap(v2);
v1.printf_container(v1);
v2.printf_container(v2);
}void vector_test3()
{
vector<int> v(10, 1);
vector<int>::iterator it = v.insert(v.begin() + 2, 4);
vector<int>::iterator it1 = v.erase(v.begin() + 2);
(*it) += 100;
(*it1) += 50;cout << *it1 << endl;
cout << *it << endl;
v.printf_container(v);
}void vector_test4()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
vector<int> v2(v1.begin(),v1.end());vector<int> v3(10, 1);
vector<int> v4(v3);v1 = v3;
v1.printf_container(v1);
v3.printf_container(v3);
v2.printf_container(v2);
v4.printf_container(v4);
}
}int main()
{
//gjk::vector_test1();
//gjk::vector_test2();
//gjk::vector_test3();
gjk::vector_test4();return 0;
}