1. vector的介绍
点击查看—>[vector的文档介绍]
（1）vector是表示可变大小数组的序列容器。
（2）就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
（3）本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。
（4） vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
（5） 因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。
（6）与其它动态序列容器相比（deques, lists and forward_lists）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起lists和forward_lists统一的迭代器和引用更好。
2.STL—vector的使用
2.1 vector的构造接口
vector的三种访问方式：
方法一：
#include<iostream>
#include<vector>
using namespace std;
void main()
{
vector<int> iv1;
vector<int> iv2(10,5);
for (const auto &e : iv2)
{
cout << e << " ";
}
cout << endl;
}
方法二：
#include<iostream>
#include<vector>
using namespace std;
void main()
{
vector<int> iv1;
vector<int> iv2(10,5);
vector<int>::iterator it = iv2.begin();
//auto it = iv2.begin();
while (it != iv2.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
方法三：
#include<iostream>
#include<vector>
using namespace std;
void main()
{
vector<int> iv1;
vector<int> iv2(10,5);
for (int i = 0; i < iv2.size(); ++i)
{
cout << iv2[i] << " ";
}
cout << endl;
}
如上几个函数接口的使用如下：
（1）构造并初始化n个val
#include<iostream>
#include<vector>
using namespace std;
void main()
{
vector<int> iv(10, 5);
for (const auto &e : iv)
{
cout << e << " ";
}
cout << endl;
}
（2）使用迭代器进行初始化构造
#include<iostream>
#include<vector>
using namespace std;
void main()
{
int arr[] = {
1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int n = sizeof(arr) / sizeof(arr[0]);
vector<int> iv(arr, arr+n);
for (const auto &e : iv)
{
cout << e << " ";
}
cout << endl;
vector<int> iv1(iv.begin(), iv.end());
for (const auto &e : iv1)
{
cout << e << " ";
}
cout << endl;
}
（3）拷贝构造
#include<iostream>
#include<vector>
using namespace std;
void main()
{
int arr[] = {
1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int n = sizeof(arr) / sizeof(arr[0]);
vector<int> iv(arr, arr + n);
for (const auto &e : iv)
{
cout << e << " ";
}
cout << endl;
//拷贝构造
vector<int> iv1(iv);
for (const auto &e : iv)
{
cout << e << " ";
}
cout << endl;
}
（4）对向量进行初始化(只有C++11支持)
#include<iostream>
#include<vector>
using namespace std;
void main()
{
vector<int> iv{
1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
for (const auto &e : iv)
{
cout << e << " ";
}
cout << endl;
}
2.2 vector iterator 的使用
使用如下：
#include<iostream>
#include<vector>
using namespace std;
void main()
{
vector<int> vec{
1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
vector<int>::iterator it = vec.begin();
while (it != vec.end())
{
cout << *it << " ";
++it;
}
cout << endl;
vector<int>::reverse_iterator rit = vec.rbegin();
while (rit != vec.rend())
{
cout << *rit << " ";
++rit;
}
cout << endl;
}
2.3 vector空间增长问题
- capacity的代码在vs下是按1.5倍增长，在VC6.0下是按2倍增长的
如下是在vs下的测试：
void main()
{
vector<int> vec;
cout << "size = " << vec.size() << endl;
cout << "capacity = " << vec.capacity() << endl;
vec.push_back(1);
cout << "size = " << vec.size() << endl;
cout << "capacity = " << vec.capacity() << endl;
vec.push_back(2);
cout << "size = " << vec.size() << endl;
cout << "capacity = " << vec.capacity() << endl;
vec.push_back(3);
cout << "size = " << vec.size() << endl;
cout << "capacity = " << vec.capacity() << endl;
vec.push_back(4);
cout << "size = " << vec.size() << endl;
cout << "capacity = " << vec.capacity() << endl;
vec.push_back(5);
cout << "size = " << vec.size() << endl;
cout << "capacity = " << vec.capacity() << endl;
vec.push_back(6);
cout << "size = " << vec.size() << endl;
cout << "capacity = " << vec.capacity() << endl;
vec.push_back(7);
cout << "size = " << vec.size() << endl;
cout << "capacity = " << vec.capacity() << endl;
}
- resize在开辟空间的同时还会进行初始化，只针对size修改，但是，空间不足就得扩容，所以会影响capacity，调大会扩容(size和capacity都会变大)，调小只会改变size的大小，capacity不会改变
验证如下：
void main()
{
vector<int> vec;
vec.push_back(1);
cout << "size = " << vec.size() << endl;
cout << "capacity = " << vec.capacity() << endl;
vec.resize(100);
cout << "size = " << vec.size() << endl;
cout << "capacity = " << vec.capacity() << endl;
vec.resize(10);
cout << "size = " << vec.size() << endl;
cout << "capacity = " << vec.capacity() << endl;
}
- reserve 只针对 capacity 修改，负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题，调小容量不会变
验证如下：
如下代码运行起来需要增容很多次，如下图所示：
void main()
{
vector<int> vec;
for (int i = 0; i < 100;++i)
{
vec.push_back(1);
cout << "size = " << vec.size() << endl;
cout << "capacity = " << vec.capacity() << endl;
}
}
而当我们知道需要多大的容量后，我们可以提前预留足够的容量，如下所示
void main()
{
vector<int> vec;
vec.reserve(100);
for (int i = 0; i < 100;++i)
{
vec.push_back(1);
cout << "size = " << vec.size() << endl;
cout << "capacity = " << vec.capacity() << endl;
}
}
2.4 vector 的增删查改交换接口
使用如下：
增删查改
void main()
{
vector<int> vec;
//尾插
vec.push_back(1);
vec.push_back(2);
vec.push_back(3);
vec.push_back(4);
vec.push_back(5);
vec.push_back(6);
vec.push_back(7);
vec.push_back(8);
//尾删
vec.pop_back();
//查找
vector<int>::iterator pos = find(vec.begin(), vec.end(), 2);
//找到之后修改
*pos = 99;
//在pos之前插入
vec.insert(pos, 321);
vector<int>::iterator it = vec.begin();
while (it != vec.end())
{
cout << *it << " ";
++it;
}
cout << endl;
//删除pos位置的值
pos = find(vec.begin(), vec.end(), 6);
vec.erase(pos);
it = vec.begin();
while (it != vec.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
交换两个vector的数据空间
void main()
{
vector<int>vec1{
1, 2, 3, 4, 5 };
vector<int>vec2{
6,7,8,9,10};
vector<int>::iterator it = vec1.begin();
while (it != vec1.end())
{
cout << *it << " ";
++it;
}
cout << endl;
vector<int>::iterator pit = vec2.begin();
while (pit != vec2.end())
{
cout << *pit << " ";
++pit;
}
cout << endl;
//交换两个vector的数据空间
vec1.swap(vec2);
it = vec1.begin();
while (it != vec1.end())
{
cout << *it << " ";
++it;
}
cout << endl;
pit = vec2.begin();
while (pit != vec2.end())
{
cout << *pit << " ";
++pit;
}
cout << endl;
}
operator[ ] ,向量也可以像数组一样访问，因为底层重载了[ ]
void main()
{
vector<int> vec{
1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
for (int i = 0; i < vec.size(); ++i)
{
cout << vec[i] << " ";
}
cout << endl;
}
3. vector 迭代器失效问题
迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如：vector的迭代器就是原生态指针T*。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃)。
3.1 对于vector可能引起迭代器失效的操作
（1）会引起其底层空间改变的操作(涉及到扩容的方法)，都有可能使迭代器失效；比如：resize，reserve，insert,assgin，push_back等
图解如下：
先让一个it迭代器指向vec的第一个元素，然后给vec赋值100个6，此时必会扩容，扩容后再对原迭代器 it 进行操作，就会出错，代码验证如下：
void main()
{
vector<int> vec{
1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
//it迭代器指向vec的第一个元素
vector<int>::iterator it = vec.begin();
//给vec赋值100个6
//此时必会扩容
vec.assign(100, 6);
//扩容后在对原迭代器操作
while (it != vec.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
（2）指定位置元素的删除操作——erase
首先我们来看一下如下代码：
很显然，在VS平台下此代码并不能正常运行，erase删除pos位置元素后，pos位置之后的元素会往前搬移(，因为vector中元素是连续存储的，相当于迭代器删除pos位置的数据后，会向后移)，没有导致底层空间的改变，理论上迭代器应该不会失效(内存角度)，但是：如果pos刚好是最后一个元素，删完之后pos刚好在end的位置，而end位置是没有元素的，那么pos就失效了。因此删除vector中任意位置上的元素，VS就认为该迭代器失效了(如上图所示迭代器迭代8，将8删除后，迭代器不能再访问8，所以认为迭代器失效(逻辑角度))，但在VC6.0上可以正常运行
图解如下：
【例题】以下代码的功能是删除vector中所有的偶数，请问代码是正确的吗？
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> v{
1, 2, 3, 4 };
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
//删除之后迭代器失效，不能在对此迭代器操作
v.erase(it);
++it;
}
return 0;
}
很显然此代码是有错误的，erase()函数删除it迭代器指向位置的与元素后迭代器将失效，不能再对迭代器进行操作
修改后的代码如下：
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> v{
1, 2, 3, 4 };
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
it = v.erase(it);
}
else
{
++it;
}
}
it = v.begin();
while (it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
return 0;
}
迭代器失效的解决办法：在使用前对迭代器重新赋值
4. vector 的模拟实现
#include<iostream>
using namespace std;
namespace myvector
{
template<class _Ty>
class vector
{
public:
typedef _Ty* iterator;
typedef const _Ty* const_iterator;//常迭代器
public:
//构造方法
vector() :_start(nullptr), _finish(nullptr), _end(nullptr)
{
}
vector(size_t n, const _Ty &val = _Ty()) :_start(nullptr), _finish(nullptr), _end(nullptr)
{
insert(begin(), n, val);
}
vector(_Ty *first, _Ty *last) :_start(nullptr), _finish(nullptr), _end(nullptr)
{
/*insert(begin(), first, last);*/
while (first != last)
{
push_back(*first);
++first;
}
}
//拷贝构造
vector(const vector<int> &v) :_start(nullptr), _finish(nullptr), _end(nullptr)
{
reserve(v.capacity());
//insert(begin(), v.begin(), v.end());
auto it = v.begin();
while (it != v.end())
{
push_back(*it++);
}
}
//赋值
vector &operator=(const vector<_Ty> &v)
{
vector<_Ty> tem(v);
swap(tem);
return *this;
}
//析构
~vector()
{
delete[] _start;
_start = _finish = _end = nullptr;
}
public:
//求元素个数
size_t size()const
{
return _finish - _start;
}
//求容量大小
size_t capacity()const
{
return _end - _start;
}
//判空
bool empty()const
{
return (size() == 0);
}
public:
//预留空间
void reserve(size_t n)
{
//大于capacity扩容，小于capacity不变
if (n > capacity())
{
int old_size = size();
_Ty* new_base = new _Ty[n];
//若原始空间不为空，则需要拷贝原始数据到新的空间
if (_start)
{
memcpy(new_base, _start, sizeof(_Ty)*old_size);
delete[] _start;
}
_start = new_base;
_finish = _start + old_size;
_end = _start + n;
}
}
public:
//在pos位置插入
iterator insert(iterator pos, const _Ty& x)
{
int old_sz = size();
int old_capa = capacity();
//确保pos位置有效
//防止pos给空
if (pos == nullptr)
{
pos = _start;
}
if (old_sz + 1 > old_capa)
{
//防止迭代器失效，找不到迭代器之前指向的位置
size_t it_pos = pos - _start;
//2倍扩容
size_t new_capa = old_capa * 2;
if (new_capa == 0)
{
new_capa = 1;
}
reserve(new_capa);
//重新给_p赋值,更新迭代器
pos = _start + it_pos;
}
//移动数据
iterator tail = _finish++;
while (tail != pos)
{
*tail = *(tail - 1);
--tail;
}
*pos = x;
return pos;
}
//在pos位置插入n个x
void insert(iterator pos, size_t n, const _Ty& x)
{
while (n--)
{
insert(pos, x);
}
}
//在pos位置插入一个区间
void insert(iterator pos, const_iterator first, const_iterator last)
{
while (first != last)
{
insert(pos, *first);
++first;
}
}
public:
//尾插
void push_back(const _Ty & x)
{
insert(end(), x);
}
public:
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const iterator begin()const
{
return _start;
}
const iterator end()const
{
return _finish;
}
public:
//重载[ ]
_Ty &operator[](int i)
{
return _start[i];
}
const _Ty &operator[](int i)const
{
return _start[i];
}
//at()函数，要对下标的有效性进行检测
_Ty &at(int i)
{
assert(i >= 0 && i < size());
return _start[i];
}
const _Ty &at(int i)const
{
assert(i >= 0 && i < size());
return _start[i];
}
//resize()调整size大小
void resize(size_t n, const _Ty& x = _Ty())
{
if (n <= size())
{
_finish = _start + n;
}
//调整的大小大于容量，就要扩容
if (n > capacity())
{
reserve(n);
}
//保留已有元素的末尾位置
iterator tail = _finish;
//移动_finish
_finish = _start + n;
//将已有元素后置为x
while (tail < _finish)
{
*tail = x;
++tail;
}
}
//交换两个向量
void swap(vector & str)
{
std::swap(_start, str._start);
std::swap(_finish, str._finish);
std::swap(_end, str._end);
}
private:
iterator _start;
iterator _finish;
iterator _end;
};
}
void main()
{
int arr[] = {
1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
//myvector::vector<int> vec(10,6);
myvector::vector<int> vec(arr, arr + 5);
/*cout << "size = " << vec.size() << endl;
cout << "capacity = " << vec.capacity() << endl;*/
myvector::vector<int> vec1(arr+5,arr+10);
/*vec.swap(vec1);*/
vec = vec1;
myvector::vector<int>::iterator it = vec.begin();
while (it != vec.end())
{
cout << *it << " ";
++it;
}
cout << endl;
myvector::vector<int>::iterator pit = vec1.begin();
while (pit != vec1.end())
{
cout << *pit << " ";
++pit;
}
cout << endl;
//vec.reserve(10);
//vec.insert(vec.begin(), 1);
/*vec.push_back(1);
vec.push_back(2);
vec.push_back(3);*/
//vec.insert(vec.end(), 10, 5);
//myvector::vector<int>::iterator it = vec1.begin();
//while (it != vec1.end())
//{
// cout << *it << " ";
// ++it;
//}
//cout << endl;
//cout << "size = " << vec.size() << endl;
//cout << "capacity = " << vec.capacity() << endl;
//cout << "size = " << vec.size() << endl;
//cout << "capacity = " << vec.capacity() << endl;
//for (int i = 0; i < vec.size(); i++)
//{
// cout << vec[i] << " ";
//}
//cout << endl;
//vec.resize(15,6);
//for (int i = 0; i < vec.size(); i++)
//{
// cout << vec.at(i) << " ";
//}
//cout << endl;
//cout << "size = " << vec.size() << endl;
//cout << "capacity = " << vec.capacity() << endl;
}
转载：https://blog.csdn.net/weixin_50886514/article/details/116450704
查看评论