文章目录
- 1. 认识vector
- 2. vector的遍历
- 3. vector的构造
- 4. vector常用的接口
- 5. vector的容量
- 6. vector的元素访问
- 7. vector的修改
- 8. vector<vector\<int\>>的使用
- 9. vector的使用
- 10. 模拟实现vector
- 11. 迭代器失效
- 11.1 insert插入数据内部迭代器失效
- 11.2 insert插入数据外部迭代器失效
- 11.3 erase删除数据迭代器失效
- 12. 模拟实现resize
- 13. 模拟实现vector的拷贝构造
- 14. 模拟实现vector的赋值操作符重载
- 15. 模拟实现reserve存在的坑
- 16. 模拟实现vector初始化
- 17. vector构造时容易出现的坑
- 18. 模拟实现vector代码
1. 认识vector
- vector是向量、矢量的意思
- vector其实就是数据结构阶段学过的顺序表,行为看起来像指针一样的容器,底层不一定是用指针实现的,具体根据编译器的底层实现结构为准
- vector的使用:
vector<数据类型> 对象名
2. vector的遍历
3. vector的构造
- 对于vector的析构,跟string类似,它会自动调用
4. vector常用的接口
- vector上述的接口与string的接口并无二异
- cbegin( )和cend( )的用法与begin和end类似,无非就是常量迭代器不能改变数据而已
5. vector的容量
- 对于判空empty和请求缩容shrink_to_fit不再过多赘述,string里面都有讲到
6. vector的元素访问
- at和下标访问操作符[ ]都是用来访问vector内的元素,区别是越界时下标操作符[ ]会报错,而at会抛出异常,关于这点string已经讲过,后续讲到捕获异常时可重温复习以加深理解
7. vector的修改
- 其余的像swap用来交换两个vector对象,使用时可参考官方文档,大部分与string类模版中的用法类似
8. vector<vector<int>>的使用
- vector<vector<int>>其实就是类似二维数组的用法,使用vector实例化出int类型的对象,再使用vector<vector<int>>实例化出vector<int>的对象
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main()
{
size_t numRows = 0;
cin >> numRows;
vector<vector<int>> vv(numRows);
for (size_t i = 0; i < numRows; i++)
{vv[i].resize(i + 1, 1);
}
for (size_t i = 2; i < numRows; i++)
{for (size_t j = 1; j < vv[i].size() - 1; j++){vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];}
}
for (size_t i = 0; i < numRows; i++)
{for (size_t k = 0; k < numRows - i - 1; k++){cout << " ";}for (size_t j = 0; j < vv[i].size(); j++){cout << vv[i][j] << " ";}cout << endl;
}
return 0;
}
9. vector的使用
- 对于vector容器,也可以使用string类型,其插入string类型的数据如下
- 关于vector和C++算法库的一些使用,以下先作为一个了解
10. 模拟实现vector
- 之前讲述过,迭代器都是左闭右开的区间,对于begin指向第一个数,而end则指向最后一个数的下个位置
- 因此对于vector的成员变量_start和_finish、_end_of_storage来讲,_finish就是指向有效数据的下个位置,_end_of_storage就指向容量的下个位置
- insert在pos位置插入字符
- 注意:pos的类型是迭代器iterator,因为vector的成员变量是iterator类型,类似迭代器begin()和end()
- 对于上述insert插入数据的代码,存在一个巨大隐患:迭代器失效的问题,接下来主要讲容器中的迭代器失效的问题
11. 迭代器失效
11.1 insert插入数据内部迭代器失效
11.2 insert插入数据外部迭代器失效
- 即使是库里面实现的vector,对于insert插入数据也会出现迭代器失效的问题
- 迭代器失效的根本原因就是扩容,扩容前后外部迭代器指向的是旧空间,而扩容后旧空间被释放,再访问就会报错
- 因此对于insert插入数据后外部传参的迭代器,由于不同的平台结果可能不同,统一认为该迭代器失效
- 解决办法:insert插入数据后更新迭代器
11.3 erase删除数据迭代器失效
- 解决办法:在erase删除数据后即使更新迭代器it
- 总结
- 对于迭代器失效的问题,主要存在于容器插入和删除元素时,这里以vector为例,在insert插入数据和erase删除数据后,迭代器就处于失效的状态,这是因为插入数据扩容导致以及删除数据缩容导致的一系列问题
- 对于不同的编译器,结果可能不同,并且vs对于迭代器失效的检查尤为严格,它会对失效的迭代器进行标记,如果尝试使用这些失效的迭代器,它就会报错
- 因此统一认为容器插入数据和删除数据后迭代器处于失效的状态
- 如果想继续使用失效的迭代器,解决办法就是在插入数据或删除数据前后根据实际情况及时更新迭代器,使迭代器正确指向对应的数据
12. 模拟实现resize
13. 模拟实现vector的拷贝构造
14. 模拟实现vector的赋值操作符重载
15. 模拟实现reserve存在的坑
- 插入前四个字符串时没有问题,但是插入第5个字符串时,为什么会出现问题呢?
- 因为插入第5个字符串时会扩容,reserve扩容中的memcpy其实就是一个浅拷贝,之前再C语言阶段实现过memcpy这个函数,它是一个字节一个字节拷贝的
- 参考链接:memcpy的使用和模拟实现
16. 模拟实现vector初始化
- C++11提供了vector初始化列表来进行初始化
- inltializer_list是C++11设置一个模版类型
- 其用法和之前创建数组有点类似
17. vector构造时容易出现的坑
18. 模拟实现vector代码
template <class T>
class vector
{
public:typedef T* iterator;typedef const T* const_iterator;vector(){}vector(initializer_list<T> il){reserve(il.size());for (auto& e : il){push_back(e);}cout << "初始化列表初始化:" << endl;}template <class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}vector(int n, const T& val = T()){resize(n, val);}vector(size_t n, const T& val = T()){resize(n, val);}vector(const vector<T>& v){reserve(v.size());for (auto& e : v){push_back(e);}}size_t size() const{return _finish - _start;}size_t capacity() const{return _end_of_storage - _start;}iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}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 reserve(size_t n){if (n > capacity()){size_t oldsize = size();T* tmp = new T[n];for (size_t i = 0; i < oldsize; i++){tmp[i] = _start[i];}delete[] _start;_start = tmp;_finish = oldsize + _start;_end_of_storage = n + _start;}}void push_back(const T& x){if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : 2 * capacity());}*_finish = x;_finish++;}void pop_back(){assert(_finish > _start);_finish--;}T& operator[](size_t i){return _start[i];}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<T>& operator=(const vector<T>& v){swap(v);return *this;}void insert(iterator pos, const T& x){assert(pos >= _start);assert(pos <= _finish);if (_finish == _end_of_storage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : 2 * capacity());pos = _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);iterator begin = pos + 1;while (begin < _finish){*(begin - 1) = *begin;++begin;}--_finish;return pos;}~vector(){delete[] _start;_start = _finish = _end_of_storage = nullptr;}
private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;
};