Vector的實現

//test.h
#pragma once#include <iostream>
#include <cstdio>
#include <string.h>
#include <assert.h>using namespace std;typedef int DataType;#define TESTHEADER printf("\n================%s===============\n", __FUNCTION__)

class Vector
{
public:Vector();Vector(const Vector& v);~Vector();Vector& operator = (Vector& v);void Swap(Vector& v);size_t Size()const;size_t Capacity()const;void Reserve(size_t n);void Resize(size_t n, DataType);DataType& operator[](size_t pos);void PushBack(DataType v);void PopBack();
private:void Expand(size_t n);DataType* _start;DataType* _finish;DataType* _endofstorage;
};//test.cc
/***構造函數**/
#include "test.h"Vector::Vector():_start(NULL),_finish(NULL),_endofstorage(NULL)
{
}/*** 拷貝構造函數**/
//v(v1)
Vector::Vector(const Vector& v)
{_start = new DataType[v.Size()];memcpy(_start, v._start, v.Size() * sizeof(DataType));_finish = _start + v.Size();_endofstorage = _start + v.Size();
}/*** 擴展空間**/
void Vector::Expand(size_t n)
{if(n > Capacity()){size_t size = Size();DataType* tmp = new DataType [n];if(_start != NULL){memcpy(tmp, _start, size * sizeof(DataType));delete [] _start;}_start = tmp;_finish = _start + size;_endofstorage = _start + n;}
}/*** 預先分配空間并且初始化**/
void Vector::Resize(size_t n, DataType value = DataType())
{if(n <= Size()){_finish = _start + n;_endofstorage = _start + n;}else{if(n > Capacity()){Expand(n);size_t i = 0;for(; i < Size(); ++i){_start[i] = value;}}//end if(n > Capacity())}//end else
}/*** 預先分配空間但是不進行初始化**/
void Vector::Reserve(size_t n)
{Expand(n);
}/*** 尾插一個元素**/void Vector::PushBack(DataType v)
{if(_finish == _endofstorage){size_t new_capacity = Capacity() == 0 ? 3 : (Capacity() * 2);Expand(new_capacity);}*_finish = v;++_finish;
}/*** 交換內置類型(成員變量)**/
void Vector::Swap(Vector& v)
{swap(_start, v._start);swap(_finish, v._finish);swap(_endofstorage, v._endofstorage);
}/*** 賦值**/
//v1 = v2
//operator = (v1, v2)
Vector& Vector::operator = (Vector& v)
{Swap(v);return *this;
}//v[pos]
DataType& Vector::operator[](size_t pos)
{assert(pos < Size());return _start[pos];
}/*** 析構函數**/
Vector::~Vector()
{if(_start){delete [] _start;_start = _finish = _endofstorage = NULL;}
}/*** 返回Vector的有效字符個數**/
size_t Vector:: Size()const
{return _finish - _start;
}/*** Vector的容量**/
size_t Vector::Capacity()const
{return _endofstorage - _start;
}/*** 尾刪一個元素**/
void Vector::PopBack()
{--_finish;
}

List的實現

//list.h
#pragma once
#include <iostream>
#include <cstdio>
#include <assert.h>
using namespace std;typedef int DataType;
struct ListNode
{DataType _data;ListNode* _next;ListNode* _prev;ListNode(DataType x):_data(x),_next(NULL),_prev(NULL){}
};class List
{typedef ListNode Node;
public:List();//構造函數~List();//析構函數List(const List& l);//拷貝構造List& operator = (List l);//賦值構造函數void PushBack(DataType l);//尾插函數void PushFront(DataType l);//頭插函數void PopBack();//尾刪函數void PopFront();//頭刪函數void Insert(Node* pos, DataType l);//往pos處插入一個結點void Erase(Node* pos);//刪除某個位置上的某個結點void Print();void Clean();//清空
private:Node* _head;
};//test.cc
#include "list.h"/*** 構造函數**/
List::List()
{_head = new Node(DataType());_head -> _next = _head;_head -> _prev = _head;
}void List:: Insert(Node* pos, DataType l)
{assert(pos);Node* prev= pos -> _prev;Node* next = pos;Node* new_node = new Node(l);//new_node VS next;new_node -> _next = next;next -> _prev = new_node;//new_node VS prevprev -> _next = new_node;new_node -> _prev = prev;
}void List::Erase(Node* pos)
{Node* next = pos;Node* prev = pos -> _prev;prev -> _next = next;next -> _prev = prev;
}void List::PushBack(DataType l)
{this -> Insert(_head, l);
}//l1(l2)
List::List(const List& l)
{_head = new Node(DataType());_head -> _prev = _head;_head -> _next = _head;Node* cur = l._head -> _next;while(cur != l._head){this -> PushBack(cur -> _data);cur = cur -> _next;}
}void List::PushFront(DataType l)
{Insert(_head -> _next, l);
}/*** 清空**/
void List::Clean()
{Node* cur = _head -> _next;while(cur != _head){Node* next = cur -> _next;delete cur;cur = next;}
}void List::Print()
{assert(_head -> _next != _head);Node* cur = _head -> _next;while(cur != _head){cout << cur -> _data << " ";cur = cur -> _next;}cout << endl;
}
List::~List()
{Clean();delete _head;
}void List::PopBack()
{Erase(_head -> _prev);
}//l1 = l2
List& List::operator = (List l)
{swap(this -> _head, l._head);return *this;
}void List::PopFront()
{Erase(_head -> _next);
}