C++——模拟实现list

1.初步实现结点和链表

namespace jxy
{
template<class T>
struct list_node
{
T _data;
list_node<T>* _prev;
list_node<T>* _next;

list_node(const T& x = T())
:_data(x)
,_prev(nullptr)
,_next(nullptr)
{}
};

template<class T>
class list//list的框架本质是封装+运算符重载
{
typedef list_node<T> Node;

public:

    void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}

list()
{
empty_init();
}

private:
Node* _head;
size_t _size;
//不写_size变量的话，想获取size的大小，从头遍历链表，时间复杂度是O(N)
};
}

2.push_back

namespace jxy
{
template<class T>
struct list_node
{
T _data;
list_node<T>* _prev;
list_node<T>* _next;

list_node(const T& x = T())
:_data(x)
,_prev(nullptr)
,_next(nullptr)
{}
};

template<class T>
class list//list的框架本质是封装+运算符重载
{
typedef list_node<T> Node;

public:

    void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;

_size = 0;
}

list()
{
empty_init();
}

void push_back(const T& x)
{
Node* tail = _head->_prev;
Node* newnode = new Node(x);//调用构造函数

tail->_next = newnode;
newnode->_prev = tail;

newnode->_next = _head;
_head->_prev = newnode;
}

private:
Node* _head;
size_t _size;
};
}

3.初步实现迭代器

将迭代器封装为类来实现其功能

namespace jxy
{
template<class T>
struct list_node
{
T _data;
list_node<T>* _prev;
list_node<T>* _next;

list_node(const T& x = T())
:_data(x)
,_prev(nullptr)
,_next(nullptr)
{}
};

template<class T>
struct __list_iterator//一般前加__就说明这是内部的实现
{
typedef list_node<T> Node;
typedef __list_iterator<T> self;
Node* _node;

__list_iterator(Node* node)
:_node(node)
{}

self& operator++()//不是连续的物理空间，++不能到下一个位置
{
_node = _node->_next;
return *this;
}

T& operator*()
{
return _node->_data;
}

bool operator!=(const self& s)
{
return (_node != s._node);
}
};

template<class T>
class list//list的框架本质是封装+运算符重载
{
typedef list_node<T> Node;

public:
typedef __list_iterator<T> iterator;
iterator begin()
{
//return iterator(_head->_next);
return _head->_next;
}

iterator end()
{
//return iterator(_head);
return _head;
}

void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}

list()
{
empty_init();
}

void push_back(const T& x)
{
Node* tail = _head->_prev;
Node* newnode = new Node(x);//调用构造函数

tail->_next = newnode;
newnode->_prev = tail;

newnode->_next = _head;
_head->_prev = newnode;
}

private:
Node* _head;
size_t _size;
};

void test_list1()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);

// 封装，屏蔽了底层差异和实现细节
// 提供了统一的访问、修改和遍历方式
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
*it += 10;//还可以修改

cout << *it << " ";
++it;
}
cout << endl;

for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
}
}

4.插入和删除

namespace jxy
{
template<class T>
struct list_node
{
T _data;
list_node<T>* _prev;
list_node<T>* _next;

list_node(const T& x = T())
:_data(x)
,_prev(nullptr)
,_next(nullptr)
{}
};

template<class T>
struct __list_iterator//一般前加__就说明这是内部的实现
{
typedef list_node<T> Node;
typedef __list_iterator<T> self;
Node* _node;

__list_iterator(Node* node)
:_node(node)
{}

self& operator++()//不是连续的物理空间，++不能到下一个位置
{
_node = _node->_next;
return *this;
}

T& operator*()
{
return _node->_data;
}

bool operator!=(const self& s)
{
return (_node != s._node);
}
};

template<class T>
class list//list的框架本质是封装+运算符重载
{
typedef list_node<T> Node;

public:
typedef __list_iterator<T> iterator;

void clear()//不清哨兵位的头结点
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}

void push_back(const T& x)
{
insert(end(), x);
}

void push_front(const T& x)
{
insert(begin(), x);
}

void pop_front()
{
erase(begin());
}

void pop_back()
{
erase(--end());
}

//void insert(iterator pos,const T& x)
//{
//Node* cur = pos._node;
//Node* newnode = new Node(x);

//Node* prev = cur->_prev;

////prev  newnode  cur
//prev->_next = newnode;
//newnode->_prev = prev;

//newnode->_next = cur;
//cur->_prev = newnode;

////理论上可以认为list的迭代器不存在失效问题
//}

iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* newnode = new Node(x);

Node* prev = cur->_prev;

//prev  newnode  cur
prev->_next = newnode;
newnode->_prev = prev;

newnode->_next = cur;
cur->_prev = newnode;

++_size;

return iterator(newnode);//指向新插入的元素
}

//void erase(iterator pos)
//{
//Node* cur = pos._node;

//Node* prev = cur->_prev;
//Node* next = cur->_next;

//delete cur;
//prev->_next = next;
//next->_prev = prev;

//}

iterator erase(iterator pos)
{
Node* cur = pos._node;

Node* prev = cur->_prev;
Node* next = cur->_next;

delete cur;
prev->_next = next;
next->_prev = prev;

--_size;

//erase后的迭代器会失效，所有最好把返回值类型改为iterator
return iterator(next);
}

size_t size()
{
return _size;
}

private:
Node* _head;
size_t _size;
};

}

5.拷贝构造和赋值

namespace jxy
{
template<class T>
struct list_node
{
T _data;
list_node<T>* _prev;
list_node<T>* _next;

list_node(const T& x = T())
:_data(x)
,_prev(nullptr)
,_next(nullptr)
{}
};

template<class T>
struct __list_iterator//一般前加__就说明这是内部的实现
{
typedef list_node<T> Node;
typedef __list_iterator<T> self;
Node* _node;

__list_iterator(Node* node)
:_node(node)
{}

self& operator++()//不是连续的物理空间，++不能到下一个位置
{
_node = _node->_next;
return *this;
}

T& operator*()
{
return _node->_data;
}

bool operator!=(const self& s)
{
return (_node != s._node);
}
};

template<class T>
class list//list的框架本质是封装+运算符重载
{
typedef list_node<T> Node;

public:
typedef __list_iterator<T> iterator;

iterator begin()
{
//return iterator(_head->_next);
return _head->_next;
}

iterator end()
{
//return iterator(_head);
return _head;
}

void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}

list()
{
empty_init();
}

~list()
{
clear();

delete(_head);
_head = nullptr;
}

//拷贝构造
//list(const list<T>& lt)//这里是const迭代器
list(list<T>& lt)
{
empty_init();
for (auto e : lt)
{
push_back(e);
}
}

传统写法
//list<int>& operator=(const list<int>& lt)
//{
//if (this != &lt)
//{
//clear();
//for (auto e : lt)
//{
//push_back(e);
//}
//}
//return *this;
//}

void swap(list<int>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}

list<int>& operator=(list<int> lt)//调用拷贝构造
{
swap(lt);
return *this;
}

private:
Node* _head;
size_t _size;
};

}

6.完善迭代器

namespace jxy
{
template<class T>
struct list_node
{
T _data;
list_node<T>* _prev;
list_node<T>* _next;

list_node(const T& x = T())
:_data(x)
,_prev(nullptr)
,_next(nullptr)
{}
};

template<class T>
struct __list_iterator//一般前加__就说明这是内部的实现
{
typedef list_node<T> Node;
typedef __list_iterator<T> self;
Node* _node;

__list_iterator(Node* node)
:_node(node)
{}

self& operator++()//不是连续的物理空间，++不能到下一个位置
{
_node = _node->_next;
return *this;
}

self& operator--()
{
_node = _node->_prev;
return *this;
}

//自定义类型尽量使用前置++，后置++要返回++之前的值
self operator++(int)
{
self tmp(*this);

_node = _node->_next;
return tmp;
}

self operator--(int)
{
self tmp(*this);

_node = _node->_prev;
return tmp;
}

T& operator*()
{
return _node->_data;
}

bool operator!=(const self& s)
{
return (_node != s._node);
}

bool operator==(const self& s)
{
return (_node == s._node);
}

//迭代器不需要析构函数
//它虽然有结点的指针，但是指针是不属于它的，它不能释放

//迭代器的拷贝构造和赋值也不需要去实现深拷贝
};

template<class T>
class list
{
typedef list_node<T> Node;

public:

private:
Node* _head;
size_t _size;
};

}

7.补充：迭代器的->运算符重载

namespace jxy
{
template<class T>
struct list_node
{
T _data;
list_node<T>* _prev;
list_node<T>* _next;

list_node(const T& x = T())
:_data(x)
,_prev(nullptr)
,_next(nullptr)
{}
};

template<class T>
struct __list_iterator//一般前加__就说明这是内部的实现
{
typedef list_node<T> Node;
typedef __list_iterator<T> self;
Node* _node;

__list_iterator(Node* node)
:_node(node)
{}

self& operator++()//不是连续的物理空间，++不能到下一个位置
{
_node = _node->_next;
return *this;
}

T& operator*()
{
return _node->_data;
}

bool operator!=(const self& s)
{
return (_node != s._node);
}

T* operator->()
{
return &_node->_data;
}
};

template<class T>
class list
{
typedef list_node<T> Node;

public:

private:
Node* _head;
size_t _size;
};

void test_list3()
{//存一个自定义类型
list<AA> lt;
lt.push_back(AA(1, 2));
lt.push_back(AA(2, 3));
lt.push_back(AA(3, 4));

list<AA>::iterator it = lt.begin();
while (it != lt.end())
{
//cout << *it << " ";//*it的类型是AA，不支持流插入

//一、让AA类支持流插入

//二、打印公有成员变量
//cout << (*it)._a1 << " " << (*it)._a2 << endl;

//三、让AA类支持->
    //自定义类型不支持运算符，需要重载
cout << it->_a1 << " " << it->_a2 << endl;
cout << it.operator->()->_a1 << " " << it.operator->()->_a2 << endl;

++it;

//当数据存储自定义类型时，重载->
}

//解引用有三种方式：*、[]、->
int* p = new int;
*p = 1;

AA* ptr = new AA;
ptr->_a1=1;
}

}

8.const迭代器

namespace jxy
{
template<class T>
struct list_node
{
T _data;
list_node<T>* _prev;
list_node<T>* _next;

list_node(const T& x = T())
:_data(x)
,_prev(nullptr)
,_next(nullptr)
{}
};


    //const迭代器模拟的是指向的内容不能改变，而不是本身不能改变
    //const迭代器本身可以++
template<class T>
struct __list_const_iterator//const迭代器是一个单独的类
{
typedef list_node<T> Node;
typedef __list_const_iterator<T> self;
Node* _node;

__list_const_iterator(Node* node)
:_node(node)
{}

self& operator++()
{
_node = _node->_next;
return *this;
}

self& operator--()
{
_node = _node->_prev;
return *this;
}

self operator++(int)
{
self tmp(*this);

_node = _node->_next;
return tmp;
}

self operator--(int)
{
self tmp(*this);

_node = _node->_prev;
return tmp;
}

const T& operator*() //通过解引用才能修改数据
{
return _node->_data;//返回的是const别名，不能修改
}

const T* operator->()
 {
return &_node->_data;
}

bool operator!=(const self& s)
{
return (_node != s._node);
}

bool operator==(const self& s)
{
return (_node == s._node);
}
};

template<class T>
class list//list的框架本质是封装+运算符重载
{
typedef list_node<T> Node;

public:
typedef __list_iterator<T> iterator;
typedef __list_const_iterator<T> const_iterator;
//单独去支持一个类型：const_iterator

const_iterator begin() const
{
//return const_iterator(_head->_next);
return _head->_next;
}

const_iterator end() const
{
//return const_iterator(_head);
return _head;
}

private:
Node* _head;
size_t _size;
};

    //测试const迭代器
void print_list(const list<int>& lt)
//容器通常不支持流插入，所以要写个print函数
{
list<int>::const_iterator it = lt.begin();
while (it != lt.end())
{
//*it = 100;//不可修改

cout << *it << " ";
it++;
}
cout << endl;
}

void test_list4()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);

print_list(lt);
}
}

9.改善为模板

当前代码的实现太过冗余，iterator类和const_iterator类的代码实现高度重合

namespace jxy
{
template<class T>
struct list_node
{
T _data;
list_node<T>* _prev;
list_node<T>* _next;

list_node(const T& x = T())
:_data(x)//这里是拷贝构造
,_prev(nullptr)
,_next(nullptr)
{}
};


//T  T&  T*
//T  const T&  const T*
template<class T,class Ref,class Ptr>
struct __list_iterator
{
typedef list_node<T> Node;
typedef __list_iterator<T,Ref,Ptr> self;
Node* _node;

__list_iterator(Node* node)
:_node(node)
{}

self& operator++()//不是连续的物理空间，++不能到下一个位置
{
_node = _node->_next;
return *this;
}

self& operator--()
{
_node = _node->_prev;
return *this;
}


self operator++(int)
{
self tmp(*this);

_node = _node->_next;
return tmp;
}

self operator--(int)
{
self tmp(*this);

_node = _node->_prev;
return tmp;
}

Ref operator*()//从泛型的角度来说，这里返回值类型是什么是不知道的
{
return _node->_data;
}

Ptr operator->()
{
return &_node->_data;
}

bool operator!=(const self& s)
{
return (_node != s._node);
}

bool operator==(const self& s)
{
return (_node == s._node);
}

//所以迭代器到底如何实现，是根据容器的底层结构来决定的
};


template<class T>
class list//list的框架本质是封装+运算符重载
{
typedef list_node<T> Node;

public:
typedef __list_iterator<T,T&,T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;

const_iterator begin() const
{
//return const_iterator(_head->_next);
return _head->_next;
}

const_iterator end() const
{
//return const_iterator(_head);
return _head;
}


iterator begin()
{
//return iterator(_head->_next);
return _head->_next;
}

iterator end()
{
//return iterator(_head);
return _head;
}

void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;

_size = 0;
}

list()
{
empty_init();
}

~list()
{
clear();

delete(_head);
_head = nullptr;
}

//拷贝构造
list(const list<T>& lt)//这里是const迭代器
{
empty_init();
for (auto e : lt)
{
push_back(e);
}
}


void swap(list<int>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}

list<int>& operator=(list<int> lt)//调用拷贝构造
{
swap(lt);
return *this;
}

void clear()//不清哨兵位的头结点
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}

void push_back(const T& x)
{
insert(end(), x);
}

void push_front(const T& x)
{
insert(begin(), x);
}

void pop_front()
{
erase(begin());
}

void pop_back()
{
erase(--end());
}

iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* newnode = new Node(x);

Node* prev = cur->_prev;

//prev  newnode  cur
prev->_next = newnode;
newnode->_prev = prev;

newnode->_next = cur;
cur->_prev = newnode;

++_size;

return iterator(newnode);//指向新插入的元素
}


iterator erase(iterator pos)
{
Node* cur = pos._node;

Node* prev = cur->_prev;
Node* next = cur->_next;

delete cur;
prev->_next = next;
next->_prev = prev;

--_size;

//erase后的迭代器会失效，所有最好把返回值类型改为iterator
return iterator(next);
}

size_t size()
{
return _size;
}

private:
Node* _head;
size_t _size;
};

    //测试const迭代器
void print_list(const list<int>& lt)
{
list<int>::const_iterator it = lt.begin();
while (it != lt.end())
{
//*it = 100;//不可修改

cout << *it << " ";
it++;
}
cout << endl;

for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
}

void test_list4()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);

print_list(lt);
}
}

10.关于typename

namespace jxy
{
template<class T>
struct list_node
{
T _data;
list_node<T>* _prev;
list_node<T>* _next;

list_node(const T& x = T())
:_data(x)
,_prev(nullptr)
,_next(nullptr)
{}
};

template<class T>
void print_list(const list<T>& lt)//之前的print只支持int类型
{
list<T>::const_iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
it++;
}
cout << endl;

for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
}

void test_list4()
{
list<string> lt1;
lt1.push_back("1111111111111111111111");
lt1.push_back("1111111111111111111111");
lt1.push_back("1111111111111111111111");
lt1.push_back("1111111111111111111111");

//这里会不会涉及深层次的深拷贝问题？
//之前的vector容器就涉及到了深层次的浅拷贝问题
//它的主要原因是因为扩容时使用了memcpy
//list不存在扩容的事情，也就不涉及这个问题

print_list(lt1);

}
}

但事实上，这样修改以后是编译不通过的。

 

这就涉及到另一个知识点，在日常使用中，模板命名时，使用class和使用typename是等价的

template<class T>
template<typename T>

但此时的场景下，就要使用typename了。

namespace jxy
{
template<class T>
struct list_node
{
T _data;
list_node<T>* _prev;
list_node<T>* _next;

list_node(const T& x = T())
:_data(x)
,_prev(nullptr)
,_next(nullptr)
{}
};


template<typename T>
void print_list(const list<T>& lt)//之前的print只支持int类型
{
typename list<T>::const_iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
it++;
}
cout << endl;

for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
}

void test_list4()
{

list<string> lt1;
lt1.push_back("1111111111111111111111");
lt1.push_back("1111111111111111111111");
lt1.push_back("1111111111111111111111");
lt1.push_back("1111111111111111111111");

print_list(lt1);

}
}

typename list<T>::const_iterator it = lt.begin();
当模板是未实例化的类模板时，如list<T>
编译器不能去它里面查找，它里面带有许多不可确定的东西
编译器在编译阶段、没有实例化时，只会对这里进行初步的检查
所以编译器无法判断list<T>::const_iterator是内嵌类型，还是静态成员变量
所以这里要加上typename，凡是这种类模板中取类型都要加
前面加一个typename就是告诉编译器，这里是一个类型
要等list<T>实例化了，再去类里面去取
模板里面取东西都要加typename，使得编译器初步检查时先通过
然后实例化后，再去类中取这个类型，就知道它具体是什么了

11.再次改善为模板

namespace jxy
{
template<class T>
struct list_node
{
T _data;
list_node<T>* _prev;
list_node<T>* _next;

list_node(const T& x = T())
:_data(x)
,_prev(nullptr)
,_next(nullptr)
{}
};


template<typename T>
void print_list(const list<T>& lt)
{
typename list<T>::const_iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
it++;
}
cout << endl;

for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
}

void test_list4()
{

list<string> lt1;
lt1.push_back("1111111111111111111111");
lt1.push_back("1111111111111111111111");
lt1.push_back("1111111111111111111111");
lt1.push_back("1111111111111111111111");

print_list(lt1);


vector<string> v;
v.push_back("111111111111");
v.push_back("111111111111");
v.push_back("111111111111");
v.push_back("111111111111");
v.push_back("111111111111");

print_list(v);//此时是打印不了的
}
}

print_list是专门打印list的，想要打印vector，难道再去写一个逻辑高度重复的print函数吗?

namespace jxy
{
template<class T>
struct list_node
{
T _data;
list_node<T>* _prev;
list_node<T>* _next;

list_node(const T& x = T())
:_data(x)
,_prev(nullptr)
,_next(nullptr)
{}
};


template<typename Container>
void print_container(const Container& con)//针对容器的打印
{
typename Container::const_iterator it = con.begin();
while (it != con.end())
{
cout << *it << " ";
it++;
}
cout << endl;
}
//模板实现了泛型编程，本质就是本来应该由我们做的事情交给了编译器

void test_list4()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);

print_container(lt);

list<string> lt1;
lt1.push_back("1111111111111111111111");
lt1.push_back("1111111111111111111111");
lt1.push_back("1111111111111111111111");
lt1.push_back("1111111111111111111111");

print_container(lt1);

vector<string> v;
v.push_back("111111111111");
v.push_back("111111111111");
v.push_back("111111111111");
v.push_back("111111111111");
v.push_back("111111111111");

print_container(v);

}
}

12.总结：对比vector和list

原文地址：https://blog.csdn.net/2301_80342122/article/details/142698680

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！