C++迈向精通：vector复现与sort复现

vector复现

思考过程

对于vector考虑如下几点：

• 底层数据结构
• 算法实现方式
• 对外表现形式

这里底层的数据结构采用了顺序表，当然，原版STL中的vector也是采用的顺序表。
算法实现的方式放在代码中去设计
对外表现形式是数组，因此需要重载 [] 运算符。

对于sort考虑如下几点：

• 算法（快排）
• 模板类的实现方式（放在代码中实现）

代码

详细描述根据注释来解释。

#include <cstddef>
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <functional>// 命名空间
namespace my {
template <typename T>class 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;}
};// 三点取中法
template<typename 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
template<typename iterator>
void sort(iterator begin, iterator end) {sort(begin, end, std::less<decltype(*(begin))>());return ;
}// 三个参数的sort
template<typename 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_reference<decltype(*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 ;
}template<typename 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::vector<int> 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::vector<float> 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::vector<my::vector<int>> v3;for (int i = 0; i < 3; ++i) {v3.push_back(my::vector<int> ());for (int j = 0; j < 4; ++j) {v3[i].push_back(0);}}my::vector<my::vector<int>> 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;
}