【STL】vector介绍（附部分接口模拟实现）

1.介绍

​ vector容器是一种大小可变的序列容器，可以看作一个动态数组，其采用连续的存储空间来存储元素，允许动态插入和删除元素，可以自动管理内存空间，当需要的内存空间大小大于当前内存空间大小时，会自动分配一个更大的新的数组，将全部元素转移过来，其也具备可迭代性。

2.使用

​ 同样，在使用上，这里只介绍一些经常使用的接口函数。

2.1 vector的构造

1.定义

构造函数声明	说明
vector()	无参构造
vector(size_type n,const value_type& val = value_type())	构造并用n个val初始化
vector(const vector& x)	拷贝构造
vector(InputIterator first, InputIterator last)	使用迭代器进行初始化构造

2.使用

#include <iostream>
#include <vector>//包含头文件using namespace std;template<typename T>
void PrintVector(vector<T>& v)
{for (auto e : v){cout << e << " ";}cout << endl;
}void test1()
{//vector的构造 <>中的类型可以修改vector<int> v1;//无参构造vector<int> v2(10, 2);//用10个2初始化构造vector<int> v3(v2);//用v2拷贝构造vector<int> v4(v2.begin() + 1, v2.end() - 1);//迭代器构造从v2的begin() + 1到end() - 1位置PrintVector(v1);PrintVector(v2);PrintVector(v3);PrintVector(v4);
}int main()
{test1();return 0;
}

结果如下：

2.2 vector空间相关接口

2.2.1 size()

1.声明及作用：

声明	作用
size_type size() const;	获取有效数据个数

2.使用：

void test2()
{vector<int> nums({ 1,2,3,4,5,6 });size_t nums_len = nums.size();cout << nums_len << endl;//6
}int main()
{test2();return 0;
}

2.2.2 capacity()

1.声明及作用：

声明	作用
size_type capacity() const;	获取空间容量大小

2.使用：

void test3()
{vector<int> nums;size_t capacity = nums.capacity();//使用for (size_t i = 1; i <= 100; i++){nums.push_back(1);//尾插100个1size_t new_capacity = nums.capacity();//使用//如果空间容量大小发生变化，打印新的大小if (new_capacity != capacity){capacity = new_capacity;cout << capacity << endl;}}
}
int main()
{test3();return 0;
}输出结果为：
1
2
3
4
6
9
13
19
28
42
63
94
141

​ 这里我们通过尾插100个1顺便观察VS下vector的扩容规律：其capacity是按1.5倍增长的，注：在不同的环境下vector的增容不一定相同，比如：在Linux g++下其可能是按2倍扩容。

2.2.3 empty()

1.声明及作用：

声明	作用
bool empty() const;	判断该vector是否为空

2.使用：

void test4()
{vector<int> v1;if (v1.empty()){cout << "v1是空的" << endl;}else{cout << "v1是非空的" << endl;}vector<int> v2{1,2,3,4};if (v2.empty()){cout << "v2是空的" << endl;}else{cout << "v2是非空的" << endl;}
}
int main()
{test4();return 0;
}
输出：
v1是空的
v2是非空的

2.2.4 resize()

1.声明及作用：

声明	作用
void resize (size_type n, value_type val = value_type())；	指定vector有效size大小为n,当n大于当前 vector的大小时，resize()会在vector末尾添加新元素val,不填val则为默认值。当n小于当前vector的大小时，resize()会移除vector末尾的元素，使vector的大小变为n。

2.使用：

template<typename T>
void PrintVector(vector<T>& v)
{for (auto e : v){cout << e << " ";}cout << endl;
}void test5()
{vector<int> v;v.resize(10, 1);//n=10>当前size,在末尾添加10个val = 1;PrintVector(v);//打印vv.resize(20);//n=20>当前size,在末尾添加10个val,默认为0;PrintVector(v);v.resize(5);//n=5<当前size,从末尾移除元素直至size=5PrintVector(v);
}
int main()
{test5();return 0;
}

结果如下：

2.2.5 reserve()

1.声明及作用：

声明	作用
void reserve (size_type n);	预先分配至少能容纳数量为n的内存空间，它会增加vector的capacity但不会改变有效元素的数量size

2.使用：

void test6()
{vector<int> v;cout << "before reserve'size:" << v.size() << endl;cout << "before reserve'capacity:" << v.capacity()<< endl;v.reserve(20);cout << "after reserve'size:" << v.size() << endl;//不改变sizecout << "after reserve'capacity:" << v.capacity() << endl;//增加capacity
}
int main()
{test6();return 0;
}

结果如下：

​ 当我们知道需要大概多少的空间大小时，我们可以通过reserve提前开辟空间以缓解vector增容的代价。

2.3 vector的增删查改

2.3.1 push_back()

1.声明及作用

声明	作用
void push_back (const value_type& val);	尾插val

2.使用：

template<typename T>
void PrintVector(vector<T>& v)
{for (auto e : v){cout << e << " ";}cout << endl;
}void test7()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);PrintVector(v);//1 2 3 4 5
}
int main()
{test6();return 0;
}

2.3.2 insert()

1.声明及作用

声明	作用
iterator insert (const_iterator position, const value_type& val);	在position位置的值前插入val
iterator insert (const_iterator position, size_type n, const value_type& val);	在position位置的值前插入n个val

2.使用：

template<typename T>
void PrintVector(vector<T>& v)
{for (auto e : v){cout << e << " ";}cout << endl;
}
void test8()
{vector<int> v;v.insert(v.begin(), 1);//在起始位置前插入1（相当于头插）PrintVector(v);//1v.insert(v.end(), 2);//在结束位置前插入1（相当于尾插）PrintVector(v);//1 2v.insert(v.begin() + 1, 5, 3);//在begin()+1位置前插入5个3PrintVector(v);//1 3 3 3 3 3 2
}
int main()
{test8();return 0;
}

2.3.3 pop_back()

1.声明及作用

声明	作用
void pop_back();	尾删

2.使用

template<typename T>
void PrintVector(vector<T>& v)
{for (auto e : v){cout << e << " ";}cout << endl;
}
void test9()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);PrintVector(v);//1 2 3 4 5v.pop_back();//尾删PrintVector(v);//1 2 3 4v.pop_back();PrintVector(v);//1 2 3v.pop_back();PrintVector(v);//1 2v.pop_back();PrintVector(v);//1v.pop_back();PrintVector(v);//
}
int main()
{test9();return 0;
}

2.3.4 erase()

1.声明及作用

声明	作用
iterator erase (const_iterator position);	删除position位置的值
iterator erase (const_iterator first, const_iterator last);	从first位置开始删到last位置前（左闭右开）

2.使用

void test10()
{vector<int> v;for (int i = 1; i <= 10; i++){v.push_back(i);}PrintVector(v);//1 2 3 4 5 6 7 8 9 10v.erase(v.begin() + 5);//删除begin()+5位置的值（6）PrintVector(v);//1 2 3 4 5 7 8 9 10v.erase(v.begin() + 1, v.end() - 1);PrintVector(v);//1 10
}
int main()
{test10();return 0;
}

2.3.5 swap()

1.声明及作用

声明	作用
void swap (vector& x);	交换两个vector的数据空间

2.使用

template<typename T>
void PrintVector(vector<T>& v)
{for (auto e : v){cout << e << " ";}cout << endl;
}
void test11()
{vector<int> v1(5, 1);vector<int> v2(10, 2);cout << "before swap v1:";PrintVector(v1);cout << "before swap v2:";PrintVector(v2);v1.swap(v2);//交换v1和v2cout << "after swap v1:";PrintVector(v1);cout << "after swap v2:";PrintVector(v2);
}
int main()
{test11();return 0;
}

结果如下：

2.3.6 operator[]

1.声明及作用

声明	作用
reference operator[] (size_type n);	用于非const对象，返回vector中索引为n的值，可进行读取和修改
const_reference operator[] (size_type n) const;	用于const对象，返回vector中索引为n的值，只能进行读取

2.使用

void test12()
{//非const对象vector<int> v1;for (int i = 1; i <= 10; i++){v1.push_back(i);}for (int i = 0; i < 10; i++){cout << v1[i] << " ";//读取索引为i的值}cout << endl;for (int i = 0; i < 10; i++){++v1[i];//修改索引为i的值}for (int i = 0; i < 10; i++){cout << v1[i] << " ";}cout << endl;//const对象const vector<int> v2(10, 2);for (int i = 0; i < 10; i++){cout << v2[i] << " ";//读取索引为i的值}cout << endl;//for (int i = 0; i < 10; i++)//{//	++v2[i];//不允许修改//}
}
int main()
{test12();return 0;
}

结果如下：

注：关于查找find()

​ 在vector中没有单独添加find()的接口函数，可以使用算法板块的查找操作，这里举个例子：

void test13()
{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);v.push_back(7);PrintVector(v);//1 2 3 4 5 6 7v.insert(find(v.begin(),v.end(),4), 5, 3);//通过find从v的begin到end区间找到4，并返回4的位置，在该位置前插入5个3PrintVector(v);//1 2 3 3 3 3 3 3 4 5 6 7
}
int main()
{test13();return 0;
}

2.4 其它

2.4.1 at()

1.作用：返回索引值位置的值，对于非const对象可以进行读取和修改，对于const对象只能读取

2.使用：

void test14()
{vector<int> v1{1,2,3,4,5};cout << v1.at(0) << endl;//1++v1.at(0);cout << v1.at(0) << endl;//2const vector<int> v2{1,2,3,4,5};cout << v2.at(2) << endl;//3//++v2.at(2);   const对象  不允许修改
}
int main()
{test14();return 0;
}

2.4.2 front()和back()

1.作用：front()返回容器中的首元素，back()返回容器中的末尾元素

2.使用：

void test15()
{vector<int> v{ 1,2,3,4,5,6 };cout << "front():" << v.front() << endl;//front():1cout << "back():" << v.back() << endl;//back():6
}int main()
{test15();return 0;
}

3.部分接口的模拟实现

​ 这里仅给出代码，不做详细介绍，有任何问题欢迎提出讨论。

#pragma once
#include <iostream>
#include <assert.h>
using namespace std;namespace myVector
{template<class T>class vector{public:// Vector的迭代器是一个原生指针typedef T* iterator;typedef const T* const_iterator;// construct and destroyvector(){}/*vector(size_t n, const T& value = T()){resize(n, value);}*//*vector(int n, const T& val = T()){resize(n, val);}*/vector(int n, const T& value = T()){assert(n >= 0);reserve(n);for (int i = 0; i < n; i++){_start[i] = value;}_finish = _start + n;}vector(size_t n, const T& value = T()){reserve(n);for (int i = 0; i < n; i++){_start[i] = value;}_finish = _start + n;}vector(const vector<T>& v){reserve(v.capacity());for (const auto& e : v){push_back(e);}}template <class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}/*vector(const vector<T>& v){_start = new T[v.capacity()];memcpy(_start, v._start, v.size()* sizeof(T));_finish = _start + v.size();_endofstorage = _start + v.capacity();}*//*vector<T>& operator=(vector<T> v){swap(v);return *this;}*/vector<T>& operator=(vector<T> v){T* tmp = new T[v.size()];if (v._start){for (int i = 0; i < v.size(); i++){tmp[i] = v[i];}}_start = tmp;_finish = _start + v.size();_endOfStorage = _start + v.capacity();return *this;}~vector(){if (_start){delete[] _start;_start = nullptr;_finish = nullptr;_endOfStorage = nullptr;}}iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}// capacitysize_t size() const{return _finish - _start;}size_t capacity() const{return _endOfStorage - _start;}void reserve(size_t n){if (n > capacity()){size_t old = size();T* tmp = new T[n];if (_start){for (size_t i = 0; i < old; i++){tmp[i] = _start[i];}}delete[] _start;_start = tmp;_finish = _start + old;_endOfStorage = _start + n;}}void resize(size_t n, const T& value = T()){if (n > capacity()){reserve(n);while (_finish < _start + n){*_finish = value;++_finish;}}else{_finish = _start + n;}}T& operator[](size_t pos){return _start[pos];}const T& operator[](size_t pos)const{return _start[pos];}void push_back(const T& x){if (_finish == _endOfStorage){size_t new_capacity = capacity() == 0 ? 4 : capacity() * 2;reserve(new_capacity);}*_finish = x;++_finish;}void pop_back(){assert(size() > 0);--_finish;}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endOfStorage, v._endOfStorage);}iterator insert(iterator pos, const T& x){assert(pos >= _start && pos <= _finish);if (_finish == _endOfStorage){size_t len = pos - _start;size_t new_capacity = capacity() == 0 ? 4 : capacity() * 2;reserve(new_capacity);pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;}iterator erase(iterator pos){assert(pos >= _start && pos <= _finish);iterator it = pos + 1;while (it < _finish){*(it - 1) = *it;++it;}--_finish;return pos;}private:iterator _start = nullptr; //指向数据块的开始iterator _finish = nullptr; //指向有效数据的尾iterator _endOfStorage = nullptr; //指向存储容量的尾};void print_vector(const vector<int>& v){for (auto e : v){cout << e << " ";}cout << endl;}
}