文章目录
vector的介绍
vector介绍
1.vector表示可变大小的数组容器
2.vector同数组一样，采用连续的内存空间存储数组，也能通过下标来访问数据。但vector的大小是可以动态改变的。
3.当vector要插入一个新元素时，vector会开辟一段新的存储空间，并将原空间的元素转移到新空间。
4. vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
5. 与其它动态序列容器相比（deque, list and forward_list）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效（连续存储）。对于其它不在末尾的删除和插入操作，效率更低。比起list和forward_list统一的迭代器和引用更好。
vector的定义
| (constructor)构造函数声明 | 接口说明 |
|---|---|
| vector() | 无参构造 |
| vector（size_type n, const value_type& val = value_type()） | 构造并初始化n个val |
| vector (const vector& x) | 拷贝构造 |
| vector (InputIterator first, InputIterator last) | 使用迭代器进行初始化构造 |
vector iterator 的使用
| iterator的使用 | 接口说明 |
|---|---|
| begin + end | 获取第一个数据位置的iterator/const_iterator， 获取最后一个数据的下一个位置的iterator/const_iterator |
| rbegin + rend | 获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的reverse_iterator |
vector 空间增长问题
| 容量空间 | 接口说明 |
|---|---|
| size | 获取数据个数 |
| capacity | 获取容量大小 |
| empty | 判断是否为空 |
| resize | 改变vector的size |
| reserve | 改变vector的capacity |
1.容量（capacity）在vs下是1.5倍增长的，在g++下是2倍增长的。
2.reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。
3.resize在开空间的同时还会进行初始化，影响size。
vector的增删查改
| vector增删查改 | 接口说明 |
|---|---|
| push_back（重点） | 尾插 |
| pop_back （重点） | 尾删 |
| find | 查找。（注意这个是算法模块实现，不是vector的成员接口） |
| insert | 在position之前插入val |
| erase | 删除position位置的数据 |
| swap | 交换两个vector的数据空间 |
| operator[] （重点） | 像数组一样访问 |
vector的模拟实现
创建vector类和成员变量
namespace bit
{
template<class T>
class vector
{
public:
// Vector的迭代器是一个原生指针
typedef T* iterator；
typedef const T* const_iterator；
private:
iterator _start=nullptr; // 指向数据块的开始
iterator _finish = nullptr; // 指向有效数据的尾
iterator _endOfStorage = nullptr; // 指向存储容量的尾
};
}
}
iterator迭代器
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator cbegin()
{
return _finish;
}
const_iterator cend() const
{
return _start;
}
范围for
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
// 使用范围for循环遍历vector
for (const auto& element : vec) {
std::cout << element << ' ';
}
return 0;
}
范围for利用了迭代器的原理来遍历容器（如vector、list、array等）中的元素。范围for循环提供了一种更加简洁和直观的方式来遍历容器，而无需显式地管理迭代器。使用begin()和end()成员函数来获取容器的起始和结束位置，然后在一个循环中递增迭代器，直到它等于结束迭代器为止。在每次迭代中，它都会解引用迭代器以获取当前元素的值。
构造函数
vector()
{}//声明时给了缺省值，初始化列表会自动在声明处取
vector(int n, const T& value = T())
{
resize(n, value);
}
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
++first;
}
}
vector(const vector<T>& v)
{
reserve(v.capacity());
for (auto& e : v)
{
push_back(e);
}
}
赋值、析构
vector<T>& operator= (vector<T> v)
{
swap(v);
return *this;
}//传值返回，交换后原来的v不受影响
~vector()
{
delete[] _start;
_start = _finish = _endOfStorage = nullptr;
}
空间容量
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _endOfstorage - _start;
}
void reserve(size_t n)
{
if (n > capacity())
{
size_t old = size();
T* tmp = new T[n];
if (_start)
{
for (size_t i = 0; i < old; i++)
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + old;
_endOfStorage = _start + n;
}
}//只有当n大于容量时扩容，扩容开辟一个新的空间，将原来的数据转移到新空间内，
//old确定旧空间的大小，便于找到新空间的_finish的位置，当n小于容量时，
//并不会发生缩容！！！
void resize(size_t n, const T& value = T())
{
if (n > size())
{
reserve(n);
while (_finish < _start + n)
{
*_finish = value;
++_finish;
}
}
else
{
_finish = _start + n;
}
}
resize和reserve的区别
resize关注的是vector当前包含多少个元素，即其逻辑大小。
reserve关注的是vector内部为存储元素而预先分配的内存量，即其容量。
reserve仅仅改变vector的容量，并不改变其大小（即不添加或删除元素）。
如果你知道将要向vector中添加大量元素，可以先使用reserve来避免频繁的重新分配。
如果你想立即拥有特定数量的元素（可能是一些默认值），可以使用resize。
虽然resize在必要时能够开辟新的内存空间，但reserve允许你更加主动地管理vector的内存分配，以优化性能。
下标操作符重载
T& operator[](size_t pos)
{
assert(pos < size());
return *(_start + pos);
}
const T& operator[](size_t pos)const
{
assert(pos < size());
return *(_start + pos);
}
插入删除交换
void push_back(const T& x)
{
if (_finish == _endOfStorage)
{
size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
reserve(newcapacity);
}
*_finish = x;
++_finish;
}//先看容量是否充足，不够先扩容，再插入。
void pop_back()
{
assert(size() > 0);
--_finish;
}
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endOfstorage, v._endOfstorage);
}
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start && pos <= _finish);
if (_finish == _endOfStorage)
{
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = x;
++_finish;
return pos;
}//返回插入元素的迭代器
iterator erase(Iterator pos)
{
assert(pos >= _start && pos < _finish);
iterator it = pos + 1;
while (it < _finish)
{
*(it - 1) = *it;
++it;
}
_finish--;
return pos;
}//这里删除一个数是利用后面的元素覆盖前面的元素，返回被删元素位置的迭代器
vector深度剖析
vector迭代器失效问题
迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如：vector的迭代器就是原生态指针T* 。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃)。
1.底层空间改变
会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、push_back等。
vector扩容时开辟了新的空间，原来的旧空间被释放掉了，而迭代器还是使用的释放前的旧空间，对释放的空间进行实际操作就会引起代码运行时崩溃。
解决方式：在以上操作完成之后，如果想要继续通过迭代器操作vector中的元素，只需给it（迭代器）重新赋值即可。
2.指定位置元素的删除操作–erase
#include <iostream>
using namespace std;
#include <vector>
int main()
{
int a[] = { 1, 2, 3, 4 };
vector<int> v(a, a + sizeof(a) / sizeof(int));
// 使用find查找3所在位置的iterator
vector<int>::iterator pos = find(v.begin(), v.end(), 3);
// 删除pos位置的数据，导致pos迭代器失效。
v.erase(pos);
cout << *pos << endl; // 此处会导致非法访问
return 0;
}
erase返回被删元素位置的迭代器。当被删元素是最后一位元素时，最后一位被后面的_end覆盖，而_end位置是没有元素的，所以pos就失效了。
与vector类似，string在插入+扩容操作+erase之后，迭代器也会失效。
使用memcpy拷贝问题
假设模拟实现的vector中的reserve接口中，使用memcpy进行的拷贝，以下代码会发生什么问题？
- memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中
- 如果拷贝的是内置类型的元素，memcpy既高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝。
在扩容期间使用memcpy拷贝后，新空间和就空间的str都指向同一块内存空间，当将旧空间的内容转移到新空间后，要释放旧空间，同时释放掉了新空间指向的地址空间，新的_str就指向了一块已经释放的空间。
结论：如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃。
动态二维数组的理解
bit::vector<bit::vector> vv(n);
和a[i][j];
a[i][j]的调用本质是指针的解引用
可以写成*(*(a+i)+j)
而vv[i][j]是2个函数的调用
可以写成vv.operator[]（i）.operator[]（j）