前言

本节将要介绍STL容器中的vector的常用接口函数，简单模拟实现一下vector。

---

1. vector 是什么

vector是可变大小的顺序容器，类似于数组，存放元素的空间是连续的，所以可以实现类似于数组的随机访问；
相对于其他容器deque、list、forward_list，vector的优势：

• 尾插和尾删操作相对高效，访问元素时也是相当高效；

劣势：

• 头插和中间插入元素、头删和中间删除元素的操作由于涉及到大量元素的移动，效率很低；
• vector的空间可以动态的开辟，开辟空间是存在系统资源的消耗的，所以vector不是每新增一个元素就重新开辟空间，而是再空间满时开辟适当的空间，具体开辟多少空间取决于不同版本实现者的考虑。虽然每次开辟的空间没有具体要求，但是需要保证开辟空间是以对数间隔进行的，以便于每次在结束位置插入数据时vector能提供均摊的常数时间复杂度；
• 与string的元素类型是char不同，vector是一个类模板，这意味着它可以接受任意类型的参数，存放任意类型的元素；

---

2. 见见vector的常用接口函数吧

构造函数

无参构造函数

函数声明

vector();

例子

vector<int> v;

注意不能写成vector<int> v();，定义初始化时，如果是无参构造或是全缺省的构造不加括号()，否则编译器会把这句代码识别成无参、返回类型是vector<int>的函数声明；只有这句代码并不会报错，但当你把v当做vector<int>类型的变量去使用时就会出现问题，因为编译器认为v是一个函数指针；

使用n个val构造

声明

vector(size_t n, const value_type& val = value_type());

eg

vector<char> v1(3, 'x'); // 结果为 xxx，没有'\0'
vector<int> v2(3, 7) 	 // 结果为 777

拷贝构造

声明

vector (const vector& x);

例子

// 5个9构造vector<int>类型对象 v1
vector<int> v1(5, 9);

vector<int> v2(v1);

使用迭代器范围构造

声明
两个参数first和last都是迭代器类型，且该函数时函数模板，迭代器类型可以指定，即可以使用其他顺序容器的迭代器构造vector；

template <class InputIterator>
 vector (InputIterator first, InputIterator last);

eg

vector<int> v1(5, 6); // 66666

vector<int>v2(v1.begin(), v1,begin() + 3); // 666

初始化形参列表构造

声明
initializer_list是一个类模板，使用由大括号括起来的以逗号分隔的元素构造initializer_list对象；

vector (initializer_list<value_type> il);

eg

vector<int> v1{1,2,3,4,5}; // 1 2 3 4 5
vector<int> v2 = {3,4,5,6,7); // 3 4 5 6 7

---

析构函数

声明
在vector对象销毁之前调用，释放vector对象申请的资源；

~vector();

赋值运算符重载函数

声明

vector& operator= (const vector& x);

eg
直接vector v2 = v1; 使用会被编译器当做定义初始化而调用拷贝构造函数，而不是赋值运算符重载函数；

vector<int> v1(5, 6); // 66666
vector<int> v2;

v2 = v1; // 66666

元素访问

[]运算符重载函数访问

声明
[]运算符重载函数会在内部对传入的坐标参数进行严格检查，超出有效坐标范围将会报错，这与系统的抽查不同；
[]运算符重载函数既需要满足读也要满足写，所以实现了非const版本和const版本；

reference operator[] (size_type n);
const_reference operator[] (size_type n) const;

eg

非const

vector<int> v{ 1,2,3,4,5 };
for (int i = 0; i < v.size(); ++i) {
    v[i]++;
    cout << v[i] << " "; // 结果为2 3 4 5 6
}
cout << endl;

const

const vector<int> v{ 1,2,3,4,5 };
for (int i = 0; i < v.size(); ++i) {
    //v[i]++; 不能修改const对象成员
    cout << v[i] << " "; // 结果为1 2 3 4 5
}
cout << endl;

at函数访问

声明
at也会对传入的坐标参数进行判断，超出坐标范围后会抛异常，而不是报错；

reference at (size_type n);
const_reference at (size_type n) const;

eg

非const

vector<int> v{ 1,2,3,4,5 };
for (int i = 0; i < v.size(); ++i) {
    v.at(i)++;
    cout << v.at(i) << " ";
}
cout << endl;

const

const vector<int> v{ 1,2,3,4,5 };
for (int i = 0; i < v.size(); ++i) {
    cout << v.at(i) << " ";
}
cout << endl;

front函数

声明
返回第一个元素的引用

reference front();
const_reference front() const;

eg

vector<int> v{1,2,3,4};
v.first(); // 结果为 1

back函数

声明
返回最后一个元素的引用

reference back();
const_reference back() const;

eg

vector<int> v{1,2,3};
v.back(); // 结果为 3

迭代器相关

迭代器是像指针一样的类型，使用时需要解引用*

正向迭代器

定义
包括非const和const迭代器；

返回vector对象内元素起始位置的迭代器

iterator begin() noexcept;
const_iterator begin() const noexcept;

返回vector对象内元素结束位置的下一个位置的迭代器

iterator end() noexcept;
const_iterator end() const noexcept;

eg

vector<int> v1{ 1,2,3,4,5 };
vector<int>::iterator it = v1.begin();
while (it != v1.end()) {
    cout << *it << " "; // 结果为 1 2 3 4 5
    it++;
}
cout << endl;

const vector<int> v2{ 6,7,8,9,0 };
vector<int>::const_iterator cit = v2.begin();
while (cit != v2.end()) {
    cout << *cit << " "; // 结果为6 7 8 9 0
    cit++;
}
cout << endl;

反向迭代器

定义

返回vector对象内最后一个元素的所在位置的迭代器

reverse_iterator rbegin() noexcept;
const_reverse_iterator rbegin() const noexcept;

返回vector对象内第一个位置的元素的前一个理论位置的迭代器

reverse_iterator rend() noexcept;
const_reverse_iterator rend() const noexcept;

eg

容量相关

size函数

声明
返回vector对象的元素个数

size_type size() const noexcept;

eg

vector<int> v{1,2,3,4,5};
v.size(); // 结果为 5

capacity函数

声明
返回vector对象的引用

size_type capacity() const noexcept;

eg

vector<int> v{1,2,3,4,5};
v.capacity(); // 结果为 5

empty函数

声明
判断vector对象是否为空，是则返回true；否则返回false

bool empty() const noexcept;

eg

vector<int> v1; // 空
vector<int> v2(2, 3); // 33

v1.empty(); // true
v2.empty(); // false

reserve函数

声明
参数size_type n，表示要申请开辟的容量大小；
改变vector对象的容量capacity，当n小于等于当前vector对象的容量capacity时，reserve函数什么也不做；
只有当n大于vector对象的容量时，reserve函数才会向系统申请开辟空间；即reserve函数一般只进行扩容处理，不缩容；

void reserve (size_type n);

eg

vector<int> v{ 1,2,3,4,5 }; // capacity为 5

v.reserve(3); // capacity为 5

v.reserve(5); // capacity为 5

v.reserve(10); // capacity为 10

resize函数

声明
参数size_t n表示vector对象有效元素的个数；
如果n小于vector原有的size，相当于删除元素直到size为n；
如果n等于vector原有size就什么也不做；
如果n大于vector原有size且小于等于vector的原有capacity，相当于尾插元素直到size为n；
如果n大于vector原有的capacity，相当于先扩容使容量增大，再尾插元素直到size为n；

void resize (size_type n);
void resize (size_type n, const value_type& val);

eg

vector<int> v2{1,2,3,4,5};
	v2.reserve(10);
	cout << v2.size() << endl;
	cout << v2.capacity() << endl;
	print(v2);

	v2.resize(3);
	cout << v2.size() << endl;
	cout << v2.capacity() << endl;
	print(v2);

	v2.resize(8, 1);
	cout << v2.size() << endl;
	cout << v2.capacity() << endl;
	print(v2);

	v2.resize(15, 2);
	cout << v2.size() << endl;
	cout << v2.capacity() << endl;
	print(v2);

增删查改相关

push_back函数

声明
在vector对象内最后一个元素的末尾增加一个元素，增加的元素参数val的拷贝；

void push_back (const value_type& val);
void push_back (value_type&& val);

eg

vector<int> v;
for (int i = 0; i < 5; ++i) {
    v.push_back(i);
}
// v的内容为 0 1 2 3 4 

pop_back

声明
删除vecrot的最后一个元素，但是debug模式下，当vector为空时调用pop_back尾删元素时程序会出错；

void push_back (const value_type& val);
void push_back (value_type&& val);

eg

vector<int> v;

for (int i = 0; i < 5; ++i) {
    v.push_back(i);
}
// v的内容为 0 1 2 3 4 
for (int i = 0; i < 5; ++i) {
    v.pop_back();
}
// v的内容为 空

assign函数

声明
使用参数迭代器first和last表示元素的起始位置和结束位置；
使用迭代器范围内的元素为vector赋值，同时会把vector原先的内容去除；
这个范围是左闭右开的区间[first, last]；

// range (1)
template <class InputIterator>
void assign (InputIterator first, InputIterator last);

eg

vector<int> v1{ 1,2,3,4 };
vector<int> v2;
v2.assign(v1.begin(), v1.end()); // 结果为 1 2 3 4

声明
使用size_t类型的n个value_type类型的val为vector赋值；

// fill (2)	
void assign (size_type n, const value_type& val);

eg

vector<int> v1{ 1,2,3,4 };
vector<int> v2;
v2.assign(3, 5); // 结果为 555

声明
使用初始化列表对vector对象进行赋值

// initializer list (3)	
void assign (initializer_list<value_type> il);

eg

vector<int> v2;
v2.assign({ 1,2,3,4,5 }); // 结果为 1 2 3 4 5

insert函数

声明
参数const_iterator pos是vector内的元素对应位置的迭代器；
参数const value_type是待插入的值；
在迭代器位置pos之前插入一个元素，该元素是val的拷贝；

// single element (1)
iterator insert (const_iterator pos, const value_type& val);

eg

vector<int> v3{ 1,2,3,4,5 }; 
v3.insert(v3.begin() + 3, 9); // 结果为 1 2 3 9 4 5

声明
参数const_iterator pos是vector内的元素对应位置的迭代器；
参数size_type n是插入元素的个数；
参数const value_type是待插入的值；
在迭代器位置pos之前插入n个元素；

// fill (2)	
iterator insert (const_iterator pos, size_type n, const value_type& val);

eg

vector<int> v3{ 1,2,3,4,5 }; 
v3.insert(v3.begin() + 3, 5，9); // 结果为 1 2 3 9 9 9 9 9 4 5

声明
参数const_iterator pos是vector内的元素对应位置的迭代器；
参数first、last是迭代器范围，first是起始位置，last是结束位置；
在迭代器pos位置之前依次插入[first, last)范围内的所有元素；

// range (3)	
template <class InputIterator>
iterator insert (const_iterator pos, InputIterator first, InputIterator last);

eg

vector<int> v1{ 1,2,3,4,5 };

vector<int> v2{ 1,2,3,4,5 };
v4.insert(v2.begin()+ 4, v1.begin(), v1.begin() + 3); // 结果为 1 2 3 4 1 2 3 5

声明

// initializer list (5)	
iterator insert (const_iterator pos, initializer_list<value_type> il);

eg

vector<int> v{ 1, 2, 3, 4 };
v.insert(v.begin(), { 2, 3 ,3 }); // 结果是 1 2 3 2 3 3 4

erase函数

声明
参数const_iterator pos表示vector内元素所在位置的迭代器；
删除pos位置的元素；

iterator erase (const_iterator pos);

eg

vector<int> v{ 1,2,3,4,5 };
v.erase(v.begin() + 2);

声明
参数first是待删除范围的起始元素的位置；
参数last是待删除范围的最后一个元素的下一个位置；
删除迭代器范围内的所有元素；

iterator erase (const_iterator first, const_iterator last);

eg

vector<int> v{ 1,2,3,4,5 };
v.erase(v1.begin() + 1, v.begin() + 4);

clear函数

声明
清空vector对象，删除所有元素；

void clear() noexcept;

eg

vector<int> v2{ 9, 9, 9, 9, 9 }; // size = 5, capacity = 5

v2.clear(); // size = 0, capacity = 5

swap函数

声明
与另一个vector对象进行内容的交换，也包括size和capacity；

void swap (vector& x);

eg

vector<int> vv1{ 1,2,3,4,5 };   // size=5, capacity=5;
vector<int> vv2{ 6, 6, 6 }; 	// size=3, capacity=3;

vv1.swap(vv2); 
// vv1 -> 内容：6 6 6       size=3, capacity=3; 
// vv2 -> 内容：1 2 3 4 5   size=5, capacity=5

emplace函数

声明
参数pos是vector的元素对应位置的迭代器
参数args是待插入的元素
在pos位置之前插入元素，类似于insert

template <class... Args>
iterator emplace (const_iterator pos, Args&&... args);

eg

vector<int> vvv1{ 1, 2, 3, 4, 5 };
vvv1.emplace(vvv1.begin() + 3, 233); // 1 2 3 233 4 5
vvv1.emplace(vvv1.end(), 1145); 	 // 1 2 3 233 4 5 1145 

非成员函数 - 关系运算符重载函数

==

声明
比较两个vector对象v1, v2的内容是否相同；
比较过程：先比较v1和v2的size是否相等，不相等直接不相等；相等就继续顺序比较二者的元素，如果存在一对不相等的元素就是不相等；元素都相等时才是相等；
不比较二者的cappacity；

template <class T>
bool operator==(const vector<T>& v1, const vector<T>& v2);

eg

vector<int> v1{ 1,2,3,4,5 };
vector<int> v2{ 1,2,3,4,5 };
v1 == v2;		// true
v1.reserve(10);
v1 == v2;       // true
v1.resize(3);
v1 == v2;       // false

!=

声明

template <class T>
bool operator!=(const vector<T>& v1, const vector<T>& v2);

eg

vector<int> v1{ 1,2,3,4,5 };
vector<int> v2{ 1,2,3,4,5 };
v1 != v2;		// false

<

声明

template <class T>
bool operator<(const vector<T>& v1, const vector<T>& v2);

eg

vector<int> v1{ 1,2,3,4,5 };
vector<int> v2{ 1,2,3,4,5 };
v1 < v2; // false

<=

声明

template <class T>
bool operator<=(const vector<T>& v1, const vector<T>& v2);

eg

vector<int> v1{ 1,2,3,4,5 };
vector<int> v2{ 1,2,3,4,5 };
v1 <= v2; // true

>

声明

template <class T>
bool operator>(const vector<T>& v1, const vector<T>& v2);

eg

vector<int> v1{ 1,2,3,4,5 };
vector<int> v2{ 1,2,3,4,5 };
v1 > v2; // false

>=

声明

template <class T>
bool operator>=(const vector<T>& v1, const vector<T>& v2);

eg

vector<int> v1{ 1,2,3,4,5 };
vector<int> v2{ 1,2,3,4,5 };
v1 >= v2; // true

非成员函数 - 其他函数

swap函数

声明
与另一个vector对象进行内容的交换，也包括size和capacity；
与成员函数swap相比，第一个参数不再是隐式的this了；

template <class T>
  void swap (vector<T>& x, vector<T>& y);

eg

vector<int> v1{6, 6, 6, 6};   // size=4, capacity=4
vector<int> v2{1, 2, 3, 4, 5} // size=5, capacity=5
swap(v1, v2);
// v1 -> 1,2,3,4,5  size=5, capacity=5
// v2 -> 6,6,6,6    size=4, capacity=4

---

3. 揭开vector的真面目-模拟实现吧

底层成员变量

vector类模板的底层设计中包含三个T类型的指针：
_start指向空间的起始地址，也是第一个元素的地址；
_finish指向最后一个元素的下一个位置；
_end_of_storage指向空间的结尾位置的下一个位置；

template<class T>
class vector {
public:
private:
	T* _start;
	T* _finish;
	T* _end_of_storage;
};

构造函数

默认无参构造

不传参数时把三个指针都初始化为nullptr；

vector()
    :_start(nullptr)
    ,_finish(nullptr)
    ,_end_of_storage(nullptr){ }

使用n个val构造

new申请的空间大小是n*sizeof(T)，别忘记类型T的大小；

vector(size_t n, const T& val = T()) {
    _start = new T[n * sizeof(T)];
    _end_of_storage = _finish = _start + n;
    for (int i = 0; i < _finish - _start; ++i) {
        _start[i] = val;
    }
}

与上面的函数都是使用n个val构造，只是上面函数n的类型是size_t，而本函数n的类型是int；
对于vector<int> v(5, 1)这句代码，编译器将会调用vector(InputIterator first, InputIterator last)函数，而不是vector(size_t n, const T& val = T())；
首先模板参数T实例化为int，而5和1默认作为int类型参数处理，两个参数类型一致，编译器会把vector(InputIterator first, InputIterator last)的InputIterator模板参数实例化为int，即vector(int first,int last)从而更符合参数5和1的类型，但是5和1不是迭代器范围，编译时报错；
所以需要额外实现函数vector(int n, const T& val = T())可以直接匹配5和1参数；
对于vector<int> v(5, 'a')等情况则仍将会正常调用vector(size_t n, const T& val)函数的；

vector(int n, const T& val = T()) {
    _start = new T[n * sizeof(T)];
    _end_of_storage = _finish = _start + n;
    for (int i = 0; i < _finish - _start; ++i) {
        _start[i] = val;
    }
}

使用迭代器范围构造

template<class InputIterator>
vector(InputIterator first, InputIterator last) {
    size_t n = last - first;
    reserve(n);
    iterator it = begin();
    while (first != last) {
        (*it) = (*first);
        it++;
        first++;
    }
    _finish = _start + n;
}

拷贝构造函数

vector(const vector<T>& v)
    :_start(nullptr)
    , _finish(nullptr)
    , _end_of_storage(nullptr) {
    reserve(v.capacity());
    iterator it = begin();
    const_iterator cit = v.begin();
    while (cit != v.end()) {
        *it = *cit;
        ++it;
        ++cit;
    }
    _finish = it;
}

vector(const vector<T>& v) 
    :_start(nullptr)
    ,_finish(nullptr)
    ,_end_of_storage(nullptr){
    T* tmp = new T[v.capacity()];
    for (int i = 0; i < v.size(); ++i) {
        tmp[i] = v[i];
    }
    _start = tmp;
    _finish = _start + v.size();
    _end_of_storage = _start + v.capacity();
}

赋值运算符重载

现代写法，提高了代码书写效率
开空间交给了拷贝构造函数，而不是我们再次实现；

vector<T>& operator=(vector<T> v) {
    swap(v);
    return *this;
}

传统写法

vector<T>& operator=(const vector<T>& v) {
    // 不能自己给自己赋值
    if (*this != v) {
        T* tmp = new T[v.capacity()];
        for (int i = 0; i < v.size(); ++i) {
            tmp[i] = v[i];
        }
        //
        delete[] _start;
        _start = tmp;
        _finish = _start + v.size();
        _end_of_storage = _start + v.capacity();
    }
    return *this;
}

析构函数

~vector() {
    if (_start) {
        delete[] _start;
        _start = _finish = _end_of_storage = nullptr;
    }
}

迭代器相关

迭代器的实现 - 原生指针

typedef T* iterator;
typedef const T* const_iterator;

迭代器的返回类型，传值返回还是传引用返回？
对于非const版本，都可以，一般传值返回即可；
对于const版本，只能传值返回；因为引用返回会导致权限的放大，this指针类型是vector<T>*const，是指针常量，const修饰时变为vector<T> const * const，常量指针常量，函数返回类型const_iterator&即const T* &，返回指针变量_start是this指针指向的内容，故类型是T* const，所以由T*const到const T *将会出错；

正向迭代器

非const版本

begin返回指向开始元素的迭代器，即_start
end返回指向最后一个元素的下一个位置的迭代器，即_finish

iterator begin() {
    return _start;
}
iterator end() {
    return _finish;
}

const版本

const_iterator begin() const{
    return _start;
}
const_iterator end() const {
    return _finish;
}

元素访问

operator[]

访问pos位置的元素，注意需要对pos进行检查，防止越界访问；

非const版本

T& operator[](size_t pos) {
    assert(pos < size());
    return _start[pos];
}

const版本

const T& operator[](size_t pos) const {
    assert(pos < size());
    return _start[pos];
}

容量相关

size函数

vector没有直接记录元素个数的变量，通过_finish - _start指针相减计算；

size_t size() const {
    return _finish - _start;
}

capacity函数

vector没有直接记录空间容量的变量，通过_finish - _start指针相减计算；

size_t capacity() const {
    return _end_of_storage - _start;
}

reserve函数

改变vector对象的容量capacity,
当n小于等于当前vector对象的容量capacity时，reserve函数什么也不做；
只有当n大于vector对象的容量时，reserve函数才会向系统申请开辟空间；即reserve函数一般只进行扩容处理，不缩容；

void reserve(size_t n) {
    if(n <= capacity()) return;
    T* tmp = new T[n];
    for (int i = 0; i < size(); ++i) {
        tmp[i] = _start[i];
    }
    // 保存旧空间，防止_start更新后直接调用size()函数导致计算错误，
    // 此时_start是新的，而_finish还是旧的；
    int oldsize = size();
    delete[] _start;
    _start = tmp;
    _finish = _start + oldsize;
    _end_of_storage = _start + n;
}

resize函数

如果n小于vector原有的size，相当于删除元素直到size为n，_finish更新为_start + n即可；
如果n等于vector原有size就什么也不做；
如果n大于vector原有size且小于等于vector的原有capacity，相当于尾插元素直到size为n，即每次把val拷贝给_finish指向位置的元素，再++_finish直到_finish等于_start+n；
如果n大于vector原有的capacity，相当于先扩容使容量增大，再尾插元素直到size为n；

void resize(size_t n, const T& val = T()) {
    // 小于 
    if (n < size()) {
        _finish = _start + n;
    }
    else if (n < capacity()) {
        while (_finish < _start + n) {
            *_finish = val;
            ++_finish;
        }
    }
    else {
        reserve(n);
        while (_finish < _start + n) {
            *_finish = val;
            ++_finish;
        }
    }
}

empty函数

bool empty() const {
    return size() == 0;
}

增删查改相关

push_back函数

dd

void push_back(const T& val) {
    if (_finish == _end_of_storage) {
        int newcapacity = _end_of_storage - _start == 0 ? 4 : 2 * (_end_of_storage - _start);
        reserve(newcapacity);
    }
    *_finish = val;
    _finish++;
}

insert函数

再pos迭代器位置之前插入元素

插入一个元素

iterator insert(iterator pos, const T& val) {
    assert(pos >= _start && pos < _finish);
    int len = pos - _start;
    if (_finish == _end_of_storage) {
        int newcapacity = capacity() == 0 ? 4 : 2 * capacity();
        reserve(newcapacity);
    }
    // update pos
    pos = _start + len;
    // move
    iterator end = _finish;
    while (end > pos) {
        *end = *(end - 1);
        end--;
    }
    
    *pos = val;
    ++_finish;
    return pos;
}

insert的迭代器失效问题

例子引入

vector<int> v(4, 3);
vector<int>::iterator pos = v.begin() + 1;
v.insert(pos, 9);
(*pos)++; // 野指针

vector<int> v(4, 3);
vector<int>::iterator pos = v.begin() + 1;
pos = v.insert(pos, 9);
(*pos)++; // 正确访问

传值传入插入位置的迭代器变量pos，在insert内部vector对象会先进行容量检查：

• 如果容量满了就会进行扩容，这将会导致_start指向的空间变为扩容后新申请的空间，而pos还是指向旧空间的位置，此时pos是野指针，我们不能使用旧的pos了，需要pos指向新空间对应元素的位置后，再使用pos才能正确访问到元素；而外部调用insert函数后，作为参数的外部pos也失效了，其也指向了旧空间的位置，直接使用就是访问已经释放的空间，是非法访问内存，解决方法是外部pos接受insert的返回值新pos；
• 如果容量没满就无需扩容，内部pos不会失效，外部pos也不会失效；

为什么insert函数的参数iterator pos不使用引用类型iterator& pos？

• 诚然，使用引用后，外部的pos可以随着内部pos的更新而更新，不会失效了；但是此时形参pos只能是iterator的引用，遇到匿名对象等具有常性的迭代器时就会报错，导致权限放大问题即iterator 引用了 const_iterator对象，于是乎前人考虑的种种情况下，选择了insert更新后的pos作为返回值为外部提供，这样当外部想继续使用pos之前需要接收insert的参数即可。

插入多个元素

iterator insert(iterator pos, size_t n, const T& val) {
    assert(pos >= _start && pos < _finish);
    int len = pos - _start;
    if (size() + n > 2 * capacity()) {
        // 2
    }
    else if (size() + n > capacity()) {

    }
    pos = _start + len;
    // move
    iterator end = _finish;
    while (end > pos) {
        *(end + n - 1) = *(end - 1);
        end--;
    }

    iterator begin = pos;
    while (begin < pos + n) {
        *begin = val;
        ++begin;
    }
    _finish += n;
    return pos;
}

erase函数

删除pos位置的元素

iterator erase(iterator pos) {
    assert(pos >= _start && pos < _finish);
    iterator begin = pos + 1;
    while (begin < _finish) {
        *(begin - 1) = *begin;
        begin++;
    }
    _finish--;
    return pos;
}

erase的迭代器失效问题

例子引入：

vector<int> v = {1, 2, 3, 4}; //
vector<int>::iterator pos1 = v.end() - 1;
v.erase(pos1);
(*pos1)++; // 

vector<int>::iterator pos2 = v.begin();
v.erase(pos2);
(*pos2)++; //

这个例子的容器v分别执行了erase操作之后，迭代器pos1和pos2你是否认为失效了呢？
这在g++和vs2019编译器下有着不同的结果：

• g++编译器认为没有失效，erase操作之后pos2仍然指向第二个位置，此时该位置的元素是3，g++版本的STL的vector底层实现上迭代器是一个原生的指针即typedef T* iterator，即使我们使用了失效的迭代器也无法检查出来；
• vs编译器会对迭代器进行强制检查，认为pos2是失效的，程序会直接报错。这是因为vs下STL的实现方式更加复杂，对于vector容器的迭代器来说，不是一个原生的指针，而是被进一步封装为一个类，在使用迭代器时会先进行检查是否失效，如果失效了程序就会报错，反之就正常执行；
  当前我们实现的版本更加接近g++的vector版本，是一个原生的指针，也就是说我们实现的版本在erase操作之后也无法对失效的迭代器进行有效检查；

那么到底该不该认为erase操作之后的迭代器失效呢？

• 我的答案是不管编译器是否认为erase之后的迭代器是否失效，都认为迭代器是失效的，即每次erase之后及时更新迭代器，这样不管在g++编译器还是vs编译器下我们写的程序都是统一能跑的。

assign函数

为vector对象分配一个新值

一个迭代器范围[first, last)作为参数

template <class InputIterator>
void assign(InputIterator first, InputIterator last) {
    assert(first);
    assert(last);
    assert(first < last);
    if(_start) delete[] _start;
    _start = _finish = _end_of_storage = nullptr;
    while (first != last) {
        push_back(*first);
        first++;
    }
}

n个val作为参数；
有两个版本，功能完全相同，只有参数n的类型不同，目的是为了防止特殊情况下导致的问题：
如传入(5, 1)时期望是用5个int类型的1赋值给vector对象，但是在没有assign(int,const T&)函数时将会优先匹配assign(InputIterator first, InputIterator last)函数导致其内部解引用产生非法访问内存错误。

void assign(size_t n, const T& val) {
    vector<T> tmp(n, val);
    swap(tmp);
}
void assign(int n, const T& val) {
    vector<T> tmp(n, val);
    swap(tmp);
}

非成员函数 - swap函数

交换两个vector对象的内容

template <class T>
void swap(vector<T>& x, vector<T>& y) {
	x.swap(y);
}

---

4. vector的一些深拷贝问题

reserve函数是进行扩容的函数，其中涉及到开辟新空间，再把旧空间内容拷贝到新空间，最后释放旧空间的过程。
对于把内容从旧空间拷贝到新空间的方式，对于内置类型进行值拷贝就行；对于自定义类型特别是涉及资源管理的自定义类型来说，不能简单的进行值拷贝如使用memcpy函数，而是需要进行深拷贝，调用赋值运算符重载函数，前提是该自定义类型内部已经显式实现了深拷贝功能。

使用memcpy函数拷贝包含资源管理的自定义类型时发生的问题
以vector类为例，string类内部包含的指针指向了堆上的可变的字符数组，是需要管理的空间资源。其作为vector的元素在扩容时将会涉及到vector本身的深拷贝和string内部的深拷贝，也就是两层深拷贝。




解决方法：赋值操作，当是自定义类型时将会调用该自定义类型的赋值运算符重载函数完成深拷贝操作

---

结语

本节主要介绍了STL容器部分的vector，对于接口函数的学习先使我们整体了解vector如何使用。之后深入探究vector底层的实现方式，对比的是SGI版本，其中需要着重注意的是使用insert和erase导致的迭代器失效问题，实现vector的resere函数时考虑到涉及到资源管理的自定义类型需要深拷贝的情况。

---

$The$ $End$