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;}
}