C++:STL:vector类常用函数介绍(附加部分重要函数模拟实现)

cplusplus.com/reference/vector/vector/https://cplusplus.com/reference/vector/vector/

vector在实际中非常的重要，在实际中我们熟悉常见的接口就可以，有了string的基础，vector其实大体使用方法上二者是类似的：

这里我们先给出我们简单模拟实现时所用的成员函数：

private:iterator _start;iterator _finish;iterator _end_of_storage;

下文在介绍与string实现方式基本相同的地方，或者用法与string中相同函数基本一致的地方，均会直接以表格加实现代码的方式进行介绍，以便于我们重点介绍vector中我们需要了解的两个新知识：迭代器失效和更深层次的深浅拷贝问题。 

一，vector的定义

1.1(constructor)构造函数声明

cplusplus.com/reference/vector/vector/vector/https://cplusplus.com/reference/vector/vector/vector/其中我们需要重点掌握的是以下几个构造函数：

以下是我们的简单实现代码：

template<class T>
class vector
{
public:	vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){}template<class InputIterator>vector(InputIterator first, InputIterator last):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){assert(first && last);InputIterator itor = first;for (; itor < last; itor++){push_back(*itor);}}vector(size_t n, const T& value = T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){resize(n, value);}vector(const vector<T>& v):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){reserve(v.capacity());_finish = _start + v.size();for (size_t i = 0; i < size(); i++){(*this)[i] = v[i];}}vector<T>& operator=(vector<T> v){swap(this, v);return *this;}
}

其中的swap,push_back,resize以及reserve与string中的功能基本一样，我们后面在来介绍实现它们， 这里我们先不管它们如何实现。我们要重点说的是这里拷贝构造时遇到的深浅拷贝问题，这里先埋个伏笔。

1.2vector iterator 的使用

cplusplus.com/reference/vector/vector/begin/

cplusplus.com/reference/vector/vector/end/

 cplusplus.com/reference/vector/vector/rbegin/

 cplusplus.com/reference/vector/vector/rend/

typedef T* iterator;
typedef const T* const_iterator;
//iterator
iterator begin()
{return _start;
}iterator end()
{return _finish;
}const_iterator begin()const
{return _start;
}const_iterator end()const
{return _finish;
}

二，vector 空间增长问题 

cplusplus.com/reference/vector/vector/size/ 

cplusplus.com/reference/vector/vector/capacity/

cplusplus.com/reference/vector/vector/empty/

cplusplus.com/reference/vector/vector/resize/

cplusplus.com/reference/vector/vector/reserve/

 

size_t size()const
{return _finish - _start;
}size_t capacity()const
{return _end_of_storage - _start;
}
void resize(size_t n, const T& pos = T())
{while (size() < n){push_back(pos);}if (n <= size())_finish = _start + n;
}

接下来的reserve我们需要单独拎出来讲，先来看下我们在实现string的reserve时的模拟实现代码：

void string::reserve(size_t n)
{if (n > _capacity){char* tmp = new char[n + 1] {'\0'};strcpy(tmp, _str);delete[] _str;_str = tmp;_capacity = n;}
}

从string的模拟实现我们第一时间会想到去用memcpy来完成对n>capacity时的数据拷贝。当然，这种方法对于我们所有的内置类型都没有问题，比如vector<int>,vector<char>等等， 但如果是vector<string>这种成员元素是标准库类型的数据呢， 如果我们只是简单的去拷贝每一个字节，其实是对每一个元素的浅拷贝，就像这样：

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

很明显的问题，接下来tmp中的string对象都会指向一块随即空间，也就是它们中的成员指针全部成了野指针。直接就会报错，解决方法其实也很简单，我们只需要改用for循环去拷贝数据即可，虽然会些许浪费时间，但是是我们简单模拟时一种较好的解决方法：

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

 除此之外，需要注意的点还有：

1.capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。
2.reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代
价缺陷问题。
3.resize在开空间的同时还会进行初始化，影响size。

三，vector 增删查改 

 cplusplus.com/reference/vector/vector/reserve/

cplusplus.com/reference/vector/vector/push_back/

 cplusplus.com/reference/vector/vector/pop_back/

cplusplus.com/reference/algorithm/find/?kw=find

cplusplus.com/reference/vector/vector/insert/

cplusplus.com/reference/vector/vector/erase/

cplusplus.com/reference/vector/vector/swap/

 cplusplus.com/reference/vector/vector/operator[]/

//access
T& operator[](size_t i)
{assert(i < size());return _start[i];
}const T& operator[](size_t i)const
{assert(i < size());return _start[i];
}//modify
void push_back(T n)
{if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = n;_finish++;	
}void pop_back()
{assert(size());_finish--;
}void swap(vector<T>& v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_sstorage);
}

 

TIPS:迭代器失效问题

（注意：Linux下，g++编译器对迭代器失效的检测并不是非常严格，处理也没有vs下极端。）

这里我们借助insert与erase来介绍：

iterator insert(iterator pos, const T& x){assert(pos >= _start && pos <= _finish);if (_finish == _end_of_storage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator itor = _finish;while (itor >= pos){*(itor + 1) = *itor;--itor;}*pos = x;_finish++;return pos;
}iterator erase(iterator pos)
{assert(pos >= _start && pos < _finish);iterator itor = pos;while (itor < _finish - 1){*pos = *(pos + 1);}_finish--;return pos;
}

这里给出insert与erase主要是为了便于我们去对照vs与linux下实现代码的差异，下面我们来看第一种失效：

1.扩容引起的野指针：

我们来看下面一组例子：

void test_vector3()
{ELY::vector<int> v1;//ELY是我实现的vector所在的命名空间v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);//v1.push_back(4);for (auto e : v1){cout << e << " ";}cout << endl;int x;cin >> x;auto it = find(v1.begin(), v1.end(), x);if (it != v1.end()){v1.insert(it, 10 * x);cout << *it << endl;}for (auto e : v1){cout << e << " ";}cout << endl;
}

这串代码在vs下的运行结果如下图：

显然此时我们的it已经失效，因为扩容后，it如果没有更新，此时it指向的空间已经被释放了，导致it迭代器成了野指针，致使迭代器失效。

2.删除数据导致数据的挪动致使迭代器失效

void test_vector4(){std::vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (auto e : v1){cout << e << " ";}cout << endl;int x;cin >> x;auto it = find(v1.begin(), v1.end(), x);if (it != v1.end()){v1.erase(it);cout << *it << endl;}}

 vs下面会直接报错：

g++ 下面正常运行：

再来看这样一组例子，删除数据中的所有偶数：

void test_vector4()
{std::vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (auto e : v1){cout << e << " ";}cout << endl;auto it = v1.begin();while (it != v1.end()){if (*it % 2 == 0)v1.erase(it);++it;}for (auto i : v1){cout << i << ' ';}cout << endl;
}

vs下面还是直接报错:

 

g++上面运行：

这里直接端错误。

换一组数据我们会发现偶数并没有被删干净。

///

从上述三个例子中可以看到：SGI STL中，迭代器失效后，代码并不一定会崩溃，但是运行
结果肯定不对，如果it不在begin和end范围内，肯定会崩溃的。

所以我们在使用迭代器的时候，一定要注意迭代器失效的问题，要及时更新我们的迭代器。

迭代器失效解决办法：在使用前，对迭代器重新赋值即可。