做企业网站必须要座机吗,网站建设黄页免费在线观看,企业网站栏目设计,在网上建设网站需要花钱么vector复现
思考过程
对于vector考虑如下几点#xff1a;
底层数据结构算法实现方式对外表现形式
这里底层的数据结构采用了顺序表#xff0c;当然#xff0c;原版STL中的vector也是采用的顺序表。 算法实现的方式放在代码中去设计 对外表现形式是数组#xff0c;因此需…vector复现
思考过程
对于vector考虑如下几点
底层数据结构算法实现方式对外表现形式
这里底层的数据结构采用了顺序表当然原版STL中的vector也是采用的顺序表。 算法实现的方式放在代码中去设计 对外表现形式是数组因此需要重载 [] 运算符。
对于sort考虑如下几点
算法快排模板类的实现方式放在代码中实现
代码
详细描述根据注释来解释。
#include cstddef
#include iostream
#include algorithm
#include cstdio
#include cstdlib
#include cmath
#include functional// 命名空间
namespace my {
template typename Tclass vector {
public:// 迭代器typedef T * iterator;// 默认大小为2vector(size_t n 2) {__size n;data (T *)malloc(sizeof(T) * __size);_Finish data __size;_M_pos data;}vector(const vector v) {__size v.__size;data (T *)malloc(sizeof(T) * __size);for (size_t i 0; i v.size(); i) {new(data i) T(v[i]); // 采用 new 的原地构造 因为有的类型并没有重载 ‘’ 运算符}_Finish data __size;_M_pos data v.size();}vector(vector v) {__size v.__size;data v.data;_M_pos v._M_pos;_Finish v._Finish;v.data v._M_pos v._Finish v._M_pos nullptr;}~vector() {if (data nullptr) return ;// free(data); 存储的数据可能都有对应的析构方法而使用free不会调用析构方法for (size_t i 0; i __size; i) {data[i].~T();}free(data);return ;}iterator begin() const { return data; }iterator end() const { return _M_pos; }T operator[](size_t ind) const { return data[ind]; }size_t size() const { return _M_pos - data; }void push_back(const T obj) {// 如果数据到最后但是没有成功扩展内存就报错退出if (_M_pos _Finish !__expand()) {std::cout expand failed! std::endl;return ;}new(_M_pos) T(obj); // 调用new的原地构造_M_pos 1;return ;}private:size_t __size;T *data;T *_M_pos, *_Finish;bool __expand() {// 重新扩展内存T *p (T *)realloc(data, sizeof(T) * __size * 2);if (p nullptr) return false;size_t offset _M_pos - data;__size * 2;data p;_M_pos data offset;_Finish data __size;return true;}
};// 三点取中法
templatetypename T, typename Func_T
T __median(T first, T medium, T last, Func_T cmp) {if (cmp(medium, first)) std::swap(medium, first);if (cmp(last, medium)) std::swap(medium, last);return medium;
}// 重载两个参数的sort
templatetypename iterator
void sort(iterator begin, iterator end) {sort(begin, end, std::lessdecltype(*(begin))());return ;
}// 三个参数的sort
templatetypename iterator, typename _Compare
void sort(iterator begin, iterator end, _Compare cmp) {if (end - begin 2) return;iterator x begin, y end - 1;typename std::remove_referencedecltype(*begin)::type z __median(*x, *(begin (end - begin) / 2), *y, cmp);do {while (cmp(*x, z)) x;while (cmp(z, *y)) y--;if (x y) {std::swap(*x, *y);x, --y;}} while (x y);y;my::sort(begin, y, cmp);my::sort(x, end, cmp);return ;
}templatetypename T
void output(T *begin, T *end) {std::cout arr : ;for (T *p begin; p end; p) {std::cout *p ;}std::cout std::endl;
}} // end of namespace myint main() {#define MAX_N 10srand(time(0));my::vectorint v1;for (int i 0; i MAX_N; i) {v1.push_back(rand() % 100);}for (auto x : v1) std::cout x ; std::cout std::endl;my::sort(v1.begin(), v1.end());for (auto x : v1) std::cout x ; std::cout std::endl;std::cout std::endl;my::vectorfloat v2;for (int i 0; i MAX_N; i) {v2.push_back(rand() % 10000 * 1.0 / 100.0);}for (auto x : v2) std::cout x ; std::cout std::endl;my::sort(v2.begin(), v2.end());for (auto x : v2) std::cout x ; std::cout std::endl;std::cout std::endl;my::vectormy::vectorint v3;for (int i 0; i 3; i) {v3.push_back(my::vectorint ());for (int j 0; j 4; j) {v3[i].push_back(0);}}my::vectormy::vectorint v4(v3);v3[1][2] 123;for (int i 0; i 3; i) {for (int j 0; j 4; j) {std::cout v3[i][j] ;}std::cout std::endl;}std::cout ----------------------- std::endl;for (int i 0; i 3; i) {for (int j 0; j 4; j) {std::cout v4[i][j] ;}std::cout std::endl;}std::cout std::endl;return 0;
}
