算法库中的find
查看文档发现vector中并没有查找的函数，是但是算法库为STL中提供了一个查找的函数，不然每一个容器都要写查找岂不是很麻烦？
模板是类模板，函数的参数使用类模板与迭代器实现的。
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { vector<int>arr; arr.push_back(1); arr.push_back(2); arr.push_back(3); arr.push_back(4); arr.push_back(5); vector<int>::iterator p = find(arr.begin(), arr.end(), 3); if(p != arr.end()) arr.insert(p, 10);//在3的位置进行头插 for (auto e : arr) { cout << e << ' '; } cout << endl; return 0; }
vector的底层小部分框架
在模拟实现string的时候，成员变量有三个，存储字符串的空间位置，此对象的字符串有效长度大小和有效空间大小。
如果去看库中实现的vector源码，我们会发现成员变量最主要的有三个：
一是start，指向了这组数的开头。
二是finish，指向有效数据的最后一个位置的下一个位置，这样与start相减就是有效数据的长度了。
三是end_of_storage，指向了有效空间的末尾。
类型是* iterator。
模拟实现vectot
模拟vector的整体代码
#include <iostream> #include <string.h> #include <assert.h> using namespace std; namespace baiye { template<class T> class vector { public: // Vector的迭代器是一个原生指针 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; } // construct and destroy vector() : _start(nullptr) , _finish(nullptr) , _endOfStorage(nullptr) { } vector(size_t n, const T& value = T()) : _start(nullptr) , _finish(nullptr) , _endOfStorage(nullptr) { reserve(n); for (size_t i = 0; i < n; i++) { push_back(value); } } vector(int n, const T& value = T())//这里有一个参数n为int类型是防止传参是两个整形，如果是size_t需要隐式类型转换 : _start(nullptr) //这会导致调用的不是这个构造函数而是带有模板的构造函数了 , _finish(nullptr) , _endOfStorage(nullptr) { reserve(n); for (size_t i = 0; i < n; i++) { push_back(value); } } template<class InputIterator> vector(InputIterator first, InputIterator last)//模板的优先级大于隐式类型转换 : _start(nullptr) , _finish(nullptr) , _endOfStorage(nullptr) { while (first != last) { push_back(*first); ++first; } } vector(const vector<T>& v) : _start(nullptr) , _finish(nullptr) , _endOfStorage(nullptr) { vector<T>gcc(v.begin(), v.end()); swap(gcc); } vector<T>& operator= (vector<T> v) { swap(v); return *this; } ~vector() { delete[] _start; _start = _finish = _endOfStorage = nullptr; } // capacity size_t size() const { return _finish - _start; } size_t capacity() const { return _endOfStorage - _start; } void reserve(size_t n) { if (n > capacity()) { T* p = new T[n]; int a = size(); if (_start) { for (int i = 0; i < a; i++) { p[i] = _start[i]; } delete[] _start; } _start = p; _finish = _start + a; _endOfStorage = _start + n; } } void resize(size_t n, const T& value = T()) { if (n > capacity()) { reserve(n); } if (n > size()) { while (_finish != _start + n) { *_finish = value; _finish++; } } else { _finish = _start + n; } } ///access/// T& operator[](size_t pos) { assert(pos < size()); return _start[pos]; } const T& operator[](size_t pos)const { assert(pos < size()); return _start[pos]; } ///modify/ void push_back(const T& x) { if (_finish == _endOfStorage) { int sum = capacity() == 0 ? 4 : 2 * capacity(); reserve(sum); } *_finish = x; _finish++; } bool empty() const { return !(_finish - _start); } void pop_back() { assert(!empty()); _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 <= _finish); assert(pos > _start); if (_finish == _endOfStorage) { int n = pos - _start; int sum = capacity() == 0 ? 4 : 2 * capacity(); reserve(sum); pos = _start + n; } iterator p1 = _finish; while (p1 > pos) { *p1 = *(p1 - 1); p1--; } *pos = x; ++_finish; return pos; } iterator erase(iterator pos) { assert(pos >= _start); assert(pos < _finish); iterator p = pos + 1; while (p < _finish) { *(p - 1) = *p; p++; } _finish--; return pos; } void clear() { _finish = _start; } private: iterator _start; // 指向数据块的开始 iterator _finish; // 指向有效数据的尾 iterator _endOfStorage; // 指向存储容量的尾 }; }
不过，在模拟vector的过程中，最致命的问题有两个。
迭代器失效问题
在实现到vector的接口insert时，我写的代码是这样的。
iterator insert(iterator pos, const T& x) { assert(pos <= _finish); assert(pos > _start); if (_finish == _endOfStorage) { int sum = capacity() == 0 ? 4 : 2 * capacity(); reserve(sum); } iterator p1 = _finish; while (p1 > pos) { *p1 = *(p1 - 1); p1--; } *pos = x; ++_finish; return pos; }
在测试的时候发现结果是这样的：
然后我进行了调试发现：
上面是最初的位置。
然后向下走，需要扩容。
