STL - vector的使用和模拟实现

目录

一：vector的构造函数

二：vector的迭代器

三vector的空间增长问题

四：vector 增删查改接口

五：vector的模拟实现

（一）一些简单接口的实现：

（二）一些复杂接口的实现

迭代器失效问题：

（三）五个构造函数的模拟实现

（1）默认构造

（2）拷贝构造函数

（3）使用n个val去初始化容器的构造

（4）迭代器区间初始化构造：

（5）赋值构造

---

vector其实就是我们数据结构中的顺序表。

一：vector的构造函数

（1）无参构造：即默认构造。vector构造一个没有元素的空容器。

	// 走默认构造vector<char> vc;

（2）填充构造函数：构造一个包含 n 个元素的容器。每个元素都是 val 的副本。

	// 默认初始化为0vector<int> v1(10);// 初始化为1vector<int> v2(10, 1);

 （3）拷贝构造函数：构造一个容器，其中包含与范围 [first，last] 一样多的元素，每个元素都按相同的顺序从该区域中的相应元素构造。

	// 拷贝构造vector<int> v3(v2);

（4）使用迭代器进行初始化的构造：构造一个容器，其中包含与范围 [first，last] 一样多的元素，每个元素都按相同的顺序从该区域中的相应元素构造。

	vector<int> v1(10);// 使用迭代器进行初始化vector<int> v3(v1.begin(), v1.end()-3);

二：vector的迭代器

同其他的string容器一样，begin和end分别是容器的第一个位置和最后一个位置，反向迭代器则相反。const迭代器和非const迭代器和string的也是一样的C++_STL_string使用和模拟实现-CSDN博客

这里可以看一下。

// 初始化为一个定值
vector<int> v2(10, 1);
// 迭代器使用
//vector<int>::iterator it;
//vector<int>::const_iterator it;
// 反向迭代器
vector<int>::reverse_iterator it;
//it = v2.begin();
it = v2.rbegin();
//while (it != v2.end())
while (it != v2.rend())
{//cout << ++(*it) << " ";cout << *it << " ";it++;
}

三vector的空间增长问题

（1）size()：返回元素的实际个数

（2）capacity()：容器容量的大小

（3）resize() ：修改实际容器元素个数

（4）reserve()：改变capacity的大小

（5）empty()：判断容器是否为空

注意：在g++和vs中capacity在扩容的时候可能不一样，有的是1.5倍扩容，有的是2倍扩容

具体我们来看下这几个接口的情况：

// 测试vector 空间增长问题接口
void test02()
{vector<int> v2(10, 1);cout << v2.size() << endl;cout << v2.capacity() << endl;cout << v2.empty() << endl;// resize如果n大于size的话会将size的元素进行初始化v2.resize(40);// 这里改变capacity的为13并不会缩容v2.reserve(13);cout << v2.capacity() << endl;for (auto& x : v2){cout << x << " ";}
}

四：vector 增删查改接口

（1）push_back：在容器末尾插入一个值

void push_back (const value_type& val);

（2）pop_back：删除容器末尾的一个值

void pop_back();

（3）find：在范围内查找值

返回范围中比较等于 的第一个元素的迭代器。如果未找到此类元素，则函数返回 。

template <class InputIterator, class T>   InputIterator find (InputIterator first, InputIterator last, const T& val);

（4）insert：通过在指定位置的元素之前插入新元素来扩展向量，从而有效地增加容器大小（增加插入的元素数）。

single element (1)	
iterator insert (iterator position, const value_type& val);
fill (2)	void insert (iterator position, size_type n, const value_type& val);
range (3)	
template <class InputIterator>    void insert (iterator position, InputIterator first, InputIterator last);

（5）erase：从向量中删除单个元素 （位置） 或一系列元素 （[first，last））

iterator erase (iterator position);iterator erase (iterator first, iterator last);

（6）swap：交换向量的数据空间

void swap (vector& x);

（7）operator[]：返回对向量容器中位置 n 处的元素的引用。

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

1~7接口代码：

void test03()
{//find
//push_back 
///vector<int> v2;for (int i = 0; i < 100; i++){v2.push_back(i);}v2.pop_back();//for (auto& e : v2)//{//	cout << e << " ";//}cout << endl;// 在一个范围内查找数据val,并且返回第一个等于val的迭代器,如果没有找到就返回区间的末尾迭代器vector<int>::iterator it = find(v2.begin(),v2.end(), 31);//while (it != v2.end())//{//	//cout << ++(*it) << " ";//	cout << *it << " ";//	it++;//}
/
//insert
//在pos迭代器位置插入val，不是下标v2.insert(v2.begin() + 10, 10025);it = v2.begin();//while (it != v2.end())//{//	//cout << ++(*it) << " ";//	cout << *it << " ";//	it++;//}//erase
//删除迭代区间的数据或者迭代pos位置的数据// iterator erase (iterator first, iterator last);v2.erase(v2.begin() + 3, v2.end() - 10);it = v2.begin();while (it != v2.end()){//cout << ++(*it) << " ";cout << *it << " ";it++;}// iterator erase (iterator position);v2.erase(v2.begin() + 20);it = v2.begin();while (it != v2.end()){//cout << ++(*it) << " ";cout << *it << " ";it++;}	
}// 测试swap
void test04()
{// template <class T, class Alloc>// void swap(vector<T, Alloc>&x, vector<T, Alloc>&y);vector<int> v2(10, 1);vector<int> v3(10, 3);// 交换两个向量的空间v2.swap(v3);vector<int>::iterator it;it = v2.begin();//while (it != v2.end())//{//	//cout << ++(*it) << " ";//	cout << *it << " ";//	it++;//}
//
//reference operator[] (size_type n);const_reference operator[] (size_type n) const;for (int i = 0; i < v2.size(); i++){cout << ++v2[i]<< ' ';}}

五：vector的模拟实现

在实现vector的时候我们采用模板来实现，方便vector存取任意的类型，可以是自定义类型，也可以是内置类型，例如：vector<vector<int>>(二维数组)。

因为vector的数据结构本质是顺序表，所以我们可以设置一个顺序表来模拟实现它。

然后设置三个标志位：

private:iterator _start = nullptr;iterator _finsh = nullptr;iterator _end_of_storage = nullptr;

_start表示容器的起始位置，_finsh表示有效数据个数的最后一个位置，_end_of_storage表示容器容量的大小。

iterator使我们使用typedef将模板类型重命名的。

namespace cp
{template<class T>class vector {public:typedef T* iterator;typedef const T* const_iterator;private:iterator _start = nullptr;iterator _finsh = nullptr;iterator _end_of_storage = nullptr;};    
}

我们将我们的vector使用一个单独的命名空间CP包起来，避免跟库里面的vector冲突。

关于模板请看：C++模板初阶-CSDN博客

（一）一些简单接口的实现：

一些比较简单的接口我们就将他们放到类里面

关于容量相关的接口：

//清除数据
void clear()
{_finsh = _start;
}
//判断容器是否为空
bool empty()const 
{return _finsh == _start;
}
//获取容器容量的大小
size_t size() const 
{//指针相减得到元素个数return _finsh - _start;
}
//获取容器容量的大小
size_t capacity() const 
{return _end_of_storage - _start;
}

迭代器的实现：const迭代器和非const迭代器，反向迭代器就不实现了

几种迭代器
iterator begin()
{return _start;
}
iterator end()
{return _finsh;
}
const_iterator cbegin() const
{return _start;
}
const_iterator begin() const
{return _start;
}
const_iterator end() const
{return _finsh;
}
const_iterator cend() const
{return _finsh;
}

函数后边加const表示成员变量不可以修改。

方括号下标[ ]的重载实现：

//返回普通引用，可以修改
T& operator[](size_t pos)
{return _start[pos];
}
//返回const引用，不可以修改
const T& operator[](size_t pos)const
{return _start[pos];
}

尾删除函数

void pop_back()
{assert(!empty());--_finsh;
}

（二）一些复杂接口的实现

这些复杂的接口我们将他们放到类外面。

（1）reserve：开辟空间并检查。

template<class T>
void vector<T>::reserve(size_t n)
{if (n > capacity()){size_t old_size = size();T* tmp = new T[n];for (int i = 0; i < old_size; i++){tmp[i] = _start[i];}if (_start){delete[] _start;}_start = tmp;_finsh = _start + old_size;_end_of_storage = _start + n;}
}

注意：在更新成员变量的时候要先预存一份没交换之前的size，因为在_start和tmp交换的时候也会影响到size的改变。另外，记得释放旧空间，当然如果原来的容器是空的就不用释放了。

（2）push_back：在容器的末尾位置尾插一个数据

template<class T>
void vector<T>::push_back(const T& x)
{if (_finsh == _end_of_storage){reserve(capacity() == 0 ? 4 : 2 * capacity());}*_finsh = x;++_finsh;
}

只要是往容器里面插入数据都要检查容器是否满了，如果满了就需要先扩容再插入数据，这和数据结构的顺序表是一样的。

迭代器失效问题：

通常我们在插入和删除的时候使用的是迭代器，所以在一些情况下会导致迭代器失效，string的迭代器版本也会有这样的情况。

（1）insert：在pos迭代器位置插入数据，并且返回当前插入数据位置的迭代器。

	template<class T>typename vector<T>::iterator vector<T>::insert(iterator pos, T val){assert(pos >= _start);assert(pos < _finsh);if (_finsh == _end_of_storage){//防止pos位置因为扩容而失效size_t len = pos - _start;reserve(capacity() == 0 ? 4 : 2 * capacity());pos = _start + len;}iterator end = _finsh;while (end >= pos){*end = *(end - 1);end--;}*pos = val;_finsh++;pos++;return pos;}

知识点补充：在这里我们使用typename的原因,因为在实例化的时候编译器不知道迭代器（iterator）到底是类型还是成员变量，所以我们使用typename。（规定使用typename指定的是类型）。

在实现insert的时候我们要先扩容，但是扩容的时候原来_start指向的空间和tmp交换了

但是我们的pos位置迭代器还是原来空间的pos，原来空间交换给tmp之后随着函数结束tmp变量指向的空间销毁，pos所指向的也就是一个随机空间。当我们在挪动数据的时候，因为pos不是当前对象指向的空间位置，所以会发生一些错误，插入数据也就会导致一些问题。

解决方案：

如上述代码，我们先记录pos的相对位置，在更新_start指向的空间的之后我们也更新pos的迭代器，这样就不会发生问题了。

这是第一种迭代器失效的情况：迭代器指向的空间被释放，类似于野指针。

（2）erase：挪动覆盖删除迭代器位置的数据，返回pos位置的迭代器。

我们先实现一下这个成员函数，同样，我们将他们放到类外面。

template<class T>
typename vector<T>::iterator vector<T>::erase(iterator pos)
{assert(pos >= _start);assert(pos < _finsh);iterator start = pos;while (start < _finsh){*start = *(start + 1);start++;}_finsh--;return pos;
}

当我们删除数据之后，pos还是指向原来的位置，但是如果我们以下标的形式看待它。

例如：我们来测试一下，我们写一个vector，往里面放一些数据，删除之后使用它的迭代器来操作。

因为方便测试我们实现一个打印容器的函数模板：

	template<class Container>void print_container(const Container& con){/*auto it = con.cbegin();while (it != con.cend()){cout << *it << " ";++it;}cout << endl;*/for (auto& e : con){cout << e << " ";}cout << endl;}

//测试迭代器失效问题
void test_vaid_iterator()
{cp::vector<int> v;v.push_back(0);v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);//删除5位置的内容cp::vector<int>::iterator it = v.erase(v.begin()+3);cp::print_container(v);*it *= 10;cp::print_container(v);
}

可以看到原来位置的意义已经改变了，我们原本的位置在删除数据之后已经改变了。

（3）库里面的迭代器失效问题：Windows平台下。

我们来测试一下库里面的insert和erase。

测试函数：

（1）测试insert:

//测试迭代器失效问题
void test_vaid_iterator()
{std::vector<int> v;v.push_back(0);v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);//删除5位置的内容std::vector<int>::iterator pos = v.begin() + 3;v.insert(pos, 3);//删除pos位置的内容cp::print_container(v);//访问pos位置*pos*=10;cp::print_container(v);
}

(2)的是erase:

//测试迭代器失效问题
void test_vaid_iterator()
{std::vector<int> v;v.push_back(0);v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);//删除5位置的内容std::vector<int>::iterator pos = v.begin() + 3;cp::print_container(v);v.erase(pos);//删除pos位置的内容*pos *= 10;cp::print_container(v);
}

在vs2020中编译器会强制检查报错。在insert和erase之后是不允许访问pos位置的迭代器的。

总结：不管是自己实现的还是标准库内部实现的，在容器中（string,vector..）为了安全考虑，在insert和erase之后就不要访问pos位置的迭代器了。如果要访问就要更新迭代器。

（三）五个构造函数的模拟实现

接下来我们来实现他们的成员函数。

（1）默认构造

因为构造函数默认走初始化列表，所以我们在实现默认构造函数的时候可以这样写。

vector() = default;

因为我们在成员变量哪里给了缺省值，所以使用default关键字可以强制编译器生成默认构造。

当然，如果们没在成员变量给缺省参数的话可以自己走初始化列表：

		vector():_start(nullptr),_finsh(nullptr),_end_of_storage(nullptr){// 啥也不干，因为会自动走舒适化列表用缺省值完成初始化}

我们来测试一下：

可以看到v对象的三个成员已经被初始化完成了，都是空指针。

（2）拷贝构造函数

用一个已经存在的对象去初始化另一个刚创建的对象

template<class T>
vector<T>::vector(const vector<T>& v)
{//防止自己给自己赋值if (this != &v){reserve(v.capacity());for (auto& e : v){push_back(e);}//_finsh和_endd_of_storage是指针，不是整型，不能直接赋值，而且在reserve和push_back的时候已经更新过了，不用更新//_finsh = v._finsh;//_end_of_storage = v._end_of_storage;}
}

（3）使用n个val去初始化容器的构造

	template<class T>vector<T>::vector(size_t n, vector<T>& val){reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}

（4）迭代器区间初始化构造：

template<class input_iterator>
vector(input_iterator first, input_iterator last)
{while (first != last){push_back(*first);first++;}
}

测试：

void Test03()
{cp::vector<int> v;v.push_back(0);v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);cp::print_container(v);cp::vector<int> v4(v.begin()+2, v.begin() + 5);cp::print_container(v4);}

（5）赋值构造

因为都是自定义类型，且需要开辟空间，所以和拷贝构造一样都是深拷贝。

		//this = vvector<T>& operator=(const vector<T>& v){if (this != &v){clear();reserve(v.size());/*size_t size = v.size();T* tmp = new T[v.capacity()];for (size_t i = 0; i < size; i++){tmp[i] = v._start[i];}if (_start)delete[] _start;_start = tmp;_finsh = _start + size;_end_of_storage = _start + v.capacity();*/for (auto& e : v){push_back(e);}}return *this;}

赋值构造的现代写法：

void swap(vector<T>& v)
{std::swap(_start, v._start);std::swap(_finsh, v._finsh);std::swap(_end_of_storage, v._end_of_storage);
}
//现代写法
vector<T>& operator=(vector<T> v)
{swap(v);return *this;
}

（6）析构函数

~vector()
{if (_start)//如果_start是空（为假），则说明已经析构了，不需要析构{delete[] _start;_start = _finsh = _end_of_storage = nullptr;}
}