目录

1. vector的介绍

2. vector的使用

2.1 构造函数

2.2 遍历方式

2.3 reserve与resize

2.4 shrink_to_fit 

2.5 insert，erase，find

3. vector模拟实现

3.1 初始结构

3.2 析构函数 

3.3 获取容量和元素个数

3.4 扩容reserve

3.5 resize改变有效个数并赋值val

3.6 方括号访问operator[]

3.7 迭代器

3.8 insert在pos前面插入

3.9 尾插push_back

3.10 erase删除pos位置的值

3.11 拷贝构造

3.12 赋值重载

3.13 用迭代器区间构造

3.14 用n个val构造

---

1. vector的介绍

vector是模板实现的。

Vectors are sequence containers representing arrays that can change in size.

 

2. vector的使用

使用上分几大部分：默认成员函数，迭代器，容量相关，访问相关，修改。

2.1 构造函数

void test1()
{//无参vector<int> v1;//有参vector<int> v2(10); //val的缺省值是0。vector<int> v3(10, 1);//迭代器vector<int> v4(v3.begin(), v3.end());//拷贝构造vector<int> v5(v4);
}

2.2 遍历方式

1. 下标加[ ]，2. 迭代器，3. 范围for。

void test2()
{vector<int> v(10, 5);//下标+[]for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;//迭代器vector<int>::iterator it = v.begin();while (it != v.end()){cout << *it << " ";it++;}cout << endl;//范围forfor (auto e : v){cout << e << " ";}cout << endl;
}

2.3 reserve与resize

reserve改变容量。

预先开空间就用reserve，容量改变，有效个数不变。

---

 

resize改变有效个数。

---

【区别】

---

【扩容机制】

vs：1.5倍扩容，g++：2倍扩容

2.4 shrink_to_fit 

缩容：将容量缩到和有效个数一样。

一般是异地缩容。

2.5 insert，erase，find

(1)在pos位置的元素前面插入val。

(2)在pos位置的元素前面插入n个val。

(3)在pos位置的元素前面插入一段迭代器区间。

注意：传入的是迭代器。

---

找到pos的位置需要借助find，find在算法库里，容器通用。

find传的迭代器区间都是左闭右开，没找到就返回last。

---

 删除某个位置或一段区间。

 

---

【结合用法】

void test3()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);for (auto e : v){cout << e << " ";}cout << endl;//头插v.insert(v.begin(), 9);for (auto e : v){cout << e << " ";}cout << endl;//在3前面插入6vector<int>::iterator it1 = find(v.begin(), v.end(), 3);if (it1 != v.end()){v.insert(it1, 6);}for (auto e : v){cout << e << " ";}cout << endl;//把6删除auto it2 = find(v.begin(), v.end(), 6);if (it2 != v.end()){v.erase(it2);}for (auto e : v){cout << e << " ";}cout << endl;
}

vector官方文档：vector - C++ Reference (cplusplus.com) 

 

3. vector模拟实现

3.1 初始结构

_start指向元素开始位置，_finish指向最后一个元素的下一个位置，_end指向最大容量的下一个位置。

namespace lyh
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;//无参构造vector(){}private:iterator _begin = nullptr;  //元素开始位置。iterator _end = nullptr;    //元素末尾的下一个位置。iterator _capacity = nullptr;    //最大容量的下一个位置。};
}

3.2 析构函数 

释放空间，指针置空。

        ~vector(){delete[] _begin;_begin = nullptr;_end = nullptr;_capacity = nullptr;}

3.3 获取容量和元素个数

利用指针相减。

		size_t size() const{return _end - _begin;}size_t capacity() const{return _capacity - _begin;}

3.4 扩容reserve

 n小于容量不用管，n大于容量才扩容。

新开一个大空间，拷贝数据，释放原空间，更新成员变量的指向。

memcpy是浅拷贝，这里用赋值重载才能完成深拷贝，内置类型就浅拷贝，自定义类型就调用自己的赋值重载。

		void reserve(size_t n){if (n > capacity()){size_t sz = size();T* tmp = new T[n];//原空间有数据才需要拷贝。if (_begin){for (size_t i = 0; i < sz; i++){tmp[i] = _begin[i];}//释放原空间。delete[] _begin;}//更新成员指向。_begin = tmp;_end = tmp + sz;_capacity = tmp + n;}}

3.5 resize改变有效个数并赋值val

改变有效个数有三种情况。

小于原先size就缩小。

大于size就交给reserve判断要不要扩容，然后不断尾插直到n。

		void resize(size_t n, const T& val = T()){if (n <= size()){_end = _start + n;}else{reserve(n);while (_end < _begin + n){*_end = val;++_end;}}}

3.6 方括号访问operator[]

需要断言传入的下标是否合法，返回下标对应的元素的别名。可以提供const版本，可以访问但不能修改。

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

3.7 迭代器

begin指向第一个位置，end指向最后一个位置的下一个。可以提供const版本。

		iterator begin(){return _begin;}iterator end(){return _end;}const_iterator begin() const{return _begin;}const_iterator end() const{return _end;}

3.8 insert在pos前面插入

先断言pos在合法范围，再判断是否需要扩容，然后pos位置开始往后挪给pos腾出空间插入。

扩容是异地扩容除了更新原本的成员变量指向还需更新pos的指向，不然pos会变成野指针也就是迭代器失效。

		void insert(iterator pos, const T& val){assert(pos >= _begin && pos <= _end);if (_end == _capacity){size_t len = pos - _begin;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _begin + len;}iterator key = _end;while (key > pos){_start[key] = _start[key - 1];--key}*key = val;++_end;}

3.9 尾插push_back

复用insert

		void push_back(const T& val){insert(end(), val);}

3.10 erase删除pos位置的值

先断言pos是否合法，然后将pos之后的位置往前移。

erase之后认为迭代器失效，不能访问。

 ​

返回的迭代器指向原本删除元素的下一个元素。

An iterator pointing to the new location of the element that followed the last element erased by the function call.

		iterator erase(iterator pos){assert(pos >= _begin && pos < _end);iterator key = pos + 1;while (key < _end){*(key-1) = *key;++key;}--_end;return pos;}

3.11 拷贝构造

先开一个和v一样大的空间，再把v的元素拷贝过来(遍历尾插)。

		vector(const vector<T>& v){reserve(v.capacity());for (auto& e : v){push_back(e);}}

3.12 赋值重载

假设v3 = v1，将v1传值拷贝构造给tmp，v3和tmp交换。先拷贝构造给了形参再和形参交换。

		void swap(vector<T>& tmp){std::swap(_begin, tmp._begin);std::swap(_end, tmp._end);std::swap(_capacity, tmp._capacity);}vector<T>& operator=(vector<T> tmp){swap(tmp);return *this;}

3.13 用迭代器区间构造

当begin不等于end就不断尾插。

		vector(InputIterator begin, InputIterator end){while (begin != end){push_back(*begin);++begin;}}

3.14 用n个val构造

复用用resize。

		vector(size_t n, const T& val = T()){resize(n, val);}

Vector/Vector · 林宇恒/code-cpp - 码云 - 开源中国 (gitee.com)