目录

一、vector的介绍及使用

1.1 vector的介绍

1.1.1 认识vector

1.1.2 成员类型​​​​​​​

1.1.3 成员函数一览

1.1.4 非成员函数重载 

1.2 vector的使用

1.2.1 构造、析构与赋值操作符重载

1.2.2 reserve 与 resize

1.2.3 insert、erase 与 find

extra train

1. 二叉树的前序遍历

2. 只出现一次的数字

3. 杨辉三角

二、vector的深度剖析及模拟实现

2.1 vector的深度剖析         

2.1.1 memcpy 浅拷贝问题

2.2.2 iterator 迭代器失效问题        

insert 迭代器失效

erase 迭代器失效        

2.2 vector的模拟实现        

extra train   

1. 只出现一次的数字 II    

2. 电话号码的字母组合  

---

---

---

二、vector的深度剖析及模拟实现

2.1 vector的深度剖析         

2.1.1 memcpy 浅拷贝问题

void reserve(size_t n)
{if (n > capacity()){	// 创建新的空间T* tmp = new T[n];size_t sz = size();if (_start){// 拷贝数据 并 删除旧的空间memcpy(tmp, _start, sizeof(T) * n);	//浅拷贝delete[] _start;}_start = tmp;_finish = _start + sz;_endofstorage = _start + n;}
}

        

        

2.2.2 iterator 迭代器失效问题        

insert 迭代器失效

void insert(iterator pos, const T& x)
{assert(pos >= _start);assert(pos <= _finish);if (_finish == _endofstorage){reserve(capacity() == 0 ? 4 : capacity() * 2);}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;
}

        

为了防止迭代器失效，需要我们记录_start与pos的相对位置，及时更新pos。具体的实现方法见<vector的模拟实现>

erase 迭代器失效        

void erase(iterator pos)
{assert(pos >= _start);assert(pos <= _finish);vector<int>::iterator it = pos - 1;while (it < _finish){*(it - 1) = *it;++it;}--_finish;
}void test_vector()
{// 测试三组用例// 1 2 3 4 5        output: 1 3 5// 1 2 3 4 5 6      output: 崩溃// 2 2 3 4 5        output: 2 3 5std::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);//v.push_back(6);for (auto e : v){cout << e << " ";}cout << endl;auto it = v.begin();while (it != v.end()){if (*it % 2 == 0){v.erase(it);// it = v.erase(it);}++it;}for (auto e : v){cout << e << " ";}cout << endl;
}erase后的迭代器无法正常使用，为了防止出现问题，我们可以记录erase后的迭代器并返回接受，更新原来的迭代器。具体的实现方法见<vector的模拟实现>

        

2.2 vector的模拟实现        

#pragma once
#include <assert.h>namespace myvector
{// 模板template<class T>class vector{public:// 迭代器（反向迭代器未实现）typedef T* iterator;typedef const T* const_iterator;iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const {return _start;}const_iterator end() const{return _finish;}vector()	// 注意：该构造函数不能删去，有其它函数需要使用它{}template <class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}// size_t 类型的 nvector(size_t n, const T& val = T()){// const T& val 的缺省参数最好还是给 T()reserve(n);	// 扩容，检查都交给reservefor (size_t i = 0; i < n; i++){push_back(val);}}// int 类型的 n（为了更好地匹配使用）vector(int n, const T& val = T()){reserve(n);for (int i = 0; i < n; i++){push_back(val);}}// copy构造vector(const vector<T>& v){reserve(v.capacity());for (auto& e : v){push_back(e);}}// 初始化列表vector():_start(nullptr),_finish(nullptr),_endofstorage(nullptr){}// 析构~vector(){delete[] _start;_start = _finish = _endofstorage = nullptr;}void swap(vector<T>& v){// “swap”前面加上“std::”确保调用库中的swapstd::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}// 赋值操作符重载vector<T>& operator=(vector<T> tmp){// 赋值需要传参，传参调用copy构造// 实际上是copy构造帮助完成了赋值swap(tmp);return *this;}void push_back(const T& x){/*if (_finish == _endofstorage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;++_finish;*/// 借用 insert insert(end(), x);}// []操作符重载（可读可写）T& operator[](size_t pos){assert(pos < size());return _start[pos];}// []操作符重载（只读）const T& operator[](size_t pos) const{assert(pos < size());return _start[pos];}// 容量size_t capacity() const{return _endofstorage - _start;}// 大小size_t size() const{return _finish - _start;}void reserve(size_t n){if (n > capacity()){	// 创建新的空间T* tmp = new T[n];size_t sz = size();if (_start){// 拷贝数据 并 删除旧的空间//memcpy(tmp, _start, sizeof(T) * n);	//浅拷贝for (size_t i = 0; i < sz; i++)		{tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + sz;_endofstorage = _start + n;}}//void resize(size_t n, T val = T())	两种写法是一致的void resize(size_t n, const T& val = T()){if (n <= size()){_finish = _start + n;}else{reserve(n);while (_finish < _start + n){*_finish = val;_finish++;}}}// 插入void insert(iterator pos, const T& x){assert(pos >= _start);assert(pos <= _finish);if (_finish == _endofstorage){size_t len = pos - _start;	// reserve扩容导致迭代器pos失效（pos指向的原来的_start已经释放了）reserve(capacity() == 0 ? 4 : capacity() * 2);// 及时更改pospos = _start + len;			}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;}// 删除（返回值用于解决迭代器失效的问题）iterator erase(iterator pos){assert(pos >= _start);assert(pos <= _finish);vector<int>::iterator it = pos - 1;while (it < _finish){*(it - 1) = *it;++it;}--_finish;return pos;}private:iterator _start;iterator _finish;iterator _endofstorage;};
}

        

extra train   

1. 只出现一次的数字 II    

137. 只出现一次的数字 II - 力扣（LeetCode）        

//137. 只出现一次的数字 II
// 数电解法
class Solution137I {
public:int singleNumber(vector<int>& nums){int a = 0, b = 0;for (auto e : nums){b = ~a & (b ^ e);a = ~b & (a ^ e);}return b;}
};// 按位解法
class Solution137II {
public:int singleNumber(vector<int>& nums){int ans = 0;for (int i = 0; i < 32; ++i){int total = 0;for (auto num : nums){// 取出num的第i个二进制位total += ((num >> i) & 1);  // & 按位与}if (total % 3){ans |= (1 << i);    // | 按位或}}return ans;}
};

2. 电话号码的字母组合  

17. 电话号码的字母组合 - 力扣（LeetCode）  

// 17. 电话号码的字母组合class Solution17 {const char* numStrArr[10] = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
public:void Combine(const string& digits, int i, vector<string>& ret, string combineStr){if (i == digits.size()){ret.push_back(combineStr);return;}int num = digits[i] - '0';string str = numStrArr[num];for (size_t j = 0; j < str.size(); j++){Combine(digits, i + 1, ret, combineStr + str[j]);}}vector<string> letterCombinations(string digits){vector<string> v;if (digits.empty()){return v;}string str;Combine(digits, 0, v, str);return v;}
};

        

        

---