C++迈向精通：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;
// 默认大小为2
vector(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 my
int main() {
#define MAX_N 10
srand(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;
}