共计 8035 个字符，预计需要花费 21 分钟才能阅读完成。
1.vector 类的实现
重要构造定义：
template<class T>
class myVector{
public:
typedef T value_type;// 元素类型 起别名
typedef value_type* pointer;//
typedef value_type* iterator;// 迭代器
typedef value_type& reference;// 援用
typedef const value_type* const_pointer;// 常量指针
typedef const value_type& const_reference;// 常量援用
typedef size_t size_type;// 数据类型根本尺寸大小
private:
iterator start;
iterator finish;
iterator end_of_storage;供类外部以及派生类应用：
protected:
// 调配空间并填充初始值, 不返回任何值
void __allocate_add_fill(size_type n, const T& value){iterator result = (iterator)malloc(n*sizeof(T));
if (result){//result!=0 申请内存胜利，在失去的内存上创建对象
start = result;
end_of_storage = start + n;
finish = end_of_storage;
while (n--){
// 指针偏移，进行赋值
construct(result, value);// 在内存上，一个个的进行结构对象
++result;
}
}
else{
cout << "内存不足，程序终止！" << endl;
exit(0);
}
}// 调配空间 从 first 开始复制 n 个值到新空间中, 并返回新开拓的空间的首地址
iterator __allocate_and_copy(iterator first, size_type n){
// 内存申请
iterator result = (iterator)malloc(n*sizeof(T));
iterator _start = result;
if (0 != result){while(n--){construct(result, *first);
++result;
++first;
}
cout << endl;
}
else{
cout << "内存不足，程序终止！" << endl;
exit(0);
}
return _start;
}// 将 first 到 last 迭代器之间 (first,last) 的元素拷贝到_start 开始的内存中, 并返回 指向 拷贝完所有数据之后最初一个数据的下一个地位的指针
iterator __copy(iterator first, iterator last, iterator _start){while (first < last){*_start++ = *first++;}
return _start;
}// 将 first 到 last 迭代器之间 (first,last) 的元素从新赋值
iterator __fill(iterator first, iterator last, const T& value){while (first < last){*first++ = value;}
return first;
}// 本人写的 从迭代器 first 开始填充 n 个值为 value 的元素
iterator __fill_n(iterator first, size_type n, const T& value){while (n--){*first++ = value;}
return first;
}
// 本人写的 将从 [first,last)所有元素 一一顺次后移，最初的一个元素移到 end 的地位
void __backCopy(iterator first, iterator last, iterator end){while (last >= first){ //
*end-- = *last--;
}
}
供内部应用的接口：
public:
// 返回首元素指针
iterator begin(){ return start;}
const iterator begin() const { return start;}
// 返回尾元素下一个地位的指针
iterator end(){ return finish;}
const iterator end() const{ return finish;}
//------------------
// 取元素 本人写
T front(){ return *begin(); }// 取 vector 中第一个元素
T back(){ return *(end() - 1); }// 取 vector 中最初一个元素
// 容器大小
size_type size() const{ return (size_type)(end() - begin()); }
// 容器的理论大小
size_type capacity() const{ return (end_of_storage - begin()); }
// 判断容器是否为空
bool empty(){ return begin() == end();}
// 默认构造函数
myVector() :start(NULL), finish(NULL), end_of_storage(NULL){cout << "默认构造函数，不调配空间" << endl;}
// 构造函数重载
myVector(size_type n, const T& value){__allocate_add_fill(n, value); }
myVector(int n, const T&value){__allocate_add_fill(n, value); }
myVector(long n, const T&value){__allocate_add_fill(n, value); }
myVector(size_type n){__allocate_add_fill(n, T()); }//??? T()??
myVector(int n){__allocate_add_fill(n, T()); }
myVector(long n){__allocate_add_fill(n, T()); }// 元素操作
// 删除最初一个元素
void pop_back(){if (!empty()){
--finish;
destroy(finish);
}
}
// 删除指定地位上的元素，并返回指向删除元素的迭代器
iterator erase(iterator position){if (position > begin() && position < end()){__copy(position + 1, finish, position);
}
destroy(finish);
--finish;
return position;
}// 删除指定范畴的元素 并返回 迭代器返回的元素
iterator erase(iterator first, iterator last){if (first > begin() && first < last && last < end()){iterator iter = __copy(last, finish, first);
destroy(iter, finish);
finish -= (last - first);
return first;
}
}
// 革除全副元素
void clear(){erase(begin(), end());
}
push_back 函数：
// 在 vector 容器的前面增加一个元素，值为 value
void push_back(const T& value){if (finish != end_of_storage){// 如果新退出元素后，空间够用的话
construct(finish, value);
++finish;
}
else{// 如果新退出元素之后 空间不够用的话
// 重新分配空间
const size_type old_size = size();
const size_type new_size = (old_size == 0) ? 1 : 2 * old_size;// 如果原空间为 0，则配置 1 的大小，如果原空间不为 0，则配置原空间二倍大小的新空间到新的地址
iterator new_start = (iterator)malloc(new_size*sizeof(T));
iterator new_finish = new_start;// 开始时，未拷贝前，完结地位等于起始地位
iterator new_capacity = new_start + new_size;
// 内存调配要具备原子性，即：要么全副胜利，要么全副失败
try{//1: 将原空间的全副元素拷贝到新空间 2: 为新的元素设定初始值 3: 调整 new_finish
for (iterator it = begin(); it < end(); ++it){//1: 将原空间的全副元素拷贝到新空间
construct(new_finish, *it);
}
construct(new_finish, value);//2: 为新的元素设定初始值
++new_finish;//3: 调整 new_finish
}
catch (...){// 如果内存调配失败了
destroy(new_start, new_finish);
free(new_start);// 删除申请到的内存
new_start = NULL;
new_finish = NULL;
throw("从新分配内存失败！");
}
destroy(begin(), end());// 析构，并开释原 vector
free(start);// 删除原 vector 的内存
start = new_start;// 更改迭代器，指向新的 vector
finish = new_finish;
end_of_storage = new_start + new_size;
}
}insert 函数：
// 插入 在值为 value 的一个元素到 position 的地位上
void insert(iterator position, const T& value){insert(position, 1, value);
}
// 在 position 地位之后，插入 n 的值为 value 的元素
void insert(iterator position, size_type n, const T& value){if (n == 0)return;
if ((end_of_storage - finish) >= n){// 备用空间够插入 n 个新元素
T x_copy = value;
const size_type size_from_position_to_end = finish - position;
iterator old_finish = finish;
if (size_from_position_to_end > n){
// 先从 pos 到 oldfinish 拿出后 n 个数，放到前面
// 再将 pos 到剩下的几个数向后挪动到 oldfinish
// 插入 n 个 value 到 pos->pos+n
__copy(finish - n, finish, finish);
finish += n;
__backCopy(position, old_finish - n, old_finish);
__fill(position, position + n, x_copy);
}
else{
// 在前面先插入多的 value，而后再将 pos 到 oldfinish 的拿进去插到前面
// 而后将剩下的 value 放到 pos 到 oldfinsh
__fill_n(finish, n - size_from_position_to_end, x_copy);
finish += n - size_from_position_to_end;
__copy(position, old_finish, finish);
finish += size_from_position_to_end;
__fill(position, old_finish, x_copy);// 在
}
}
else{
// 从新申请空间
const size_type old_size = size();
size_type _max = 0;
if (old_size > n) _max = old_size;
else _max = n;
const size_type len = old_size + _max;
iterator new_start = (iterator)malloc(len * sizeof(T));
iterator new_finish = new_start;
// 内存的调配要有原子性，即: 要么全副胜利，要么全副失败。try{new_finish = __copy(begin(), position, new_start);//1. 将原内容 至 position 的所有元素(不蕴含 position) 拷贝到新的 vector
new_finish = __fill_n(new_finish, n, value);//2. 将 position 地位到前面的 n 个元素都填充为 value
new_finish = __copy(position, end(), new_finish);//3. 拷贝从 position 地位到 end()地位的原 vector 的所有残余元素}
catch (...)// 如果失败了
{destroy(new_start, new_finish);
free(new_start);// 删除申请到的内存
new_start = new_finish = NULL;
throw; // 抛出异样
}
// 析构并开释原 vector
destroy(begin(), end());
// 删除内存
free(start);
// 调整迭代器，指向新的 vector
start = new_start;
finish = new_finish;
end_of_storage = new_start + len;
}
}// 重载操作符
reference operator[](size_type n){return *(begin() + n); }// 取 第 n 个元素
const_reference operator[](size_type n) const{return *(begin() + n); }
// 两个容器是否相等（每个元素）bool operator==(const myVector&v){if (v.size() != size())return false;
iterator it;
for (it = v.begin(); it < v.end(); ++it){if (*it != *(begin() + (it - v.begin()))) break;
}
// 比拟到了最初就齐全相等
if (it == v.end()) return true;
else return false;
}
bool operator!=(const myVector&v){return !(operator==(v));
}
};2. 自定义函数
#pragma once
template<class T1, class T2>
inline void construct(T1 *p, const T2 &value){new (p)T1(value); // 用 placement new 在所指对象上创立一个对象，value 是初始化对象的值
}
template<class T>
inline void destroy(T* pointer){// 只做了一层包装，将指针所指的对象析构 -- 通过间接调用类的析构函数
pointer->~T();}
template<class ForwardIterator>
inline void destroy(ForwardIterator first, ForwardIterator last){//destroy 的泛化版 承受两个迭代器为参数
for (; first < last; ++first){destroy(&*first);// 得 了解一下 &*
}
}
inline void destroy(char*, char*){};// 针对 char* 的特化版
inline void destroy(wchar_t*, wchar_t*){};// 针对 wchar_t* 的特化版3. 测试代码
void display(const myVector<int> &v){for (myVector<int>::iterator it = v.begin(); it != v.end(); ++it){cout << *it << " ";}
cout << endl;
}
void test(){
cout << "test--------" << endl;
myVector<int> v(100);
v.push_back(10);
v.push_back(9);
v.push_back(8);
v.push_back(7);
v.push_back(6);
v.push_back(5);
for (int i = 0; i < v.size(); ++i)
cout << v[i] << " ";
cout << endl;
myVector<int>::iterator it;
for (it = v.begin(); it != v.end(); ++it){cout << *it << " ";}
cout << endl;
cout << "size:" << v.size() << endl;}void test1(){
cout << "test1--------" << endl;
myVector<int> v(100);
v.push_back(10);
v.push_back(9);
v.push_back(8);
v.push_back(7);
v.push_back(6);
v.push_back(5);
myVector<int>::iterator it = v.begin() + 3;
v.insert(it, 3, 300); display(v);
v.insert(it, 4, 500); display(v);
v.insert(it, 2, 200); display(v);
v.insert(it, 2, 20); display(v);
v.insert(it, 3, 30); display(v);
v.insert(it, 4, 40); display(v);
}void test2(){
cout << "test2--------" << endl;
myVector<int> v(100);
v.push_back(10);
v.push_back(9);
v.push_back(8);
v.push_back(7);
v.push_back(6);
v.push_back(5);
myVector<int>::iterator it = v.begin();
v.insert(it, 300); display(v);
v.insert(it, 500); display(v);
v.insert(it, 200); display(v);
v.insert(it, 20); display(v);
v.insert(it, 30); display(v);
v.insert(it, 40); display(v);
}运行后果：
/*
test--------
10 9 8 7 6 5
10 9 8 7 6 5
size: 6
test1--------
10 9 8 300 300 300 7 6 5
10 9 8 500 500 500 500 300 300 300 7 6 5
10 9 8 200 200 500 500 500 500 300 300 300 7 6 5
10 9 8 20 20 200 200 500 500 500 500 300 300 300 7 6 5
10 9 8 30 30 30 20 20 200 200 500 500 500 500 300 300 300 7 6 5
10 9 8 40 40 40 40 30 30 30 20 20 200 200 500 500 500 500 300 300 300 7 6 5
test2--------
300 10 9 8 7 6 5
500 300 10 9 8 7 6 5
200 500 300 10 9 8 7 6 5
20 200 500 300 10 9 8 7 6 5
30 20 200 500 300 10 9 8 7 6 5
40 30 20 200 500 300 10 9 8 7 6 5
Program ended with exit code: 0
*/援用:https://github.com/MissStrick…
正文完