一：vector的介绍及使用
1.1vector的介绍
1.vector时可变大小数组的序列容器。
2.类似于数组，vector也采用连续储存空间来储存元素。vector支持下标访问元素。
3.vector使用动态分配数组来储存他的元素。当新的元素插入的时候，这个数组需要被重新分配大小。
4.vector分配空间策略：vector会分配一些额外的空间来适应可能的增长，因为储存空间比实际需要的存储空间更大。重新分配都应该是对数增长的间隔的大小，以至于在末尾插入一个新的元素的时间复杂度往往为O（1）.
5.vector占用了更多的储存空间，为了获得管理储存空间的能力，以一种有效的方式动态增长。
6.与其他动态序列容器相比，vector在访问元素的时候更加高效，在末尾添加或删除元素相对高效，但在中间位置进行相关操作，成本稍高。
1.2vector使用
1.2.1vector定义
vector一.vector的介绍及使用1.1vector的介绍1.vector时可变大小数组的序列容器。 2.类似于数组，vector也采用连续储存空间来储存元素。vector支持下标访问元素。 3.vector使用动态分配数组来储存他的元素。当新的元素插入的时候，这个数组需要被重新分配大小。 4.vector分配空间策略：vector会分配一些额外的空间来适应可能的增长，因为储存空间比实际需要的存储空间更大。重新分配都应该是对数增长的间隔的大小，以至于在末尾插入一个新的元素的时间复杂度往往为O（1）. 5.vector占用了更多的储存空间，为了获得管理储存空间的能力，以一种有效的方式动态增长。 6.与其他动态序列容器相比，vector在访问元素的时候更加高效，在末尾添加或删除元素相对高效，但在中间位置进行相关操作，成本稍高。 1.2vector使用1.2.1vector定义
示例： ? 1.2.2vector iterator 的使用
示例：
? 1.2.3vector空间增长问题
capacity再vs下是1.5倍增长，g++下是2倍增长。
?
? reserve只负责开辟空间。 resize支持开辟空间的同时也会进行初始化，影响size。 可以看得到，前期扩容比较频繁，可以使用reserve进行提前扩容，以提升性能。
?
? 1.2.3vector增删查改
?
? 1.2.4vector迭代器失效问题迭代器的主要作用是让算法能够不关心底层数据结构，其底层实际上是一个指针，或者是针对指针进行了封装。 vector的迭代器就是原生指针T*，迭代器失效就是迭代器底层对应指针所指向的空间被销毁了，使用了一块已经释放的空间。造成的结果就是程序崩溃。 对于vector可能导致迭代器失效的操作有： 1.引起空间底层改变的操作，可能引起迭代器的失效。比如：resize，reserve，insert，assign，push_back。 2. 指定位置元素的删除操作--erase 1.erase的失效都是意义变了，或者不在有效访问数据范围。 2.一般不会使用缩容方案，那么erase的失效，一般不存在野指针的失效。 一般vector删除数据，都不会考虑缩容方案。 缩容方案：size()<capacity()/2时，可以考虑开一个size()大小的空间，拷贝数据，释放旧空间。 缩容的本质是时间换空间。一般设计都不考虑缩容，因为实际关注的大都是时间效率，不关注空间效率，因为现在的硬件设备都比较大，时间储存也比较便宜。 erase(pos)以后pos就失效了，pos的意义变了，但是不同平台下面对于访问pos的反应是不一样的。我们用的时候要小心，统一以失效角度去看待 3. 注意：Linux下，g++编译器对迭代器失效的检测并不是非常严格，处理也没有vs下极端。 g++对于erase迭代器失效检查时就非常的佛系，但在实际场景中，迭代器的意义变了，也会出现各种问题 *补充：vector迭代器失效有2种： 1.扩容，缩容，导致野指针，失效。 2.迭代器指向位置意义变了。 * 系统的越界机制检查。 ---- 不一定能查到。 编译实现机制检查。 ---- 相对靠谱。 二.模拟实现vector部分接口#2.1关于底层的问题##vector本身就是容器，意味着vector本身就必须满足各种类型的变量，即vector要使用模板。 准备阶段： namespace bit
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
*******
private:
iterator _start;
iterator _finish;
iterator _end_of_storage;
}
} 2.2 构造函数无参的默认构造函数只需要将private中的参数设置成nullptr即可 //实现默认构造函数
//无参
vector()
:_start(nullptr)
,_finish(nullptr)
,_end_of_storage(nullptr)
{} 迭代器的方法初始化一段空间采用模板，使得其能够泛型编程 //构造函数，拷贝构造一段空间
template<class InputIterator>
vector(InputIterator first, InputIterator last)
: _start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
while (first != last)
{
push_back(*first);
first++;
}
} 构造并初始化一段空间这个接口并不常用，但是是给构造函数铺路用的 //构造并初始化一段空间
vector(size_t n, T& val = T())//给予一个默认构造函数
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
//预开n个大小的空间
reserve(n);
//插入val
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
} 还需要重载一个（int， T）类型的，因为无法完成类似于vector<int> v(10,2)的初始化。 //构造并初始化一段空间
vector(int n, T& val = T())//给予一个默认构造函数
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
//预开n个大小的空间
reserve(n);
//插入val
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
} 交换函数采用c++库中的swap接口即可，本质上是交换指针 //交换swap函数,本质上是交换指针。
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
} 拷贝构造采取的是现代化写法，编译器自己生成vector后，通过swap函数，交换指针即可 //拷贝构造
vector(const vector<T>& v)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
vector<T> tmp(v.begin(), v.end());
swap(tmp);
} 重载=现代化写法 //重载=
vector<T> operator=(vector<T> v)//这里已经进行了一次拷贝构造了
{
swap(v);
return *this;
} 2.3实现size 和 capacity接口值得注意的是size指的是有效数据的大小 capacity指的是可以储存的有效数据的大小 因为类型没有规定，所以要单独使用接口来获取 //大小
size_t size()const
{
return _finish - _start;
}
//容量
size_t capacity()
{
return _end_of_storage - _start;
} 2.4迭代器部分接口实现主要实现迭代器的begin 和 end 接口，保证正向迭代器能够正常使用，至于++不需要重载，因为 本身底层就是使用的“迭代器”，指针++可以跳过一个类型的长度。 <u>迭代器要满足const && 非const类型的指针都能够使用。<u> //迭代器返回begin end
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin()const
{
return _start;
}
const_iterator end()const
{
return _finish;
} 2.5模拟实现reservereserve就是进行扩容的函数接口 //实现扩容接口reverse
//上面提及扩容会导致迭代器失效，这里就是因为扩容销毁了更改了原有的指针指向
//导致pos指针成了野指针，所以要更新pos指针。
/***更新方法：记录pos和_start之间的相对距离，以便更新pos***/
void reserve(size_t n)
{
size_t sz = size();
//避免无端的申请扩容
if (n > capacity())
{
T* tmp = new T[n];
//判断数据是否需要拷贝
if (_start)
{
//memcpy(tmp, _start, size() * sizeof(T));
//memcpy是浅拷贝，会导致内存泄漏的风险。
? ? ? ? ? ? ? ? ? ?for(size_t i = 0;i<size(),i++)
? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? tmp[i] = _start[i];
? ? ? ? ? ? ? ? ? }
delete[] _start;
}
//更新private数据
_start = tmp;
}
_finish = _start + sz;
_end_of_storage = _start + n;
} 2.5模拟实现resize接口string提及过resize可以更改capacity和size，并且还能进行相应的初始化，vector也一样。
void resize(size_t n, T val = T())//单参数支持隐式类型的转换
{
//n > capacity
if (n > capacity)
{
reserve(n);
}
else
{
//n>size() && n<capacity
if (n > size())
{
while (_finish < _end_of_storage)
{
*_finish = val;
_finish++;
}
}
else
{
_finish = _start + n;
}
}
} 2.6模拟实现push_back && pop_back##push_back是尾插，尾插就需要考虑扩容和越界访问的问题 pop_back是尾删，要考虑越界访问的问题。 //插入push_back
void push_back(const T& val)
{
//判断是否需要扩容
if (_finish == _end_of_storage)
{
size_t newcapacity = capacity() == 0 ? 4 :capacity()* 2;
reserve(newcapacity);
}
//插入数据
*_finish = val;
_finish++;
}
?
//pop_back
void pop_back()
{
assert(_finish > _start);
--_finish;
} 2.7重载[]vector是在堆上开辟的一段连续的空间，用于储存数据的容器，所以它可以支持类似于数组的下标直接访问的优势，重载[]是必不可少的。 //重载[]
//为了减少拷贝构造，可以引用返回。
T& operator[](const size_t pos)
{
assert(pos < size());
?
return *(_start + pos);
}
//const版本
const T& operator[](const size_t pos)const
{
assert(pos < size());
?
return _start[pos];
} 2.8模拟实现insert && ersae对于insert要考虑： 1.给定的pos是否合法？ 2.插入是否会需要扩容？ 3.pos指针是否会失效，导致迭代器失效？ 4.挪动数据是否会出现问题？ 5.是否需要更新基底？ 对于earse要考虑： *1.给定的pos是否合法？ 2.是否存在越界删除？ 3.是否需要更新基地？* //模拟insert
iterator insert(iterator pos, const T& val)
{
//检查pos是否合法
assert(pos>=_start && pos<=_finish);
//判断是否需要扩容
if (_finish == _end_of_storage)
{
size_t n = pos - _start;
?
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
?
pos = _start + n;
}
//开始挪动数据
//扩容完成后，pos的位置会指向不明确，会使得迭代器失效。需要单独处理pos.
auto end = _finish -1;
while (end >= pos)
{
*(end + 1) = *end;
end--;
}
*pos = val;
_finish++;
return pos;
}
iterator erase(iterator pos)
{
//判断pos是否合法
assert(pos >= _start && pos <= _finish);
auto it = pos;
while (it < _finish)
{
*it = *(it + 1);
it++;
}
--_finish;
return pos;
} 2.9清屏函数清屏：将有效数据删除 void clear()
{
_start = _finish;
} 3.0资源管理//资源管理
~vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
} vector完结。 | ||||||||||||||||||||||||||||||||||||||||||||
