C++vector及其实现

第一个参数是类型(可以是自定义也可以是内置类型)   

相当于生成一个该类型的数组    

allocator是空间配置器

遍历

1.下标遍历

2.迭代器遍历

3.范围for

对象访问

有名对象访问

匿名对象访问

隐式类型转换

成员函数

sort

使用sort需要包含头文件algorithm

eg.

sort的使用非常灵活,只需要在前两个参数限定范围就可以实现范围排序

eg.

最后面的参数是仿函数,是用来进行数据比较的

使用sort默认是升序,如果要降序,可以

greater就是重载">"运算符

同时sort也可以用来排序自定义类型,但是需要自行重载">"和"<",或者自行写仿函数

insert

finish指向最后有效数据的后一位

迭代器失效

经过扩容后会导致迭代器失效

因为扩容本质是开一段新的空间,而pos还是指向旧的已经被释放的空间,则pos是野指针

因此如果要再次使用迭代器,需要堆迭代器进行更新

erase

erase之后,我们通常认为迭代器失效

因为删除数据后,较小可能存在缩容,导致空间改变

导致迭代器失效

就算不缩容,如果删除最后一个数据

此时再去访问迭代器,就是一种越界访问

因此我们认为erase后迭代器失效

对于失效的迭代器,vs做了强制的检查,防止迭代器失效

eg.

错误:

正确:

find

除去string,其他的类型的find函数被包在算法头文件algorithm中

find函数返回该数据的位置,如果没找到就返回最后一个位置

拷贝构造

没有写拷贝构造编译器会默认生成拷贝构造,

默认的浅拷贝拷贝构造可以实现拷贝,但是无法实现赋值

构造函数

1.

2.

eg.

多参数构造的隐式类型转换

initializer list

它是一个类模板

它是一个常量数组,其中存在两个指针,指向数组的开始和结束

初始化方式

string数组的问题

尾插1次后

没有问题

但是,再多push_back后

起初有4块空间,memcpy对任意类型都是浅拷贝

reserve后,由于是浅拷贝

新旧空间指向同一空间

但是由于reserve是释放旧空间

导致旧空间被释放,导致前4组指针是野指针

解决方法

1.写深拷贝

模拟实现

#pragma once
#include<assert.h>
namespace bit 
{template<class T>class vector{public:typedef T* iterator;iterator begin(){return _start;}iterator end(){return _finish;}//类模板的成员函数//函数模板--目的是支持任意容器的迭代器区间初始化template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}vector(size_t n, const T& val = T())//缺省值给T()(匿名对象)初始化,适用于任何类型{reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}vector(initializer_list<T> il){reserve(il.size());for (auto e : il){push_back(e);}}//强制编译器生成默认的构造函数vector() = default;vector(const vector<T>& v){reserve(v.capacity());for (auto e : v){push_back(e);}}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_capacity, v._capacity);}vector<T>& operator=(vector<T> v){this->swap(v);return *this;}void reserve(size_t n)//参数为需要扩为多大{if (n > capacity()){size_t oldsize = size();T* tmp = new T[n];if (_start){/*memcpy(tmp, _start, sizeof(T) * size());*/for (size_t i = 0; u < oldsize; i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + oldsize;_end_of_storage = _start + n;}}size_t capacity(){return _end_of_storage - _start;}size_t size(){return _finish - _start;}T& operator[](size_t i){assert(i < size());return _start[i];}void push_back(const T& x){if (_finish == _end_of_storage){size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);}*_finish = x;++_finish;}void pop_back(){assert(size() > 0);--_finish;}iterator insert(iterator pos, const T& x){assert(pos >= _start);assert(pos <= _finish);if (_finish == _end_of_storage){size_t len = pos - _start;size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;}void erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator it = pos + 1;while (it != _finish){*(it - 1) = *it;++it;}--_finish;}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;};void test_vector1(){bit::vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.insert(v1.begin() + 1, 2005);//for (size_t i = 0; i < v1.size(); i++)//{//	cout << v1[i] << " ";//应该用不了,但是在test中上面展开了包含了头文件,所以可以用//}//cout << endl;v1.erase(v1.begin());for (auto e : v1){cout << e << " ";}cout << endl;//vector<int>::iterator it = v1.begin();//while (it != v1.end())//{//	cout << *it << " ";//	++it;//}//cout << endl;}
}