[STL]vector的使用+模拟实现

[STL]vector的使用+模拟实现

一、vector的使用

1.构造函数

vector的构造函数提供了4种构造方式

1.无参构造方式

2.n个val的构造方式

3.迭代器区间的构造方式

4.拷贝构造

其中最后的参数是一个空间配置器(提高空间分配效率)，一般我们默认不用传这个参数。

其中，在n个val的构造中，默认的缺省值是T()，而不是0。这是因为在T不仅仅是内置类型，也可以是自定义类型。例如：string、stack、queue等。

我们由此发现在C++中，内置类型也可以使用匿名对象。例如：int()、double()、char()等。

2.迭代器

和string中说的很相似。

• 普通迭代器

• begin : 返回容器中的第一个位置

• end : 返回容器中的最后一个位置

• 反向迭代器

• rbegin : 返回容器中的最后一个位置

• rend : 返回容器中的第一个位置

• const对象迭代器
• cbegin : 返回容器中的第一个位置
• cend :返回容器中的最后一个位置

• const对象反向迭代器
• crbegin : 返回容器中的最后一个位置
• crend : 返回容器中的第一个位置

3.容量操作

• size : 返回容器中的内容大小

• max_size : 返回容器最大容量大小

• capacity : 返回容器中的容量

• empty : 返回容器是否为空

• resize : 改变容器中空间大小
  

1. 如果n < v.size(),缩写原来的大小到n
2. 如果 v.size() < n < v.capcaity()修改容器size为n。
3. 如果 n > v.capacity(), 容器扩容到n

• reserve : 改变容器中的容量大小

1.n < v.capacity(), 不变

2.n > v.capacity(), 改变容器容量

4.vector的访问

• operator[] : 容器的随机访问
• front : 容器的第一个位置的内容
• back ： 容器的最后一个位置的内容

5.vector的修改

• push_back : 尾部插入
• pop_back : 尾部删除

• insert : 插入

1.pos位置 + val值

2.pos位置 + n个val值

3.pos位置 + 迭代器区间

• erase : 删除

1. pos位置删除
2. 迭代器区间删除

• swap : 交换
• clear : 清空容器

二、几个细节

1.范围for

范围for的原理十分简单，仅仅是对代码进行了替换。通过调用begin()和end()接口进行比对，判断循环是否停止。

我们可以进入反汇编中去查看汇编下范围for是怎么生成的。

如果我们在模拟实现中，将begin()和end()改为Begin()和End()，那样编译器无法识别就会报错，所以在使用范围for时，一定要确保begin()和end()是否正确。

2.扩容机制

我们可以用下面这么一段代码测试一下编译器的扩容机制：(我使用的是vs2019)

int main()
{vector<int> v;size_t capacity = 0;capacity = v.capacity();cout << " vector change : " << endl;for (int i = 0; i < 100; i++){v.push_back(i);if (capacity != v.capacity()){capacity = v.capacity();cout << " vector capacity : " << capacity << endl;}}return 0;
}

我们发现vs2019的扩容机制是约1.5倍的扩容。

我们再看一下linux下的扩容机制。

我们看到linux下扩容是一个标准二倍的扩容。

3.迭代器失效

我们使用insert和erase一般配合着算法库里的find接口使用。

• find : 查找数据，有，返回pos位置， 无，
  
  

我们去掉解引用pos:

这里就是我们所说的迭代器失效问题：

在我们使用insert和erase后，迭代器pos就会失效，需要使用就得更新一下pos :

所以一般我们实现的和STL库中的，都会有一个有返回值的insert和erase接口。

但是linux下不会出现这种情况。

原因可能是vs对库进行了封装，我们每次使用insert和erase后,vs都进行了处理。而linux下使用的是原生的，没有进行过处理或者修改。

所以，我们默认使用insert和erase后迭代器会失效，需要我们进行更新后使用。

4.构造函数错误调用

    vector(size_t n, const T& val = T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}template <class InputIterator>vector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){while (first != last){push_back(*first);++first;}}

在我们构造一个有n个val的vector时(仅仅在构造int类型时出现)，会出现一个奇怪的报错非法访问寻址。

这里报错的原因是，编译器分不清我们调用的是哪个构造函数，编译器为了方便简单，选择了将两个Inputlterator实例化为int，而不是一个隐式转换为size_t，一个实例化为int。这样编译器就会调用迭代器构造，而迭代器构造中就会有解引用，对一个整形解引用就会出现上面的非法访问寻址。

而解决的方法很简单，我们手动写一个int类型的构造即可。

vector(int n, const T& val = T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){reserve(n);for (int i = 0; i < n; i++){push_back(val);}}

5.vector的深拷贝与浅拷贝

我们在实现reserve接口时，不进行开辟新的空间就会出现浅拷贝问题。

对于浅拷贝问题，大体上都是这样的：

我们将新开辟的空间中记录了被释放掉的旧空间，当程序结束又对这块空间进行了释放。

我们这里的reserve也容易出现这里的浅拷贝问题(只会对使用自定义类型出现)：

void reserve(size_t n)
{if (n > capacity()){size_t OldSize = size();T* tmp = new T[n];if (_start){memcpy(tmp, _start, sizeof(T) * size());delete[]_start;}_start = tmp;_finish = tmp + OldSize;_end_of_storage = _start + n;}
}

我们没有开辟储存数据的空间，而是直接使用memcpy按字节拷贝过来，虽然我们对存放v[i]进行了深拷贝，但是他们可能还是指向了原来的将要被析构的旧空间。当旧空间被析构，而程序结束时这块空间再次被析构。造成了对同一块空间进行多次析构的错误。

修改方法很简单：

void reserve(size_t n)
{if (n > capacity()){size_t OldSize = size();T* tmp = new T[n];if (_start){//memcpy(tmp, _start, sizeof(T) * size());for (size_t i = 0; i < OldSize; i++){tmp[i] = _start[i];}delete[]_start;}_start = tmp;_finish = tmp + OldSize;_end_of_storage = _start + n;}
}

6.vector的框架

通过读《STL的源码剖析》,我发现了一个vecor的框架，有助于我们对vector有更深的理解。

三、vector模拟实现

vector.h

#pragma once
#include <string.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;}T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos) const{assert(pos < size());return _start[pos];}vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){}vector(int n, const T& val = T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){reserve(n);for (int i = 0; i < n; i++){push_back(val);}}vector(size_t n, const T& val = T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}template <class InputIterator>vector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){while (first != last){push_back(*first);++first;}}vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){vector<T> tmp(v.begin(), v.end());swap(tmp);}vector<T>& operator=(vector<T> v){swap(v);return *this;}~vector(){delete[] _start;_start = _finish = _end_of_storage = nullptr;}void reserve(size_t n){if (n > capacity()){size_t OldSize = size();T* tmp = new T[n];if (_start){//memcpy(tmp, _start, sizeof(T) * size());for (size_t i = 0; i < OldSize; i++){tmp[i] = _start[i];}delete[]_start;}_start = tmp;_finish = tmp + OldSize;_end_of_storage = _start + n;}}void resize(size_t n, T val = T()){if (n > capacity()){reserve(n);}if (n > size()){while (_finish < _start + n){*_finish = val;++_finish;}}else{_finish = _start + n;}}size_t size() const{return _finish - _start;}size_t capacity() const{return _end_of_storage - _start;}bool empty(){return _finish == _start;}void push_back(const T& x){if (_finish == _end_of_storage){size_t NewCapcity = capacity() == 0 ? 4 : capacity() * 2;reserve(NewCapcity);}*_finish = x;++_finish;}void pop_back(){assert(!empty());--_finish;}iterator insert(iterator pos, const T& val){assert(pos >= _start);assert(pos < _finish);//判断扩容if (_end_of_storage == _finish){size_t len = _finish - _start;size_t NewCapcity = capacity() == 0 ? 4 : capacity() * 2;reserve(NewCapcity);pos = _start + len;}//挪动数据iterator end = _finish - 1;while (end >= pos){(*end + 1) = (*end);--end;}*pos = val;++_finish;return pos;}iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator begin = pos + 1;while (begin < _finish){*(begin - 1) = *begin;++begin;}--_finish;return pos;}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}void clear(){_finish = _start;}private:iterator _start;iterator _finish;iterator _end_of_storage;};
}

test.cpp

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <assert.h>
using namespace std;
#include "vector.h"
void test()
{myVector::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.begin();v.pop_back();for (auto e : v){cout << e << " ";}cout << endl;cout << v.capacity() << endl;cout << v.size() << endl;for (int i = 0; i < v.size(); i++){cout << v[i];cout << ' ';}cout << endl;
}void test1()
{myVector::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);for (auto e : v){cout << e << " ";}cout << endl;cout << v.capacity() << endl;cout << v.size() << endl;v.reserve(10);cout << v.capacity() << endl;cout << v.size() << endl;
}
void test2()
{myVector::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);for (auto e : v){cout << e << " ";}cout << endl;cout << v.capacity() << endl;cout << v.size() << endl;v.reserve(11);cout << v.capacity() << endl;cout << v.size() << endl;v.resize(9, 2);for (auto e : v){cout << e << " ";}cout << endl;cout << v.capacity() << endl;cout << v.size() << endl;
}
void test3()
{myVector::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);for (auto e : v){cout << e << " ";}cout << endl;myVector::vector<string> v1;v1.push_back("111");v1.push_back("111");v1.push_back("111");v1.push_back("111");v1.push_back("111");for (auto e : v1){cout << e << " ";}cout << endl;
}
void test4()
{myVector::vector<myVector::vector<int>> vv;myVector::vector<int> v(5, 1);vv.push_back(v);vv.push_back(v);vv.push_back(v);vv.push_back(v);vv.push_back(v);for (size_t i = 0; i < vv.size(); ++i){for (size_t j = 0; j < vv[i].size(); ++j){cout << vv[i][j] << " ";}cout << endl;}cout << endl;
}void test5()
{// 要求删除所有偶数myVector::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(2);v.push_back(3);v.push_back(4);//v.push_back(5);myVector::vector<int>::iterator it = v.begin();while (it != v.end()){if (*it % 2 == 0){it = v.erase(it);}else{++it;}}for (auto e : v){cout << e << " ";}cout << endl;}void test6()
{// 要求删除所有偶数myVector::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(2);v.push_back(3);v.push_back(4);myVector::vector<int> v1(v);for (auto e : v1){cout << e << " ";}cout << endl;myVector::vector<int> v2;v2.push_back(10);v2.push_back(20);v1 = v2;for (auto e : v1){cout << e << " ";}cout << endl;v1 = v1;for (auto e : v1){cout << e << " ";}cout << endl;
}void test7()
{std::string str("hello");myVector::vector<int> v(str.begin(), str.end());for (auto e : v){cout << e << " ";}cout << endl;//vector<int> v1(v.begin(), v.end());myVector::vector<int> v1(10, 1);//vector<char> v1(10, 'A');for (auto e : v1){cout << e << " ";}cout << endl;
}void test8()
{myVector::vector<myVector::vector<int>> vv;myVector::vector<int> v(5, 1);vv.push_back(v);vv.push_back(v);vv.push_back(v);vv.push_back(v);vv.push_back(v);for (size_t i = 0; i < vv.size(); ++i){for (size_t j = 0; j < vv[i].size(); ++j){cout << vv[i][j] << " ";}cout << endl;}cout << endl;
}class Solution {
public:myVector::vector<myVector::vector<int>> generate(int numRows) {myVector::vector<myVector::vector<int>> vv;vv.resize(numRows);for (size_t i = 0; i < vv.size(); ++i){vv[i].resize(i + 1, 0);vv[i][0] = vv[i][vv[i].size() - 1] = 1;}for (size_t i = 0; i < vv.size(); ++i){for (size_t j = 0; j < vv[i].size(); ++j){if (vv[i][j] == 0){vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];}}}return vv;}
};void test9()
{myVector::vector<myVector::vector<int>> vvRet = Solution().generate(5);for (size_t i = 0; i < vvRet.size(); ++i){for (size_t j = 0; j < vvRet[i].size(); ++j){cout << vvRet[i][j] << " ";}cout << endl;}cout << endl;
}int main()
{//test();//test1();//test2();//test3();//test4();//test5();//test6();//test8();test9();return 0;
}

大学排行榜