vector类

一、STL库 vector

1.1 vector的介绍

vector英文意思为向量：向量是表示大小可以改变的数组的序列容器。

指向其元素的常规指针上的偏移量来访问其元素，并且与数组中的效率一样高。但与数组不同，它们的大小可以动态变化，其存储由容器自动处理。

总之，vector就是一个可以动态开辟空间的任意类型的容器，可以看成一个自定义类型动态序列，支持随机访问，尾插尾删效率高。

可以通过看文档来了解：vector - C++ Reference (cplusplus.com)

这里包含allocator的可以看成无参，以后再说。

1.2vector的使用

1.2.1构造函数constructor

选择几种着重介绍

vector()（重点）

vector（size_type n, const value_type& val =value_type()）

vector (const vector& x); （重点）

vector (InputIterator first, InputIterator last);

 value_type是模版T

size_type是由 typedef 而来本质是size_t

value_type()不是一个函数，而是类似于构造，不过是对于内置类型的构造

一般它的值是0

几乎所有值的是0，包括字符对应的Ascll也是0

但是这种构造是不适合指针的；

补充完知识，现在开始看vector的构造

 值得注意的是vector的底层,它是有三个指针构成的

 分别对应指向动态开辟空间的三个指针：这个在后面的模拟实现会说到

还有一点，使用迭代器构造时，可以跨容器进行构造

 1.2.2迭代器

迭代器的作用还是为了遍历

 

 1.2.3vector 空间函数

size_type size()const; 返回大小

size_type capacity()const;返回容量

bool empty()const;判空

void resize(size_type n, value_type val=value_type());以某值初始化改容

void reserve(size_t n);扩容

就看着几个够用了

 前三个不同看了，很简单

void resize(size_type n, value_type val=value_type());

如果，n小于目前的size，那么就会保留前n个元素。移除剩下不要的元素

如果n大于size小于capacity的话，就会以某一个值扩充元素直到n==size

如果大于capacity的话就会扩容。(重新分配空间)

不举例了，已经很清楚了

void reserve(size_t n);

其实就是扩容，n大于capacity时扩容小于等于不影响。并且reserve不改变vector的元素

1.2.4vector的增删查改

增删查改都会影响到容量，大小，如果大小为0还要删就会报错

如果容量不够时，就需要扩容

举例吧！

int main()
{vector<int>vec(1, 5);cout << "扩容前" << vec.capacity() << endl;vec.push_back(1);vec.push_back(1);vec.push_back(1); vec.push_back(1);printf("打印元素:");for (auto e : vec){cout<<e<< " ";}cout <<endl<<"扩容后" << vec.capacity() << endl;vec.pop_back();	vec.pop_back();	vec.pop_back();	vec.pop_back();for (auto e : vec) { cout << e << " "; }return 0;
}

提醒：不同平台扩容机制不同，但是底层相同

 insert与string有所不同，这里是通过迭代器来insert的，最后一个函数是通过迭代器查找位置然后使用一个迭代器区间进行插入，这里支持跨容器。

vector<int>vec(10, 5);
vector<int>::iterator it = vec.begin();
vec.insert(it, 1);
for (auto& e : vec) { cout << e << " "; }
cout << endl;
//这里迭代器的位置发生了改变，所以要让它重回位置
//这里也叫做迭代器失效
it = vec.begin();
vec.insert(it, 5, 10);
for (auto& e : vec) { cout << e << " "; }

 

erase的使用也很简单

删除某个位置数据，删除某个迭代器区间位置

int main()
{vector<int>vec{1, 2, 3, 4, 5, 67, 8, 9, 10, 11, 12};for (auto& e : vec) { cout << e << " "; }cout << endl;auto it = vec.begin();vec.erase(it);for (auto& e : vec) { cout << e << " "; }cout << endl;//防止迭代器失效it = vec.begin();vec.erase(it,it+3);//左闭右开for (auto& e : vec) { cout << e << " "; }cout << endl;return 0;
}

当然，也可以接受erase的返回值，此时erase返回的就是删除元素位置的下一个元素的迭代器

 find在vector中只有全局的函数

看到它的声明，就已经理解了含义了！ 

使用迭代器确定区间，查找某一个元素

成功返回该元素的迭代器，失败返回最后一个迭代器

举例很简单

int main()
{
    vector<int>vec{ 1,23,4,6,6 };
    vector<int>::iterator it=find(vec.begin(), vec.end(), 23);
    if (it != vec.end())
    {
        cout << "找到了" << endl;
    }
    else
        cout << "没有找到" << endl;
    return 0;
}

 好吧，就是这么用。

这个就是支持随机访问吧！！

很简单的。

int main()
{
    vector<int>vec{ 1,2,3,4,5,6,7,8,9,10 };
    cout<<vec[0]<<endl;
    cout<<vec[5]<<endl;
    cout<<vec[9]<<endl;

    return 0;
}

1.2.5vector补充

vector在示例化的时候不仅可以使用内置类型实例化，还可以使用容器实例化。

vector<string> a;
vector<list<int>>b;
vector<vector<int>>c;

在进行初始化时，还有一些方式

vector<int>vec10{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

vector<int>vec1; vector<int>vec2; vector<int>vec3; vector<int>vec4; vector<int>vec5;
vector<vector<int>>vec7{ vector<int>{1,2,3,4,5},vector<int>{1,2,3,4}};
vector<vector<int>>vec6{ vec1,vec2,vec3,vec4 };
vector<vector<int>>vec8{ {1,2,3},{1,23,5} };

//这些都是为了最后一种的简化

//主要的原理还是隐式类型转换

二、vector的模拟实现

2.1代码实现

#pragma once
#include<iostream>
#include<assert.h>
namespace practice {
template<class T>
class vector {
public:typedef T*  iterator;typedef const T*  const_iterator;iterator begin(){return _start;}const_iterator begin()const{return _start;}iterator end(){return _finish;}const_iterator end() const{return _finish;}size_t size() const{return _finish - _start;}size_t capacity() const{return _end_of_storage - _start;}vector():_start(nullptr),_finish(nullptr), _end_of_storage(nullptr){}vector(size_t n,const T& val=T()){resize(n,val);}~vector(){if (_start){delete[] _start;_start = _finish = _end_of_storage = nullptr;}}//vector(const vector<T>&vec){reserve(vec.capacity());for (int i = 0; i < vec.size(); ++i){_start[i] = vec[i];}}void reserve(size_t n){if (n >capacity()){T* temp = new T[n];if (_start != nullptr){size_t oldsize = size();for (size_t i = 0; i < size(); ++i){temp[i] = _start[i];}delete[] _start;_start = temp;_finish = _start + oldsize;_end_of_storage = _start + n;}else{_start = temp;_finish = _start;_end_of_storage = _start + n;}}}void resize(size_t n,const T& val=T()){if (n <=size()){_finish = _finish - (size() - n); return;}if (n > capacity()){reserve(capacity() == 0 ? 4 : 2 * capacity());}size_t x = n - size();for (int i = 0; i < x; ++i){*_finish++ = val;}}iterator insert(iterator pos ,const T val ){assert(pos >= begin());assert(pos <=end());size_t xpos = pos - begin();if (_finish == _end_of_storage){reserve(capacity()==0?4:2 * capacity());pos = _start + xpos;}iterator it = end();while (it != pos){*(it) = *(it-1);--it;}*pos = val;return pos;}iterator erase(iterator pos){assert(pos >= begin());assert(pos < end());iterator it = pos;while (it != end()){*(it) = *(it +1);it++;}return pos;}T& front(){assert(size() > 0);return _start[0];}const T& front()const{assert(size() > 0);return _start[0];}T& back(){assert(size() > 0);return _start[size() - 1];}const T& back() const{assert(size() > 0);return _start[size() - 1];}bool empty() const{return size() == 0;}void push_back(const T& val){if (_end_of_storage == _finish){reserve(capacity() == 0 ? 4 : 2 * capacity());}*_finish++ = val;}void pop_back(){assert(size() > 0);_finish--;}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=(vector<T> v){swap(v);return *this;}T& operator[](size_t i){assert(i < size());return _start[i];}const T& operator[](size_t i) const{assert(i < size());return _start[i];}
private:T *_start;T *_finish;T *_end_of_storage;
};
template<typename container>
void print_container(const container& con)
{for (auto& e : con){std::cout << e <<" ";}std::cout << std::endl;
}
}

2.2 注意事项

1. vector类的迭代器，无需封装，就是模版类型指针。

2.在进行扩容时，会涉及到异地扩容，如果vector的模版类型是内置类型，使用memcpy没有错，但是如果是自定义类型就会发生内容丢失，因为删除旧空间时，就有可能把自定义类型指向的资源删除，但是memcpy不会深拷贝

3.在未实例化模版内找类型时，可能会报错，要加上typename,让编译器认为是类型

4.使用mecpy的拷贝问题，这是一个浅拷贝的问题。使用memcpy拷贝内置内型没有问题

但是使用它拷贝自定义类型时，是浅拷贝，会造成数据丢失。